I'm converting over a number theory library I wrote in C# many years ago. It has all generic arguments and I'd like to use bigints as generics but the lack of the copy trait keeps tripping me up. Everything works great for i128 but that's not gonna work to factor very large numbers. I like the uint crate with up to u2048 with fixed size but this time the lack of Signed trips me up. I'm just getting started in Rust so I may very well be missing something but changing everything over to satisfy either the constraints of bigints or u2048 seems very difficult so I thought I could make a wrapper for an unsigned type to make it a signed type so I'd effectively turn the u2048 into an i2048. I'd just make a structure with is_neg: bool for sign and abs_val for the magnitude which would be unsigned. I then have to do all the traits so that the arithmetic is done correctly but it seems doable, though a bit tedious. Being new to Rust though, I hesitate to start on such a thing if I'm ultimately doomed to failure or if there's an easier way to handle things or perhaps if somebody has already done such a thing. Looking for advice here though I'm diving into the wrapper for now. It'll be a learning experience if nothing else. Thanks for any ideas.
The num crate has both signed and unsigned 'Big Integer' types. I've used those types with no problems.
If one doesn't exist, the existing Copy but unsigned implementation is going to be the easier one to wrap or modify. But it will be tedious.
If you can lower the requirements to a Clone you will have a much easier time.
It is possible to write a stack allocated version using const generics or macros, but the former is definitively not beginner friendly and the latter is still very difficult (to debug).
There are also existing crates for this:
- fixed-bigint — Rust math library // Lib.rs (using const generics)
- Uint — data structures in Rust // Lib.rs (using macros)
- ApInt — data structures in Rust // Lib.rs (using allocations)
As far as I can tell (and I've tried them), fixed-bigint and Uint don't support any signed types and apint doesn't support copy so these fail to work for me. Thanks though for pointing them out - didn't know about apint.
Yes, but they don't have Copy so they still don't work. Thanks though!
Why do you need Copy rather than just Clone?
Because I don't want to clone primitives like i32 which will also be coming in through these generics plus all those clones just kind of gunk up the code IMHO so I'd rather have a = b than a = b.Clone() which is gonna occur a LOT in this number theoretic code. I've almost got the unsigned to signed wrapper going so hopefully this will all be taken care of by that.
Your fundamental problem is that big integers aren't Copy, instead they are almost always implemented using a dynamically-sized array (i.e. Vec<u8> for the digits).
(for reference, a Vec<u8> is just a wrapper around a *mut u8 and two numbers for tracking length and capacity)
It needs to be trivial to make copies of your value by just copying its bytes around, however in a non-GC'd language like Rust if you were to trivially copy a Vec<u8> you would be copying the *mut u8 pointer around and each instance would think it owns (and therefore is responsible for freeing) the memory being pointed to.
The way you deal with this is by just not copying the BigInt around all the time. By forcing people to explicitly call clone() every time it reminds people that copying a BigInt is expensive.
Instead, you can write your code so that it works with references. For example, you might accept &BigInt as a function parameter, and overloading the + operator might take two &BigInts and return a new BigInt instance.
That way you retain the niceties of not needing to clone() all the time while also saving on performance... C# doesn't necessarily have this issue because each decimal is an immutable reference type and copying the reference around is a cheap operation (which you pay for by making the GC do more work).
If you're worried about performance:
Cloning Copy types like i32 is exactly as fast as moving them.
Cloning IBig is cheap and involves no memory allocation if the numbers are small enough (currently everything below 2^64 on 64-bit machines).
If you have very large numbers, sharing them by reference will be faster regardless of how they are represented.
If you want to implement your own i2048 type, I would go with two's complement representation rather than sign-magnitude, it's easier to deal with for fixed size types.
" Your fundamental problem is that big integers aren't Copy"
Yes, I know that for arbitrarily sized ints this isn't even possible. Consequently, I had settled for the Uint package which has fixed sizes up to 2048 bits. I consider this large enough to handle pretty much whatever I'd like to handle. The only problem is, the Uint crate only handles unsigned ints and I need to return/use negative values on occasion (for instance, the coefficients to multiply in a linear equation to get two values to add to their GCD). Consequently, I am writing (and almost finished with) this UToI module which provides a UToI.<T> type which takes an unsigned fixed size type and returns a signed fixed size type. Using that with Uint should do everything I want. I know there are other ways but this seems easiest to wrap my mind around right now. Besides, writing UToI has really taught me a lot about some of the little back alleys of Rust and implementing a numeric type.
Other's have said this but it bears repeating: Cloning rather than copying has absolutely zero impact on primitives. Being explicit about where to clone can be tedious but it will never hurt performance.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.