let mut x: BigInt = 0.into();
let y: isize = -1;
x += y;
assert_eq!(BigInt::from(-1), x); // fails
// x is actually 2^64-1

x + y gives the proper result (-1), and if y is i32 or i64 it works as expected, but isize somehow breaks things. When compiled for 64-bit the result is off by 2^64, and for 32-bit it is off by 2^32.

Maybe it will be more convenient to write the following code after adding trait Step for BigInt:

for i in BigInt::from(1)..BigInt::from(1000) {
    // do something
}

If you disable the std feature, this crate won't compile.

Just try:

git clone https://github.com/rust-num/num-bigint
cargo build --no-default-features

You'll get a ton of errors.

Currently it seems that only BigUint implements BitAnd, BitOr, and BitXor. As a result it's not possible to perform such operations when using a BigInt. Would it be possible for these traits to be implemented for BigInt as well?

Hello,
I am looking a way to use BigUint in Postgres when using rust-postgres.
I found only 1 issue in rust-postgres talking about Big numbers support, but no resolution for it.
Sadly my knowledge in the triplet Big Numbers, Postgres and Rust is not sufficient to figure out a way to do it on my own. I don't know how Big Numbers are represented, how to store them in Postgres nor my skills in Rust are good enough for that.

I will gladly try to implement the num-bigint for rust-postgres with some guidance.

It would be nice to have a method for getting the memory consumption of BigInts and BigUInts. In particular this crate is being used by RustPython, and the python spec requires builtins to implement a __sizeof__ method that returns the amount of memory used by an object in bytes. This is quite easy to calculate using std::mem::size_of_val, unfortunately it requires a reference to the underlying data Vec, which of course is not exposed by the BigInt api.

My proposal is to either:

1. Add a method for getting a reference to data or
2. Add a method for getting the size of BigInt/BigUInt

I would prefer the first option because it will support a lot more unforseen use cases.

See the discussion at RustPython/RustPython#1172

Hi there,
Just trying to run the example but there seems to be a problem to access RandBigInt.
Any help?

main.rs

  1 extern crate rand;
  2 extern crate num_bigint as bigint;
  3 
  4 use bigint::{ToBigInt, RandBigInt};
  5 
  6 fn main() {
  7     let mut rng = rand::thread_rng();
  8     let a = rng.gen_bigint(1000);
  9 
 10     let low = -10000.to_bigint().unwrap();
 11     let high = 10000.to_bigint().unwrap();
 12     let b = rng.gen_bigint_range(&low, &high);
 13 
 14     // Probably an even larger number.
 15      println!("{}", a * b);
 16 }

Cargo.toml

  6 [dependencies]
  7 rand = "0.5"
  8 num-bigint = "0.2"

...

 Updating registry `https://github.com/rust-lang/crates.io-index`
   Compiling num-traits v0.2.5
   Compiling num-integer v0.1.39                                                                                                                                                       
   Compiling num-bigint v0.2.0                                                                                                                                                         
   Compiling libc v0.2.42                                                                                                                                                              
   Compiling rand_core v0.2.1                                                                                                                                                          
   Compiling rand v0.5.4                                                                                                                                                               
   Compiling biginttesting v0.1.0                                                                                     
error[E0432]: unresolved import `bigint::RandBigInt`=============>     ] 12/13: biginttesting                                                                                          
 --> src/main.rs:4:24
  |
4 | use bigint::{ToBigInt, RandBigInt};
  |                        ^^^^^^^^^^ no `RandBigInt` in the root

warning: unused import: `RandBigInt`
 --> src/main.rs:4:24
  |
4 | use bigint::{ToBigInt, RandBigInt};
  |                        ^^^^^^^^^^
  |
  = note: #[warn(unused_imports)] on by default

error[E0599]: no method named `gen_bigint` found for type `rand::ThreadRng` in the current scope
 --> src/main.rs:8:17
  |
