1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
13 //! A `BigUint` is represented as an array of `BigDigit`s.
14 //! A `BigInt` is a combination of `BigUint` and `Sign`.
16 //! Common numerical operations are overloaded, so we can treat them
17 //! the same way we treat other numbers.
22 //! # #![allow(deprecated)]
23 //! use num::bigint::BigUint;
24 //! use std::num::{Zero, One};
25 //! use std::mem::replace;
27 //! // Calculate large fibonacci numbers.
28 //! fn fib(n: uint) -> BigUint {
29 //! let mut f0: BigUint = Zero::zero();
30 //! let mut f1: BigUint = One::one();
31 //! for _ in range(0, n) {
33 //! // This is a low cost way of swapping f0 with f1 and f1 with f2.
34 //! f0 = replace(&mut f1, f2);
39 //! // This is a very large number.
40 //! println!("fib(1000) = {}", fib(1000));
43 //! It's easy to generate large random numbers:
46 //! # #![allow(deprecated)]
47 //! use num::bigint::{ToBigInt, RandBigInt};
50 //! let mut rng = rand::task_rng();
51 //! let a = rng.gen_bigint(1000u);
53 //! let low = -10000i.to_bigint().unwrap();
54 //! let high = 10000i.to_bigint().unwrap();
55 //! let b = rng.gen_bigint_range(&low, &high);
57 //! // Probably an even larger number.
58 //! println!("{}", a * b);
64 use std::{cmp, fmt, hash};
65 use std::default::Default;
66 use std::from_str::FromStr;
67 use std::num::CheckedDiv;
68 use std::num::{ToPrimitive, FromPrimitive};
69 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
70 use std::string::String;
71 use std::{uint, i64, u64};
73 /// A `BigDigit` is a `BigUint`'s composing element.
74 pub type BigDigit = u32;
76 /// A `DoubleBigDigit` is the internal type used to do the computations. Its
77 /// size is the double of the size of `BigDigit`.
78 pub type DoubleBigDigit = u64;
80 pub static ZERO_BIG_DIGIT: BigDigit = 0;
81 static ZERO_VEC: [BigDigit, ..1] = [ZERO_BIG_DIGIT];
83 #[allow(non_snake_case)]
86 use super::DoubleBigDigit;
88 // `DoubleBigDigit` size dependent
89 pub static bits: uint = 32;
91 pub static base: DoubleBigDigit = 1 << bits;
92 static lo_mask: DoubleBigDigit = (-1 as DoubleBigDigit) >> bits;
95 fn get_hi(n: DoubleBigDigit) -> BigDigit { (n >> bits) as BigDigit }
97 fn get_lo(n: DoubleBigDigit) -> BigDigit { (n & lo_mask) as BigDigit }
99 /// Split one `DoubleBigDigit` into two `BigDigit`s.
101 pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
102 (get_hi(n), get_lo(n))
105 /// Join two `BigDigit`s into one `DoubleBigDigit`
107 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
108 (lo as DoubleBigDigit) | ((hi as DoubleBigDigit) << bits)
112 /// A big unsigned integer type.
114 /// A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
115 /// `(a + b * BigDigit::base + c * BigDigit::base^2)`.
121 impl PartialEq for BigUint {
123 fn eq(&self, other: &BigUint) -> bool {
124 match self.cmp(other) { Equal => true, _ => false }
127 impl Eq for BigUint {}
129 impl PartialOrd for BigUint {
131 fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
132 Some(self.cmp(other))
136 impl Ord for BigUint {
138 fn cmp(&self, other: &BigUint) -> Ordering {
139 let (s_len, o_len) = (self.data.len(), other.data.len());
140 if s_len < o_len { return Less; }
141 if s_len > o_len { return Greater; }
143 for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
144 if self_i < other_i { return Less; }
145 if self_i > other_i { return Greater; }
151 impl Default for BigUint {
153 fn default() -> BigUint { Zero::zero() }
156 impl<S: hash::Writer> hash::Hash<S> for BigUint {
157 fn hash(&self, state: &mut S) {
158 // hash 0 in case it's all 0's
161 let mut found_first_value = false;
162 for elem in self.data.iter().rev() {
163 // don't hash any leading 0's, they shouldn't affect the hash
164 if found_first_value || *elem != 0 {
165 found_first_value = true;
172 impl fmt::Show for BigUint {
173 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
174 write!(f, "{}", self.to_str_radix(10))
178 impl FromStr for BigUint {
180 fn from_str(s: &str) -> Option<BigUint> {
181 FromStrRadix::from_str_radix(s, 10)
185 impl Num for BigUint {}
187 impl BitAnd<BigUint, BigUint> for BigUint {
188 fn bitand(&self, other: &BigUint) -> BigUint {
189 BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
193 impl BitOr<BigUint, BigUint> for BigUint {
194 fn bitor(&self, other: &BigUint) -> BigUint {
195 let zeros = ZERO_VEC.iter().cycle();
196 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
197 let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
200 return BigUint::new(ored);
204 impl BitXor<BigUint, BigUint> for BigUint {
205 fn bitxor(&self, other: &BigUint) -> BigUint {
206 let zeros = ZERO_VEC.iter().cycle();
207 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
208 let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
211 return BigUint::new(xored);
215 impl Shl<uint, BigUint> for BigUint {
217 fn shl(&self, rhs: &uint) -> BigUint {
218 let n_unit = *rhs / BigDigit::bits;
219 let n_bits = *rhs % BigDigit::bits;
220 return self.shl_unit(n_unit).shl_bits(n_bits);
224 impl Shr<uint, BigUint> for BigUint {
226 fn shr(&self, rhs: &uint) -> BigUint {
227 let n_unit = *rhs / BigDigit::bits;
228 let n_bits = *rhs % BigDigit::bits;
229 return self.shr_unit(n_unit).shr_bits(n_bits);
233 impl Zero for BigUint {
235 fn zero() -> BigUint { BigUint::new(Vec::new()) }
238 fn is_zero(&self) -> bool { self.data.is_empty() }
241 impl One for BigUint {
243 fn one() -> BigUint { BigUint::new(vec!(1)) }
246 impl Unsigned for BigUint {}
248 impl Add<BigUint, BigUint> for BigUint {
249 fn add(&self, other: &BigUint) -> BigUint {
250 let zeros = ZERO_VEC.iter().cycle();
251 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
254 let mut sum: Vec<BigDigit> = a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
255 let (hi, lo) = BigDigit::from_doublebigdigit(
256 (*ai as DoubleBigDigit) + (*bi as DoubleBigDigit) + (carry as DoubleBigDigit));
260 if carry != 0 { sum.push(carry); }
261 return BigUint::new(sum);
265 impl Sub<BigUint, BigUint> for BigUint {
266 fn sub(&self, other: &BigUint) -> BigUint {
267 let new_len = cmp::max(self.data.len(), other.data.len());
268 let zeros = ZERO_VEC.iter().cycle();
269 let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
272 let diff: Vec<BigDigit> = a.take(new_len).zip(b).map(|(ai, bi)| {
273 let (hi, lo) = BigDigit::from_doublebigdigit(
275 + (*ai as DoubleBigDigit)
276 - (*bi as DoubleBigDigit)
277 - (borrow as DoubleBigDigit)
280 hi * (base) + lo == 1*(base) + ai - bi - borrow
281 => ai - bi - borrow < 0 <=> hi == 0
283 borrow = if hi == 0 { 1 } else { 0 };
288 "Cannot subtract other from self because other is larger than self.");
289 return BigUint::new(diff);
293 impl Mul<BigUint, BigUint> for BigUint {
294 fn mul(&self, other: &BigUint) -> BigUint {
295 if self.is_zero() || other.is_zero() { return Zero::zero(); }
297 let (s_len, o_len) = (self.data.len(), other.data.len());
298 if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]); }
299 if o_len == 1 { return mul_digit(self, other.data.as_slice()[0]); }
301 // Using Karatsuba multiplication
302 // (a1 * base + a0) * (b1 * base + b0)
303 // = a1*b1 * base^2 +
304 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
306 let half_len = cmp::max(s_len, o_len) / 2;
307 let (s_hi, s_lo) = cut_at(self, half_len);
308 let (o_hi, o_lo) = cut_at(other, half_len);
310 let ll = s_lo * o_lo;
311 let hh = s_hi * o_hi;
313 let (s1, n1) = sub_sign(s_hi, s_lo);
314 let (s2, n2) = sub_sign(o_hi, o_lo);
316 (Equal, _) | (_, Equal) => hh + ll,
317 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
318 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
322 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
325 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
326 if n == 0 { return Zero::zero(); }
327 if n == 1 { return (*a).clone(); }
330 let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
331 let (hi, lo) = BigDigit::from_doublebigdigit(
332 (*ai as DoubleBigDigit) * (n as DoubleBigDigit) + (carry as DoubleBigDigit)
337 if carry != 0 { prod.push(carry); }
338 return BigUint::new(prod);
342 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
343 let mid = cmp::min(a.data.len(), n);
344 return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
345 BigUint::from_slice(a.data.slice(0, mid)));
349 fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
351 Less => (Less, b - a),
352 Greater => (Greater, a - b),
353 _ => (Equal, Zero::zero())
359 impl Div<BigUint, BigUint> for BigUint {
361 fn div(&self, other: &BigUint) -> BigUint {
362 let (q, _) = self.div_rem(other);
367 impl Rem<BigUint, BigUint> for BigUint {
369 fn rem(&self, other: &BigUint) -> BigUint {
370 let (_, r) = self.div_rem(other);
375 impl Neg<BigUint> for BigUint {
377 fn neg(&self) -> BigUint { fail!() }
380 impl CheckedAdd for BigUint {
382 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
383 return Some(self.add(v));
387 impl CheckedSub for BigUint {
389 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
393 return Some(self.sub(v));
397 impl CheckedMul for BigUint {
399 fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
400 return Some(self.mul(v));
404 impl CheckedDiv for BigUint {
406 fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
410 return Some(self.div(v));
414 impl Integer for BigUint {
416 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
417 self.div_mod_floor(other)
421 fn div_floor(&self, other: &BigUint) -> BigUint {
422 let (d, _) = self.div_mod_floor(other);
427 fn mod_floor(&self, other: &BigUint) -> BigUint {
428 let (_, m) = self.div_mod_floor(other);
432 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
433 if other.is_zero() { fail!() }
434 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
435 if *other == One::one() { return ((*self).clone(), Zero::zero()); }
437 match self.cmp(other) {
438 Less => return (Zero::zero(), (*self).clone()),
439 Equal => return (One::one(), Zero::zero()),
440 Greater => {} // Do nothing
444 let mut n = *other.data.last().unwrap();
445 while n < (1 << BigDigit::bits - 2) {
449 assert!(shift < BigDigit::bits);
450 let (d, m) = div_mod_floor_inner(self << shift, other << shift);
451 return (d, m >> shift);
454 fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
456 let mut d: BigUint = Zero::zero();
459 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
461 let mut prod = b * d0;
463 // FIXME(#5992): assignment operator overloads
466 // FIXME(#5992): assignment operator overloads
475 // FIXME(#5992): assignment operator overloads
478 // FIXME(#5992): assignment operator overloads
486 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
487 -> (BigUint, BigUint, BigUint) {
488 if a.data.len() < n {
489 return (Zero::zero(), Zero::zero(), (*a).clone());
492 let an = a.data.tailn(a.data.len() - n);
493 let bn = *b.data.last().unwrap();
494 let mut d = Vec::with_capacity(an.len());
496 for elt in an.iter().rev() {
497 let ai = BigDigit::to_doublebigdigit(carry, *elt);
498 let di = ai / (bn as DoubleBigDigit);
499 assert!(di < BigDigit::base);
500 carry = (ai % (bn as DoubleBigDigit)) as BigDigit;
501 d.push(di as BigDigit)
505 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
507 return (BigUint::new(d), One::one(), (*b).clone());
509 let one: BigUint = One::one();
510 return (BigUint::new(d).shl_unit(shift),
516 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
518 /// The result is always positive.
520 fn gcd(&self, other: &BigUint) -> BigUint {
521 // Use Euclid's algorithm
522 let mut m = (*self).clone();
523 let mut n = (*other).clone();
532 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
534 fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
536 /// Deprecated, use `is_multiple_of` instead.
537 #[deprecated = "function renamed to `is_multiple_of`"]
539 fn divides(&self, other: &BigUint) -> bool { return self.is_multiple_of(other); }
541 /// Returns `true` if the number is a multiple of `other`.
543 fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
545 /// Returns `true` if the number is divisible by `2`.
547 fn is_even(&self) -> bool {
548 // Considering only the last digit.
549 match self.data.as_slice().head() {
550 Some(x) => x.is_even(),
555 /// Returns `true` if the number is not divisible by `2`.
557 fn is_odd(&self) -> bool { !self.is_even() }
560 impl ToPrimitive for BigUint {
562 fn to_i64(&self) -> Option<i64> {
563 self.to_u64().and_then(|n| {
564 // If top bit of u64 is set, it's too large to convert to i64.
573 // `DoubleBigDigit` size dependent
575 fn to_u64(&self) -> Option<u64> {
576 match self.data.len() {
578 1 => Some(self.data.as_slice()[0] as u64),
579 2 => Some(BigDigit::to_doublebigdigit(self.data.as_slice()[1], self.data.as_slice()[0])
586 impl FromPrimitive for BigUint {
588 fn from_i64(n: i64) -> Option<BigUint> {
590 FromPrimitive::from_u64(n as u64)
598 // `DoubleBigDigit` size dependent
600 fn from_u64(n: u64) -> Option<BigUint> {
601 let n = match BigDigit::from_doublebigdigit(n) {
602 (0, 0) => Zero::zero(),
603 (0, n0) => BigUint::new(vec!(n0)),
604 (n1, n0) => BigUint::new(vec!(n0, n1))
610 /// A generic trait for converting a value to a `BigUint`.
611 pub trait ToBigUint {
612 /// Converts the value of `self` to a `BigUint`.
613 fn to_biguint(&self) -> Option<BigUint>;
616 impl ToBigUint for BigInt {
618 fn to_biguint(&self) -> Option<BigUint> {
619 if self.sign == Plus {
620 Some(self.data.clone())
621 } else if self.sign == NoSign {
629 impl ToBigUint for BigUint {
631 fn to_biguint(&self) -> Option<BigUint> {
636 macro_rules! impl_to_biguint(
637 ($T:ty, $from_ty:path) => {
638 impl ToBigUint for $T {
640 fn to_biguint(&self) -> Option<BigUint> {
647 impl_to_biguint!(int, FromPrimitive::from_int)
648 impl_to_biguint!(i8, FromPrimitive::from_i8)
649 impl_to_biguint!(i16, FromPrimitive::from_i16)
650 impl_to_biguint!(i32, FromPrimitive::from_i32)
651 impl_to_biguint!(i64, FromPrimitive::from_i64)
652 impl_to_biguint!(uint, FromPrimitive::from_uint)
653 impl_to_biguint!(u8, FromPrimitive::from_u8)
654 impl_to_biguint!(u16, FromPrimitive::from_u16)
655 impl_to_biguint!(u32, FromPrimitive::from_u32)
656 impl_to_biguint!(u64, FromPrimitive::from_u64)
658 impl ToStrRadix for BigUint {
659 fn to_str_radix(&self, radix: uint) -> String {
660 assert!(1 < radix && radix <= 16, "The radix must be within (1, 16]");
661 let (base, max_len) = get_radix_base(radix);
662 if base == BigDigit::base {
663 return fill_concat(self.data.as_slice(), radix, max_len)
665 return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
667 fn convert_base(n: &BigUint, base: DoubleBigDigit) -> Vec<BigDigit> {
668 let divider = base.to_biguint().unwrap();
669 let mut result = Vec::new();
670 let mut m = n.clone();
672 let (d, m0) = m.div_mod_floor(÷r);
673 result.push(m0.to_uint().unwrap() as BigDigit);
677 result.push(m.to_uint().unwrap() as BigDigit);
682 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> String {
684 return "0".to_string()
686 let mut s = String::with_capacity(v.len() * l);
687 for n in v.iter().rev() {
688 let ss = (*n as uint).to_str_radix(radix);
689 s.push_str("0".repeat(l - ss.len()).as_slice());
690 s.push_str(ss.as_slice());
692 s.as_slice().trim_left_chars('0').to_string()
697 impl FromStrRadix for BigUint {
698 /// Creates and initializes a `BigUint`.
700 fn from_str_radix(s: &str, radix: uint) -> Option<BigUint> {
701 BigUint::parse_bytes(s.as_bytes(), radix)
706 /// Creates and initializes a `BigUint`.
708 /// The digits are be in base 2^32.
710 pub fn new(mut digits: Vec<BigDigit>) -> BigUint {
711 // omit trailing zeros
712 let new_len = digits.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
713 digits.truncate(new_len);
714 BigUint { data: digits }
717 /// Creates and initializes a `BigUint`.
719 /// The digits are be in base 2^32.
721 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
722 BigUint::new(Vec::from_slice(slice))
725 /// Creates and initializes a `BigUint`.
726 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
727 let (base, unit_len) = get_radix_base(radix);
728 let base_num = match base.to_biguint() {
729 Some(base_num) => base_num,
730 None => { return None; }
733 let mut end = buf.len();
734 let mut n: BigUint = Zero::zero();
735 let mut power: BigUint = One::one();
737 let start = cmp::max(end, unit_len) - unit_len;
738 match uint::parse_bytes(buf.slice(start, end), radix) {
740 let d: Option<BigUint> = FromPrimitive::from_uint(d);
743 // FIXME(#5992): assignment operator overloads
747 None => { return None; }
750 None => { return None; }
756 // FIXME(#5992): assignment operator overloads
757 // power *= base_num;
758 power = power * base_num;
763 fn shl_unit(&self, n_unit: uint) -> BigUint {
764 if n_unit == 0 || self.is_zero() { return (*self).clone(); }
766 BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
770 fn shl_bits(&self, n_bits: uint) -> BigUint {
771 if n_bits == 0 || self.is_zero() { return (*self).clone(); }
774 let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
775 let (hi, lo) = BigDigit::from_doublebigdigit(
776 (*elem as DoubleBigDigit) << n_bits | (carry as DoubleBigDigit)
781 if carry != 0 { shifted.push(carry); }
782 return BigUint::new(shifted);
786 fn shr_unit(&self, n_unit: uint) -> BigUint {
787 if n_unit == 0 { return (*self).clone(); }
788 if self.data.len() < n_unit { return Zero::zero(); }
789 return BigUint::from_slice(
790 self.data.slice(n_unit, self.data.len())
795 fn shr_bits(&self, n_bits: uint) -> BigUint {
796 if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
799 let mut shifted_rev = Vec::with_capacity(self.data.len());
800 for elem in self.data.iter().rev() {
801 shifted_rev.push((*elem >> n_bits) | borrow);
802 borrow = *elem << (BigDigit::bits - n_bits);
804 let shifted = { shifted_rev.reverse(); shifted_rev };
805 return BigUint::new(shifted);
808 /// Determines the fewest bits necessary to express the `BigUint`.
809 pub fn bits(&self) -> uint {
810 if self.is_zero() { return 0; }
811 let zeros = self.data.last().unwrap().leading_zeros();
812 return self.data.len()*BigDigit::bits - zeros;
816 // `DoubleBigDigit` size dependent
818 fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
820 2 => (4294967296, 32),
821 3 => (3486784401, 20),
822 4 => (4294967296, 16),
823 5 => (1220703125, 13),
824 6 => (2176782336, 12),
825 7 => (1977326743, 11),
826 8 => (1073741824, 10),
827 9 => (3486784401, 10),
828 10 => (1000000000, 9),
829 11 => (2357947691, 9),
830 12 => (429981696, 8),
831 13 => (815730721, 8),
832 14 => (1475789056, 8),
833 15 => (2562890625, 8),
834 16 => (4294967296, 8),
835 _ => fail!("The radix must be within (1, 16]")
839 /// A Sign is a `BigInt`'s composing element.
840 #[deriving(PartialEq, PartialOrd, Eq, Ord, Clone, Show)]
841 pub enum Sign { Minus, NoSign, Plus }
843 impl Neg<Sign> for Sign {
844 /// Negate Sign value.
846 fn neg(&self) -> Sign {
855 /// A big signed integer type.
862 impl PartialEq for BigInt {
864 fn eq(&self, other: &BigInt) -> bool {
865 self.cmp(other) == Equal
869 impl Eq for BigInt {}
871 impl PartialOrd for BigInt {
873 fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
874 Some(self.cmp(other))
878 impl Ord for BigInt {
880 fn cmp(&self, other: &BigInt) -> Ordering {
881 let scmp = self.sign.cmp(&other.sign);
882 if scmp != Equal { return scmp; }
886 Plus => self.data.cmp(&other.data),
887 Minus => other.data.cmp(&self.data),
892 impl Default for BigInt {
894 fn default() -> BigInt { Zero::zero() }
897 impl fmt::Show for BigInt {
898 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
899 write!(f, "{}", self.to_str_radix(10))
903 impl<S: hash::Writer> hash::Hash<S> for BigInt {
904 fn hash(&self, state: &mut S) {
905 (self.sign == Plus).hash(state);
906 self.data.hash(state);
910 impl FromStr for BigInt {
912 fn from_str(s: &str) -> Option<BigInt> {
913 FromStrRadix::from_str_radix(s, 10)
917 impl Num for BigInt {}
919 impl Shl<uint, BigInt> for BigInt {
921 fn shl(&self, rhs: &uint) -> BigInt {
922 BigInt::from_biguint(self.sign, self.data << *rhs)
926 impl Shr<uint, BigInt> for BigInt {
928 fn shr(&self, rhs: &uint) -> BigInt {
929 BigInt::from_biguint(self.sign, self.data >> *rhs)
933 impl Zero for BigInt {
935 fn zero() -> BigInt {
936 BigInt::from_biguint(NoSign, Zero::zero())
940 fn is_zero(&self) -> bool { self.sign == NoSign }
943 impl One for BigInt {
946 BigInt::from_biguint(Plus, One::one())
950 impl Signed for BigInt {
952 fn abs(&self) -> BigInt {
954 Plus | NoSign => self.clone(),
955 Minus => BigInt::from_biguint(Plus, self.data.clone())
960 fn abs_sub(&self, other: &BigInt) -> BigInt {
961 if *self <= *other { Zero::zero() } else { *self - *other }
965 fn signum(&self) -> BigInt {
967 Plus => BigInt::from_biguint(Plus, One::one()),
968 Minus => BigInt::from_biguint(Minus, One::one()),
969 NoSign => Zero::zero(),
974 fn is_positive(&self) -> bool { self.sign == Plus }
977 fn is_negative(&self) -> bool { self.sign == Minus }
980 impl Add<BigInt, BigInt> for BigInt {
982 fn add(&self, other: &BigInt) -> BigInt {
983 match (self.sign, other.sign) {
984 (NoSign, _) => other.clone(),
985 (_, NoSign) => self.clone(),
986 (Plus, Plus) => BigInt::from_biguint(Plus, self.data + other.data),
987 (Plus, Minus) => self - (-*other),
988 (Minus, Plus) => other - (-*self),
989 (Minus, Minus) => -((-self) + (-*other))
994 impl Sub<BigInt, BigInt> for BigInt {
996 fn sub(&self, other: &BigInt) -> BigInt {
997 match (self.sign, other.sign) {
998 (NoSign, _) => -other,
999 (_, NoSign) => self.clone(),
1000 (Plus, Plus) => match self.data.cmp(&other.data) {
1001 Less => BigInt::from_biguint(Minus, other.data - self.data),
1002 Greater => BigInt::from_biguint(Plus, self.data - other.data),
1003 Equal => Zero::zero()
1005 (Plus, Minus) => self + (-*other),
1006 (Minus, Plus) => -((-self) + *other),
1007 (Minus, Minus) => (-other) - (-*self)
1012 impl Mul<BigInt, BigInt> for BigInt {
1014 fn mul(&self, other: &BigInt) -> BigInt {
1015 match (self.sign, other.sign) {
1016 (NoSign, _) | (_, NoSign) => Zero::zero(),
1017 (Plus, Plus) | (Minus, Minus) => {
1018 BigInt::from_biguint(Plus, self.data * other.data)
1020 (Plus, Minus) | (Minus, Plus) => {
1021 BigInt::from_biguint(Minus, self.data * other.data)
1027 impl Div<BigInt, BigInt> for BigInt {
1029 fn div(&self, other: &BigInt) -> BigInt {
1030 let (q, _) = self.div_rem(other);
1035 impl Rem<BigInt, BigInt> for BigInt {
1037 fn rem(&self, other: &BigInt) -> BigInt {
1038 let (_, r) = self.div_rem(other);
1043 impl Neg<BigInt> for BigInt {
1045 fn neg(&self) -> BigInt {
1046 BigInt::from_biguint(self.sign.neg(), self.data.clone())
1050 impl CheckedAdd for BigInt {
1052 fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
1053 return Some(self.add(v));
1057 impl CheckedSub for BigInt {
1059 fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
1060 return Some(self.sub(v));
1064 impl CheckedMul for BigInt {
1066 fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1067 return Some(self.mul(v));
1071 impl CheckedDiv for BigInt {
1073 fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1077 return Some(self.div(v));
1082 impl Integer for BigInt {
1084 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1085 // r.sign == self.sign
1086 let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1087 let d = BigInt::from_biguint(Plus, d_ui);
1088 let r = BigInt::from_biguint(Plus, r_ui);
1089 match (self.sign, other.sign) {
1090 (_, NoSign) => fail!(),
1091 (Plus, Plus) | (NoSign, Plus) => ( d, r),
1092 (Plus, Minus) | (NoSign, Minus) => (-d, r),
1093 (Minus, Plus) => (-d, -r),
1094 (Minus, Minus) => ( d, -r)
1099 fn div_floor(&self, other: &BigInt) -> BigInt {
1100 let (d, _) = self.div_mod_floor(other);
1105 fn mod_floor(&self, other: &BigInt) -> BigInt {
1106 let (_, m) = self.div_mod_floor(other);
1110 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1111 // m.sign == other.sign
1112 let (d_ui, m_ui) = self.data.div_rem(&other.data);
1113 let d = BigInt::from_biguint(Plus, d_ui);
1114 let m = BigInt::from_biguint(Plus, m_ui);
1115 match (self.sign, other.sign) {
1116 (_, NoSign) => fail!(),
1117 (Plus, Plus) | (NoSign, Plus) => (d, m),
1118 (Plus, Minus) | (NoSign, Minus) => if m.is_zero() {
1121 (-d - One::one(), m + *other)
1123 (Minus, Plus) => if m.is_zero() {
1126 (-d - One::one(), other - m)
1128 (Minus, Minus) => (d, -m)
1132 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
1134 /// The result is always positive.
1136 fn gcd(&self, other: &BigInt) -> BigInt {
1137 BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1140 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
1142 fn lcm(&self, other: &BigInt) -> BigInt {
1143 BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1146 /// Deprecated, use `is_multiple_of` instead.
1147 #[deprecated = "function renamed to `is_multiple_of`"]
1149 fn divides(&self, other: &BigInt) -> bool { return self.is_multiple_of(other); }
1151 /// Returns `true` if the number is a multiple of `other`.
1153 fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
1155 /// Returns `true` if the number is divisible by `2`.
1157 fn is_even(&self) -> bool { self.data.is_even() }
1159 /// Returns `true` if the number is not divisible by `2`.
1161 fn is_odd(&self) -> bool { self.data.is_odd() }
1164 impl ToPrimitive for BigInt {
1166 fn to_i64(&self) -> Option<i64> {
1168 Plus => self.data.to_i64(),
1171 self.data.to_u64().and_then(|n| {
1172 let m: u64 = 1 << 63;
1186 fn to_u64(&self) -> Option<u64> {
1188 Plus => self.data.to_u64(),
1195 impl FromPrimitive for BigInt {
1197 fn from_i64(n: i64) -> Option<BigInt> {
1199 FromPrimitive::from_u64(n as u64).and_then(|n| {
1200 Some(BigInt::from_biguint(Plus, n))
1203 FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1205 Some(BigInt::from_biguint(Minus, n))
1213 fn from_u64(n: u64) -> Option<BigInt> {
1217 FromPrimitive::from_u64(n).and_then(|n| {
1218 Some(BigInt::from_biguint(Plus, n))
1224 /// A generic trait for converting a value to a `BigInt`.
1225 pub trait ToBigInt {
1226 /// Converts the value of `self` to a `BigInt`.
1227 fn to_bigint(&self) -> Option<BigInt>;
1230 impl ToBigInt for BigInt {
1232 fn to_bigint(&self) -> Option<BigInt> {
1237 impl ToBigInt for BigUint {
1239 fn to_bigint(&self) -> Option<BigInt> {
1243 Some(BigInt { sign: Plus, data: self.clone() })
1248 macro_rules! impl_to_bigint(
1249 ($T:ty, $from_ty:path) => {
1250 impl ToBigInt for $T {
1252 fn to_bigint(&self) -> Option<BigInt> {
1259 impl_to_bigint!(int, FromPrimitive::from_int)
1260 impl_to_bigint!(i8, FromPrimitive::from_i8)
1261 impl_to_bigint!(i16, FromPrimitive::from_i16)
1262 impl_to_bigint!(i32, FromPrimitive::from_i32)
1263 impl_to_bigint!(i64, FromPrimitive::from_i64)
1264 impl_to_bigint!(uint, FromPrimitive::from_uint)
1265 impl_to_bigint!(u8, FromPrimitive::from_u8)
1266 impl_to_bigint!(u16, FromPrimitive::from_u16)
1267 impl_to_bigint!(u32, FromPrimitive::from_u32)
1268 impl_to_bigint!(u64, FromPrimitive::from_u64)
1270 impl ToStrRadix for BigInt {
1272 fn to_str_radix(&self, radix: uint) -> String {
1274 Plus => self.data.to_str_radix(radix),
1275 NoSign => "0".to_string(),
1276 Minus => format!("-{}", self.data.to_str_radix(radix)),
1281 impl FromStrRadix for BigInt {
1282 /// Creates and initializes a BigInt.
1284 fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1285 BigInt::parse_bytes(s.as_bytes(), radix)
1289 pub trait RandBigInt {
1290 /// Generate a random `BigUint` of the given bit size.
1291 fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1293 /// Generate a random BigInt of the given bit size.
1294 fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1296 /// Generate a random `BigUint` less than the given bound. Fails
1297 /// when the bound is zero.
1298 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1300 /// Generate a random `BigUint` within the given range. The lower
1301 /// bound is inclusive; the upper bound is exclusive. Fails when
1302 /// the upper bound is not greater than the lower bound.
1303 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1305 /// Generate a random `BigInt` within the given range. The lower
1306 /// bound is inclusive; the upper bound is exclusive. Fails when
1307 /// the upper bound is not greater than the lower bound.
1308 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1311 impl<R: Rng> RandBigInt for R {
1312 fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1313 let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1314 let mut data = Vec::with_capacity(digits+1);
1315 for _ in range(0, digits) {
1316 data.push(self.gen());
1319 let final_digit: BigDigit = self.gen();
1320 data.push(final_digit >> (BigDigit::bits - rem));
1325 fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1326 // Generate a random BigUint...
1327 let biguint = self.gen_biguint(bit_size);
1328 // ...and then randomly assign it a Sign...
1329 let sign = if biguint.is_zero() {
1330 // ...except that if the BigUint is zero, we need to try
1331 // again with probability 0.5. This is because otherwise,
1332 // the probability of generating a zero BigInt would be
1333 // double that of any other number.
1335 return self.gen_bigint(bit_size);
1339 } else if self.gen() {
1344 BigInt::from_biguint(sign, biguint)
1347 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1348 assert!(!bound.is_zero());
1349 let bits = bound.bits();
1351 let n = self.gen_biguint(bits);
1352 if n < *bound { return n; }
1356 fn gen_biguint_range(&mut self,
1360 assert!(*lbound < *ubound);
1361 return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1364 fn gen_bigint_range(&mut self,
1368 assert!(*lbound < *ubound);
1369 let delta = (*ubound - *lbound).to_biguint().unwrap();
1370 return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1375 /// Creates and initializes a BigInt.
1377 /// The digits are be in base 2^32.
1379 pub fn new(sign: Sign, digits: Vec<BigDigit>) -> BigInt {
1380 BigInt::from_biguint(sign, BigUint::new(digits))
1383 /// Creates and initializes a `BigInt`.
1385 /// The digits are be in base 2^32.
1387 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1388 if sign == NoSign || data.is_zero() {
1389 return BigInt { sign: NoSign, data: Zero::zero() };
1391 BigInt { sign: sign, data: data }
1394 /// Creates and initializes a `BigInt`.
1396 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1397 BigInt::from_biguint(sign, BigUint::from_slice(slice))
1400 /// Creates and initializes a `BigInt`.
1401 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigInt> {
1402 if buf.is_empty() { return None; }
1403 let mut sign = Plus;
1409 return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1410 .map(|bu| BigInt::from_biguint(sign, bu));
1413 /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1415 pub fn to_biguint(&self) -> Option<BigUint> {
1417 Plus => Some(self.data.clone()),
1418 NoSign => Some(Zero::zero()),
1427 use super::{BigDigit, BigUint, ToBigUint};
1428 use super::{Plus, BigInt, RandBigInt, ToBigInt};
1430 use std::cmp::{Less, Equal, Greater};
1431 use std::from_str::FromStr;
1433 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1434 use std::num::{ToPrimitive, FromPrimitive};
1435 use std::num::CheckedDiv;
1436 use std::rand::task_rng;
1438 use std::hash::hash;
1441 fn test_from_slice() {
1442 fn check(slice: &[BigDigit], data: &[BigDigit]) {
1443 assert!(data == BigUint::from_slice(slice).data.as_slice());
1446 check([0, 0, 0], []);
1447 check([1, 2, 0, 0], [1, 2]);
1448 check([0, 0, 1, 2], [0, 0, 1, 2]);
1449 check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1455 let data: [&[_], ..7] = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ];
1456 let data: Vec<BigUint> = data.iter().map(|v| BigUint::from_slice(*v)).collect();
1457 for (i, ni) in data.iter().enumerate() {
1458 for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1461 assert_eq!(ni.cmp(nj), Equal);
1462 assert_eq!(nj.cmp(ni), Equal);
1464 assert!(!(ni != nj));
1467 assert!(!(ni < nj));
1468 assert!(!(ni > nj));
1470 assert_eq!(ni.cmp(nj), Less);
1471 assert_eq!(nj.cmp(ni), Greater);
1473 assert!(!(ni == nj));
1477 assert!(!(ni >= nj));
1479 assert!(!(ni > nj));
1481 assert!(!(nj <= ni));
1483 assert!(!(nj < ni));
1492 let a = BigUint::new(vec!());
1493 let b = BigUint::new(vec!(0));
1494 let c = BigUint::new(vec!(1));
1495 let d = BigUint::new(vec!(1,0,0,0,0,0));
1496 let e = BigUint::new(vec!(0,0,0,0,0,1));
1497 assert!(hash(&a) == hash(&b));
1498 assert!(hash(&b) != hash(&c));
1499 assert!(hash(&c) == hash(&d));
1500 assert!(hash(&d) != hash(&e));
1505 fn check(left: &[BigDigit],
1507 expected: &[BigDigit]) {
1508 assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1509 BigUint::from_slice(expected));
1512 check([268, 482, 17],
1519 fn check(left: &[BigDigit],
1521 expected: &[BigDigit]) {
1522 assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1523 BigUint::from_slice(expected));
1526 check([268, 482, 17],
1533 fn check(left: &[BigDigit],
1535 expected: &[BigDigit]) {
1536 assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1537 BigUint::from_slice(expected));
1540 check([268, 482, 17],
1547 fn check(s: &str, shift: uint, ans: &str) {
1548 let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1549 let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1550 assert_eq!(bu.as_slice(), ans);
1662 check("88887777666655554444333322221111", 16,
1663 "888877776666555544443333222211110000");
1668 fn check(s: &str, shift: uint, ans: &str) {
1669 let opt_biguint: Option<BigUint> =
1670 FromStrRadix::from_str_radix(s, 16);
1671 let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1672 assert_eq!(bu.as_slice(), ans);
1780 check("888877776666555544443333222211110000", 16,
1781 "88887777666655554444333322221111");
1784 // `DoubleBigDigit` size dependent
1786 fn test_convert_i64() {
1787 fn check(b1: BigUint, i: i64) {
1788 let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1790 assert!(b1.to_i64().unwrap() == i);
1793 check(Zero::zero(), 0);
1794 check(One::one(), 1);
1795 check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1797 check(BigUint::new(vec!( )), 0);
1798 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1799 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1800 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1801 check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1803 assert_eq!(i64::MIN.to_biguint(), None);
1804 assert_eq!(BigUint::new(vec!(-1, -1 )).to_i64(), None);
1805 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_i64(), None);
1806 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1809 // `DoubleBigDigit` size dependent
1811 fn test_convert_u64() {
1812 fn check(b1: BigUint, u: u64) {
1813 let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1815 assert!(b1.to_u64().unwrap() == u);
1818 check(Zero::zero(), 0);
1819 check(One::one(), 1);
1820 check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1821 check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1823 check(BigUint::new(vec!( )), 0);
1824 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1825 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1826 check(BigUint::new(vec!( 0, 1)), (1 << (1*BigDigit::bits)));
1827 check(BigUint::new(vec!(-1, -1)), u64::MAX);
1829 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_u64(), None);
1830 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1834 fn test_convert_to_bigint() {
1835 fn check(n: BigUint, ans: BigInt) {
1836 assert_eq!(n.to_bigint().unwrap(), ans);
1837 assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1839 check(Zero::zero(), Zero::zero());
1840 check(BigUint::new(vec!(1,2,3)),
1841 BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1844 static sum_triples: &'static [(&'static [BigDigit],
1845 &'static [BigDigit],
1846 &'static [BigDigit])] = &[
1848 (&[], &[ 1], &[ 1]),
1849 (&[ 1], &[ 1], &[ 2]),
1850 (&[ 1], &[ 1, 1], &[ 2, 1]),
1851 (&[ 1], &[-1], &[ 0, 1]),
1852 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1853 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1854 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1855 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1860 for elm in sum_triples.iter() {
1861 let (a_vec, b_vec, c_vec) = *elm;
1862 let a = BigUint::from_slice(a_vec);
1863 let b = BigUint::from_slice(b_vec);
1864 let c = BigUint::from_slice(c_vec);
1866 assert!(a + b == c);
1867 assert!(b + a == c);
1873 for elm in sum_triples.iter() {
1874 let (a_vec, b_vec, c_vec) = *elm;
1875 let a = BigUint::from_slice(a_vec);
1876 let b = BigUint::from_slice(b_vec);
1877 let c = BigUint::from_slice(c_vec);
1879 assert!(c - a == b);
1880 assert!(c - b == a);
1886 fn test_sub_fail_on_underflow() {
1887 let (a, b) : (BigUint, BigUint) = (Zero::zero(), One::one());
1891 static mul_triples: &'static [(&'static [BigDigit],
1892 &'static [BigDigit],
1893 &'static [BigDigit])] = &[
1897 (&[ 1], &[ 1], &[1]),
1898 (&[ 2], &[ 3], &[ 6]),
1899 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1900 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1901 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1902 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1903 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1904 (&[-1], &[-1], &[ 1, -2]),
1905 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1906 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1907 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1908 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1909 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1910 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1911 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1912 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1913 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1914 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1917 static div_rem_quadruples: &'static [(&'static [BigDigit],
1918 &'static [BigDigit],
1919 &'static [BigDigit],
1920 &'static [BigDigit])]
1922 (&[ 1], &[ 2], &[], &[1]),
1923 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1924 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1925 (&[ 0, 1], &[-1], &[1], &[1]),
1926 (&[-1, -1], &[-2], &[2, 1], &[3])
1931 for elm in mul_triples.iter() {
1932 let (a_vec, b_vec, c_vec) = *elm;
1933 let a = BigUint::from_slice(a_vec);
1934 let b = BigUint::from_slice(b_vec);
1935 let c = BigUint::from_slice(c_vec);
1937 assert!(a * b == c);
1938 assert!(b * a == c);
1941 for elm in div_rem_quadruples.iter() {
1942 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1943 let a = BigUint::from_slice(a_vec);
1944 let b = BigUint::from_slice(b_vec);
1945 let c = BigUint::from_slice(c_vec);
1946 let d = BigUint::from_slice(d_vec);
1948 assert!(a == b * c + d);
1949 assert!(a == c * b + d);
1955 for elm in mul_triples.iter() {
1956 let (a_vec, b_vec, c_vec) = *elm;
1957 let a = BigUint::from_slice(a_vec);
1958 let b = BigUint::from_slice(b_vec);
1959 let c = BigUint::from_slice(c_vec);
1962 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1965 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1969 for elm in div_rem_quadruples.iter() {
1970 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1971 let a = BigUint::from_slice(a_vec);
1972 let b = BigUint::from_slice(b_vec);
1973 let c = BigUint::from_slice(c_vec);
1974 let d = BigUint::from_slice(d_vec);
1976 if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1981 fn test_checked_add() {
1982 for elm in sum_triples.iter() {
1983 let (a_vec, b_vec, c_vec) = *elm;
1984 let a = BigUint::from_slice(a_vec);
1985 let b = BigUint::from_slice(b_vec);
1986 let c = BigUint::from_slice(c_vec);
1988 assert!(a.checked_add(&b).unwrap() == c);
1989 assert!(b.checked_add(&a).unwrap() == c);
1994 fn test_checked_sub() {
1995 for elm in sum_triples.iter() {
1996 let (a_vec, b_vec, c_vec) = *elm;
1997 let a = BigUint::from_slice(a_vec);
1998 let b = BigUint::from_slice(b_vec);
1999 let c = BigUint::from_slice(c_vec);
2001 assert!(c.checked_sub(&a).unwrap() == b);
2002 assert!(c.checked_sub(&b).unwrap() == a);
2005 assert!(a.checked_sub(&c).is_none());
2008 assert!(b.checked_sub(&c).is_none());
2014 fn test_checked_mul() {
2015 for elm in mul_triples.iter() {
2016 let (a_vec, b_vec, c_vec) = *elm;
2017 let a = BigUint::from_slice(a_vec);
2018 let b = BigUint::from_slice(b_vec);
2019 let c = BigUint::from_slice(c_vec);
2021 assert!(a.checked_mul(&b).unwrap() == c);
2022 assert!(b.checked_mul(&a).unwrap() == c);
2025 for elm in div_rem_quadruples.iter() {
2026 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2027 let a = BigUint::from_slice(a_vec);
2028 let b = BigUint::from_slice(b_vec);
2029 let c = BigUint::from_slice(c_vec);
2030 let d = BigUint::from_slice(d_vec);
2032 assert!(a == b.checked_mul(&c).unwrap() + d);
2033 assert!(a == c.checked_mul(&b).unwrap() + d);
2038 fn test_checked_div() {
2039 for elm in mul_triples.iter() {
2040 let (a_vec, b_vec, c_vec) = *elm;
2041 let a = BigUint::from_slice(a_vec);
2042 let b = BigUint::from_slice(b_vec);
2043 let c = BigUint::from_slice(c_vec);
2046 assert!(c.checked_div(&a).unwrap() == b);
2049 assert!(c.checked_div(&b).unwrap() == a);
2052 assert!(c.checked_div(&Zero::zero()).is_none());
2058 fn check(a: uint, b: uint, c: uint) {
2059 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2060 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2061 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2063 assert_eq!(big_a.gcd(&big_b), big_c);
2075 fn check(a: uint, b: uint, c: uint) {
2076 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2077 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2078 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2080 assert_eq!(big_a.lcm(&big_b), big_c);
2088 check(99, 17, 1683);
2093 let one: BigUint = FromStr::from_str("1").unwrap();
2094 let two: BigUint = FromStr::from_str("2").unwrap();
2095 let thousand: BigUint = FromStr::from_str("1000").unwrap();
2096 let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
2097 let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
2098 assert!(one.is_odd());
2099 assert!(two.is_even());
2100 assert!(thousand.is_even());
2101 assert!(big.is_even());
2102 assert!(bigger.is_odd());
2103 assert!((one << 64).is_even());
2104 assert!(((one << 64) + one).is_odd());
2107 fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, String)>)> {
2108 let bits = BigDigit::bits;
2109 vec!(( Zero::zero(), vec!(
2110 (2, "0".to_string()), (3, "0".to_string())
2111 )), ( BigUint::from_slice([ 0xff ]), vec!(
2112 (2, "11111111".to_string()),
2113 (3, "100110".to_string()),
2114 (4, "3333".to_string()),
2115 (5, "2010".to_string()),
2116 (6, "1103".to_string()),
2117 (7, "513".to_string()),
2118 (8, "377".to_string()),
2119 (9, "313".to_string()),
2120 (10, "255".to_string()),
2121 (11, "212".to_string()),
2122 (12, "193".to_string()),
2123 (13, "168".to_string()),
2124 (14, "143".to_string()),
2125 (15, "120".to_string()),
2126 (16, "ff".to_string())
2127 )), ( BigUint::from_slice([ 0xfff ]), vec!(
2128 (2, "111111111111".to_string()),
2129 (4, "333333".to_string()),
2130 (16, "fff".to_string())
2131 )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2133 format!("10{}1", "0".repeat(bits - 1))),
2135 format!("2{}1", "0".repeat(bits / 2 - 1))),
2137 32 => "8589934593".to_string(),
2138 16 => "131073".to_string(),
2142 format!("2{}1", "0".repeat(bits / 4 - 1)))
2143 )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2145 format!("11{}10{}1",
2146 "0".repeat(bits - 2),
2147 "0".repeat(bits - 1))),
2150 "0".repeat(bits / 2 - 1),
2151 "0".repeat(bits / 2 - 1))),
2153 32 => "55340232229718589441".to_string(),
2154 16 => "12885032961".to_string(),
2159 "0".repeat(bits / 4 - 1),
2160 "0".repeat(bits / 4 - 1)))
2165 fn test_to_str_radix() {
2166 let r = to_str_pairs();
2167 for num_pair in r.iter() {
2168 let &(ref n, ref rs) = num_pair;
2169 for str_pair in rs.iter() {
2170 let &(ref radix, ref str) = str_pair;
2171 assert_eq!(n.to_str_radix(*radix).as_slice(),
2178 fn test_from_str_radix() {
2179 let r = to_str_pairs();
2180 for num_pair in r.iter() {
2181 let &(ref n, ref rs) = num_pair;
2182 for str_pair in rs.iter() {
2183 let &(ref radix, ref str) = str_pair;
2185 &FromStrRadix::from_str_radix(str.as_slice(),
2190 let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2191 assert_eq!(zed, None);
2192 let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2193 assert_eq!(blank, None);
2194 let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2196 assert_eq!(minus_one, None);
2201 fn factor(n: uint) -> BigUint {
2202 let mut f: BigUint = One::one();
2203 for i in range(2, n + 1) {
2204 // FIXME(#5992): assignment operator overloads
2205 // f *= FromPrimitive::from_uint(i);
2206 f = f * FromPrimitive::from_uint(i).unwrap();
2211 fn check(n: uint, s: &str) {
2213 let ans = match FromStrRadix::from_str_radix(s, 10) {
2214 Some(x) => x, None => fail!()
2220 check(10, "3628800");
2221 check(20, "2432902008176640000");
2222 check(30, "265252859812191058636308480000000");
2227 assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2228 let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2229 assert_eq!(n.bits(), 0);
2230 let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2231 assert_eq!(n.bits(), 1);
2232 let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2233 assert_eq!(n.bits(), 2);
2234 let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2235 assert_eq!(n.bits(), 39);
2236 let one: BigUint = One::one();
2237 assert_eq!((one << 426).bits(), 427);
2242 let mut rng = task_rng();
2243 let _n: BigUint = rng.gen_biguint(137);
2244 assert!(rng.gen_biguint(0).is_zero());
2248 fn test_rand_range() {
2249 let mut rng = task_rng();
2251 for _ in range(0u, 10) {
2252 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2253 &FromPrimitive::from_uint(237).unwrap()),
2254 FromPrimitive::from_uint(236).unwrap());
2257 let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2258 let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2259 for _ in range(0u, 1000) {
2260 let n: BigUint = rng.gen_biguint_below(&u);
2263 let n: BigUint = rng.gen_biguint_range(&l, &u);
2271 fn test_zero_rand_range() {
2272 task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2273 &FromPrimitive::from_uint(54).unwrap());
2278 fn test_negative_rand_range() {
2279 let mut rng = task_rng();
2280 let l = FromPrimitive::from_uint(2352).unwrap();
2281 let u = FromPrimitive::from_uint(3513).unwrap();
2282 // Switching u and l should fail:
2283 let _n: BigUint = rng.gen_biguint_range(&u, &l);
2290 use super::{BigDigit, BigUint, ToBigUint};
2291 use super::{Sign, Minus, NoSign, Plus, BigInt, RandBigInt, ToBigInt};
2293 use std::cmp::{Less, Equal, Greater};
2295 use std::num::CheckedDiv;
2296 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2297 use std::num::{ToPrimitive, FromPrimitive};
2298 use std::rand::task_rng;
2300 use std::hash::hash;
2303 fn test_from_biguint() {
2304 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2305 let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2306 let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2307 assert_eq!(inp, ans);
2309 check(Plus, 1, Plus, 1);
2310 check(Plus, 0, NoSign, 0);
2311 check(Minus, 1, Minus, 1);
2312 check(NoSign, 1, NoSign, 0);
2317 let vs: [&[BigDigit], ..4] = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2318 let mut nums = Vec::new();
2319 for s in vs.iter().rev() {
2320 nums.push(BigInt::from_slice(Minus, *s));
2322 nums.push(Zero::zero());
2323 nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2325 for (i, ni) in nums.iter().enumerate() {
2326 for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2329 assert_eq!(ni.cmp(nj), Equal);
2330 assert_eq!(nj.cmp(ni), Equal);
2332 assert!(!(ni != nj));
2335 assert!(!(ni < nj));
2336 assert!(!(ni > nj));
2338 assert_eq!(ni.cmp(nj), Less);
2339 assert_eq!(nj.cmp(ni), Greater);
2341 assert!(!(ni == nj));
2345 assert!(!(ni >= nj));
2347 assert!(!(ni > nj));
2349 assert!(!(nj <= ni));
2351 assert!(!(nj < ni));
2360 let a = BigInt::new(NoSign, vec!());
2361 let b = BigInt::new(NoSign, vec!(0));
2362 let c = BigInt::new(Plus, vec!(1));
2363 let d = BigInt::new(Plus, vec!(1,0,0,0,0,0));
2364 let e = BigInt::new(Plus, vec!(0,0,0,0,0,1));
2365 let f = BigInt::new(Minus, vec!(1));
2366 assert!(hash(&a) == hash(&b));
2367 assert!(hash(&b) != hash(&c));
2368 assert!(hash(&c) == hash(&d));
2369 assert!(hash(&d) != hash(&e));
2370 assert!(hash(&c) != hash(&f));
2374 fn test_convert_i64() {
2375 fn check(b1: BigInt, i: i64) {
2376 let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2378 assert!(b1.to_i64().unwrap() == i);
2381 check(Zero::zero(), 0);
2382 check(One::one(), 1);
2383 check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2384 check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2387 (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2391 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2395 BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2399 BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2404 fn test_convert_u64() {
2405 fn check(b1: BigInt, u: u64) {
2406 let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2408 assert!(b1.to_u64().unwrap() == u);
2411 check(Zero::zero(), 0);
2412 check(One::one(), 1);
2413 check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2414 check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2417 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2420 let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2421 assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2422 assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2426 fn test_convert_to_biguint() {
2427 fn check(n: BigInt, ans_1: BigUint) {
2428 assert_eq!(n.to_biguint().unwrap(), ans_1);
2429 assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2431 let zero: BigInt = Zero::zero();
2432 let unsigned_zero: BigUint = Zero::zero();
2433 let positive = BigInt::from_biguint(
2434 Plus, BigUint::new(vec!(1,2,3)));
2435 let negative = -positive;
2437 check(zero, unsigned_zero);
2438 check(positive, BigUint::new(vec!(1,2,3)));
2440 assert_eq!(negative.to_biguint(), None);
2443 static sum_triples: &'static [(&'static [BigDigit],
2444 &'static [BigDigit],
2445 &'static [BigDigit])] = &[
2447 (&[], &[ 1], &[ 1]),
2448 (&[ 1], &[ 1], &[ 2]),
2449 (&[ 1], &[ 1, 1], &[ 2, 1]),
2450 (&[ 1], &[-1], &[ 0, 1]),
2451 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
2452 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
2453 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
2454 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
2459 for elm in sum_triples.iter() {
2460 let (a_vec, b_vec, c_vec) = *elm;
2461 let a = BigInt::from_slice(Plus, a_vec);
2462 let b = BigInt::from_slice(Plus, b_vec);
2463 let c = BigInt::from_slice(Plus, c_vec);
2465 assert!(a + b == c);
2466 assert!(b + a == c);
2467 assert!(c + (-a) == b);
2468 assert!(c + (-b) == a);
2469 assert!(a + (-c) == (-b));
2470 assert!(b + (-c) == (-a));
2471 assert!((-a) + (-b) == (-c))
2472 assert!(a + (-a) == Zero::zero());
2478 for elm in sum_triples.iter() {
2479 let (a_vec, b_vec, c_vec) = *elm;
2480 let a = BigInt::from_slice(Plus, a_vec);
2481 let b = BigInt::from_slice(Plus, b_vec);
2482 let c = BigInt::from_slice(Plus, c_vec);
2484 assert!(c - a == b);
2485 assert!(c - b == a);
2486 assert!((-b) - a == (-c))
2487 assert!((-a) - b == (-c))
2488 assert!(b - (-a) == c);
2489 assert!(a - (-b) == c);
2490 assert!((-c) - (-a) == (-b));
2491 assert!(a - a == Zero::zero());
2495 static mul_triples: &'static [(&'static [BigDigit],
2496 &'static [BigDigit],
2497 &'static [BigDigit])] = &[
2501 (&[ 1], &[ 1], &[1]),
2502 (&[ 2], &[ 3], &[ 6]),
2503 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
2504 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
2505 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
2506 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
2507 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
2508 (&[-1], &[-1], &[ 1, -2]),
2509 (&[-1, -1], &[-1], &[ 1, -1, -2]),
2510 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
2511 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
2512 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
2513 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
2514 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
2515 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
2516 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
2517 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
2518 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
2521 static div_rem_quadruples: &'static [(&'static [BigDigit],
2522 &'static [BigDigit],
2523 &'static [BigDigit],
2524 &'static [BigDigit])]
2526 (&[ 1], &[ 2], &[], &[1]),
2527 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
2528 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2529 (&[ 0, 1], &[-1], &[1], &[1]),
2530 (&[-1, -1], &[-2], &[2, 1], &[3])
2535 for elm in mul_triples.iter() {
2536 let (a_vec, b_vec, c_vec) = *elm;
2537 let a = BigInt::from_slice(Plus, a_vec);
2538 let b = BigInt::from_slice(Plus, b_vec);
2539 let c = BigInt::from_slice(Plus, c_vec);
2541 assert!(a * b == c);
2542 assert!(b * a == c);
2544 assert!((-a) * b == -c);
2545 assert!((-b) * a == -c);
2548 for elm in div_rem_quadruples.iter() {
2549 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2550 let a = BigInt::from_slice(Plus, a_vec);
2551 let b = BigInt::from_slice(Plus, b_vec);
2552 let c = BigInt::from_slice(Plus, c_vec);
2553 let d = BigInt::from_slice(Plus, d_vec);
2555 assert!(a == b * c + d);
2556 assert!(a == c * b + d);
2561 fn test_div_mod_floor() {
2562 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2563 let (d, m) = a.div_mod_floor(b);
2565 assert_eq!(m.sign, b.sign);
2567 assert!(m.abs() <= b.abs());
2568 assert!(*a == b * d + m);
2569 assert!(d == *ans_d);
2570 assert!(m == *ans_m);
2573 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2575 check_sub(a, b, d, m);
2576 check_sub(a, &b.neg(), &d.neg(), m);
2577 check_sub(&a.neg(), b, &d.neg(), m);
2578 check_sub(&a.neg(), &b.neg(), d, m);
2580 check_sub(a, b, d, m);
2581 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2582 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2583 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2587 for elm in mul_triples.iter() {
2588 let (a_vec, b_vec, c_vec) = *elm;
2589 let a = BigInt::from_slice(Plus, a_vec);
2590 let b = BigInt::from_slice(Plus, b_vec);
2591 let c = BigInt::from_slice(Plus, c_vec);
2593 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2594 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2597 for elm in div_rem_quadruples.iter() {
2598 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2599 let a = BigInt::from_slice(Plus, a_vec);
2600 let b = BigInt::from_slice(Plus, b_vec);
2601 let c = BigInt::from_slice(Plus, c_vec);
2602 let d = BigInt::from_slice(Plus, d_vec);
2605 check(&a, &b, &c, &d);
2613 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2614 let (q, r) = a.div_rem(b);
2616 assert_eq!(r.sign, a.sign);
2618 assert!(r.abs() <= b.abs());
2619 assert!(*a == b * q + r);
2620 assert!(q == *ans_q);
2621 assert!(r == *ans_r);
2624 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2625 check_sub(a, b, q, r);
2626 check_sub(a, &b.neg(), &q.neg(), r);
2627 check_sub(&a.neg(), b, &q.neg(), &r.neg());
2628 check_sub(&a.neg(), &b.neg(), q, &r.neg());
2630 for elm in mul_triples.iter() {
2631 let (a_vec, b_vec, c_vec) = *elm;
2632 let a = BigInt::from_slice(Plus, a_vec);
2633 let b = BigInt::from_slice(Plus, b_vec);
2634 let c = BigInt::from_slice(Plus, c_vec);
2636 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2637 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2640 for elm in div_rem_quadruples.iter() {
2641 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2642 let a = BigInt::from_slice(Plus, a_vec);
2643 let b = BigInt::from_slice(Plus, b_vec);
2644 let c = BigInt::from_slice(Plus, c_vec);
2645 let d = BigInt::from_slice(Plus, d_vec);
2648 check(&a, &b, &c, &d);
2654 fn test_checked_add() {
2655 for elm in sum_triples.iter() {
2656 let (a_vec, b_vec, c_vec) = *elm;
2657 let a = BigInt::from_slice(Plus, a_vec);
2658 let b = BigInt::from_slice(Plus, b_vec);
2659 let c = BigInt::from_slice(Plus, c_vec);
2661 assert!(a.checked_add(&b).unwrap() == c);
2662 assert!(b.checked_add(&a).unwrap() == c);
2663 assert!(c.checked_add(&(-a)).unwrap() == b);
2664 assert!(c.checked_add(&(-b)).unwrap() == a);
2665 assert!(a.checked_add(&(-c)).unwrap() == (-b));
2666 assert!(b.checked_add(&(-c)).unwrap() == (-a));
2667 assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2668 assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2673 fn test_checked_sub() {
2674 for elm in sum_triples.iter() {
2675 let (a_vec, b_vec, c_vec) = *elm;
2676 let a = BigInt::from_slice(Plus, a_vec);
2677 let b = BigInt::from_slice(Plus, b_vec);
2678 let c = BigInt::from_slice(Plus, c_vec);
2680 assert!(c.checked_sub(&a).unwrap() == b);
2681 assert!(c.checked_sub(&b).unwrap() == a);
2682 assert!((-b).checked_sub(&a).unwrap() == (-c))
2683 assert!((-a).checked_sub(&b).unwrap() == (-c))
2684 assert!(b.checked_sub(&(-a)).unwrap() == c);
2685 assert!(a.checked_sub(&(-b)).unwrap() == c);
2686 assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2687 assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2692 fn test_checked_mul() {
2693 for elm in mul_triples.iter() {
2694 let (a_vec, b_vec, c_vec) = *elm;
2695 let a = BigInt::from_slice(Plus, a_vec);
2696 let b = BigInt::from_slice(Plus, b_vec);
2697 let c = BigInt::from_slice(Plus, c_vec);
2699 assert!(a.checked_mul(&b).unwrap() == c);
2700 assert!(b.checked_mul(&a).unwrap() == c);
2702 assert!((-a).checked_mul(&b).unwrap() == -c);
2703 assert!((-b).checked_mul(&a).unwrap() == -c);
2706 for elm in div_rem_quadruples.iter() {
2707 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2708 let a = BigInt::from_slice(Plus, a_vec);
2709 let b = BigInt::from_slice(Plus, b_vec);
2710 let c = BigInt::from_slice(Plus, c_vec);
2711 let d = BigInt::from_slice(Plus, d_vec);
2713 assert!(a == b.checked_mul(&c).unwrap() + d);
2714 assert!(a == c.checked_mul(&b).unwrap() + d);
2718 fn test_checked_div() {
2719 for elm in mul_triples.iter() {
2720 let (a_vec, b_vec, c_vec) = *elm;
2721 let a = BigInt::from_slice(Plus, a_vec);
2722 let b = BigInt::from_slice(Plus, b_vec);
2723 let c = BigInt::from_slice(Plus, c_vec);
2726 assert!(c.checked_div(&a).unwrap() == b);
2727 assert!((-c).checked_div(&(-a)).unwrap() == b);
2728 assert!((-c).checked_div(&a).unwrap() == -b);
2731 assert!(c.checked_div(&b).unwrap() == a);
2732 assert!((-c).checked_div(&(-b)).unwrap() == a);
2733 assert!((-c).checked_div(&b).unwrap() == -a);
2736 assert!(c.checked_div(&Zero::zero()).is_none());
2737 assert!((-c).checked_div(&Zero::zero()).is_none());
2743 fn check(a: int, b: int, c: int) {
2744 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2745 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2746 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2748 assert_eq!(big_a.gcd(&big_b), big_c);
2763 fn check(a: int, b: int, c: int) {
2764 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2765 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2766 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2768 assert_eq!(big_a.lcm(&big_b), big_c);
2783 let zero: BigInt = Zero::zero();
2784 let one: BigInt = One::one();
2785 assert_eq!((-one).abs_sub(&one), zero);
2786 let one: BigInt = One::one();
2787 let zero: BigInt = Zero::zero();
2788 assert_eq!(one.abs_sub(&one), zero);
2789 let one: BigInt = One::one();
2790 let zero: BigInt = Zero::zero();
2791 assert_eq!(one.abs_sub(&zero), one);
2792 let one: BigInt = One::one();
2793 let two: BigInt = FromPrimitive::from_int(2).unwrap();
2794 assert_eq!(one.abs_sub(&-one), two);
2798 fn test_to_str_radix() {
2799 fn check(n: int, ans: &str) {
2800 let n: BigInt = FromPrimitive::from_int(n).unwrap();
2801 assert!(ans == n.to_str_radix(10).as_slice());
2812 fn test_from_str_radix() {
2813 fn check(s: &str, ans: Option<int>) {
2814 let ans = ans.map(|n| {
2815 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2818 assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2820 check("10", Some(10));
2821 check("1", Some(1));
2822 check("0", Some(0));
2823 check("-1", Some(-1));
2824 check("-10", Some(-10));
2828 // issue 10522, this hit an edge case that caused it to
2829 // attempt to allocate a vector of size (-1u) == huge.
2831 from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
2832 let _y = x.to_string();
2837 assert!(-BigInt::new(Plus, vec!(1, 1, 1)) ==
2838 BigInt::new(Minus, vec!(1, 1, 1)));
2839 assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2840 BigInt::new(Plus, vec!(1, 1, 1)));
2841 let zero: BigInt = Zero::zero();
2842 assert_eq!(-zero, zero);
2847 let mut rng = task_rng();
2848 let _n: BigInt = rng.gen_bigint(137);
2849 assert!(rng.gen_bigint(0).is_zero());
2853 fn test_rand_range() {
2854 let mut rng = task_rng();
2856 for _ in range(0u, 10) {
2857 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2858 &FromPrimitive::from_uint(237).unwrap()),
2859 FromPrimitive::from_uint(236).unwrap());
2862 fn check(l: BigInt, u: BigInt) {
2863 let mut rng = task_rng();
2864 for _ in range(0u, 1000) {
2865 let n: BigInt = rng.gen_bigint_range(&l, &u);
2870 let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2871 let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2872 check( l.clone(), u.clone());
2873 check(-l.clone(), u.clone());
2874 check(-u.clone(), -l.clone());
2879 fn test_zero_rand_range() {
2880 task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2881 &FromPrimitive::from_int(54).unwrap());
2886 fn test_negative_rand_range() {
2887 let mut rng = task_rng();
2888 let l = FromPrimitive::from_uint(2352).unwrap();
2889 let u = FromPrimitive::from_uint(3513).unwrap();
2890 // Switching u and l should fail:
2891 let _n: BigInt = rng.gen_bigint_range(&u, &l);
2898 use self::test::Bencher;
2901 use std::mem::replace;
2902 use std::num::{FromPrimitive, Zero, One};
2904 fn factorial(n: uint) -> BigUint {
2905 let mut f: BigUint = One::one();
2906 for i in iter::range_inclusive(1, n) {
2907 f = f * FromPrimitive::from_uint(i).unwrap();
2912 fn fib(n: uint) -> BigUint {
2913 let mut f0: BigUint = Zero::zero();
2914 let mut f1: BigUint = One::one();
2915 for _ in range(0, n) {
2917 f0 = replace(&mut f1, f2);
2923 fn factorial_100(b: &mut Bencher) {
2930 fn fib_100(b: &mut Bencher) {
2937 fn to_string(b: &mut Bencher) {
2938 let fac = factorial(100);
2949 fn shr(b: &mut Bencher) {
2950 let n = { let one : BigUint = One::one(); one << 1000 };
2952 let mut m = n.clone();
2953 for _ in range(0u, 10) {