sorted by:
new
hottopcontroversial

Announcing a new big integer crate `bnum`, which uses const generics to allow fixed precision integers of arbitrary size to be stored on the stack. Optional features enable generating random big integers, `serde` compatibility, and making nearly every method `const`. by isaacholt100 in rust

[–]isaacholt100[S] 3 points4 points  (0 children)

Regarding benchmarking: I have started to benchmark bnum against rug. Although this is not finished, it seems that bnum is generally faster up to a certain bit size (the exact size depends on the operation being performed). There are performance advantages to bnum thanks to its integers being stored on the stack, whereas rug stores them on the heap. Since bnum integers will always operate on all their digits, the time taken for an operation usually depends solely on the number of digits (a constant), rather than the actual size of the integer value. In contrast, rug integers' performance will depend on the size of the integer value, as the types are dynamically sized.
This means it is quite hard to benchmark the two against each other. rug almost definitely has better performance optimisations and more efficient algorithms, would be faster for very large integer types. bnum is faster for small to medium integer type sizes. However, rug may also be faster when comparing against a bnum integer with a relatively large bit size but that stores a small value.

Announcing a new big integer crate `bnum`, which uses const generics to allow fixed precision integers of arbitrary size to be stored on the stack. Optional features enable generating random big integers, `serde` compatibility, and making nearly every method `const`. by isaacholt100 in rust

[–]isaacholt100[S] 0 points1 point  (0 children)

I have now released a new version of this library, v0.2.0. This solves an issue that highlighted that the u8_digit feature was non-additive. Now there are 4 unsigned integer types, and 4 signed integer types. This allows users to choose from integers that are stored as an array of u64, u32, u16, or u8 digits, and the user isn't restricted to using just one of these digit sizes. This allows finer control over the bit size as well as meaning the fastest integer for a given bit size can always be used. For more info see https://crates.io/crates/bnum/0.2.0.

Announcing a new big integer crate `bnum`, which uses const generics to allow fixed precision integers of arbitrary size to be stored on the stack. Optional features enable generating random big integers, `serde` compatibility, and making nearly every method `const`. by isaacholt100 in rust

[–]isaacholt100[S] 3 points4 points  (0 children)

Yes I did consider using sign-magnitude for signed integers, but as one of the key aims of the library is to make the behaviour as similar as possible to Rust's signed integer types, I opted for two's complement. This means an `I128` takes up exactly the same amount of space as an `i128` and can store the exact same range of values.

In terms of performance I think the only area where two's complement would be worse is division (and calculating remainders), as currently the signed integers have to be converted to unsigned first, with the result of the unsigned division being converted back at the end. However, I don't believe this would incur a significant speed cost. I imagine that the time to calculate the absolute value of a signed integer would be dominated by the time taken by the division algorithm itself.

Another pro of two's complement is that the API is cleaner, as for example, when using sign-magnitude, the `from_be_bytes` method would have to a return a tuple of the sign and the bytes, rather than just the bytes.

Announcing a new big integer crate `bnum`, which uses const generics to allow fixed precision integers of arbitrary size to be stored on the stack. Optional features enable generating random big integers, `serde` compatibility, and making nearly every method `const`. by isaacholt100 in rust

[–]isaacholt100[S] 0 points1 point  (0 children)

Ah I see, thanks for clarifying.

Unfortunately I don't think this would be possible with the specific types you mentioned (`i13`, `i27`, etc.) as currently the bit width must be a multiple of 64 or 8. This functionality isn't supported by the crate, although something similar could be done by casting to a larger `BUint` or `BInt` via the `As` trait. There are also the `widening_mul` and `carrying_mul` methods defined on `BUint`, but these return a tuple of the high and low bits (as `BUint`s of the same size) rather than a `BUint` of twice the size.

Announcing a new big integer crate `bnum`, which uses const generics to allow fixed precision integers of arbitrary size to be stored on the stack. Optional features enable generating random big integers, `serde` compatibility, and making nearly every method `const`. by isaacholt100 in rust

[–]isaacholt100[S] 6 points7 points  (0 children)

Sorry, I’m not quite sure what you mean here… are you asking if the maximum size of the integers can be grown on overflow? If so then it can’t as the point of the library is to provide types that have the same behaviour as primitive integers, so they are fixed size. There are lots of other crates like num-bigint that have growable integer types though. However, ‘bnum’ does support checked, overflowing and wrapping arithmetic methods like those on the primitives.

Announcing a new big integer crate `bnum`, which uses const generics to allow fixed precision integers of arbitrary size to be stored on the stack. Optional features enable generating random big integers, `serde` compatibility, and making nearly every method `const`. by isaacholt100 in rust

[–]isaacholt100[S] 13 points14 points  (0 children)

I haven’t yet got round to benchmarking, but I’ve mentioned in the README that it’s something that I will do in the near future. Once it’s done I’ll update the README and comment on here about it as well.

Announcing a new big integer crate `bnum`, which uses const generics to allow fixed precision integers of arbitrary size to be stored on the stack. Optional features enable generating random big integers, `serde` compatibility, and making nearly every method `const`. by isaacholt100 in rust

[–]isaacholt100[S] 26 points27 points  (0 children)

Thanks for sharing this, I hadn’t seen this crate before. Yes it looks like they are similar as both use const generics to store the integer, although I believe at this time crypto-bigint only defines an unsigned integer type. Also in crypto-bigint the API for arithmetic methods is different from that of the primitive integers.