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.
13 A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
15 A `BigUint` is represented as an array of `BigDigit`s.
16 A `BigInt` is a combination of `BigUint` and `Sign`.
23 use std::from_str::FromStr;
24 use std::num::CheckedDiv;
25 use std::num::{Bitwise, ToPrimitive, FromPrimitive};
26 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
28 use std::strbuf::StrBuf;
33 A `BigDigit` is a `BigUint`'s composing element.
35 A `BigDigit` is half the size of machine word size.
37 #[cfg(target_word_size = "32")]
38 pub type BigDigit = u16;
41 A `BigDigit` is a `BigUint`'s composing element.
43 A `BigDigit` is half the size of machine word size.
45 #[cfg(target_word_size = "64")]
46 pub type BigDigit = u32;
48 pub static ZERO_BIG_DIGIT: BigDigit = 0;
49 static ZERO_VEC: [BigDigit, ..1] = [ZERO_BIG_DIGIT];
54 #[cfg(target_word_size = "32")]
55 pub static bits: uint = 16;
57 #[cfg(target_word_size = "64")]
58 pub static bits: uint = 32;
60 pub static base: uint = 1 << bits;
61 static lo_mask: uint = (-1 as uint) >> bits;
64 fn get_hi(n: uint) -> BigDigit { (n >> bits) as BigDigit }
66 fn get_lo(n: uint) -> BigDigit { (n & lo_mask) as BigDigit }
68 /// Split one machine sized unsigned integer into two `BigDigit`s.
70 pub fn from_uint(n: uint) -> (BigDigit, BigDigit) {
71 (get_hi(n), get_lo(n))
74 /// Join two `BigDigit`s into one machine sized unsigned integer
76 pub fn to_uint(hi: BigDigit, lo: BigDigit) -> uint {
77 (lo as uint) | ((hi as uint) << bits)
82 A big unsigned integer type.
84 A `BigUint`-typed value `BigUint { data: ~[a, b, c] }` represents a number
85 `(a + b * BigDigit::base + c * BigDigit::base^2)`.
94 fn eq(&self, other: &BigUint) -> bool {
95 match self.cmp(other) { Equal => true, _ => false }
98 impl TotalEq for BigUint {}
100 impl Ord for BigUint {
102 fn lt(&self, other: &BigUint) -> bool {
103 match self.cmp(other) { Less => true, _ => false}
107 impl TotalOrd for BigUint {
109 fn cmp(&self, other: &BigUint) -> Ordering {
110 let (s_len, o_len) = (self.data.len(), other.data.len());
111 if s_len < o_len { return Less; }
112 if s_len > o_len { return Greater; }
114 for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
115 if self_i < other_i { return Less; }
116 if self_i > other_i { return Greater; }
122 impl fmt::Show for BigUint {
123 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
124 write!(f.buf, "{}", self.to_str_radix(10))
128 impl FromStr for BigUint {
130 fn from_str(s: &str) -> Option<BigUint> {
131 FromStrRadix::from_str_radix(s, 10)
135 impl Num for BigUint {}
137 impl BitAnd<BigUint, BigUint> for BigUint {
138 fn bitand(&self, other: &BigUint) -> BigUint {
139 BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
143 impl BitOr<BigUint, BigUint> for BigUint {
144 fn bitor(&self, other: &BigUint) -> BigUint {
145 let zeros = ZERO_VEC.iter().cycle();
146 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
147 let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
150 return BigUint::new(ored);
154 impl BitXor<BigUint, BigUint> for BigUint {
155 fn bitxor(&self, other: &BigUint) -> BigUint {
156 let zeros = ZERO_VEC.iter().cycle();
157 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
158 let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
161 return BigUint::new(xored);
165 impl Shl<uint, BigUint> for BigUint {
167 fn shl(&self, rhs: &uint) -> BigUint {
168 let n_unit = *rhs / BigDigit::bits;
169 let n_bits = *rhs % BigDigit::bits;
170 return self.shl_unit(n_unit).shl_bits(n_bits);
174 impl Shr<uint, BigUint> for BigUint {
176 fn shr(&self, rhs: &uint) -> BigUint {
177 let n_unit = *rhs / BigDigit::bits;
178 let n_bits = *rhs % BigDigit::bits;
179 return self.shr_unit(n_unit).shr_bits(n_bits);
183 impl Zero for BigUint {
185 fn zero() -> BigUint { BigUint::new(Vec::new()) }
188 fn is_zero(&self) -> bool { self.data.is_empty() }
191 impl One for BigUint {
193 fn one() -> BigUint { BigUint::new(vec!(1)) }
196 impl Unsigned for BigUint {}
198 impl Add<BigUint, BigUint> for BigUint {
199 fn add(&self, other: &BigUint) -> BigUint {
200 let zeros = ZERO_VEC.iter().cycle();
201 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
204 let mut sum: Vec<BigDigit> = a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
205 let (hi, lo) = BigDigit::from_uint((*ai as uint) + (*bi as uint) + (carry as uint));
209 if carry != 0 { sum.push(carry); }
210 return BigUint::new(sum);
214 impl Sub<BigUint, BigUint> for BigUint {
215 fn sub(&self, other: &BigUint) -> BigUint {
216 let new_len = cmp::max(self.data.len(), other.data.len());
217 let zeros = ZERO_VEC.iter().cycle();
218 let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
221 let diff: Vec<BigDigit> = a.take(new_len).zip(b).map(|(ai, bi)| {
222 let (hi, lo) = BigDigit::from_uint(
223 BigDigit::base + (*ai as uint) - (*bi as uint) - (borrow as uint)
226 hi * (base) + lo == 1*(base) + ai - bi - borrow
227 => ai - bi - borrow < 0 <=> hi == 0
229 borrow = if hi == 0 { 1 } else { 0 };
233 assert_eq!(borrow, 0); // <=> assert!((self >= other));
234 return BigUint::new(diff);
238 impl Mul<BigUint, BigUint> for BigUint {
239 fn mul(&self, other: &BigUint) -> BigUint {
240 if self.is_zero() || other.is_zero() { return Zero::zero(); }
242 let (s_len, o_len) = (self.data.len(), other.data.len());
243 if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]); }
244 if o_len == 1 { return mul_digit(self, other.data.as_slice()[0]); }
246 // Using Karatsuba multiplication
247 // (a1 * base + a0) * (b1 * base + b0)
248 // = a1*b1 * base^2 +
249 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
251 let half_len = cmp::max(s_len, o_len) / 2;
252 let (s_hi, s_lo) = cut_at(self, half_len);
253 let (o_hi, o_lo) = cut_at(other, half_len);
255 let ll = s_lo * o_lo;
256 let hh = s_hi * o_hi;
258 let (s1, n1) = sub_sign(s_hi, s_lo);
259 let (s2, n2) = sub_sign(o_hi, o_lo);
261 (Equal, _) | (_, Equal) => hh + ll,
262 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
263 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
267 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
270 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
271 if n == 0 { return Zero::zero(); }
272 if n == 1 { return (*a).clone(); }
275 let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
276 let (hi, lo) = BigDigit::from_uint(
277 (*ai as uint) * (n as uint) + (carry as uint)
282 if carry != 0 { prod.push(carry); }
283 return BigUint::new(prod);
287 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
288 let mid = cmp::min(a.data.len(), n);
289 return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
290 BigUint::from_slice(a.data.slice(0, mid)));
294 fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
296 Less => (Less, b - a),
297 Greater => (Greater, a - b),
298 _ => (Equal, Zero::zero())
304 impl Div<BigUint, BigUint> for BigUint {
306 fn div(&self, other: &BigUint) -> BigUint {
307 let (q, _) = self.div_rem(other);
312 impl Rem<BigUint, BigUint> for BigUint {
314 fn rem(&self, other: &BigUint) -> BigUint {
315 let (_, r) = self.div_rem(other);
320 impl Neg<BigUint> for BigUint {
322 fn neg(&self) -> BigUint { fail!() }
325 impl CheckedAdd for BigUint {
327 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
328 return Some(self.add(v));
332 impl CheckedSub for BigUint {
334 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
338 return Some(self.sub(v));
342 impl CheckedMul for BigUint {
344 fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
345 return Some(self.mul(v));
349 impl CheckedDiv for BigUint {
351 fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
355 return Some(self.div(v));
359 impl Integer for BigUint {
361 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
362 self.div_mod_floor(other)
366 fn div_floor(&self, other: &BigUint) -> BigUint {
367 let (d, _) = self.div_mod_floor(other);
372 fn mod_floor(&self, other: &BigUint) -> BigUint {
373 let (_, m) = self.div_mod_floor(other);
377 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
378 if other.is_zero() { fail!() }
379 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
380 if *other == One::one() { return ((*self).clone(), Zero::zero()); }
382 match self.cmp(other) {
383 Less => return (Zero::zero(), (*self).clone()),
384 Equal => return (One::one(), Zero::zero()),
385 Greater => {} // Do nothing
389 let mut n = *other.data.last().unwrap();
390 while n < (1 << BigDigit::bits - 2) {
394 assert!(shift < BigDigit::bits);
395 let (d, m) = div_mod_floor_inner(self << shift, other << shift);
396 return (d, m >> shift);
399 fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
401 let mut d: BigUint = Zero::zero();
404 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
406 let mut prod = b * d0;
408 // FIXME(#5992): assignment operator overloads
411 // FIXME(#5992): assignment operator overloads
420 // FIXME(#5992): assignment operator overloads
423 // FIXME(#5992): assignment operator overloads
431 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
432 -> (BigUint, BigUint, BigUint) {
433 if a.data.len() < n {
434 return (Zero::zero(), Zero::zero(), (*a).clone());
437 let an = a.data.tailn(a.data.len() - n);
438 let bn = *b.data.last().unwrap();
439 let mut d = Vec::with_capacity(an.len());
441 for elt in an.rev_iter() {
442 let ai = BigDigit::to_uint(carry, *elt);
443 let di = ai / (bn as uint);
444 assert!(di < BigDigit::base);
445 carry = (ai % (bn as uint)) as BigDigit;
446 d.push(di as BigDigit)
450 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
452 return (BigUint::new(d), One::one(), (*b).clone());
454 let one: BigUint = One::one();
455 return (BigUint::new(d).shl_unit(shift),
462 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
464 * The result is always positive
467 fn gcd(&self, other: &BigUint) -> BigUint {
468 // Use Euclid's algorithm
469 let mut m = (*self).clone();
470 let mut n = (*other).clone();
480 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
483 fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
485 /// Returns `true` if the number can be divided by `other` without leaving a remainder
487 fn divides(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
489 /// Returns `true` if the number is divisible by `2`
491 fn is_even(&self) -> bool {
492 // Considering only the last digit.
493 match self.data.as_slice().head() {
494 Some(x) => x.is_even(),
499 /// Returns `true` if the number is not divisible by `2`
501 fn is_odd(&self) -> bool { !self.is_even() }
504 impl ToPrimitive for BigUint {
506 fn to_i64(&self) -> Option<i64> {
507 self.to_u64().and_then(|n| {
508 // If top bit of u64 is set, it's too large to convert to i64.
517 #[cfg(target_word_size = "32")]
519 fn to_u64(&self) -> Option<u64> {
520 match self.data.len() {
522 1 => Some(self.data.as_slice()[0] as u64),
524 Some(BigDigit::to_uint(self.data.as_slice()[1], self.data.as_slice()[0]) as u64)
527 let n_lo = BigDigit::to_uint(self.data.as_slice()[1], self.data.as_slice()[0]) as
529 let n_hi = self.data.as_slice()[2] as u64;
530 Some((n_hi << 32) + n_lo)
533 let n_lo = BigDigit::to_uint(self.data.as_slice()[1], self.data.as_slice()[0])
535 let n_hi = BigDigit::to_uint(self.data.as_slice()[3], self.data.as_slice()[2])
537 Some((n_hi << 32) + n_lo)
543 #[cfg(target_word_size = "64")]
545 fn to_u64(&self) -> Option<u64> {
546 match self.data.len() {
548 1 => Some(self.data.as_slice()[0] as u64),
549 2 => Some(BigDigit::to_uint(self.data.as_slice()[1], self.data.as_slice()[0]) as u64),
555 impl FromPrimitive for BigUint {
557 fn from_i64(n: i64) -> Option<BigUint> {
559 FromPrimitive::from_u64(n as u64)
567 #[cfg(target_word_size = "32")]
569 fn from_u64(n: u64) -> Option<BigUint> {
570 let n_lo = (n & 0x0000_0000_FFFF_FFFF) as uint;
571 let n_hi = (n >> 32) as uint;
573 let n = match (BigDigit::from_uint(n_hi), BigDigit::from_uint(n_lo)) {
574 ((0, 0), (0, 0)) => Zero::zero(),
575 ((0, 0), (0, n0)) => BigUint::new(vec!(n0)),
576 ((0, 0), (n1, n0)) => BigUint::new(vec!(n0, n1)),
577 ((0, n2), (n1, n0)) => BigUint::new(vec!(n0, n1, n2)),
578 ((n3, n2), (n1, n0)) => BigUint::new(vec!(n0, n1, n2, n3)),
583 #[cfg(target_word_size = "64")]
585 fn from_u64(n: u64) -> Option<BigUint> {
586 let n = match BigDigit::from_uint(n as uint) {
587 (0, 0) => Zero::zero(),
588 (0, n0) => BigUint::new(vec!(n0)),
589 (n1, n0) => BigUint::new(vec!(n0, n1))
595 /// A generic trait for converting a value to a `BigUint`.
596 pub trait ToBigUint {
597 /// Converts the value of `self` to a `BigUint`.
598 fn to_biguint(&self) -> Option<BigUint>;
601 impl ToBigUint for BigInt {
603 fn to_biguint(&self) -> Option<BigUint> {
604 if self.sign == Plus {
605 Some(self.data.clone())
606 } else if self.sign == Zero {
614 impl ToBigUint for BigUint {
616 fn to_biguint(&self) -> Option<BigUint> {
621 macro_rules! impl_to_biguint(
622 ($T:ty, $from_ty:path) => {
623 impl ToBigUint for $T {
625 fn to_biguint(&self) -> Option<BigUint> {
632 impl_to_biguint!(int, FromPrimitive::from_int)
633 impl_to_biguint!(i8, FromPrimitive::from_i8)
634 impl_to_biguint!(i16, FromPrimitive::from_i16)
635 impl_to_biguint!(i32, FromPrimitive::from_i32)
636 impl_to_biguint!(i64, FromPrimitive::from_i64)
637 impl_to_biguint!(uint, FromPrimitive::from_uint)
638 impl_to_biguint!(u8, FromPrimitive::from_u8)
639 impl_to_biguint!(u16, FromPrimitive::from_u16)
640 impl_to_biguint!(u32, FromPrimitive::from_u32)
641 impl_to_biguint!(u64, FromPrimitive::from_u64)
643 impl ToStrRadix for BigUint {
644 fn to_str_radix(&self, radix: uint) -> ~str {
645 assert!(1 < radix && radix <= 16);
646 let (base, max_len) = get_radix_base(radix);
647 if base == BigDigit::base {
648 return fill_concat(self.data.as_slice(), radix, max_len)
650 return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
652 fn convert_base(n: &BigUint, base: uint) -> Vec<BigDigit> {
653 let divider = FromPrimitive::from_uint(base).unwrap();
654 let mut result = Vec::new();
655 let mut m = n.clone();
657 let (d, m0) = m.div_mod_floor(÷r);
658 result.push(m0.to_uint().unwrap() as BigDigit);
662 result.push(m.to_uint().unwrap() as BigDigit);
667 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> ~str {
668 if v.is_empty() { return ~"0" }
669 let mut s = StrBuf::with_capacity(v.len() * l);
670 for n in v.rev_iter() {
671 let ss = (*n as uint).to_str_radix(radix);
672 s.push_str("0".repeat(l - ss.len()));
675 s.as_slice().trim_left_chars(&'0').to_owned()
680 impl FromStrRadix for BigUint {
681 /// Creates and initializes a `BigUint`.
683 fn from_str_radix(s: &str, radix: uint)
685 BigUint::parse_bytes(s.as_bytes(), radix)
690 /// Creates and initializes a `BigUint`.
692 pub fn new(v: Vec<BigDigit>) -> BigUint {
693 // omit trailing zeros
694 let new_len = v.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
696 if new_len == v.len() { return BigUint { data: v }; }
699 return BigUint { data: v };
702 /// Creates and initializes a `BigUint`.
704 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
705 return BigUint::new(Vec::from_slice(slice));
708 /// Creates and initializes a `BigUint`.
709 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
710 let (base, unit_len) = get_radix_base(radix);
711 let base_num = match FromPrimitive::from_uint(base) {
712 Some(base_num) => base_num,
713 None => { return None; }
716 let mut end = buf.len();
717 let mut n: BigUint = Zero::zero();
718 let mut power: BigUint = One::one();
720 let start = cmp::max(end, unit_len) - unit_len;
721 match uint::parse_bytes(buf.slice(start, end), radix) {
723 let d: Option<BigUint> = FromPrimitive::from_uint(d);
726 // FIXME(#5992): assignment operator overloads
730 None => { return None; }
733 None => { return None; }
739 // FIXME(#5992): assignment operator overloads
740 // power *= base_num;
741 power = power * base_num;
746 fn shl_unit(&self, n_unit: uint) -> BigUint {
747 if n_unit == 0 || self.is_zero() { return (*self).clone(); }
749 BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
753 fn shl_bits(&self, n_bits: uint) -> BigUint {
754 if n_bits == 0 || self.is_zero() { return (*self).clone(); }
757 let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
758 let (hi, lo) = BigDigit::from_uint(
759 (*elem as uint) << n_bits | (carry as uint)
764 if carry != 0 { shifted.push(carry); }
765 return BigUint::new(shifted);
769 fn shr_unit(&self, n_unit: uint) -> BigUint {
770 if n_unit == 0 { return (*self).clone(); }
771 if self.data.len() < n_unit { return Zero::zero(); }
772 return BigUint::from_slice(
773 self.data.slice(n_unit, self.data.len())
778 fn shr_bits(&self, n_bits: uint) -> BigUint {
779 if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
782 let mut shifted_rev = Vec::with_capacity(self.data.len());
783 for elem in self.data.iter().rev() {
784 shifted_rev.push((*elem >> n_bits) | borrow);
785 borrow = *elem << (BigDigit::bits - n_bits);
787 let shifted = { shifted_rev.reverse(); shifted_rev };
788 return BigUint::new(shifted);
791 /// Determines the fewest bits necessary to express the `BigUint`.
792 pub fn bits(&self) -> uint {
793 if self.is_zero() { return 0; }
794 let zeros = self.data.last().unwrap().leading_zeros();
795 return self.data.len()*BigDigit::bits - (zeros as uint);
799 #[cfg(target_word_size = "32")]
801 fn get_radix_base(radix: uint) -> (uint, uint) {
802 assert!(1 < radix && radix <= 16);
823 #[cfg(target_word_size = "64")]
825 fn get_radix_base(radix: uint) -> (uint, uint) {
826 assert!(1 < radix && radix <= 16);
828 2 => (4294967296, 32),
829 3 => (3486784401, 20),
830 4 => (4294967296, 16),
831 5 => (1220703125, 13),
832 6 => (2176782336, 12),
833 7 => (1977326743, 11),
834 8 => (1073741824, 10),
835 9 => (3486784401, 10),
836 10 => (1000000000, 9),
837 11 => (2357947691, 9),
838 12 => (429981696, 8),
839 13 => (815730721, 8),
840 14 => (1475789056, 8),
841 15 => (2562890625, 8),
842 16 => (4294967296, 8),
847 /// A Sign is a `BigInt`'s composing element.
848 #[deriving(Eq, Ord, TotalEq, TotalOrd, Clone, Show)]
849 pub enum Sign { Minus, Zero, Plus }
851 impl Neg<Sign> for Sign {
852 /// Negate Sign value.
854 fn neg(&self) -> Sign {
863 /// A big signed integer type.
872 fn eq(&self, other: &BigInt) -> bool {
873 match self.cmp(other) { Equal => true, _ => false }
877 impl TotalEq for BigInt {}
879 impl Ord for BigInt {
881 fn lt(&self, other: &BigInt) -> bool {
882 match self.cmp(other) { Less => true, _ => false}
886 impl TotalOrd for BigInt {
888 fn cmp(&self, other: &BigInt) -> Ordering {
889 let scmp = self.sign.cmp(&other.sign);
890 if scmp != Equal { return scmp; }
894 Plus => self.data.cmp(&other.data),
895 Minus => other.data.cmp(&self.data),
900 impl fmt::Show for BigInt {
901 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
902 write!(f.buf, "{}", self.to_str_radix(10))
906 impl FromStr for BigInt {
908 fn from_str(s: &str) -> Option<BigInt> {
909 FromStrRadix::from_str_radix(s, 10)
913 impl Num for BigInt {}
915 impl Shl<uint, BigInt> for BigInt {
917 fn shl(&self, rhs: &uint) -> BigInt {
918 BigInt::from_biguint(self.sign, self.data << *rhs)
922 impl Shr<uint, BigInt> for BigInt {
924 fn shr(&self, rhs: &uint) -> BigInt {
925 BigInt::from_biguint(self.sign, self.data >> *rhs)
929 impl Zero for BigInt {
931 fn zero() -> BigInt {
932 BigInt::from_biguint(Zero, Zero::zero())
936 fn is_zero(&self) -> bool { self.sign == Zero }
939 impl One for BigInt {
942 BigInt::from_biguint(Plus, One::one())
946 impl Signed for BigInt {
948 fn abs(&self) -> BigInt {
950 Plus | Zero => self.clone(),
951 Minus => BigInt::from_biguint(Plus, self.data.clone())
956 fn abs_sub(&self, other: &BigInt) -> BigInt {
957 if *self <= *other { Zero::zero() } else { *self - *other }
961 fn signum(&self) -> BigInt {
963 Plus => BigInt::from_biguint(Plus, One::one()),
964 Minus => BigInt::from_biguint(Minus, One::one()),
965 Zero => Zero::zero(),
970 fn is_positive(&self) -> bool { self.sign == Plus }
973 fn is_negative(&self) -> bool { self.sign == Minus }
976 impl Add<BigInt, BigInt> for BigInt {
978 fn add(&self, other: &BigInt) -> BigInt {
979 match (self.sign, other.sign) {
980 (Zero, _) => other.clone(),
981 (_, Zero) => self.clone(),
982 (Plus, Plus) => BigInt::from_biguint(Plus,
983 self.data + other.data),
984 (Plus, Minus) => self - (-*other),
985 (Minus, Plus) => other - (-*self),
986 (Minus, Minus) => -((-self) + (-*other))
991 impl Sub<BigInt, BigInt> for BigInt {
993 fn sub(&self, other: &BigInt) -> BigInt {
994 match (self.sign, other.sign) {
996 (_, Zero) => self.clone(),
997 (Plus, Plus) => match self.data.cmp(&other.data) {
998 Less => BigInt::from_biguint(Minus, other.data - self.data),
999 Greater => BigInt::from_biguint(Plus, self.data - other.data),
1000 Equal => Zero::zero()
1002 (Plus, Minus) => self + (-*other),
1003 (Minus, Plus) => -((-self) + *other),
1004 (Minus, Minus) => (-other) - (-*self)
1009 impl Mul<BigInt, BigInt> for BigInt {
1011 fn mul(&self, other: &BigInt) -> BigInt {
1012 match (self.sign, other.sign) {
1013 (Zero, _) | (_, Zero) => Zero::zero(),
1014 (Plus, Plus) | (Minus, Minus) => {
1015 BigInt::from_biguint(Plus, self.data * other.data)
1017 (Plus, Minus) | (Minus, Plus) => {
1018 BigInt::from_biguint(Minus, self.data * other.data)
1024 impl Div<BigInt, BigInt> for BigInt {
1026 fn div(&self, other: &BigInt) -> BigInt {
1027 let (q, _) = self.div_rem(other);
1032 impl Rem<BigInt, BigInt> for BigInt {
1034 fn rem(&self, other: &BigInt) -> BigInt {
1035 let (_, r) = self.div_rem(other);
1040 impl Neg<BigInt> for BigInt {
1042 fn neg(&self) -> BigInt {
1043 BigInt::from_biguint(self.sign.neg(), self.data.clone())
1047 impl CheckedAdd for BigInt {
1049 fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
1050 return Some(self.add(v));
1054 impl CheckedSub for BigInt {
1056 fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
1057 return Some(self.sub(v));
1061 impl CheckedMul for BigInt {
1063 fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1064 return Some(self.mul(v));
1068 impl CheckedDiv for BigInt {
1070 fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1074 return Some(self.div(v));
1079 impl Integer for BigInt {
1081 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1082 // r.sign == self.sign
1083 let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1084 let d = BigInt::from_biguint(Plus, d_ui);
1085 let r = BigInt::from_biguint(Plus, r_ui);
1086 match (self.sign, other.sign) {
1087 (_, Zero) => fail!(),
1088 (Plus, Plus) | (Zero, Plus) => ( d, r),
1089 (Plus, Minus) | (Zero, Minus) => (-d, r),
1090 (Minus, Plus) => (-d, -r),
1091 (Minus, Minus) => ( d, -r)
1096 fn div_floor(&self, other: &BigInt) -> BigInt {
1097 let (d, _) = self.div_mod_floor(other);
1102 fn mod_floor(&self, other: &BigInt) -> BigInt {
1103 let (_, m) = self.div_mod_floor(other);
1107 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1108 // m.sign == other.sign
1109 let (d_ui, m_ui) = self.data.div_rem(&other.data);
1110 let d = BigInt::from_biguint(Plus, d_ui);
1111 let m = BigInt::from_biguint(Plus, m_ui);
1112 match (self.sign, other.sign) {
1113 (_, Zero) => fail!(),
1114 (Plus, Plus) | (Zero, Plus) => (d, m),
1115 (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1118 (-d - One::one(), m + *other)
1120 (Minus, Plus) => if m.is_zero() {
1123 (-d - One::one(), other - m)
1125 (Minus, Minus) => (d, -m)
1130 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
1132 * The result is always positive
1135 fn gcd(&self, other: &BigInt) -> BigInt {
1136 BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1140 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
1143 fn lcm(&self, other: &BigInt) -> BigInt {
1144 BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1147 /// Returns `true` if the number can be divided by `other` without leaving a remainder
1149 fn divides(&self, other: &BigInt) -> bool { self.data.divides(&other.data) }
1151 /// Returns `true` if the number is divisible by `2`
1153 fn is_even(&self) -> bool { self.data.is_even() }
1155 /// Returns `true` if the number is not divisible by `2`
1157 fn is_odd(&self) -> bool { self.data.is_odd() }
1160 impl ToPrimitive for BigInt {
1162 fn to_i64(&self) -> Option<i64> {
1164 Plus => self.data.to_i64(),
1167 self.data.to_u64().and_then(|n| {
1168 let m: u64 = 1 << 63;
1182 fn to_u64(&self) -> Option<u64> {
1184 Plus => self.data.to_u64(),
1191 impl FromPrimitive for BigInt {
1193 fn from_i64(n: i64) -> Option<BigInt> {
1195 FromPrimitive::from_u64(n as u64).and_then(|n| {
1196 Some(BigInt::from_biguint(Plus, n))
1199 FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1201 Some(BigInt::from_biguint(Minus, n))
1209 fn from_u64(n: u64) -> Option<BigInt> {
1213 FromPrimitive::from_u64(n).and_then(|n| {
1214 Some(BigInt::from_biguint(Plus, n))
1220 /// A generic trait for converting a value to a `BigInt`.
1221 pub trait ToBigInt {
1222 /// Converts the value of `self` to a `BigInt`.
1223 fn to_bigint(&self) -> Option<BigInt>;
1226 impl ToBigInt for BigInt {
1228 fn to_bigint(&self) -> Option<BigInt> {
1233 impl ToBigInt for BigUint {
1235 fn to_bigint(&self) -> Option<BigInt> {
1239 Some(BigInt { sign: Plus, data: self.clone() })
1244 macro_rules! impl_to_bigint(
1245 ($T:ty, $from_ty:path) => {
1246 impl ToBigInt for $T {
1248 fn to_bigint(&self) -> Option<BigInt> {
1255 impl_to_bigint!(int, FromPrimitive::from_int)
1256 impl_to_bigint!(i8, FromPrimitive::from_i8)
1257 impl_to_bigint!(i16, FromPrimitive::from_i16)
1258 impl_to_bigint!(i32, FromPrimitive::from_i32)
1259 impl_to_bigint!(i64, FromPrimitive::from_i64)
1260 impl_to_bigint!(uint, FromPrimitive::from_uint)
1261 impl_to_bigint!(u8, FromPrimitive::from_u8)
1262 impl_to_bigint!(u16, FromPrimitive::from_u16)
1263 impl_to_bigint!(u32, FromPrimitive::from_u32)
1264 impl_to_bigint!(u64, FromPrimitive::from_u64)
1266 impl ToStrRadix for BigInt {
1268 fn to_str_radix(&self, radix: uint) -> ~str {
1270 Plus => self.data.to_str_radix(radix),
1272 Minus => ~"-" + self.data.to_str_radix(radix)
1277 impl FromStrRadix for BigInt {
1278 /// Creates and initializes a BigInt.
1280 fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1281 BigInt::parse_bytes(s.as_bytes(), radix)
1285 pub trait RandBigInt {
1286 /// Generate a random `BigUint` of the given bit size.
1287 fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1289 /// Generate a random BigInt of the given bit size.
1290 fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1292 /// Generate a random `BigUint` less than the given bound. Fails
1293 /// when the bound is zero.
1294 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1296 /// Generate a random `BigUint` within the given range. The lower
1297 /// bound is inclusive; the upper bound is exclusive. Fails when
1298 /// the upper bound is not greater than the lower bound.
1299 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1301 /// Generate a random `BigInt` within the given range. The lower
1302 /// bound is inclusive; the upper bound is exclusive. Fails when
1303 /// the upper bound is not greater than the lower bound.
1304 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1307 impl<R: Rng> RandBigInt for R {
1308 fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1309 let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1310 let mut data = Vec::with_capacity(digits+1);
1311 for _ in range(0, digits) {
1312 data.push(self.gen());
1315 let final_digit: BigDigit = self.gen();
1316 data.push(final_digit >> (BigDigit::bits - rem));
1318 return BigUint::new(data);
1321 fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1322 // Generate a random BigUint...
1323 let biguint = self.gen_biguint(bit_size);
1324 // ...and then randomly assign it a Sign...
1325 let sign = if biguint.is_zero() {
1326 // ...except that if the BigUint is zero, we need to try
1327 // again with probability 0.5. This is because otherwise,
1328 // the probability of generating a zero BigInt would be
1329 // double that of any other number.
1331 return self.gen_bigint(bit_size);
1335 } else if self.gen() {
1340 return BigInt::from_biguint(sign, biguint);
1343 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1344 assert!(!bound.is_zero());
1345 let bits = bound.bits();
1347 let n = self.gen_biguint(bits);
1348 if n < *bound { return n; }
1352 fn gen_biguint_range(&mut self,
1356 assert!(*lbound < *ubound);
1357 return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1360 fn gen_bigint_range(&mut self,
1364 assert!(*lbound < *ubound);
1365 let delta = (*ubound - *lbound).to_biguint().unwrap();
1366 return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1371 /// Creates and initializes a BigInt.
1373 pub fn new(sign: Sign, v: Vec<BigDigit>) -> BigInt {
1374 BigInt::from_biguint(sign, BigUint::new(v))
1377 /// Creates and initializes a `BigInt`.
1379 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1380 if sign == Zero || data.is_zero() {
1381 return BigInt { sign: Zero, data: Zero::zero() };
1383 return BigInt { sign: sign, data: data };
1386 /// Creates and initializes a `BigInt`.
1388 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1389 BigInt::from_biguint(sign, BigUint::from_slice(slice))
1392 /// Creates and initializes a `BigInt`.
1393 pub fn parse_bytes(buf: &[u8], radix: uint)
1395 if buf.is_empty() { return None; }
1396 let mut sign = Plus;
1398 if buf[0] == ('-' as u8) {
1402 return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1403 .map(|bu| BigInt::from_biguint(sign, bu));
1406 /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1408 pub fn to_biguint(&self) -> Option<BigUint> {
1410 Plus => Some(self.data.clone()),
1411 Zero => Some(Zero::zero()),
1420 use super::{BigDigit, BigUint, ToBigUint};
1421 use super::{Plus, BigInt, RandBigInt, ToBigInt};
1423 use std::cmp::{Less, Equal, Greater};
1424 use std::from_str::FromStr;
1426 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1427 use std::num::{ToPrimitive, FromPrimitive};
1428 use std::num::CheckedDiv;
1429 use rand::{task_rng};
1433 fn test_from_slice() {
1434 fn check(slice: &[BigDigit], data: &[BigDigit]) {
1435 assert!(data == BigUint::from_slice(slice).data.as_slice());
1438 check([0, 0, 0], []);
1439 check([1, 2, 0, 0], [1, 2]);
1440 check([0, 0, 1, 2], [0, 0, 1, 2]);
1441 check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1447 let data: Vec<BigUint> = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ]
1448 .iter().map(|v| BigUint::from_slice(*v)).collect();
1449 for (i, ni) in data.iter().enumerate() {
1450 for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1453 assert_eq!(ni.cmp(nj), Equal);
1454 assert_eq!(nj.cmp(ni), Equal);
1456 assert!(!(ni != nj));
1459 assert!(!(ni < nj));
1460 assert!(!(ni > nj));
1462 assert_eq!(ni.cmp(nj), Less);
1463 assert_eq!(nj.cmp(ni), Greater);
1465 assert!(!(ni == nj));
1469 assert!(!(ni >= nj));
1471 assert!(!(ni > nj));
1473 assert!(!(nj <= ni));
1475 assert!(!(nj < ni));
1484 fn check(left: &[BigDigit],
1486 expected: &[BigDigit]) {
1487 assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1488 BigUint::from_slice(expected));
1491 check([268, 482, 17],
1498 fn check(left: &[BigDigit],
1500 expected: &[BigDigit]) {
1501 assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1502 BigUint::from_slice(expected));
1505 check([268, 482, 17],
1512 fn check(left: &[BigDigit],
1514 expected: &[BigDigit]) {
1515 assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1516 BigUint::from_slice(expected));
1519 check([268, 482, 17],
1526 fn check(s: &str, shift: uint, ans: &str) {
1527 let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1528 let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1529 assert_eq!(bu.as_slice(), ans);
1535 check("1" + "0000" + "0000" + "0000" + "0001" + "0000" + "0000" + "0000" + "0001", 3,
1536 "8" + "0000" + "0000" + "0000" + "0008" + "0000" + "0000" + "0000" + "0008");
1537 check("1" + "0000" + "0001" + "0000" + "0001", 2,
1538 "4" + "0000" + "0004" + "0000" + "0004");
1539 check("1" + "0001" + "0001", 1,
1540 "2" + "0002" + "0002");
1542 check("" + "4000" + "0000" + "0000" + "0000", 3,
1543 "2" + "0000" + "0000" + "0000" + "0000");
1544 check("" + "4000" + "0000", 2,
1545 "1" + "0000" + "0000");
1546 check("" + "4000", 2,
1549 check("" + "4000" + "0000" + "0000" + "0000", 67,
1550 "2" + "0000" + "0000" + "0000" + "0000" + "0000" + "0000" + "0000" + "0000");
1551 check("" + "4000" + "0000", 35,
1552 "2" + "0000" + "0000" + "0000" + "0000");
1553 check("" + "4000", 19,
1554 "2" + "0000" + "0000");
1556 check("" + "fedc" + "ba98" + "7654" + "3210" + "fedc" + "ba98" + "7654" + "3210", 4,
1557 "f" + "edcb" + "a987" + "6543" + "210f" + "edcb" + "a987" + "6543" + "2100");
1558 check("88887777666655554444333322221111", 16,
1559 "888877776666555544443333222211110000");
1564 fn check(s: &str, shift: uint, ans: &str) {
1565 let opt_biguint: Option<BigUint> =
1566 FromStrRadix::from_str_radix(s, 16);
1567 let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1568 assert_eq!(bu.as_slice(), ans);
1574 check("1" + "0000" + "0000" + "0000" + "0001" + "0000" + "0000" + "0000" + "0001", 3,
1575 "" + "2000" + "0000" + "0000" + "0000" + "2000" + "0000" + "0000" + "0000");
1576 check("1" + "0000" + "0001" + "0000" + "0001", 2,
1577 "" + "4000" + "0000" + "4000" + "0000");
1578 check("1" + "0001" + "0001", 1,
1579 "" + "8000" + "8000");
1581 check("2" + "0000" + "0000" + "0000" + "0001" + "0000" + "0000" + "0000" + "0001", 67,
1582 "" + "4000" + "0000" + "0000" + "0000");
1583 check("2" + "0000" + "0001" + "0000" + "0001", 35,
1584 "" + "4000" + "0000");
1585 check("2" + "0001" + "0001", 19,
1588 check("1" + "0000" + "0000" + "0000" + "0000", 1,
1589 "" + "8000" + "0000" + "0000" + "0000");
1590 check("1" + "0000" + "0000", 1,
1591 "" + "8000" + "0000");
1592 check("1" + "0000", 1,
1594 check("f" + "edcb" + "a987" + "6543" + "210f" + "edcb" + "a987" + "6543" + "2100", 4,
1595 "" + "fedc" + "ba98" + "7654" + "3210" + "fedc" + "ba98" + "7654" + "3210");
1597 check("888877776666555544443333222211110000", 16,
1598 "88887777666655554444333322221111");
1601 #[cfg(target_word_size = "32")]
1603 fn test_convert_i64() {
1604 fn check(b1: BigUint, i: i64) {
1605 let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1607 assert!(b1.to_i64().unwrap() == i);
1610 check(Zero::zero(), 0);
1611 check(One::one(), 1);
1612 check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1614 check(BigUint::new(vec!( )), 0);
1615 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1616 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1617 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1618 check(BigUint::new(vec!(-1, -1 )), (1 << (2*BigDigit::bits)) - 1);
1619 check(BigUint::new(vec!( 0, 0, 1 )), (1 << (2*BigDigit::bits)));
1620 check(BigUint::new(vec!(-1, -1, -1 )), (1 << (3*BigDigit::bits)) - 1);
1621 check(BigUint::new(vec!( 0, 0, 0, 1 )), (1 << (3*BigDigit::bits)));
1622 check(BigUint::new(vec!(-1, -1, -1, -1 >> 1)), i64::MAX);
1624 assert_eq!(i64::MIN.to_biguint(), None);
1625 assert_eq!(BigUint::new(vec!(-1, -1, -1, -1 )).to_i64(), None);
1626 assert_eq!(BigUint::new(vec!( 0, 0, 0, 0, 1)).to_i64(), None);
1627 assert_eq!(BigUint::new(vec!(-1, -1, -1, -1, -1)).to_i64(), None);
1630 #[cfg(target_word_size = "64")]
1632 fn test_convert_i64() {
1633 fn check(b1: BigUint, i: i64) {
1634 let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1636 assert!(b1.to_i64().unwrap() == i);
1639 check(Zero::zero(), 0);
1640 check(One::one(), 1);
1641 check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1643 check(BigUint::new(vec!( )), 0);
1644 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1645 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1646 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1647 check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1649 assert_eq!(i64::MIN.to_biguint(), None);
1650 assert_eq!(BigUint::new(vec!(-1, -1 )).to_i64(), None);
1651 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_i64(), None);
1652 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1655 #[cfg(target_word_size = "32")]
1657 fn test_convert_u64() {
1658 fn check(b1: BigUint, u: u64) {
1659 let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1661 assert!(b1.to_u64().unwrap() == u);
1664 check(Zero::zero(), 0);
1665 check(One::one(), 1);
1666 check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1667 check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1669 check(BigUint::new(vec!( )), 0);
1670 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1671 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1672 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1673 check(BigUint::new(vec!(-1, -1 )), (1 << (2*BigDigit::bits)) - 1);
1674 check(BigUint::new(vec!( 0, 0, 1 )), (1 << (2*BigDigit::bits)));
1675 check(BigUint::new(vec!(-1, -1, -1 )), (1 << (3*BigDigit::bits)) - 1);
1676 check(BigUint::new(vec!( 0, 0, 0, 1)), (1 << (3*BigDigit::bits)));
1677 check(BigUint::new(vec!(-1, -1, -1, -1)), u64::MAX);
1679 assert_eq!(BigUint::new(vec!( 0, 0, 0, 0, 1)).to_u64(), None);
1680 assert_eq!(BigUint::new(vec!(-1, -1, -1, -1, -1)).to_u64(), None);
1683 #[cfg(target_word_size = "64")]
1685 fn test_convert_u64() {
1686 fn check(b1: BigUint, u: u64) {
1687 let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1689 assert!(b1.to_u64().unwrap() == u);
1692 check(Zero::zero(), 0);
1693 check(One::one(), 1);
1694 check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1695 check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1697 check(BigUint::new(vec!( )), 0);
1698 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1699 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1700 check(BigUint::new(vec!( 0, 1)), (1 << (1*BigDigit::bits)));
1701 check(BigUint::new(vec!(-1, -1)), u64::MAX);
1703 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_u64(), None);
1704 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1708 fn test_convert_to_bigint() {
1709 fn check(n: BigUint, ans: BigInt) {
1710 assert_eq!(n.to_bigint().unwrap(), ans);
1711 assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1713 check(Zero::zero(), Zero::zero());
1714 check(BigUint::new(vec!(1,2,3)),
1715 BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1718 static sum_triples: &'static [(&'static [BigDigit],
1719 &'static [BigDigit],
1720 &'static [BigDigit])] = &[
1722 (&[], &[ 1], &[ 1]),
1723 (&[ 1], &[ 1], &[ 2]),
1724 (&[ 1], &[ 1, 1], &[ 2, 1]),
1725 (&[ 1], &[-1], &[ 0, 1]),
1726 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1727 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1728 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1729 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1734 for elm in sum_triples.iter() {
1735 let (a_vec, b_vec, c_vec) = *elm;
1736 let a = BigUint::from_slice(a_vec);
1737 let b = BigUint::from_slice(b_vec);
1738 let c = BigUint::from_slice(c_vec);
1740 assert!(a + b == c);
1741 assert!(b + a == c);
1747 for elm in sum_triples.iter() {
1748 let (a_vec, b_vec, c_vec) = *elm;
1749 let a = BigUint::from_slice(a_vec);
1750 let b = BigUint::from_slice(b_vec);
1751 let c = BigUint::from_slice(c_vec);
1753 assert!(c - a == b);
1754 assert!(c - b == a);
1758 static mul_triples: &'static [(&'static [BigDigit],
1759 &'static [BigDigit],
1760 &'static [BigDigit])] = &[
1764 (&[ 1], &[ 1], &[1]),
1765 (&[ 2], &[ 3], &[ 6]),
1766 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1767 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1768 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1769 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1770 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1771 (&[-1], &[-1], &[ 1, -2]),
1772 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1773 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1774 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1775 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1776 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1777 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1778 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1779 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1780 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1781 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1784 static div_rem_quadruples: &'static [(&'static [BigDigit],
1785 &'static [BigDigit],
1786 &'static [BigDigit],
1787 &'static [BigDigit])]
1789 (&[ 1], &[ 2], &[], &[1]),
1790 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1791 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1792 (&[ 0, 1], &[-1], &[1], &[1]),
1793 (&[-1, -1], &[-2], &[2, 1], &[3])
1798 for elm in mul_triples.iter() {
1799 let (a_vec, b_vec, c_vec) = *elm;
1800 let a = BigUint::from_slice(a_vec);
1801 let b = BigUint::from_slice(b_vec);
1802 let c = BigUint::from_slice(c_vec);
1804 assert!(a * b == c);
1805 assert!(b * a == c);
1808 for elm in div_rem_quadruples.iter() {
1809 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1810 let a = BigUint::from_slice(a_vec);
1811 let b = BigUint::from_slice(b_vec);
1812 let c = BigUint::from_slice(c_vec);
1813 let d = BigUint::from_slice(d_vec);
1815 assert!(a == b * c + d);
1816 assert!(a == c * b + d);
1822 for elm in mul_triples.iter() {
1823 let (a_vec, b_vec, c_vec) = *elm;
1824 let a = BigUint::from_slice(a_vec);
1825 let b = BigUint::from_slice(b_vec);
1826 let c = BigUint::from_slice(c_vec);
1829 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1832 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1836 for elm in div_rem_quadruples.iter() {
1837 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1838 let a = BigUint::from_slice(a_vec);
1839 let b = BigUint::from_slice(b_vec);
1840 let c = BigUint::from_slice(c_vec);
1841 let d = BigUint::from_slice(d_vec);
1843 if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1848 fn test_checked_add() {
1849 for elm in sum_triples.iter() {
1850 let (aVec, bVec, cVec) = *elm;
1851 let a = BigUint::from_slice(aVec);
1852 let b = BigUint::from_slice(bVec);
1853 let c = BigUint::from_slice(cVec);
1855 assert!(a.checked_add(&b).unwrap() == c);
1856 assert!(b.checked_add(&a).unwrap() == c);
1861 fn test_checked_sub() {
1862 for elm in sum_triples.iter() {
1863 let (aVec, bVec, cVec) = *elm;
1864 let a = BigUint::from_slice(aVec);
1865 let b = BigUint::from_slice(bVec);
1866 let c = BigUint::from_slice(cVec);
1868 assert!(c.checked_sub(&a).unwrap() == b);
1869 assert!(c.checked_sub(&b).unwrap() == a);
1872 assert!(a.checked_sub(&c).is_none());
1875 assert!(b.checked_sub(&c).is_none());
1881 fn test_checked_mul() {
1882 for elm in mul_triples.iter() {
1883 let (aVec, bVec, cVec) = *elm;
1884 let a = BigUint::from_slice(aVec);
1885 let b = BigUint::from_slice(bVec);
1886 let c = BigUint::from_slice(cVec);
1888 assert!(a.checked_mul(&b).unwrap() == c);
1889 assert!(b.checked_mul(&a).unwrap() == c);
1892 for elm in div_rem_quadruples.iter() {
1893 let (aVec, bVec, cVec, dVec) = *elm;
1894 let a = BigUint::from_slice(aVec);
1895 let b = BigUint::from_slice(bVec);
1896 let c = BigUint::from_slice(cVec);
1897 let d = BigUint::from_slice(dVec);
1899 assert!(a == b.checked_mul(&c).unwrap() + d);
1900 assert!(a == c.checked_mul(&b).unwrap() + d);
1905 fn test_checked_div() {
1906 for elm in mul_triples.iter() {
1907 let (aVec, bVec, cVec) = *elm;
1908 let a = BigUint::from_slice(aVec);
1909 let b = BigUint::from_slice(bVec);
1910 let c = BigUint::from_slice(cVec);
1913 assert!(c.checked_div(&a).unwrap() == b);
1916 assert!(c.checked_div(&b).unwrap() == a);
1919 assert!(c.checked_div(&Zero::zero()).is_none());
1925 fn check(a: uint, b: uint, c: uint) {
1926 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
1927 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
1928 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
1930 assert_eq!(big_a.gcd(&big_b), big_c);
1942 fn check(a: uint, b: uint, c: uint) {
1943 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
1944 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
1945 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
1947 assert_eq!(big_a.lcm(&big_b), big_c);
1955 check(99, 17, 1683);
1960 let one: BigUint = FromStr::from_str("1").unwrap();
1961 let two: BigUint = FromStr::from_str("2").unwrap();
1962 let thousand: BigUint = FromStr::from_str("1000").unwrap();
1963 let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
1964 let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
1965 assert!(one.is_odd());
1966 assert!(two.is_even());
1967 assert!(thousand.is_even());
1968 assert!(big.is_even());
1969 assert!(bigger.is_odd());
1970 assert!((one << 64).is_even());
1971 assert!(((one << 64) + one).is_odd());
1974 fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, ~str)>)> {
1975 let bits = BigDigit::bits;
1976 vec!(( Zero::zero(), vec!(
1977 (2, ~"0"), (3, ~"0")
1978 )), ( BigUint::from_slice([ 0xff ]), vec!(
1994 )), ( BigUint::from_slice([ 0xfff ]), vec!(
1995 (2, ~"111111111111"),
1998 )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2001 "0".repeat(bits - 1) + "1"),
2004 "0".repeat(bits / 2 - 1) + "1"),
2006 32 => ~"8589934593", 16 => ~"131073", _ => fail!()
2010 "0".repeat(bits / 4 - 1) + "1")
2011 )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2014 "0".repeat(bits - 2) + "10" +
2015 "0".repeat(bits - 1) + "1"),
2018 "0".repeat(bits / 2 - 1) + "2" +
2019 "0".repeat(bits / 2 - 1) + "1"),
2021 32 => ~"55340232229718589441",
2022 16 => ~"12885032961",
2026 "0".repeat(bits / 4 - 1) + "2" +
2027 "0".repeat(bits / 4 - 1) + "1")
2032 fn test_to_str_radix() {
2033 let r = to_str_pairs();
2034 for num_pair in r.iter() {
2035 let &(ref n, ref rs) = num_pair;
2036 for str_pair in rs.iter() {
2037 let &(ref radix, ref str) = str_pair;
2038 assert_eq!(&n.to_str_radix(*radix), str);
2044 fn test_from_str_radix() {
2045 let r = to_str_pairs();
2046 for num_pair in r.iter() {
2047 let &(ref n, ref rs) = num_pair;
2048 for str_pair in rs.iter() {
2049 let &(ref radix, ref str) = str_pair;
2050 assert_eq!(n, &FromStrRadix::from_str_radix(*str, *radix).unwrap());
2054 let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2055 assert_eq!(zed, None);
2056 let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2057 assert_eq!(blank, None);
2058 let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2060 assert_eq!(minus_one, None);
2065 fn factor(n: uint) -> BigUint {
2066 let mut f: BigUint = One::one();
2067 for i in range(2, n + 1) {
2068 // FIXME(#5992): assignment operator overloads
2069 // f *= FromPrimitive::from_uint(i);
2070 f = f * FromPrimitive::from_uint(i).unwrap();
2075 fn check(n: uint, s: &str) {
2077 let ans = match FromStrRadix::from_str_radix(s, 10) {
2078 Some(x) => x, None => fail!()
2084 check(10, "3628800");
2085 check(20, "2432902008176640000");
2086 check(30, "265252859812191058636308480000000");
2091 assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2092 let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2093 assert_eq!(n.bits(), 0);
2094 let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2095 assert_eq!(n.bits(), 1);
2096 let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2097 assert_eq!(n.bits(), 2);
2098 let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2099 assert_eq!(n.bits(), 39);
2100 let one: BigUint = One::one();
2101 assert_eq!((one << 426).bits(), 427);
2106 let mut rng = task_rng();
2107 let _n: BigUint = rng.gen_biguint(137);
2108 assert!(rng.gen_biguint(0).is_zero());
2112 fn test_rand_range() {
2113 let mut rng = task_rng();
2115 for _ in range(0, 10) {
2116 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2117 &FromPrimitive::from_uint(237).unwrap()),
2118 FromPrimitive::from_uint(236).unwrap());
2121 let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2122 let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2123 for _ in range(0, 1000) {
2124 let n: BigUint = rng.gen_biguint_below(&u);
2127 let n: BigUint = rng.gen_biguint_range(&l, &u);
2135 fn test_zero_rand_range() {
2136 task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2137 &FromPrimitive::from_uint(54).unwrap());
2142 fn test_negative_rand_range() {
2143 let mut rng = task_rng();
2144 let l = FromPrimitive::from_uint(2352).unwrap();
2145 let u = FromPrimitive::from_uint(3513).unwrap();
2146 // Switching u and l should fail:
2147 let _n: BigUint = rng.gen_biguint_range(&u, &l);
2154 use super::{BigDigit, BigUint, ToBigUint};
2155 use super::{Sign, Minus, Zero, Plus, BigInt, RandBigInt, ToBigInt};
2157 use std::cmp::{Less, Equal, Greater};
2159 use std::num::CheckedDiv;
2160 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2161 use std::num::{ToPrimitive, FromPrimitive};
2162 use rand::{task_rng};
2166 fn test_from_biguint() {
2167 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2168 let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2169 let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2170 assert_eq!(inp, ans);
2172 check(Plus, 1, Plus, 1);
2173 check(Plus, 0, Zero, 0);
2174 check(Minus, 1, Minus, 1);
2175 check(Zero, 1, Zero, 0);
2180 let vs = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2181 let mut nums = Vec::new();
2182 for s in vs.rev_iter() {
2183 nums.push(BigInt::from_slice(Minus, *s));
2185 nums.push(Zero::zero());
2186 nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2188 for (i, ni) in nums.iter().enumerate() {
2189 for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2192 assert_eq!(ni.cmp(nj), Equal);
2193 assert_eq!(nj.cmp(ni), Equal);
2195 assert!(!(ni != nj));
2198 assert!(!(ni < nj));
2199 assert!(!(ni > nj));
2201 assert_eq!(ni.cmp(nj), Less);
2202 assert_eq!(nj.cmp(ni), Greater);
2204 assert!(!(ni == nj));
2208 assert!(!(ni >= nj));
2210 assert!(!(ni > nj));
2212 assert!(!(nj <= ni));
2214 assert!(!(nj < ni));
2222 fn test_convert_i64() {
2223 fn check(b1: BigInt, i: i64) {
2224 let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2226 assert!(b1.to_i64().unwrap() == i);
2229 check(Zero::zero(), 0);
2230 check(One::one(), 1);
2231 check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2232 check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2235 (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2239 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2243 BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2247 BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2252 fn test_convert_u64() {
2253 fn check(b1: BigInt, u: u64) {
2254 let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2256 assert!(b1.to_u64().unwrap() == u);
2259 check(Zero::zero(), 0);
2260 check(One::one(), 1);
2261 check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2262 check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2265 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2268 let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2269 assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2270 assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2274 fn test_convert_to_biguint() {
2275 fn check(n: BigInt, ans_1: BigUint) {
2276 assert_eq!(n.to_biguint().unwrap(), ans_1);
2277 assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2279 let zero: BigInt = Zero::zero();
2280 let unsigned_zero: BigUint = Zero::zero();
2281 let positive = BigInt::from_biguint(
2282 Plus, BigUint::new(vec!(1,2,3)));
2283 let negative = -positive;
2285 check(zero, unsigned_zero);
2286 check(positive, BigUint::new(vec!(1,2,3)));
2288 assert_eq!(negative.to_biguint(), None);
2291 static sum_triples: &'static [(&'static [BigDigit],
2292 &'static [BigDigit],
2293 &'static [BigDigit])] = &[
2295 (&[], &[ 1], &[ 1]),
2296 (&[ 1], &[ 1], &[ 2]),
2297 (&[ 1], &[ 1, 1], &[ 2, 1]),
2298 (&[ 1], &[-1], &[ 0, 1]),
2299 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
2300 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
2301 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
2302 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
2307 for elm in sum_triples.iter() {
2308 let (a_vec, b_vec, c_vec) = *elm;
2309 let a = BigInt::from_slice(Plus, a_vec);
2310 let b = BigInt::from_slice(Plus, b_vec);
2311 let c = BigInt::from_slice(Plus, c_vec);
2313 assert!(a + b == c);
2314 assert!(b + a == c);
2315 assert!(c + (-a) == b);
2316 assert!(c + (-b) == a);
2317 assert!(a + (-c) == (-b));
2318 assert!(b + (-c) == (-a));
2319 assert!((-a) + (-b) == (-c))
2320 assert!(a + (-a) == Zero::zero());
2326 for elm in sum_triples.iter() {
2327 let (a_vec, b_vec, c_vec) = *elm;
2328 let a = BigInt::from_slice(Plus, a_vec);
2329 let b = BigInt::from_slice(Plus, b_vec);
2330 let c = BigInt::from_slice(Plus, c_vec);
2332 assert!(c - a == b);
2333 assert!(c - b == a);
2334 assert!((-b) - a == (-c))
2335 assert!((-a) - b == (-c))
2336 assert!(b - (-a) == c);
2337 assert!(a - (-b) == c);
2338 assert!((-c) - (-a) == (-b));
2339 assert!(a - a == Zero::zero());
2343 static mul_triples: &'static [(&'static [BigDigit],
2344 &'static [BigDigit],
2345 &'static [BigDigit])] = &[
2349 (&[ 1], &[ 1], &[1]),
2350 (&[ 2], &[ 3], &[ 6]),
2351 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
2352 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
2353 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
2354 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
2355 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
2356 (&[-1], &[-1], &[ 1, -2]),
2357 (&[-1, -1], &[-1], &[ 1, -1, -2]),
2358 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
2359 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
2360 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
2361 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
2362 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
2363 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
2364 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
2365 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
2366 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
2369 static div_rem_quadruples: &'static [(&'static [BigDigit],
2370 &'static [BigDigit],
2371 &'static [BigDigit],
2372 &'static [BigDigit])]
2374 (&[ 1], &[ 2], &[], &[1]),
2375 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
2376 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2377 (&[ 0, 1], &[-1], &[1], &[1]),
2378 (&[-1, -1], &[-2], &[2, 1], &[3])
2383 for elm in mul_triples.iter() {
2384 let (a_vec, b_vec, c_vec) = *elm;
2385 let a = BigInt::from_slice(Plus, a_vec);
2386 let b = BigInt::from_slice(Plus, b_vec);
2387 let c = BigInt::from_slice(Plus, c_vec);
2389 assert!(a * b == c);
2390 assert!(b * a == c);
2392 assert!((-a) * b == -c);
2393 assert!((-b) * a == -c);
2396 for elm in div_rem_quadruples.iter() {
2397 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2398 let a = BigInt::from_slice(Plus, a_vec);
2399 let b = BigInt::from_slice(Plus, b_vec);
2400 let c = BigInt::from_slice(Plus, c_vec);
2401 let d = BigInt::from_slice(Plus, d_vec);
2403 assert!(a == b * c + d);
2404 assert!(a == c * b + d);
2409 fn test_div_mod_floor() {
2410 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2411 let (d, m) = a.div_mod_floor(b);
2413 assert_eq!(m.sign, b.sign);
2415 assert!(m.abs() <= b.abs());
2416 assert!(*a == b * d + m);
2417 assert!(d == *ans_d);
2418 assert!(m == *ans_m);
2421 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2423 check_sub(a, b, d, m);
2424 check_sub(a, &b.neg(), &d.neg(), m);
2425 check_sub(&a.neg(), b, &d.neg(), m);
2426 check_sub(&a.neg(), &b.neg(), d, m);
2428 check_sub(a, b, d, m);
2429 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2430 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2431 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2435 for elm in mul_triples.iter() {
2436 let (a_vec, b_vec, c_vec) = *elm;
2437 let a = BigInt::from_slice(Plus, a_vec);
2438 let b = BigInt::from_slice(Plus, b_vec);
2439 let c = BigInt::from_slice(Plus, c_vec);
2441 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2442 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2445 for elm in div_rem_quadruples.iter() {
2446 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2447 let a = BigInt::from_slice(Plus, a_vec);
2448 let b = BigInt::from_slice(Plus, b_vec);
2449 let c = BigInt::from_slice(Plus, c_vec);
2450 let d = BigInt::from_slice(Plus, d_vec);
2453 check(&a, &b, &c, &d);
2461 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2462 let (q, r) = a.div_rem(b);
2464 assert_eq!(r.sign, a.sign);
2466 assert!(r.abs() <= b.abs());
2467 assert!(*a == b * q + r);
2468 assert!(q == *ans_q);
2469 assert!(r == *ans_r);
2472 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2473 check_sub(a, b, q, r);
2474 check_sub(a, &b.neg(), &q.neg(), r);
2475 check_sub(&a.neg(), b, &q.neg(), &r.neg());
2476 check_sub(&a.neg(), &b.neg(), q, &r.neg());
2478 for elm in mul_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 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2485 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2488 for elm in div_rem_quadruples.iter() {
2489 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2490 let a = BigInt::from_slice(Plus, a_vec);
2491 let b = BigInt::from_slice(Plus, b_vec);
2492 let c = BigInt::from_slice(Plus, c_vec);
2493 let d = BigInt::from_slice(Plus, d_vec);
2496 check(&a, &b, &c, &d);
2502 fn test_checked_add() {
2503 for elm in sum_triples.iter() {
2504 let (aVec, bVec, cVec) = *elm;
2505 let a = BigInt::from_slice(Plus, aVec);
2506 let b = BigInt::from_slice(Plus, bVec);
2507 let c = BigInt::from_slice(Plus, cVec);
2509 assert!(a.checked_add(&b).unwrap() == c);
2510 assert!(b.checked_add(&a).unwrap() == c);
2511 assert!(c.checked_add(&(-a)).unwrap() == b);
2512 assert!(c.checked_add(&(-b)).unwrap() == a);
2513 assert!(a.checked_add(&(-c)).unwrap() == (-b));
2514 assert!(b.checked_add(&(-c)).unwrap() == (-a));
2515 assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2516 assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2521 fn test_checked_sub() {
2522 for elm in sum_triples.iter() {
2523 let (aVec, bVec, cVec) = *elm;
2524 let a = BigInt::from_slice(Plus, aVec);
2525 let b = BigInt::from_slice(Plus, bVec);
2526 let c = BigInt::from_slice(Plus, cVec);
2528 assert!(c.checked_sub(&a).unwrap() == b);
2529 assert!(c.checked_sub(&b).unwrap() == a);
2530 assert!((-b).checked_sub(&a).unwrap() == (-c))
2531 assert!((-a).checked_sub(&b).unwrap() == (-c))
2532 assert!(b.checked_sub(&(-a)).unwrap() == c);
2533 assert!(a.checked_sub(&(-b)).unwrap() == c);
2534 assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2535 assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2540 fn test_checked_mul() {
2541 for elm in mul_triples.iter() {
2542 let (aVec, bVec, cVec) = *elm;
2543 let a = BigInt::from_slice(Plus, aVec);
2544 let b = BigInt::from_slice(Plus, bVec);
2545 let c = BigInt::from_slice(Plus, cVec);
2547 assert!(a.checked_mul(&b).unwrap() == c);
2548 assert!(b.checked_mul(&a).unwrap() == c);
2550 assert!((-a).checked_mul(&b).unwrap() == -c);
2551 assert!((-b).checked_mul(&a).unwrap() == -c);
2554 for elm in div_rem_quadruples.iter() {
2555 let (aVec, bVec, cVec, dVec) = *elm;
2556 let a = BigInt::from_slice(Plus, aVec);
2557 let b = BigInt::from_slice(Plus, bVec);
2558 let c = BigInt::from_slice(Plus, cVec);
2559 let d = BigInt::from_slice(Plus, dVec);
2561 assert!(a == b.checked_mul(&c).unwrap() + d);
2562 assert!(a == c.checked_mul(&b).unwrap() + d);
2566 fn test_checked_div() {
2567 for elm in mul_triples.iter() {
2568 let (aVec, bVec, cVec) = *elm;
2569 let a = BigInt::from_slice(Plus, aVec);
2570 let b = BigInt::from_slice(Plus, bVec);
2571 let c = BigInt::from_slice(Plus, cVec);
2574 assert!(c.checked_div(&a).unwrap() == b);
2575 assert!((-c).checked_div(&(-a)).unwrap() == b);
2576 assert!((-c).checked_div(&a).unwrap() == -b);
2579 assert!(c.checked_div(&b).unwrap() == a);
2580 assert!((-c).checked_div(&(-b)).unwrap() == a);
2581 assert!((-c).checked_div(&b).unwrap() == -a);
2584 assert!(c.checked_div(&Zero::zero()).is_none());
2585 assert!((-c).checked_div(&Zero::zero()).is_none());
2591 fn check(a: int, b: int, c: int) {
2592 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2593 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2594 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2596 assert_eq!(big_a.gcd(&big_b), big_c);
2611 fn check(a: int, b: int, c: int) {
2612 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2613 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2614 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2616 assert_eq!(big_a.lcm(&big_b), big_c);
2631 let zero: BigInt = Zero::zero();
2632 let one: BigInt = One::one();
2633 assert_eq!((-one).abs_sub(&one), zero);
2634 let one: BigInt = One::one();
2635 let zero: BigInt = Zero::zero();
2636 assert_eq!(one.abs_sub(&one), zero);
2637 let one: BigInt = One::one();
2638 let zero: BigInt = Zero::zero();
2639 assert_eq!(one.abs_sub(&zero), one);
2640 let one: BigInt = One::one();
2641 let two: BigInt = FromPrimitive::from_int(2).unwrap();
2642 assert_eq!(one.abs_sub(&-one), two);
2646 fn test_to_str_radix() {
2647 fn check(n: int, ans: &str) {
2648 let n: BigInt = FromPrimitive::from_int(n).unwrap();
2649 assert!(ans == n.to_str_radix(10));
2660 fn test_from_str_radix() {
2661 fn check(s: &str, ans: Option<int>) {
2662 let ans = ans.map(|n| {
2663 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2666 assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2668 check("10", Some(10));
2669 check("1", Some(1));
2670 check("0", Some(0));
2671 check("-1", Some(-1));
2672 check("-10", Some(-10));
2676 // issue 10522, this hit an edge case that caused it to
2677 // attempt to allocate a vector of size (-1u) == huge.
2678 let x: BigInt = from_str("1" + "0".repeat(36)).unwrap();
2679 let _y = x.to_str();
2684 assert!(-BigInt::new(Plus, vec!(1, 1, 1)) ==
2685 BigInt::new(Minus, vec!(1, 1, 1)));
2686 assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2687 BigInt::new(Plus, vec!(1, 1, 1)));
2688 let zero: BigInt = Zero::zero();
2689 assert_eq!(-zero, zero);
2694 let mut rng = task_rng();
2695 let _n: BigInt = rng.gen_bigint(137);
2696 assert!(rng.gen_bigint(0).is_zero());
2700 fn test_rand_range() {
2701 let mut rng = task_rng();
2703 for _ in range(0, 10) {
2704 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2705 &FromPrimitive::from_uint(237).unwrap()),
2706 FromPrimitive::from_uint(236).unwrap());
2709 fn check(l: BigInt, u: BigInt) {
2710 let mut rng = task_rng();
2711 for _ in range(0, 1000) {
2712 let n: BigInt = rng.gen_bigint_range(&l, &u);
2717 let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2718 let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2719 check( l.clone(), u.clone());
2720 check(-l.clone(), u.clone());
2721 check(-u.clone(), -l.clone());
2726 fn test_zero_rand_range() {
2727 task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2728 &FromPrimitive::from_int(54).unwrap());
2733 fn test_negative_rand_range() {
2734 let mut rng = task_rng();
2735 let l = FromPrimitive::from_uint(2352).unwrap();
2736 let u = FromPrimitive::from_uint(3513).unwrap();
2737 // Switching u and l should fail:
2738 let _n: BigInt = rng.gen_bigint_range(&u, &l);
2745 use self::test::Bencher;
2748 use std::mem::replace;
2749 use std::num::{FromPrimitive, Zero, One};
2751 fn factorial(n: uint) -> BigUint {
2752 let mut f: BigUint = One::one();
2753 for i in iter::range_inclusive(1, n) {
2754 f = f * FromPrimitive::from_uint(i).unwrap();
2759 fn fib(n: uint) -> BigUint {
2760 let mut f0: BigUint = Zero::zero();
2761 let mut f1: BigUint = One::one();
2762 for _ in range(0, n) {
2764 f0 = replace(&mut f1, f2);
2770 fn factorial_100(b: &mut Bencher) {
2777 fn fib_100(b: &mut Bencher) {
2784 fn to_str(b: &mut Bencher) {
2785 let fac = factorial(100);
2796 fn shr(b: &mut Bencher) {
2797 let n = { let one : BigUint = One::one(); one << 1000 };
2799 let mut m = n.clone();
2800 for _ in range(0, 10) {