num_bigint/
bigrand.rs

Help
1//! Randomization of big integers
2
3use rand::distributions::uniform::{SampleBorrow, SampleUniform, UniformSampler};
4use rand::prelude::*;
5
6use crate::BigInt;
7use crate::BigUint;
8use crate::Sign::*;
9
10use crate::biguint::biguint_from_vec;
11
12use num_integer::Integer;
13use num_traits::{ToPrimitive, Zero};
14
15/// A trait for sampling random big integers.
16///
17/// The `rand` feature must be enabled to use this. See crate-level documentation for details.
18pub trait RandBigInt {
19    /// Generate a random `BigUint` of the given bit size.
20    fn gen_biguint(&mut self, bit_size: u64) -> BigUint;
21
22    /// Generate a random BigInt of the given bit size.
23    fn gen_bigint(&mut self, bit_size: u64) -> BigInt;
24
25    /// Generate a random `BigUint` less than the given bound. Fails
26    /// when the bound is zero.
27    fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
28
29    /// Generate a random `BigUint` within the given range. The lower
30    /// bound is inclusive; the upper bound is exclusive. Fails when
31    /// the upper bound is not greater than the lower bound.
32    fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
33
34    /// Generate a random `BigInt` within the given range. The lower
35    /// bound is inclusive; the upper bound is exclusive. Fails when
36    /// the upper bound is not greater than the lower bound.
37    fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
38}
39
40fn gen_bits<R: Rng + ?Sized>(rng: &mut R, data: &mut [u32], rem: u64) {
41    // `fill` is faster than many `gen::<u32>` calls
42    rng.fill(data);
43    if rem > 0 {
44        let last = data.len() - 1;
45        data[last] >>= 32 - rem;
46    }
47}
48
49impl<R: Rng + ?Sized> RandBigInt for R {
50    #[cfg(not(u64_digit))]
51    fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
52        let (digits, rem) = bit_size.div_rem(&32);
53        let len = (digits + (rem > 0) as u64)
54            .to_usize()
55            .expect("capacity overflow");
56        let mut data = vec![0u32; len];
57        gen_bits(self, &mut data, rem);
58        biguint_from_vec(data)
59    }
60
61    #[cfg(u64_digit)]
62    fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
63        use core::slice;
64
65        let (digits, rem) = bit_size.div_rem(&32);
66        let len = (digits + (rem > 0) as u64)
67            .to_usize()
68            .expect("capacity overflow");
69        let native_digits = Integer::div_ceil(&bit_size, &64);
70        let native_len = native_digits.to_usize().expect("capacity overflow");
71        let mut data = vec![0u64; native_len];
72        unsafe {
73            // Generate bits in a `&mut [u32]` slice for value stability
74            let ptr = data.as_mut_ptr() as *mut u32;
75            debug_assert!(native_len * 2 >= len);
76            let data = slice::from_raw_parts_mut(ptr, len);
77            gen_bits(self, data, rem);
78        }
79        #[cfg(target_endian = "big")]
80        for digit in &mut data {
81            // swap u32 digits into u64 endianness
82            *digit = (*digit << 32) | (*digit >> 32);
83        }
84        biguint_from_vec(data)
85    }
86
87    fn gen_bigint(&mut self, bit_size: u64) -> BigInt {
88        loop {
89            // Generate a random BigUint...
90            let biguint = self.gen_biguint(bit_size);
91            // ...and then randomly assign it a Sign...
92            let sign = if biguint.is_zero() {
93                // ...except that if the BigUint is zero, we need to try
94                // again with probability 0.5. This is because otherwise,
95                // the probability of generating a zero BigInt would be
96                // double that of any other number.
97                if self.gen() {
98                    continue;
99                } else {
100                    NoSign
101                }
102            } else if self.gen() {
103                Plus
104            } else {
105                Minus
106            };
107            return BigInt::from_biguint(sign, biguint);
108        }
109    }
110
111    fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
112        assert!(!bound.is_zero());
113        let bits = bound.bits();
114        loop {
115            let n = self.gen_biguint(bits);
116            if n < *bound {
117                return n;
118            }
119        }
120    }
121
122    fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint {
123        assert!(*lbound < *ubound);
124        if lbound.is_zero() {
125            self.gen_biguint_below(ubound)
126        } else {
127            lbound + self.gen_biguint_below(&(ubound - lbound))
128        }
129    }
130
131    fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt {
132        assert!(*lbound < *ubound);
133        if lbound.is_zero() {
134            BigInt::from(self.gen_biguint_below(ubound.magnitude()))
135        } else if ubound.is_zero() {
136            lbound + BigInt::from(self.gen_biguint_below(lbound.magnitude()))
137        } else {
138            let delta = ubound - lbound;
139            lbound + BigInt::from(self.gen_biguint_below(delta.magnitude()))
140        }
141    }
142}
143
144/// The back-end implementing rand's `UniformSampler` for `BigUint`.
145#[derive(Clone, Debug)]
146pub struct UniformBigUint {
147    base: BigUint,
148    len: BigUint,
149}
150
151impl UniformSampler for UniformBigUint {
152    type X = BigUint;
153
154    #[inline]
155    fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
156    where
157        B1: SampleBorrow<Self::X> + Sized,
158        B2: SampleBorrow<Self::X> + Sized,
159    {
160        let low = low_b.borrow();
161        let high = high_b.borrow();
162        assert!(low < high);
163        UniformBigUint {
164            len: high - low,
165            base: low.clone(),
166        }
167    }
168
169    #[inline]
170    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
171    where
172        B1: SampleBorrow<Self::X> + Sized,
173        B2: SampleBorrow<Self::X> + Sized,
174    {
175        let low = low_b.borrow();
176        let high = high_b.borrow();
177        assert!(low <= high);
178        Self::new(low, high + 1u32)
179    }
180
181    #[inline]
182    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
183        &self.base + rng.gen_biguint_below(&self.len)
184    }
185
186    #[inline]
187    fn sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X
188    where
189        B1: SampleBorrow<Self::X> + Sized,
190        B2: SampleBorrow<Self::X> + Sized,
191    {
192        rng.gen_biguint_range(low.borrow(), high.borrow())
193    }
194}
195
196impl SampleUniform for BigUint {
197    type Sampler = UniformBigUint;
198}
199
200/// The back-end implementing rand's `UniformSampler` for `BigInt`.
201#[derive(Clone, Debug)]
202pub struct UniformBigInt {
203    base: BigInt,
204    len: BigUint,
205}
206
207impl UniformSampler for UniformBigInt {
208    type X = BigInt;
209
210    #[inline]
211    fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
212    where
213        B1: SampleBorrow<Self::X> + Sized,
214        B2: SampleBorrow<Self::X> + Sized,
215    {
216        let low = low_b.borrow();
217        let high = high_b.borrow();
218        assert!(low < high);
219        UniformBigInt {
220            len: (high - low).into_parts().1,
221            base: low.clone(),
222        }
223    }
224
225    #[inline]
226    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
227    where
228        B1: SampleBorrow<Self::X> + Sized,
229        B2: SampleBorrow<Self::X> + Sized,
230    {
231        let low = low_b.borrow();
232        let high = high_b.borrow();
233        assert!(low <= high);
234        Self::new(low, high + 1u32)
235    }
236
237    #[inline]
238    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
239        &self.base + BigInt::from(rng.gen_biguint_below(&self.len))
240    }
241
242    #[inline]
243    fn sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X
244    where
245        B1: SampleBorrow<Self::X> + Sized,
246        B2: SampleBorrow<Self::X> + Sized,
247    {
248        rng.gen_bigint_range(low.borrow(), high.borrow())
249    }
250}
251
252impl SampleUniform for BigInt {
253    type Sampler = UniformBigInt;
254}
255
256/// A random distribution for `BigUint` and `BigInt` values of a particular bit size.
257///
258/// The `rand` feature must be enabled to use this. See crate-level documentation for details.
259#[derive(Clone, Copy, Debug)]
260pub struct RandomBits {
261    bits: u64,
262}
263
264impl RandomBits {
265    #[inline]
266    pub fn new(bits: u64) -> RandomBits {
267        RandomBits { bits }
268    }
269}
270
271impl Distribution<BigUint> for RandomBits {
272    #[inline]
273    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigUint {
274        rng.gen_biguint(self.bits)
275    }
276}
277
278impl Distribution<BigInt> for RandomBits {
279    #[inline]
280    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt {
281        rng.gen_bigint(self.bits)
282    }
283}
num_bigint/bigrand.rs

num_bigint/
bigrand.rs