8 |     let a = rng.gen_bigint(1000);
  |                 ^^^^^^^^^^

error[E0599]: no method named `gen_bigint_range` found for type `rand::ThreadRng` in the current scope
  --> src/main.rs:12:17
   |
12 |     let b = rng.gen_bigint_range(&low, &high);
   |                 ^^^^^^^^^^^^^^^^

error: aborting due to 3 previous errors

I want to create a BigInt for 1855425871872000000000.
I have to use this.

let c = ((BigInt::from(1855425) * BigInt::from(1000000) + BigInt::from(871872))) * BigInt::from(1000000000);

Any better way exists?

We already have them for BigUint, so this probably just needs more forwarding impls.

cc rust-num/num#173

There is currently no SQRT function which is critically important to have. Multiple algorithms on arbitrary-precision types require it. I think it worth to implement it in the crate, and as a result - in depended types, such as Ratio.

These could be helpful for printing large numbers approximately, especially if we can figure out how to do it quickly, without full digit-by-digit division.

cc rust-num/num#259

Rust 1.26 is stabilizing i128 and u128. We should add support for for these, to the same extent that other primitive types are supported. This should be a conditional feature, rather than forcing all of num-bigint up to the very latest compiler -- e.g. rust-num/num-traits#60 has a new feature "i128".

• convert to and from 128-bit integers #44
• implement operators with 128-bit operands
• implement BigDigit = u64 with DoubleBigDigit = u128
  • still conditional on new enough rustc, and probably only for specific target CPUs

I have a couple of constants which I would define as such using lazy_static! but this fails for me

lazy_static! {
      static ref BIG_3: BigUint = BigUint::from_u64(3).unwrap();
}

// later this fails with: `no implementation for `&num_bigint::BigUint - &prime::BIG_3`
let res = my_number - &BIG_3;

// but this works, but clippy is upset that I am using `&`  but if I remove it it stops compiling
if my_number < &BIG_3 { }

any ideas how to work around this?

In python, we can easily implement ceiling division for the integer type.

