rust-num / num-bigint Goto Github PK
View Code? Open in Web Editor NEWBig integer types for Rust
License: Apache License 2.0
Big integer types for Rust
License: Apache License 2.0
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
}
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/
Hi,
Is there any solution for generation of primes, safe primes and prime checking with num-bigint?
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.
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
See rust-num/num#281, and this was previously in the next branch after rust-num/num#305.
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.
BigInt::zero().lcm(&BigInt::zero())
panics instead of returning the expected result of 0.
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
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".
BigDigit = u64
with DoubleBigDigit = u128
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:
>=0.4, <0.6
Rng::gen()
.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.We already have them for BigUint
, so this probably just needs more forwarding impls.
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.
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.
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
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.
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.
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?
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));
}
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
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.
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);
}
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.
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
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.
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
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?
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
.
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?
It would be nice to have a method for getting the memory consumption of BigInt
s and BigUInt
s. 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:
data
orBigInt
/BigUInt
I would prefer the first option because it will support a lot more unforseen use cases.
See the discussion at RustPython/RustPython#1172
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?
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.
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)
See rust-num/num-traits#38 for details on this trait.
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
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.
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.
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.
BigDigit
no_std
with the alloc crate (MSRV 1.36)Pow
by value (affecting calls that currently use references){Div,Rem}::Output
with primitives to match the smaller type (related to #88)Other PRs and issues may be included too, but these are the ones that impact compatibility.
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.
(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.)
Might be useful for testing, both for ourselves and for others using num-bigint.
(from rust-num/num#241)
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.
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.
performance: By returning a native integer we remove the need to allocate on the heap, which leads to a 2x speedup with small BigInt
s. More exact benchmarks will follow in case it's deemed necessary. This can also reduces the amount of BigInt
s 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.
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
.
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
.
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?
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?
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
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
Running it in playground:
I get the wrong answer raising any number to the power of any number.
Am I using the crate incorrectly?
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
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.