1 //! Custom arbitrary-precision number (bignum) implementation.
3 //! This is designed to avoid the heap allocation at expense of stack memory.
4 //! The most used bignum type, `Big32x40`, is limited by 32 × 40 = 1,280 bits
5 //! and will take at most 160 bytes of stack memory. This is more than enough
6 //! for round-tripping all possible finite `f64` values.
8 //! In principle it is possible to have multiple bignum types for different
9 //! inputs, but we don't do so to avoid the code bloat. Each bignum is still
10 //! tracked for the actual usages, so it normally doesn't matter.
12 // This module is only for dec2flt and flt2dec, and only public because of coretests.
13 // It is not intended to ever be stabilized.
16 feature = "core_private_bignum",
17 reason = "internal routines only exposed for testing",
22 use crate::intrinsics;
24 /// Arithmetic operations required by bignums.
25 pub trait FullOps: Sized {
26 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self + other + carry`,
27 /// where `W` is the number of bits in `Self`.
28 fn full_add(self, other: Self, carry: bool) -> (bool /* carry */, Self);
30 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + carry`,
31 /// where `W` is the number of bits in `Self`.
32 fn full_mul(self, other: Self, carry: Self) -> (Self /* carry */, Self);
34 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + other2 + carry`,
35 /// where `W` is the number of bits in `Self`.
36 fn full_mul_add(self, other: Self, other2: Self, carry: Self) -> (Self /* carry */, Self);
38 /// Returns `(quo, rem)` such that `borrow * 2^W + self = quo * other + rem`
39 /// and `0 <= rem < other`, where `W` is the number of bits in `Self`.
40 fn full_div_rem(self, other: Self, borrow: Self)
41 -> (Self /* quotient */, Self /* remainder */);
44 macro_rules! impl_full_ops {
45 ($($ty:ty: add($addfn:path), mul/div($bigty:ident);)*) => (
47 impl FullOps for $ty {
48 fn full_add(self, other: $ty, carry: bool) -> (bool, $ty) {
49 // This cannot overflow; the output is between `0` and `2 * 2^nbits - 1`.
50 // FIXME: will LLVM optimize this into ADC or similar?
51 let (v, carry1) = intrinsics::add_with_overflow(self, other);
52 let (v, carry2) = intrinsics::add_with_overflow(v, if carry {1} else {0});
56 fn full_mul(self, other: $ty, carry: $ty) -> ($ty, $ty) {
57 // This cannot overflow;
58 // the output is between `0` and `2^nbits * (2^nbits - 1)`.
59 // FIXME: will LLVM optimize this into ADC or similar?
60 let v = (self as $bigty) * (other as $bigty) + (carry as $bigty);
61 ((v >> <$ty>::BITS) as $ty, v as $ty)
64 fn full_mul_add(self, other: $ty, other2: $ty, carry: $ty) -> ($ty, $ty) {
65 // This cannot overflow;
66 // the output is between `0` and `2^nbits * (2^nbits - 1)`.
67 let v = (self as $bigty) * (other as $bigty) + (other2 as $bigty) +
69 ((v >> <$ty>::BITS) as $ty, v as $ty)
72 fn full_div_rem(self, other: $ty, borrow: $ty) -> ($ty, $ty) {
73 debug_assert!(borrow < other);
74 // This cannot overflow; the output is between `0` and `other * (2^nbits - 1)`.
75 let lhs = ((borrow as $bigty) << <$ty>::BITS) | (self as $bigty);
76 let rhs = other as $bigty;
77 ((lhs / rhs) as $ty, (lhs % rhs) as $ty)
85 u8: add(intrinsics::u8_add_with_overflow), mul/div(u16);
86 u16: add(intrinsics::u16_add_with_overflow), mul/div(u32);
87 u32: add(intrinsics::u32_add_with_overflow), mul/div(u64);
88 // See RFC #521 for enabling this.
89 // u64: add(intrinsics::u64_add_with_overflow), mul/div(u128);
92 /// Table of powers of 5 representable in digits. Specifically, the largest {u8, u16, u32} value
93 /// that's a power of five, plus the corresponding exponent. Used in `mul_pow5`.
94 const SMALL_POW5: [(u64, usize); 3] = [(125, 3), (15625, 6), (1_220_703_125, 13)];
96 macro_rules! define_bignum {
97 ($name:ident: type=$ty:ty, n=$n:expr) => {
98 /// Stack-allocated arbitrary-precision (up to certain limit) integer.
100 /// This is backed by a fixed-size array of given type ("digit").
101 /// While the array is not very large (normally some hundred bytes),
102 /// copying it recklessly may result in the performance hit.
103 /// Thus this is intentionally not `Copy`.
105 /// All operations available to bignums panic in the case of overflows.
106 /// The caller is responsible to use large enough bignum types.
108 /// One plus the offset to the maximum "digit" in use.
109 /// This does not decrease, so be aware of the computation order.
110 /// `base[size..]` should be zero.
112 /// Digits. `[a, b, c, ...]` represents `a + b*2^W + c*2^(2W) + ...`
113 /// where `W` is the number of bits in the digit type.
118 /// Makes a bignum from one digit.
119 pub fn from_small(v: $ty) -> $name {
120 let mut base = [0; $n];
122 $name { size: 1, base: base }
125 /// Makes a bignum from `u64` value.
126 pub fn from_u64(mut v: u64) -> $name {
127 let mut base = [0; $n];
134 $name { size: sz, base: base }
137 /// Returns the internal digits as a slice `[a, b, c, ...]` such that the numeric
138 /// value is `a + b * 2^W + c * 2^(2W) + ...` where `W` is the number of bits in
140 pub fn digits(&self) -> &[$ty] {
141 &self.base[..self.size]
144 /// Returns the `i`-th bit where bit 0 is the least significant one.
145 /// In other words, the bit with weight `2^i`.
146 pub fn get_bit(&self, i: usize) -> u8 {
147 let digitbits = <$ty>::BITS as usize;
148 let d = i / digitbits;
149 let b = i % digitbits;
150 ((self.base[d] >> b) & 1) as u8
153 /// Returns `true` if the bignum is zero.
154 pub fn is_zero(&self) -> bool {
155 self.digits().iter().all(|&v| v == 0)
158 /// Returns the number of bits necessary to represent this value. Note that zero
159 /// is considered to need 0 bits.
160 pub fn bit_length(&self) -> usize {
161 // Skip over the most significant digits which are zero.
162 let digits = self.digits();
163 let zeros = digits.iter().rev().take_while(|&&x| x == 0).count();
164 let end = digits.len() - zeros;
165 let nonzero = &digits[..end];
167 if nonzero.is_empty() {
168 // There are no non-zero digits, i.e., the number is zero.
171 // This could be optimized with leading_zeros() and bit shifts, but that's
172 // probably not worth the hassle.
173 let digitbits = <$ty>::BITS as usize;
174 let mut i = nonzero.len() * digitbits - 1;
175 while self.get_bit(i) == 0 {
181 /// Adds `other` to itself and returns its own mutable reference.
182 pub fn add<'a>(&'a mut self, other: &$name) -> &'a mut $name {
184 use crate::num::bignum::FullOps;
186 let mut sz = cmp::max(self.size, other.size);
187 let mut carry = false;
188 for (a, b) in self.base[..sz].iter_mut().zip(&other.base[..sz]) {
189 let (c, v) = (*a).full_add(*b, carry);
201 pub fn add_small(&mut self, other: $ty) -> &mut $name {
202 use crate::num::bignum::FullOps;
204 let (mut carry, v) = self.base[0].full_add(other, false);
208 let (c, v) = self.base[i].full_add(0, carry);
219 /// Subtracts `other` from itself and returns its own mutable reference.
220 pub fn sub<'a>(&'a mut self, other: &$name) -> &'a mut $name {
222 use crate::num::bignum::FullOps;
224 let sz = cmp::max(self.size, other.size);
225 let mut noborrow = true;
226 for (a, b) in self.base[..sz].iter_mut().zip(&other.base[..sz]) {
227 let (c, v) = (*a).full_add(!*b, noborrow);
236 /// Multiplies itself by a digit-sized `other` and returns its own
237 /// mutable reference.
238 pub fn mul_small(&mut self, other: $ty) -> &mut $name {
239 use crate::num::bignum::FullOps;
241 let mut sz = self.size;
243 for a in &mut self.base[..sz] {
244 let (c, v) = (*a).full_mul(other, carry);
249 self.base[sz] = carry;
256 /// Multiplies itself by `2^bits` and returns its own mutable reference.
257 pub fn mul_pow2(&mut self, bits: usize) -> &mut $name {
258 let digitbits = <$ty>::BITS as usize;
259 let digits = bits / digitbits;
260 let bits = bits % digitbits;
262 assert!(digits < $n);
263 debug_assert!(self.base[$n - digits..].iter().all(|&v| v == 0));
264 debug_assert!(bits == 0 || (self.base[$n - digits - 1] >> (digitbits - bits)) == 0);
266 // shift by `digits * digitbits` bits
267 for i in (0..self.size).rev() {
268 self.base[i + digits] = self.base[i];
274 // shift by `bits` bits
275 let mut sz = self.size + digits;
278 let overflow = self.base[last - 1] >> (digitbits - bits);
280 self.base[last] = overflow;
283 for i in (digits + 1..last).rev() {
285 (self.base[i] << bits) | (self.base[i - 1] >> (digitbits - bits));
287 self.base[digits] <<= bits;
288 // self.base[..digits] is zero, no need to shift
295 /// Multiplies itself by `5^e` and returns its own mutable reference.
296 pub fn mul_pow5(&mut self, mut e: usize) -> &mut $name {
298 use crate::num::bignum::SMALL_POW5;
300 // There are exactly n trailing zeros on 2^n, and the only relevant digit sizes
301 // are consecutive powers of two, so this is well suited index for the table.
302 let table_index = mem::size_of::<$ty>().trailing_zeros() as usize;
303 let (small_power, small_e) = SMALL_POW5[table_index];
304 let small_power = small_power as $ty;
306 // Multiply with the largest single-digit power as long as possible ...
308 self.mul_small(small_power);
312 // ... then finish off the remainder.
313 let mut rest_power = 1;
317 self.mul_small(rest_power);
322 /// Multiplies itself by a number described by `other[0] + other[1] * 2^W +
323 /// other[2] * 2^(2W) + ...` (where `W` is the number of bits in the digit type)
324 /// and returns its own mutable reference.
325 pub fn mul_digits<'a>(&'a mut self, other: &[$ty]) -> &'a mut $name {
326 // the internal routine. works best when aa.len() <= bb.len().
327 fn mul_inner(ret: &mut [$ty; $n], aa: &[$ty], bb: &[$ty]) -> usize {
328 use crate::num::bignum::FullOps;
331 for (i, &a) in aa.iter().enumerate() {
335 let mut sz = bb.len();
337 for (j, &b) in bb.iter().enumerate() {
338 let (c, v) = a.full_mul_add(b, ret[i + j], carry);
353 let mut ret = [0; $n];
354 let retsz = if self.size < other.len() {
355 mul_inner(&mut ret, &self.digits(), other)
357 mul_inner(&mut ret, other, &self.digits())
364 /// Divides itself by a digit-sized `other` and returns its own
365 /// mutable reference *and* the remainder.
366 pub fn div_rem_small(&mut self, other: $ty) -> (&mut $name, $ty) {
367 use crate::num::bignum::FullOps;
373 for a in self.base[..sz].iter_mut().rev() {
374 let (q, r) = (*a).full_div_rem(other, borrow);
381 /// Divide self by another bignum, overwriting `q` with the quotient and `r` with the
383 pub fn div_rem(&self, d: &$name, q: &mut $name, r: &mut $name) {
384 // Stupid slow base-2 long division taken from
385 // https://en.wikipedia.org/wiki/Division_algorithm
386 // FIXME use a greater base ($ty) for the long division.
387 assert!(!d.is_zero());
388 let digitbits = <$ty>::BITS as usize;
389 for digit in &mut q.base[..] {
392 for digit in &mut r.base[..] {
397 let mut q_is_zero = true;
398 let end = self.bit_length();
399 for i in (0..end).rev() {
401 r.base[0] |= self.get_bit(i) as $ty;
404 // Set bit `i` of q to 1.
405 let digit_idx = i / digitbits;
406 let bit_idx = i % digitbits;
408 q.size = digit_idx + 1;
411 q.base[digit_idx] |= 1 << bit_idx;
414 debug_assert!(q.base[q.size..].iter().all(|&d| d == 0));
415 debug_assert!(r.base[r.size..].iter().all(|&d| d == 0));
419 impl crate::cmp::PartialEq for $name {
420 fn eq(&self, other: &$name) -> bool {
421 self.base[..] == other.base[..]
425 impl crate::cmp::Eq for $name {}
427 impl crate::cmp::PartialOrd for $name {
428 fn partial_cmp(&self, other: &$name) -> crate::option::Option<crate::cmp::Ordering> {
429 crate::option::Option::Some(self.cmp(other))
433 impl crate::cmp::Ord for $name {
434 fn cmp(&self, other: &$name) -> crate::cmp::Ordering {
436 let sz = max(self.size, other.size);
437 let lhs = self.base[..sz].iter().cloned().rev();
438 let rhs = other.base[..sz].iter().cloned().rev();
443 impl crate::clone::Clone for $name {
444 fn clone(&self) -> Self {
445 Self { size: self.size, base: self.base }
449 impl crate::fmt::Debug for $name {
450 fn fmt(&self, f: &mut crate::fmt::Formatter<'_>) -> crate::fmt::Result {
451 let sz = if self.size < 1 { 1 } else { self.size };
452 let digitlen = <$ty>::BITS as usize / 4;
454 write!(f, "{:#x}", self.base[sz - 1])?;
455 for &v in self.base[..sz - 1].iter().rev() {
456 write!(f, "_{:01$x}", v, digitlen)?;
458 crate::result::Result::Ok(())
464 /// The digit type for `Big32x40`.
465 pub type Digit32 = u32;
467 define_bignum!(Big32x40: type=Digit32, n=40);
469 // this one is used for testing only.
472 define_bignum!(Big8x3: type=u8, n=3);