def ceildiv(a, b):
    return -(-a // b)

Maybe it will be more convenient if we implement a similar method for BigInt.

extern crate num;

use num::BigInt;
use num::Zero;

pub trait CeilDiv<RHS = Self> {
    type Output;
    fn ceildiv(&self, rhs: RHS) -> Self::Output;
}

impl CeilDiv for BigInt {
    type Output = BigInt;
    fn ceildiv(&self, rhs: Self) -> Self::Output {
        let (q, r) = (self / &rhs, self % &rhs);
        let padding = ((*self < Self::zero()) ^ (rhs > Self::zero()))
            && (r != Self::zero());
        q + Self::from(padding as i32)
    }
}

fn main() {
    assert_eq!(BigInt::from(5).ceildiv(BigInt::from(2)), BigInt::from(3));
    assert_eq!(BigInt::from(5).ceildiv(BigInt::from(-2)), BigInt::from(-2));
}

The results of the default bencher are quite unstable(in successive benchmarks run without any other open programs, there were 10 % differences in the same test when comparing with benchcmp). In case you are interested, I would be glad to rewrite the current benches to use criterion and test if there are any improvement.

BigUint(and probably also BigInt) implements Add<u8> and Add<&u8>, but only AddAssign<u8>. We should probably either implement AddAssign<&u8> as well or remove Add<&u8> as the current state is somewhat surprising/unintuitive.

The same is true for all BinopAssign traits: AddAssign, MulAssign, DivAssign etc.

Currently the rand feature of num-bigint uses rand version 0.5, although version 0.6 has been released. According to the rand documentation the update shouldn't affect the required version of rustc for the rand feature.

I can't quite tell what effects it would have for backwards compatibility in general, but maybe one could use a range for the version.

Related issue: #47

There are quite a lot of places in the codebase (easy to see if you run cargo clippy) where, e.g. val as u32 is done, instead of u32::from(val).

Clippy lint: https://rust-lang-nursery.github.io/rust-clippy/v0.0.212/index.html#cast_lossless

Running it in playground:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0d25f92071a744a754c9cc583fe8ee6b

I get the wrong answer raising any number to the power of any number.

Am I using the crate incorrectly?

BigInt::zero().lcm(&BigInt::zero()) panics instead of returning the expected result of 0.

In the plain_modpow function, there are a lot of bitshifts and no comments, combined with the fact that I am more a mathematician than a programmer, I don't really know if this method of optimization is already implemented there, because I don't completely understand the code, so if it is, just close this issue.

Here is the optimization:
Since we are looking at the residue class ring (Z/(m), +, *) where m refers to the modulo inside the equivalence classes, we say that an integer a in Z/(m) to the power of a natural number b is defined as the repeated multiplication of a b-times to itself so a*a*a*..*a b-times = a^b. Thus if we find the smallest natural number c <= b which has the property that a^c = 1, the neutral element of multiplication (this is especially fast with small sets that form the ring and large exponents). We firstly find out the result of b mod c =: d. Now we declare an integer e such that c * e +d = b. We can calculate this integer with the following formula e := floor(b/c) where "/" refers to division in the rationals and floor to the largest integer smaller than (or equal to) b/c with the classical order relation on the rationals.
We arrive at the following identity: a^b = (a^c)^e * a^d = (1)^e * a^d = a^d since b = c*e+d.

Quick proof for b=c*e+d:
e is defined as e = floor(b/c), thus floor(b/c) <= b/c with the property that floor(b/c) is the largest such integer. floor(b/c) <= b/c is equivalent to floor(b/c)*c <= b = b/c * c. It follows from the definition of floor(), that this floor(b/c)*c is the largest integer less than or equal to b that can be divided by c. From the definition of modulus we know that d (which is b mod c) is the residue of the division of b with c. It follows from those two properties that b = c*e+d.
Q.E.D.

For this method to be useful the exponents have to be sufficiently large and the identity that has to be computed has to be known beforehand (especially efficient if we have rings that are often used) or the ring has to be sufficiently small. Note that here "sufficient small" can be considered quite huge numbers for humans.

This issue is based on a different idea which I explored in a now yanked rfc.

Add the following traits to num-bigint:

// I am open for name changes, as I am not perfectly satisfied with the current ones.
pub trait ReducingDiv<RHS> {
    type Output;
    fn reducing_div(self, other: RHS) -> Self::Output;
}

pub trait ReducingRem<RHS> {
    type Output;
    fn reducing_rem(self, other: RHS) -> Self::Output;
}

and add the following implementations:
(uX := u8, u16, u32, u64, u128, usize, iX := i8, i16. i32, i64, i128, isize.)

ReducingDiv<&BigUint> for uX -> uX
ReducingRem<uX> for &BigUint -> uX
ReducingRem<&uX> for &BigUint -> uX
ReducingRem<&BigUint> for uX -> uX
ReducingDiv<&BigInt> for iX -> iX
ReducingRem<iX> for &BigInt -> iX
ReducingRem<&iX> for &BigInt -> iX
ReducingRem<&BigInt> for iX -> iX

This is sound as |a| >= |a % b| < |b| and |a / b| <= |a| is always true for integer values.

Motivation

• performance: By returning a native integer we remove the need to allocate on the heap, which leads to a 2x speedup with small BigInts. More exact benchmarks will follow in case it's deemed necessary. This can also reduces the amount of BigInts in general, as many people probably keep an integer as a BigInt for longer than necessary, which also has a negative impact on performance.

• type safety: using ReducingDiv/Rem can prevent accidental panics. i.e.

fn calculate_divisor() -> u32 { 7 } 
let bigint: BigUint = BigInt::from(std::u32::MAX as u64 + 1);
let divisor = calculate_divisor();


let scalar_result: u32 = (bigint % divisor).to_u32().unwrap();
// using ReducingRem
let scalar_result: u32 = bigint.reducing_rem(divisor);

in case calculate_divisor gets changed to return a bigger integer type instead, i.e

fn calculate_divisor() -> u64 {
    std::u64::MAX
}

the current version panics while using ReducingRem causes a compile time error instead. As calculate_divisor can be arbitrarily far away from the actual operation, bugs like this are often very unexpected.

Warning

std::iX::MIN.reducing_div(BigInt::from(-1)) should panic, as std::IX::MIN / -1 == std::iX::MAX + 1, meaning that it does not fit into a iX. This is unlike std::iX::MIN / BigInt::from(-1), which is safe, as std::iX::MAX + 1 does fit into a BigInt.

Currently conversion between BigUInt, BigInt and primitives use dedicated traits ToBigInt, ToBigUInt and {To|From}Primitive, and not Try{From|Into} traits in std. While the functionality exists, this prevents using big integer types in a generic context that requires the latter. So, it would be preferable to implement them.

Some concerns:

• It might be better to integrate ToBigInt and the like directly with Try{From|Into}. But I think that will cause breakage downstream, especially with {To|From}Primitive. Still, if there is a way to do this with out breaking things, this seems preferable.

• Minimum supported rustc version. Since Try{From|Into} have been stable only since 1.34, I think naively implementing these would require bumping the rustc version number. Is there a way to avoid this? I'm not sure since I haven't dealt with minimum rustc versions before.

It seems impossible from the public API to overwrite the memory occupied by a BigUint. This is a dealbreaker for cryptographic applications since a BigUint may contain private keys for RSA or DH schemes.

Exposing the trait crate::biguint::IntDigits to the public API would solve that problem.

A reddit user showed a powm function that we could ideally replace with our modpow, but they're dealing with signed values and we currently only have that for BigUint. It should be easy to assert positive exponent and modulus, normalize the base to positive, then forward to BigUint internally.

ref: https://www.reddit.com/r/rust/comments/7w3v77/why_is_my_rust_code_100x_slower_than_python/

OK, I don't know what I'm wrong about this. But the example from the documentation seems not able to work.

extern crate rand;
extern crate num;

use num::bigint::{BigInt, RandBigInt, ToBigInt};

#[test]
fn testme() {

    let mut rng = rand::thread_rng();
    let a = rng.gen_bigint(1000);

    let low = -10000.to_bigint().unwrap();
    let high = 10000.to_bigint().unwrap();
    let b = rng.gen_bigint_range(&low, &high);

    // Probably an even larger number.
    println!("{}", a * b);
}

I think the trait should be covered already. But I got error:

error[E0599]: no method named `gen_bigint` found for type `rand::ThreadRng` in the current scope
   --> src/rsa.rs:111:17
    |
111 |     let a = rng.gen_bigint(1000);
    |                 ^^^^^^^^^^
    |
    = note: the method `gen_bigint` exists but the following trait bounds were not satisfied:
            `rand::ThreadRng : num::bigint::RandBigInt`

error[E0599]: no method named `gen_bigint_range` found for type `rand::ThreadRng` in the current scope
   --> src/rsa.rs:115:17
    |
115 |     let b = rng.gen_bigint_range(&low, &high);
    |                 ^^^^^^^^^^^^^^^^
    |
    = note: the method `gen_bigint_range` exists but the following trait bounds were not satisfied:
            `rand::ThreadRng : num::bigint::RandBigInt`

error: aborting due to 2 previous errors

Is the usage changed or I'm doing it the wrong way?

Although I don't know of a way to get negative zero (i.e. BigInt{Sign::Minus data:BigUint::zero()}), besides my first attempt at an implementation of Arbitrary, negative zero should equal positive zero, as it does with floats. Maybe we could also throw in a panic if in debug mode.

I have thought of 2 cases here. one is to know the len (size) of the base 10 output and second is for the 10^n written way of writeing numbers. might want base of e as well.

Currently num-bigint 0.2 is targeting rustc 1.15, with optional features for rand 0.4. However, rand 0.5 is coming soon, requiring rustc 1.22, so we should think how to support that (if at all). Options I see:

1. Stick with rand 0.4 only.
2. Wait for rand 0.5 before releasing num-bigint 0.2, and only support that.
   • Any users with less than rustc 1.22 won't be able to use the feature.
3. Go ahead and release with rand 0.4 support, and later update to a range like >=0.4, <0.6
   • The current rand 0.5.0-pre.2 is still compatible -- we really only use Rng::gen().
   • We did this with rand 0.3/0.4 in num-bigint 0.1. Sometimes Cargo handled this fine, but sometimes it required hacks to get it to use an older version.
   • We don't enable rand by default anymore, so some of that pain will be minimized. Only users who actually want rand will enable it, and their own choice of rand version should influence Cargo's resolution.

I had the need for this and have a variant that works well for positive numbers here, if there is interest: https://github.com/dignifiedquire/rust-rsa/blob/master/src/math.rs#L118

From @vks on March 17, 2017 17:35

Unlike integer types that are Copy, for bigints it is important to avoid cloning by supporting x + &y, &x + &y etc. for all relevant operations and comparisons. The required trait bounds are cumbersome, because they need the special for<'a> syntax. The best way to deal with that is in my opinion what @andersk proposed:

fn extended_gcd<T: Integer>(a: T, b: T) -> GcdResult<T>
    where for<'a> &'a T: IntegerOps<T>

for some appropriately defined trait IntegerOps.

This would be useful for optimizations like in #153, i.e. for generic functions like pow, gcd and binomial.

Copied from original issue: rust-num/num#273

It looks like BigInt doesn't have a From implemented. Is it possible to add this feature or is there some problems preventing this from happening?

I see that One and Zero are implemented, but it appears that this is not done so in a way that satisfy num_traits::identifies. When trying to use num_traits::pow::pow, I run into this compile time error

the trait `num_traits::identities::One` is not implemented for `&num_bigint::biguint::BigUint

Note that I am aware that I can now use the new Pow method from 0.2.3 (thank you!), But when my exponents are small, I'd like to be able to use what I am guessing would be more efficient functions.

Hi,

Is there any solution for generation of primes, safe primes and prime checking with num-bigint?

From @cuviper on January 8, 2016 6:21

With BigDigit exposed in the interface, we're somewhat limited in what kind of changes we can make to the implementation. Even just fn new(digits: Vec<BigDigit>) strongly implies that this storage will be directly used by the new BigUint.

Copied from original issue: rust-num/num#155

Well, i have an big int with ~50K digits. And when i want to print it/write it to file, to_string() takes very much. Is there a way to boost this?
P.s. i'm using --release
P.P.s this number is result for calculating factorial(1000000)

From the readme

In the future, we hope to support #![no_std] with the alloc crate when std is not enabled.

It was my understanding that we were holding back on this until alloc was stabilized, which happened fairly recently, in 1.28

I have an implementation of the https://en.wikipedia.org/wiki/Jacobi_symbol which I could PR if there is interest. It really belongs in here as the algorithm requires access to the raw digits, which are not going to be exposed as far as I understand.

• Update MSRV to 1.31, needed to deal with rand's use of package renaming
  • #130: Convert to 2018 edition too
• #62: Finish support for 64-bit BigDigit
• #101: Enable no_std with the alloc crate (MSRV 1.36)
• #105: Add comparisons with primitive integers (affecting type inference)
  • Reverted in #151, as it broke a lot of integer type inference.
• #106: Implement Pow by value (affecting calls that currently use references)
• #110: Update to rand 0.7 (MSRV 1.32) and quickcheck 0.9 (MSRV 1.34)
• Reconsider {Div,Rem}::Output with primitives to match the smaller type (related to #88)
  • Postponing.

Other PRs and issues may be included too, but these are the ones that impact compatibility.

I am working on some code that needs access to this information, and currently have no (performant) way of accessing it, as it relies on the internal data field which is not accessible either

(copying from rust-num/num#233, here for bigint types only)

The Sum and Product traits are stable in 1.12.0, so we could implement them for our types.

(But we consider it a breaking change to increase the required rustc.)

See rust-num/num#281, and this was previously in the next branch after rust-num/num#305.

The following code calculates a^i for i = 1,2,3,4:

extern crate num_bigint;
extern crate num_traits;
use num_bigint::BigInt;

fn main()
{
    let a = BigInt::from(-1);
    let m = BigInt::from(10);
    
    println!("a = {}", a);
    let a_pow_1 = a.modpow(&BigInt::from(1), &m);
    println!("a^1 mod 10 = {}", a_pow_1);
    let a_pow_2 = a.modpow(&BigInt::from(2), &m);
    println!("a^2 mod 10 = {}", a_pow_2);
    let a_pow_3 = a.modpow(&BigInt::from(3), &m);
    println!("a^3 mod 10 = {}", a_pow_3);
    let a_pow_4 = a.modpow(&BigInt::from(4), &m);
    println!("a^4 mod 10 = {}", a_pow_4);
    
    let a_times_a = (&a * &a) % &m;
    println!("a*a mod 10 = {}", a_times_a);
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7de58584f7dff3342bf0c8cce191bfb7

Expected Output:

a = -1
a^1 mod 10 = 9
a^2 mod 10 = 1
a^3 mod 10 = 9
a^4 mod 10 = 1
a*a mod 10 = 1

Real Output:

a = -1
a^1 mod 10 = 9
a^2 mod 10 = 9
a^3 mod 10 = 9
a^4 mod 10 = 9
a*a mod 10 = 1

I don't know, if my understanding of modulo calculus is correct, but from all I know, I'd assume, that -1^2 == 1 and that a * a == a^2 regardless of the modulus.

Pow<T> is not implemented for BigInt, only for &BigInt. This causes problems for using Pow on Ratio<BigInt> since Ratio<T>'s Pow implementation requires T: Pow.

Little endian is about byte order, not word order. So the order of the bytes in the u32 itself would be little endian or big endian depending on the platform, but the u32 values themselves are ordered least significant first, not in little-endian order.

It would be great to allow for BigInt and alike to be used in constant expressions. This is not possible with Vec, but if we use SmallVec instead, we might be able to make this possible. See servo/rust-smallvec#86

See rust-num/num-traits#38 for details on this trait.

From @mhogrefe on December 9, 2017 19:25

Right-shifting an primitive integer in Rust (and most other languages AFAIK) is equivalent to dividing by a power of 2 and rounding towards -∞. But right-shifting a BigInt rounds towards 0 instead.

You can see the difference by pasting the following into https://play.rust-lang.org/:

extern crate num;

fn main() {
    println!("-1 >> 1 == {} (primitive)", -1 >> 1);
    println!("-1 >> 1 == {} (BigInt)", num::BigInt::from(-1) >> 1);
}

This prints

-1 >> 1 == -1 (primitive)
-1 >> 1 == 0 (BigInt)

If this behavior is intentional it should probably be documented and unit-tested.

Copied from original issue: rust-num/num#347

I would to use serde json serialization for BigUint type. How can one do that?

If I write
#[derive(Serialize, Deserialize)]
pub struct Account {
value: BigUint
}
Then I get the error
| ^^^^^^^^^^^^^^^ the trait serde::Deserialize<'_> is not implemented for num_bigint::BigUint

How can i do this implementation? Is there a standard implementation?

Might be useful for testing, both for ourselves and for others using num-bigint.

(from rust-num/num#241)