1 // Copyright 2013 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 BigDigits.
16 A BigInt is a combination of BigUint and Sign.
19 #[allow(missing_doc)];
20 #[allow(non_uppercase_statics)];
22 use std::cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
25 use std::num::{IntConvertible, Zero, One, ToStrRadix, FromStrRadix, Orderable};
31 A BigDigit is a BigUint's composing element.
33 A BigDigit is half the size of machine word size.
35 #[cfg(target_arch = "x86")]
36 #[cfg(target_arch = "arm")]
37 #[cfg(target_arch = "mips")]
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_arch = "x86_64")]
46 pub type BigDigit = u32;
48 pub static ZERO_BIG_DIGIT: BigDigit = 0;
53 #[cfg(target_arch = "x86")]
54 #[cfg(target_arch = "arm")]
55 #[cfg(target_arch = "mips")]
56 pub static bits: uint = 16;
58 #[cfg(target_arch = "x86_64")]
59 pub static bits: uint = 32;
61 pub static base: uint = 1 << bits;
62 static hi_mask: uint = (-1 as uint) << bits;
63 static lo_mask: uint = (-1 as uint) >> bits;
66 fn get_hi(n: uint) -> BigDigit { (n >> bits) as BigDigit }
68 fn get_lo(n: uint) -> BigDigit { (n & lo_mask) as BigDigit }
70 /// Split one machine sized unsigned integer into two BigDigits.
72 pub fn from_uint(n: uint) -> (BigDigit, BigDigit) {
73 (get_hi(n), get_lo(n))
76 /// Join two BigDigits into one machine sized unsigned integer
78 pub fn to_uint(hi: BigDigit, lo: BigDigit) -> uint {
79 (lo as uint) | ((hi as uint) << bits)
84 A big unsigned integer type.
86 A BigUint-typed value BigUint { data: @[a, b, c] } represents a number
87 (a + b * BigDigit::base + c * BigDigit::base^2).
91 priv data: ~[BigDigit]
96 fn eq(&self, other: &BigUint) -> bool { self.equals(other) }
98 fn ne(&self, other: &BigUint) -> bool { !self.equals(other) }
101 impl TotalEq for BigUint {
103 fn equals(&self, other: &BigUint) -> bool {
104 match self.cmp(other) { Equal => true, _ => false }
108 impl Ord for BigUint {
110 fn lt(&self, other: &BigUint) -> bool {
111 match self.cmp(other) { Less => true, _ => false}
114 fn le(&self, other: &BigUint) -> bool {
115 match self.cmp(other) { Less | Equal => true, _ => false }
118 fn ge(&self, other: &BigUint) -> bool {
119 match self.cmp(other) { Greater | Equal => true, _ => false }
122 fn gt(&self, other: &BigUint) -> bool {
123 match self.cmp(other) { Greater => true, _ => false }
127 impl TotalOrd for BigUint {
129 fn cmp(&self, other: &BigUint) -> Ordering {
130 let (s_len, o_len) = (self.data.len(), other.data.len());
131 if s_len < o_len { return Less; }
132 if s_len > o_len { return Greater; }
134 for (&self_i, &other_i) in self.data.rev_iter().zip(other.data.rev_iter()) {
135 cond!((self_i < other_i) { return Less; }
136 (self_i > other_i) { return Greater; })
142 impl ToStr for BigUint {
144 fn to_str(&self) -> ~str { self.to_str_radix(10) }
147 impl FromStr for BigUint {
149 fn from_str(s: &str) -> Option<BigUint> {
150 FromStrRadix::from_str_radix(s, 10)
154 impl Num for BigUint {}
156 impl Orderable for BigUint {
158 fn min(&self, other: &BigUint) -> BigUint {
159 if self < other { self.clone() } else { other.clone() }
163 fn max(&self, other: &BigUint) -> BigUint {
164 if self > other { self.clone() } else { other.clone() }
168 fn clamp(&self, mn: &BigUint, mx: &BigUint) -> BigUint {
169 if self > mx { mx.clone() } else
170 if self < mn { mn.clone() } else { self.clone() }
174 impl Shl<uint, BigUint> for BigUint {
176 fn shl(&self, rhs: &uint) -> BigUint {
177 let n_unit = *rhs / BigDigit::bits;
178 let n_bits = *rhs % BigDigit::bits;
179 return self.shl_unit(n_unit).shl_bits(n_bits);
183 impl Shr<uint, BigUint> for BigUint {
185 fn shr(&self, rhs: &uint) -> BigUint {
186 let n_unit = *rhs / BigDigit::bits;
187 let n_bits = *rhs % BigDigit::bits;
188 return self.shr_unit(n_unit).shr_bits(n_bits);
192 impl Zero for BigUint {
194 fn zero() -> BigUint { BigUint::new(~[]) }
197 fn is_zero(&self) -> bool { self.data.is_empty() }
200 impl One for BigUint {
202 fn one() -> BigUint { BigUint::new(~[1]) }
205 impl Unsigned for BigUint {}
207 impl Add<BigUint, BigUint> for BigUint {
209 fn add(&self, other: &BigUint) -> BigUint {
210 let new_len = num::max(self.data.len(), other.data.len());
213 let mut sum = do vec::from_fn(new_len) |i| {
214 let ai = if i < self.data.len() { self.data[i] } else { 0 };
215 let bi = if i < other.data.len() { other.data[i] } else { 0 };
216 let (hi, lo) = BigDigit::from_uint(
217 (ai as uint) + (bi as uint) + (carry as uint)
222 if carry != 0 { sum.push(carry); }
223 return BigUint::new(sum);
227 impl Sub<BigUint, BigUint> for BigUint {
229 fn sub(&self, other: &BigUint) -> BigUint {
230 let new_len = num::max(self.data.len(), other.data.len());
233 let diff = do vec::from_fn(new_len) |i| {
234 let ai = if i < self.data.len() { self.data[i] } else { 0 };
235 let bi = if i < other.data.len() { other.data[i] } else { 0 };
236 let (hi, lo) = BigDigit::from_uint(
238 (ai as uint) - (bi as uint) - (borrow as uint)
241 hi * (base) + lo == 1*(base) + ai - bi - borrow
242 => ai - bi - borrow < 0 <=> hi == 0
244 borrow = if hi == 0 { 1 } else { 0 };
248 assert_eq!(borrow, 0); // <=> assert!((self >= other));
249 return BigUint::new(diff);
253 impl Mul<BigUint, BigUint> for BigUint {
254 fn mul(&self, other: &BigUint) -> BigUint {
255 if self.is_zero() || other.is_zero() { return Zero::zero(); }
257 let (s_len, o_len) = (self.data.len(), other.data.len());
258 if s_len == 1 { return mul_digit(other, self.data[0]); }
259 if o_len == 1 { return mul_digit(self, other.data[0]); }
261 // Using Karatsuba multiplication
262 // (a1 * base + a0) * (b1 * base + b0)
263 // = a1*b1 * base^2 +
264 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
266 let half_len = num::max(s_len, o_len) / 2;
267 let (sHi, sLo) = cut_at(self, half_len);
268 let (oHi, oLo) = cut_at(other, half_len);
273 let (s1, n1) = sub_sign(sHi, sLo);
274 let (s2, n2) = sub_sign(oHi, oLo);
276 (Equal, _) | (_, Equal) => hh + ll,
277 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
278 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
282 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
285 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
286 if n == 0 { return Zero::zero(); }
287 if n == 1 { return (*a).clone(); }
290 let mut prod = do a.data.iter().transform |ai| {
291 let (hi, lo) = BigDigit::from_uint(
292 (*ai as uint) * (n as uint) + (carry as uint)
296 }.collect::<~[BigDigit]>();
297 if carry != 0 { prod.push(carry); }
298 return BigUint::new(prod);
302 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
303 let mid = num::min(a.data.len(), n);
304 return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
305 BigUint::from_slice(a.data.slice(0, mid)));
309 fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
311 Less => (Less, b - a),
312 Greater => (Greater, a - b),
313 _ => (Equal, Zero::zero())
319 impl Div<BigUint, BigUint> for BigUint {
321 fn div(&self, other: &BigUint) -> BigUint {
322 let (q, _) = self.div_rem(other);
327 impl Rem<BigUint, BigUint> for BigUint {
329 fn rem(&self, other: &BigUint) -> BigUint {
330 let (_, r) = self.div_rem(other);
335 impl Neg<BigUint> for BigUint {
337 fn neg(&self) -> BigUint { fail!() }
340 impl Integer for BigUint {
342 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
343 self.div_mod_floor(other)
347 fn div_floor(&self, other: &BigUint) -> BigUint {
348 let (d, _) = self.div_mod_floor(other);
353 fn mod_floor(&self, other: &BigUint) -> BigUint {
354 let (_, m) = self.div_mod_floor(other);
359 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
360 if other.is_zero() { fail!() }
361 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
362 if *other == One::one() { return ((*self).clone(), Zero::zero()); }
364 match self.cmp(other) {
365 Less => return (Zero::zero(), (*self).clone()),
366 Equal => return (One::one(), Zero::zero()),
367 Greater => {} // Do nothing
371 let mut n = *other.data.last();
372 while n < (1 << BigDigit::bits - 2) {
376 assert!(shift < BigDigit::bits);
377 let (d, m) = div_mod_floor_inner(self << shift, other << shift);
378 return (d, m >> shift);
381 fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
383 let mut d = Zero::zero::<BigUint>();
386 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
388 let mut prod = b * d0;
390 // FIXME(#6050): overloaded operators force moves with generic types
393 // FIXME(#6050): overloaded operators force moves with generic types
394 // prod = prod - b_unit;
402 // FIXME(#6102): Assignment operator for BigInt causes ICE
405 // FIXME(#6102): Assignment operator for BigInt causes ICE
413 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
414 -> (BigUint, BigUint, BigUint) {
415 if a.data.len() < n {
416 return (Zero::zero(), Zero::zero(), (*a).clone());
419 let an = a.data.slice(a.data.len() - n, a.data.len());
420 let bn = *b.data.last();
423 for elt in an.rev_iter() {
424 let ai = BigDigit::to_uint(carry, *elt);
425 let di = ai / (bn as uint);
426 assert!(di < BigDigit::base);
427 carry = (ai % (bn as uint)) as BigDigit;
428 d = ~[di as BigDigit] + d;
431 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
433 return (BigUint::new(d), One::one(), (*b).clone());
435 return (BigUint::from_slice(d).shl_unit(shift),
436 One::one::<BigUint>().shl_unit(shift),
442 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
444 * The result is always positive
447 fn gcd(&self, other: &BigUint) -> BigUint {
448 // Use Euclid's algorithm
449 let mut m = (*self).clone();
450 let mut n = (*other).clone();
460 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
463 fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
465 /// Returns `true` if the number can be divided by `other` without leaving a remainder
467 fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
469 /// Returns `true` if the number is divisible by `2`
471 fn is_even(&self) -> bool {
472 // Considering only the last digit.
473 if self.data.is_empty() {
476 self.data[0].is_even()
480 /// Returns `true` if the number is not divisible by `2`
482 fn is_odd(&self) -> bool { !self.is_even() }
485 impl IntConvertible for BigUint {
487 fn to_int(&self) -> int {
488 num::min(self.to_uint(), int::max_value as uint) as int
492 fn from_int(n: int) -> BigUint {
493 if (n < 0) { Zero::zero() } else { BigUint::from_uint(n as uint) }
497 impl ToStrRadix for BigUint {
499 fn to_str_radix(&self, radix: uint) -> ~str {
500 assert!(1 < radix && radix <= 16);
501 let (base, max_len) = get_radix_base(radix);
502 if base == BigDigit::base {
503 return fill_concat(self.data, radix, max_len)
505 return fill_concat(convert_base((*self).clone(), base), radix, max_len);
508 fn convert_base(n: BigUint, base: uint) -> ~[BigDigit] {
509 let divider = BigUint::from_uint(base);
510 let mut result = ~[];
513 let (d, m0) = m.div_mod_floor(÷r);
514 result.push(m0.to_uint() as BigDigit);
518 result.push(m.to_uint() as BigDigit);
524 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> ~str {
525 if v.is_empty() { return ~"0" }
526 let mut s = str::with_capacity(v.len() * l);
527 for n in v.rev_iter() {
528 let ss = uint::to_str_radix(*n as uint, radix);
529 s.push_str("0".repeat(l - ss.len()));
532 s.trim_left_chars(&'0').to_owned()
537 impl FromStrRadix for BigUint {
538 /// Creates and initializes an BigUint.
540 pub fn from_str_radix(s: &str, radix: uint)
542 BigUint::parse_bytes(s.as_bytes(), radix)
547 /// Creates and initializes an BigUint.
549 pub fn new(v: ~[BigDigit]) -> BigUint {
550 // omit trailing zeros
551 let new_len = v.rposition(|n| *n != 0).map_move_default(0, |p| p + 1);
553 if new_len == v.len() { return BigUint { data: v }; }
556 return BigUint { data: v };
559 /// Creates and initializes an BigUint.
561 pub fn from_uint(n: uint) -> BigUint {
562 match BigDigit::from_uint(n) {
563 (0, 0) => Zero::zero(),
564 (0, n0) => BigUint::new(~[n0]),
565 (n1, n0) => BigUint::new(~[n0, n1])
569 /// Creates and initializes an BigUint.
571 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
572 return BigUint::new(slice.to_owned());
575 /// Creates and initializes an BigUint.
577 pub fn parse_bytes(buf: &[u8], radix: uint)
579 let (base, unit_len) = get_radix_base(radix);
580 let base_num: BigUint = BigUint::from_uint(base);
582 let mut end = buf.len();
583 let mut n: BigUint = Zero::zero();
584 let mut power: BigUint = One::one();
586 let start = num::max(end, unit_len) - unit_len;
587 match uint::parse_bytes(buf.slice(start, end), radix) {
588 // FIXME(#6102): Assignment operator for BigInt causes ICE
589 // Some(d) => n += BigUint::from_uint(d) * power,
590 Some(d) => n = n + BigUint::from_uint(d) * power,
597 // FIXME(#6050): overloaded operators force moves with generic types
598 // power *= base_num;
599 power = power * base_num;
604 /// Converts this big integer into a uint, returning the uint::max_value if
605 /// it's too large to fit in a uint.
606 pub fn to_uint(&self) -> uint {
607 match self.data.len() {
609 1 => self.data[0] as uint,
610 2 => BigDigit::to_uint(self.data[1], self.data[0]),
616 fn shl_unit(&self, n_unit: uint) -> BigUint {
617 if n_unit == 0 || self.is_zero() { return (*self).clone(); }
619 return BigUint::new(vec::from_elem(n_unit, ZERO_BIG_DIGIT)
624 fn shl_bits(&self, n_bits: uint) -> BigUint {
625 if n_bits == 0 || self.is_zero() { return (*self).clone(); }
628 let mut shifted = do self.data.iter().transform |elem| {
629 let (hi, lo) = BigDigit::from_uint(
630 (*elem as uint) << n_bits | (carry as uint)
634 }.collect::<~[BigDigit]>();
635 if carry != 0 { shifted.push(carry); }
636 return BigUint::new(shifted);
640 fn shr_unit(&self, n_unit: uint) -> BigUint {
641 if n_unit == 0 { return (*self).clone(); }
642 if self.data.len() < n_unit { return Zero::zero(); }
643 return BigUint::from_slice(
644 self.data.slice(n_unit, self.data.len())
649 fn shr_bits(&self, n_bits: uint) -> BigUint {
650 if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
653 let mut shifted = ~[];
654 for elem in self.data.rev_iter() {
655 shifted = ~[(*elem >> n_bits) | borrow] + shifted;
656 borrow = *elem << (BigDigit::bits - n_bits);
658 return BigUint::new(shifted);
662 #[cfg(target_arch = "x86_64")]
664 fn get_radix_base(radix: uint) -> (uint, uint) {
665 assert!(1 < radix && radix <= 16);
667 2 => (4294967296, 32),
668 3 => (3486784401, 20),
669 4 => (4294967296, 16),
670 5 => (1220703125, 13),
671 6 => (2176782336, 12),
672 7 => (1977326743, 11),
673 8 => (1073741824, 10),
674 9 => (3486784401, 10),
675 10 => (1000000000, 9),
676 11 => (2357947691, 9),
677 12 => (429981696, 8),
678 13 => (815730721, 8),
679 14 => (1475789056, 8),
680 15 => (2562890625, 8),
681 16 => (4294967296, 8),
686 #[cfg(target_arch = "arm")]
687 #[cfg(target_arch = "x86")]
688 #[cfg(target_arch = "mips")]
690 fn get_radix_base(radix: uint) -> (uint, uint) {
691 assert!(1 < radix && radix <= 16);
712 /// A Sign is a BigInt's composing element.
713 #[deriving(Eq, Clone)]
714 pub enum Sign { Minus, Zero, Plus }
718 fn lt(&self, other: &Sign) -> bool {
719 match self.cmp(other) { Less => true, _ => false}
722 fn le(&self, other: &Sign) -> bool {
723 match self.cmp(other) { Less | Equal => true, _ => false }
726 fn ge(&self, other: &Sign) -> bool {
727 match self.cmp(other) { Greater | Equal => true, _ => false }
730 fn gt(&self, other: &Sign) -> bool {
731 match self.cmp(other) { Greater => true, _ => false }
735 impl TotalEq for Sign {
736 fn equals(&self, other: &Sign) -> bool {
740 impl TotalOrd for Sign {
742 fn cmp(&self, other: &Sign) -> Ordering {
743 match (*self, *other) {
744 (Minus, Minus) | (Zero, Zero) | (Plus, Plus) => Equal,
745 (Minus, Zero) | (Minus, Plus) | (Zero, Plus) => Less,
751 impl Neg<Sign> for Sign {
752 /// Negate Sign value.
754 fn neg(&self) -> Sign {
763 /// A big signed integer type.
772 fn eq(&self, other: &BigInt) -> bool { self.equals(other) }
774 fn ne(&self, other: &BigInt) -> bool { !self.equals(other) }
777 impl TotalEq for BigInt {
779 fn equals(&self, other: &BigInt) -> bool {
780 match self.cmp(other) { Equal => true, _ => false }
784 impl Ord for BigInt {
786 fn lt(&self, other: &BigInt) -> bool {
787 match self.cmp(other) { Less => true, _ => false}
790 fn le(&self, other: &BigInt) -> bool {
791 match self.cmp(other) { Less | Equal => true, _ => false }
794 fn ge(&self, other: &BigInt) -> bool {
795 match self.cmp(other) { Greater | Equal => true, _ => false }
798 fn gt(&self, other: &BigInt) -> bool {
799 match self.cmp(other) { Greater => true, _ => false }
803 impl TotalOrd for BigInt {
805 fn cmp(&self, other: &BigInt) -> Ordering {
806 let scmp = self.sign.cmp(&other.sign);
807 if scmp != Equal { return scmp; }
811 Plus => self.data.cmp(&other.data),
812 Minus => other.data.cmp(&self.data),
817 impl ToStr for BigInt {
819 fn to_str(&self) -> ~str { self.to_str_radix(10) }
822 impl FromStr for BigInt {
824 fn from_str(s: &str) -> Option<BigInt> {
825 FromStrRadix::from_str_radix(s, 10)
829 impl Num for BigInt {}
831 impl Orderable for BigInt {
833 fn min(&self, other: &BigInt) -> BigInt {
834 if self < other { self.clone() } else { other.clone() }
838 fn max(&self, other: &BigInt) -> BigInt {
839 if self > other { self.clone() } else { other.clone() }
843 fn clamp(&self, mn: &BigInt, mx: &BigInt) -> BigInt {
844 if self > mx { mx.clone() } else
845 if self < mn { mn.clone() } else { self.clone() }
849 impl Shl<uint, BigInt> for BigInt {
851 fn shl(&self, rhs: &uint) -> BigInt {
852 BigInt::from_biguint(self.sign, self.data << *rhs)
856 impl Shr<uint, BigInt> for BigInt {
858 fn shr(&self, rhs: &uint) -> BigInt {
859 BigInt::from_biguint(self.sign, self.data >> *rhs)
863 impl Zero for BigInt {
865 fn zero() -> BigInt {
866 BigInt::from_biguint(Zero, Zero::zero())
870 fn is_zero(&self) -> bool { self.sign == Zero }
873 impl One for BigInt {
876 BigInt::from_biguint(Plus, One::one())
880 impl Signed for BigInt {
882 fn abs(&self) -> BigInt {
884 Plus | Zero => self.clone(),
885 Minus => BigInt::from_biguint(Plus, self.data.clone())
890 fn abs_sub(&self, other: &BigInt) -> BigInt {
891 if *self <= *other { Zero::zero() } else { *self - *other }
895 fn signum(&self) -> BigInt {
897 Plus => BigInt::from_biguint(Plus, One::one()),
898 Minus => BigInt::from_biguint(Minus, One::one()),
899 Zero => Zero::zero(),
904 fn is_positive(&self) -> bool { self.sign == Plus }
907 fn is_negative(&self) -> bool { self.sign == Minus }
910 impl Add<BigInt, BigInt> for BigInt {
912 fn add(&self, other: &BigInt) -> BigInt {
913 match (self.sign, other.sign) {
914 (Zero, _) => other.clone(),
915 (_, Zero) => self.clone(),
916 (Plus, Plus) => BigInt::from_biguint(Plus,
917 self.data + other.data),
918 (Plus, Minus) => self - (-*other),
919 (Minus, Plus) => other - (-*self),
920 (Minus, Minus) => -((-self) + (-*other))
925 impl Sub<BigInt, BigInt> for BigInt {
927 fn sub(&self, other: &BigInt) -> BigInt {
928 match (self.sign, other.sign) {
930 (_, Zero) => self.clone(),
931 (Plus, Plus) => match self.data.cmp(&other.data) {
932 Less => BigInt::from_biguint(Minus, other.data - self.data),
933 Greater => BigInt::from_biguint(Plus, self.data - other.data),
934 Equal => Zero::zero()
936 (Plus, Minus) => self + (-*other),
937 (Minus, Plus) => -((-self) + *other),
938 (Minus, Minus) => (-other) - (-*self)
943 impl Mul<BigInt, BigInt> for BigInt {
945 fn mul(&self, other: &BigInt) -> BigInt {
946 match (self.sign, other.sign) {
947 (Zero, _) | (_, Zero) => Zero::zero(),
948 (Plus, Plus) | (Minus, Minus) => {
949 BigInt::from_biguint(Plus, self.data * other.data)
951 (Plus, Minus) | (Minus, Plus) => {
952 BigInt::from_biguint(Minus, self.data * other.data)
958 impl Div<BigInt, BigInt> for BigInt {
960 fn div(&self, other: &BigInt) -> BigInt {
961 let (q, _) = self.div_rem(other);
966 impl Rem<BigInt, BigInt> for BigInt {
968 fn rem(&self, other: &BigInt) -> BigInt {
969 let (_, r) = self.div_rem(other);
974 impl Neg<BigInt> for BigInt {
976 fn neg(&self) -> BigInt {
977 BigInt::from_biguint(self.sign.neg(), self.data.clone())
981 impl Integer for BigInt {
983 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
984 // r.sign == self.sign
985 let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
986 let d = BigInt::from_biguint(Plus, d_ui);
987 let r = BigInt::from_biguint(Plus, r_ui);
988 match (self.sign, other.sign) {
989 (_, Zero) => fail!(),
990 (Plus, Plus) | (Zero, Plus) => ( d, r),
991 (Plus, Minus) | (Zero, Minus) => (-d, r),
992 (Minus, Plus) => (-d, -r),
993 (Minus, Minus) => ( d, -r)
998 fn div_floor(&self, other: &BigInt) -> BigInt {
999 let (d, _) = self.div_mod_floor(other);
1004 fn mod_floor(&self, other: &BigInt) -> BigInt {
1005 let (_, m) = self.div_mod_floor(other);
1010 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1011 // m.sign == other.sign
1012 let (d_ui, m_ui) = self.data.div_rem(&other.data);
1013 let d = BigInt::from_biguint(Plus, d_ui);
1014 let m = BigInt::from_biguint(Plus, m_ui);
1015 match (self.sign, other.sign) {
1016 (_, Zero) => fail!(),
1017 (Plus, Plus) | (Zero, Plus) => (d, m),
1018 (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1021 (-d - One::one(), m + *other)
1023 (Minus, Plus) => if m.is_zero() {
1026 (-d - One::one(), other - m)
1028 (Minus, Minus) => (d, -m)
1033 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
1035 * The result is always positive
1038 fn gcd(&self, other: &BigInt) -> BigInt {
1039 BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1043 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
1046 fn lcm(&self, other: &BigInt) -> BigInt {
1047 BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1050 /// Returns `true` if the number can be divided by `other` without leaving a remainder
1052 fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
1054 /// Returns `true` if the number is divisible by `2`
1056 fn is_even(&self) -> bool { self.data.is_even() }
1058 /// Returns `true` if the number is not divisible by `2`
1060 fn is_odd(&self) -> bool { self.data.is_odd() }
1063 impl IntConvertible for BigInt {
1065 fn to_int(&self) -> int {
1067 Plus => num::min(self.to_uint(), int::max_value as uint) as int,
1069 Minus => num::min((-self).to_uint(),
1070 (int::max_value as uint) + 1) as int
1075 fn from_int(n: int) -> BigInt {
1077 return BigInt::from_biguint(Plus, BigUint::from_uint(n as uint));
1080 return BigInt::from_biguint(
1081 Minus, BigUint::from_uint(uint::max_value - (n as uint) + 1)
1084 return Zero::zero();
1088 impl ToStrRadix for BigInt {
1090 fn to_str_radix(&self, radix: uint) -> ~str {
1092 Plus => self.data.to_str_radix(radix),
1094 Minus => ~"-" + self.data.to_str_radix(radix)
1099 impl FromStrRadix for BigInt {
1100 /// Creates and initializes an BigInt.
1102 fn from_str_radix(s: &str, radix: uint)
1104 BigInt::parse_bytes(s.as_bytes(), radix)
1109 /// Creates and initializes an BigInt.
1110 pub fn new(sign: Sign, v: ~[BigDigit]) -> BigInt {
1111 BigInt::from_biguint(sign, BigUint::new(v))
1114 /// Creates and initializes an BigInt.
1116 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1117 if sign == Zero || data.is_zero() {
1118 return BigInt { sign: Zero, data: Zero::zero() };
1120 return BigInt { sign: sign, data: data };
1123 /// Creates and initializes an BigInt.
1125 pub fn from_uint(n: uint) -> BigInt {
1126 if n == 0 { return Zero::zero(); }
1127 return BigInt::from_biguint(Plus, BigUint::from_uint(n));
1130 /// Creates and initializes an BigInt.
1132 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1133 BigInt::from_biguint(sign, BigUint::from_slice(slice))
1136 /// Creates and initializes an BigInt.
1138 pub fn parse_bytes(buf: &[u8], radix: uint)
1140 if buf.is_empty() { return None; }
1141 let mut sign = Plus;
1143 if buf[0] == ('-' as u8) {
1147 return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1148 .map_move(|bu| BigInt::from_biguint(sign, bu));
1151 pub fn to_uint(&self) -> uint {
1153 Plus => self.data.to_uint(),
1165 use std::cmp::{Less, Equal, Greater};
1167 use std::num::{IntConvertible, Zero, One, FromStrRadix};
1173 fn test_from_slice() {
1174 fn check(slice: &[BigDigit], data: &[BigDigit]) {
1175 assert!(data == BigUint::from_slice(slice).data);
1178 check([0, 0, 0], []);
1179 check([1, 2, 0, 0], [1, 2]);
1180 check([0, 0, 1, 2], [0, 0, 1, 2]);
1181 check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1187 let data: ~[BigUint] = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ]
1188 .map(|v| BigUint::from_slice(*v));
1189 for (i, ni) in data.iter().enumerate() {
1190 for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1193 assert_eq!(ni.cmp(nj), Equal);
1194 assert_eq!(nj.cmp(ni), Equal);
1196 assert!(!(ni != nj));
1199 assert!(!(ni < nj));
1200 assert!(!(ni > nj));
1202 assert_eq!(ni.cmp(nj), Less);
1203 assert_eq!(nj.cmp(ni), Greater);
1205 assert!(!(ni == nj));
1209 assert!(!(ni >= nj));
1211 assert!(!(ni > nj));
1213 assert!(!(nj <= ni));
1215 assert!(!(nj < ni));
1224 fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
1225 assert_eq!(BigUint::new(v) << shift, BigUint::new(ans));
1229 check(~[1, 1, 1], 3, ~[1 << 3, 1 << 3, 1 << 3]);
1230 check(~[1 << (BigDigit::bits - 2)], 2, ~[0, 1]);
1231 check(~[1 << (BigDigit::bits - 2)], 3, ~[0, 2]);
1232 check(~[1 << (BigDigit::bits - 2)], 3 + BigDigit::bits, ~[0, 0, 2]);
1236 #[cfg(target_arch = "x86_64")]
1237 fn test_shl_bits() {
1238 check(~[0x7654_3210, 0xfedc_ba98,
1239 0x7654_3210, 0xfedc_ba98], 4,
1240 ~[0x6543_2100, 0xedcb_a987,
1241 0x6543_210f, 0xedcb_a987, 0xf]);
1242 check(~[0x2222_1111, 0x4444_3333,
1243 0x6666_5555, 0x8888_7777], 16,
1244 ~[0x1111_0000, 0x3333_2222,
1245 0x5555_4444, 0x7777_6666, 0x8888]);
1248 #[cfg(target_arch = "arm")]
1249 #[cfg(target_arch = "x86")]
1250 #[cfg(target_arch = "mips")]
1251 fn test_shl_bits() {
1252 check(~[0x3210, 0x7654, 0xba98, 0xfedc,
1253 0x3210, 0x7654, 0xba98, 0xfedc], 4,
1254 ~[0x2100, 0x6543, 0xa987, 0xedcb,
1255 0x210f, 0x6543, 0xa987, 0xedcb, 0xf]);
1256 check(~[0x1111, 0x2222, 0x3333, 0x4444,
1257 0x5555, 0x6666, 0x7777, 0x8888], 16,
1258 ~[0x0000, 0x1111, 0x2222, 0x3333,
1259 0x4444, 0x5555, 0x6666, 0x7777, 0x8888]);
1265 #[ignore(cfg(target_arch = "x86"))]
1266 #[ignore(cfg(target_arch = "arm"))]
1267 #[ignore(cfg(target_arch = "mips"))]
1269 fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
1270 assert_eq!(BigUint::new(v) >> shift, BigUint::new(ans));
1274 check(~[1, 1, 1], 3,
1275 ~[1 << (BigDigit::bits - 3), 1 << (BigDigit::bits - 3)]);
1276 check(~[1 << 2], 2, ~[1]);
1277 check(~[1, 2], 3, ~[1 << (BigDigit::bits - 2)]);
1278 check(~[1, 1, 2], 3 + BigDigit::bits, ~[1 << (BigDigit::bits - 2)]);
1279 check(~[0, 1], 1, ~[0x80000000]);
1282 #[cfg(target_arch = "x86_64")]
1283 fn test_shr_bits() {
1284 check(~[0x6543_2100, 0xedcb_a987,
1285 0x6543_210f, 0xedcb_a987, 0xf], 4,
1286 ~[0x7654_3210, 0xfedc_ba98,
1287 0x7654_3210, 0xfedc_ba98]);
1288 check(~[0x1111_0000, 0x3333_2222,
1289 0x5555_4444, 0x7777_6666, 0x8888], 16,
1290 ~[0x2222_1111, 0x4444_3333,
1291 0x6666_5555, 0x8888_7777]);
1294 #[cfg(target_arch = "arm")]
1295 #[cfg(target_arch = "x86")]
1296 #[cfg(target_arch = "mips")]
1297 fn test_shr_bits() {
1298 check(~[0x2100, 0x6543, 0xa987, 0xedcb,
1299 0x210f, 0x6543, 0xa987, 0xedcb, 0xf], 4,
1300 ~[0x3210, 0x7654, 0xba98, 0xfedc,
1301 0x3210, 0x7654, 0xba98, 0xfedc]);
1302 check(~[0x0000, 0x1111, 0x2222, 0x3333,
1303 0x4444, 0x5555, 0x6666, 0x7777, 0x8888], 16,
1304 ~[0x1111, 0x2222, 0x3333, 0x4444,
1305 0x5555, 0x6666, 0x7777, 0x8888]);
1310 fn test_convert_int() {
1311 fn check(v: ~[BigDigit], i: int) {
1312 let b = BigUint::new(v);
1313 assert!(b == IntConvertible::from_int(i));
1314 assert!(b.to_int() == i);
1319 check(~[-1], (uint::max_value >> BigDigit::bits) as int);
1320 check(~[ 0, 1], ((uint::max_value >> BigDigit::bits) + 1) as int);
1321 check(~[-1, -1 >> 1], int::max_value);
1323 assert_eq!(BigUint::new(~[0, -1]).to_int(), int::max_value);
1324 assert_eq!(BigUint::new(~[0, 0, 1]).to_int(), int::max_value);
1325 assert_eq!(BigUint::new(~[0, 0, -1]).to_int(), int::max_value);
1329 fn test_convert_uint() {
1330 fn check(v: ~[BigDigit], u: uint) {
1331 let b = BigUint::new(v);
1332 assert!(b == BigUint::from_uint(u));
1333 assert!(b.to_uint() == u);
1338 check(~[-1], uint::max_value >> BigDigit::bits);
1339 check(~[ 0, 1], (uint::max_value >> BigDigit::bits) + 1);
1340 check(~[ 0, -1], uint::max_value << BigDigit::bits);
1341 check(~[-1, -1], uint::max_value);
1343 assert_eq!(BigUint::new(~[0, 0, 1]).to_uint(), uint::max_value);
1344 assert_eq!(BigUint::new(~[0, 0, -1]).to_uint(), uint::max_value);
1347 static sum_triples: &'static [(&'static [BigDigit],
1348 &'static [BigDigit],
1349 &'static [BigDigit])] = &[
1351 (&[], &[ 1], &[ 1]),
1352 (&[ 1], &[ 1], &[ 2]),
1353 (&[ 1], &[ 1, 1], &[ 2, 1]),
1354 (&[ 1], &[-1], &[ 0, 1]),
1355 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1356 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1357 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1358 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1363 for elm in sum_triples.iter() {
1364 let (aVec, bVec, cVec) = *elm;
1365 let a = BigUint::from_slice(aVec);
1366 let b = BigUint::from_slice(bVec);
1367 let c = BigUint::from_slice(cVec);
1369 assert!(a + b == c);
1370 assert!(b + a == c);
1376 for elm in sum_triples.iter() {
1377 let (aVec, bVec, cVec) = *elm;
1378 let a = BigUint::from_slice(aVec);
1379 let b = BigUint::from_slice(bVec);
1380 let c = BigUint::from_slice(cVec);
1382 assert!(c - a == b);
1383 assert!(c - b == a);
1387 static mul_triples: &'static [(&'static [BigDigit],
1388 &'static [BigDigit],
1389 &'static [BigDigit])] = &[
1393 (&[ 1], &[ 1], &[1]),
1394 (&[ 2], &[ 3], &[ 6]),
1395 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1396 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1397 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1398 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1399 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1400 (&[-1], &[-1], &[ 1, -2]),
1401 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1402 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1403 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1404 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1405 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1406 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1407 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1408 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1409 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1410 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1413 static div_rem_quadruples: &'static [(&'static [BigDigit],
1414 &'static [BigDigit],
1415 &'static [BigDigit],
1416 &'static [BigDigit])]
1418 (&[ 1], &[ 2], &[], &[1]),
1419 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1420 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1421 (&[ 0, 1], &[-1], &[1], &[1]),
1422 (&[-1, -1], &[-2], &[2, 1], &[3])
1427 for elm in mul_triples.iter() {
1428 let (aVec, bVec, cVec) = *elm;
1429 let a = BigUint::from_slice(aVec);
1430 let b = BigUint::from_slice(bVec);
1431 let c = BigUint::from_slice(cVec);
1433 assert!(a * b == c);
1434 assert!(b * a == c);
1437 for elm in div_rem_quadruples.iter() {
1438 let (aVec, bVec, cVec, dVec) = *elm;
1439 let a = BigUint::from_slice(aVec);
1440 let b = BigUint::from_slice(bVec);
1441 let c = BigUint::from_slice(cVec);
1442 let d = BigUint::from_slice(dVec);
1444 assert!(a == b * c + d);
1445 assert!(a == c * b + d);
1451 for elm in mul_triples.iter() {
1452 let (aVec, bVec, cVec) = *elm;
1453 let a = BigUint::from_slice(aVec);
1454 let b = BigUint::from_slice(bVec);
1455 let c = BigUint::from_slice(cVec);
1458 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1461 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1465 for elm in div_rem_quadruples.iter() {
1466 let (aVec, bVec, cVec, dVec) = *elm;
1467 let a = BigUint::from_slice(aVec);
1468 let b = BigUint::from_slice(bVec);
1469 let c = BigUint::from_slice(cVec);
1470 let d = BigUint::from_slice(dVec);
1472 if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1478 fn check(a: uint, b: uint, c: uint) {
1479 let big_a = BigUint::from_uint(a);
1480 let big_b = BigUint::from_uint(b);
1481 let big_c = BigUint::from_uint(c);
1483 assert_eq!(big_a.gcd(&big_b), big_c);
1495 fn check(a: uint, b: uint, c: uint) {
1496 let big_a = BigUint::from_uint(a);
1497 let big_b = BigUint::from_uint(b);
1498 let big_c = BigUint::from_uint(c);
1500 assert_eq!(big_a.lcm(&big_b), big_c);
1508 check(99, 17, 1683);
1513 assert!(FromStr::from_str::<BigUint>("1").unwrap().is_odd());
1514 assert!(FromStr::from_str::<BigUint>("2").unwrap().is_even());
1515 assert!(FromStr::from_str::<BigUint>("1000").unwrap().is_even());
1516 assert!(FromStr::from_str::<BigUint>("1000000000000000000000").unwrap().is_even());
1517 assert!(FromStr::from_str::<BigUint>("1000000000000000000001").unwrap().is_odd());
1518 assert!((BigUint::from_uint(1) << 64).is_even());
1519 assert!(((BigUint::from_uint(1) << 64) + BigUint::from_uint(1)).is_odd());
1522 fn to_str_pairs() -> ~[ (BigUint, ~[(uint, ~str)]) ] {
1523 let bits = BigDigit::bits;
1524 ~[( Zero::zero(), ~[
1525 (2, ~"0"), (3, ~"0")
1526 ]), ( BigUint::from_slice([ 0xff ]), ~[
1542 ]), ( BigUint::from_slice([ 0xfff ]), ~[
1543 (2, ~"111111111111"),
1546 ]), ( BigUint::from_slice([ 1, 2 ]), ~[
1549 str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1552 str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1554 32 => ~"8589934593", 16 => ~"131073", _ => fail!()
1558 str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1559 ]), ( BigUint::from_slice([ 1, 2, 3 ]), ~[
1562 str::from_chars(vec::from_elem(bits - 2, '0')) + "10" +
1563 str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1566 str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "2" +
1567 str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1569 32 => ~"55340232229718589441",
1570 16 => ~"12885032961",
1574 str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "2" +
1575 str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1580 fn test_to_str_radix() {
1581 let r = to_str_pairs();
1582 for num_pair in r.iter() {
1583 let &(ref n, ref rs) = num_pair;
1584 for str_pair in rs.iter() {
1585 let &(ref radix, ref str) = str_pair;
1586 assert_eq!(&n.to_str_radix(*radix), str);
1592 fn test_from_str_radix() {
1593 let r = to_str_pairs();
1594 for num_pair in r.iter() {
1595 let &(ref n, ref rs) = num_pair;
1596 for str_pair in rs.iter() {
1597 let &(ref radix, ref str) = str_pair;
1598 assert_eq!(n, &FromStrRadix::from_str_radix(*str, *radix).unwrap());
1602 assert_eq!(FromStrRadix::from_str_radix::<BigUint>("Z", 10), None);
1603 assert_eq!(FromStrRadix::from_str_radix::<BigUint>("_", 2), None);
1604 assert_eq!(FromStrRadix::from_str_radix::<BigUint>("-1", 10), None);
1609 fn factor(n: uint) -> BigUint {
1610 let mut f= One::one::<BigUint>();
1611 for i in range(2, n + 1) {
1612 // FIXME(#6102): Assignment operator for BigInt causes ICE
1613 // f *= BigUint::from_uint(i);
1614 f = f * BigUint::from_uint(i);
1619 fn check(n: uint, s: &str) {
1621 let ans = match FromStrRadix::from_str_radix(s, 10) {
1622 Some(x) => x, None => fail!()
1628 check(10, "3628800");
1629 check(20, "2432902008176640000");
1630 check(30, "265252859812191058636308480000000");
1639 use std::cmp::{Less, Equal, Greater};
1641 use std::num::{IntConvertible, Zero, One, FromStrRadix};
1645 fn test_from_biguint() {
1646 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
1647 let inp = BigInt::from_biguint(inp_s, BigUint::from_uint(inp_n));
1648 let ans = BigInt { sign: ans_s, data: BigUint::from_uint(ans_n)};
1649 assert_eq!(inp, ans);
1651 check(Plus, 1, Plus, 1);
1652 check(Plus, 0, Zero, 0);
1653 check(Minus, 1, Minus, 1);
1654 check(Zero, 1, Zero, 0);
1659 let vs = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
1661 for s in vs.rev_iter() {
1662 nums.push(BigInt::from_slice(Minus, *s));
1664 nums.push(Zero::zero());
1665 nums.push_all_move(vs.map(|s| BigInt::from_slice(Plus, *s)));
1667 for (i, ni) in nums.iter().enumerate() {
1668 for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
1671 assert_eq!(ni.cmp(nj), Equal);
1672 assert_eq!(nj.cmp(ni), Equal);
1674 assert!(!(ni != nj));
1677 assert!(!(ni < nj));
1678 assert!(!(ni > nj));
1680 assert_eq!(ni.cmp(nj), Less);
1681 assert_eq!(nj.cmp(ni), Greater);
1683 assert!(!(ni == nj));
1687 assert!(!(ni >= nj));
1689 assert!(!(ni > nj));
1691 assert!(!(nj <= ni));
1693 assert!(!(nj < ni));
1701 fn test_convert_int() {
1702 fn check(b: BigInt, i: int) {
1703 assert!(b == IntConvertible::from_int(i));
1704 assert!(b.to_int() == i);
1707 check(Zero::zero(), 0);
1708 check(One::one(), 1);
1709 check(BigInt::from_biguint(
1710 Plus, BigUint::from_uint(int::max_value as uint)
1713 assert!(BigInt::from_biguint(
1714 Plus, BigUint::from_uint(int::max_value as uint + 1)
1715 ).to_int() == int::max_value);
1716 assert!(BigInt::from_biguint(
1717 Plus, BigUint::new(~[1, 2, 3])
1718 ).to_int() == int::max_value);
1720 check(BigInt::from_biguint(
1721 Minus, BigUint::from_uint(-int::min_value as uint)
1723 assert!(BigInt::from_biguint(
1724 Minus, BigUint::from_uint(-int::min_value as uint + 1)
1725 ).to_int() == int::min_value);
1726 assert!(BigInt::from_biguint(
1727 Minus, BigUint::new(~[1, 2, 3])
1728 ).to_int() == int::min_value);
1732 fn test_convert_uint() {
1733 fn check(b: BigInt, u: uint) {
1734 assert!(b == BigInt::from_uint(u));
1735 assert!(b.to_uint() == u);
1738 check(Zero::zero(), 0);
1739 check(One::one(), 1);
1742 BigInt::from_biguint(Plus, BigUint::from_uint(uint::max_value)),
1744 assert!(BigInt::from_biguint(
1745 Plus, BigUint::new(~[1, 2, 3])
1746 ).to_uint() == uint::max_value);
1748 assert!(BigInt::from_biguint(
1749 Minus, BigUint::from_uint(uint::max_value)
1751 assert!(BigInt::from_biguint(
1752 Minus, BigUint::new(~[1, 2, 3])
1756 static sum_triples: &'static [(&'static [BigDigit],
1757 &'static [BigDigit],
1758 &'static [BigDigit])] = &[
1760 (&[], &[ 1], &[ 1]),
1761 (&[ 1], &[ 1], &[ 2]),
1762 (&[ 1], &[ 1, 1], &[ 2, 1]),
1763 (&[ 1], &[-1], &[ 0, 1]),
1764 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1765 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1766 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1767 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1772 for elm in sum_triples.iter() {
1773 let (aVec, bVec, cVec) = *elm;
1774 let a = BigInt::from_slice(Plus, aVec);
1775 let b = BigInt::from_slice(Plus, bVec);
1776 let c = BigInt::from_slice(Plus, cVec);
1778 assert!(a + b == c);
1779 assert!(b + a == c);
1780 assert!(c + (-a) == b);
1781 assert!(c + (-b) == a);
1782 assert!(a + (-c) == (-b));
1783 assert!(b + (-c) == (-a));
1784 assert!((-a) + (-b) == (-c))
1785 assert!(a + (-a) == Zero::zero());
1791 for elm in sum_triples.iter() {
1792 let (aVec, bVec, cVec) = *elm;
1793 let a = BigInt::from_slice(Plus, aVec);
1794 let b = BigInt::from_slice(Plus, bVec);
1795 let c = BigInt::from_slice(Plus, cVec);
1797 assert!(c - a == b);
1798 assert!(c - b == a);
1799 assert!((-b) - a == (-c))
1800 assert!((-a) - b == (-c))
1801 assert!(b - (-a) == c);
1802 assert!(a - (-b) == c);
1803 assert!((-c) - (-a) == (-b));
1804 assert!(a - a == Zero::zero());
1808 static mul_triples: &'static [(&'static [BigDigit],
1809 &'static [BigDigit],
1810 &'static [BigDigit])] = &[
1814 (&[ 1], &[ 1], &[1]),
1815 (&[ 2], &[ 3], &[ 6]),
1816 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1817 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1818 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1819 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1820 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1821 (&[-1], &[-1], &[ 1, -2]),
1822 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1823 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1824 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1825 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1826 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1827 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1828 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1829 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1830 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1831 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1834 static div_rem_quadruples: &'static [(&'static [BigDigit],
1835 &'static [BigDigit],
1836 &'static [BigDigit],
1837 &'static [BigDigit])]
1839 (&[ 1], &[ 2], &[], &[1]),
1840 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1841 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1842 (&[ 0, 1], &[-1], &[1], &[1]),
1843 (&[-1, -1], &[-2], &[2, 1], &[3])
1848 for elm in mul_triples.iter() {
1849 let (aVec, bVec, cVec) = *elm;
1850 let a = BigInt::from_slice(Plus, aVec);
1851 let b = BigInt::from_slice(Plus, bVec);
1852 let c = BigInt::from_slice(Plus, cVec);
1854 assert!(a * b == c);
1855 assert!(b * a == c);
1857 assert!((-a) * b == -c);
1858 assert!((-b) * a == -c);
1861 for elm in div_rem_quadruples.iter() {
1862 let (aVec, bVec, cVec, dVec) = *elm;
1863 let a = BigInt::from_slice(Plus, aVec);
1864 let b = BigInt::from_slice(Plus, bVec);
1865 let c = BigInt::from_slice(Plus, cVec);
1866 let d = BigInt::from_slice(Plus, dVec);
1868 assert!(a == b * c + d);
1869 assert!(a == c * b + d);
1874 fn test_div_mod_floor() {
1875 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
1876 let (d, m) = a.div_mod_floor(b);
1878 assert_eq!(m.sign, b.sign);
1880 assert!(m.abs() <= b.abs());
1881 assert!(*a == b * d + m);
1882 assert!(d == *ans_d);
1883 assert!(m == *ans_m);
1886 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
1888 check_sub(a, b, d, m);
1889 check_sub(a, &b.neg(), &d.neg(), m);
1890 check_sub(&a.neg(), b, &d.neg(), m);
1891 check_sub(&a.neg(), &b.neg(), d, m);
1893 check_sub(a, b, d, m);
1894 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
1895 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
1896 check_sub(&a.neg(), &b.neg(), d, &m.neg());
1900 for elm in mul_triples.iter() {
1901 let (aVec, bVec, cVec) = *elm;
1902 let a = BigInt::from_slice(Plus, aVec);
1903 let b = BigInt::from_slice(Plus, bVec);
1904 let c = BigInt::from_slice(Plus, cVec);
1906 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1907 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1910 for elm in div_rem_quadruples.iter() {
1911 let (aVec, bVec, cVec, dVec) = *elm;
1912 let a = BigInt::from_slice(Plus, aVec);
1913 let b = BigInt::from_slice(Plus, bVec);
1914 let c = BigInt::from_slice(Plus, cVec);
1915 let d = BigInt::from_slice(Plus, dVec);
1918 check(&a, &b, &c, &d);
1926 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
1927 let (q, r) = a.div_rem(b);
1929 assert_eq!(r.sign, a.sign);
1931 assert!(r.abs() <= b.abs());
1932 assert!(*a == b * q + r);
1933 assert!(q == *ans_q);
1934 assert!(r == *ans_r);
1937 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
1938 check_sub(a, b, q, r);
1939 check_sub(a, &b.neg(), &q.neg(), r);
1940 check_sub(&a.neg(), b, &q.neg(), &r.neg());
1941 check_sub(&a.neg(), &b.neg(), q, &r.neg());
1943 for elm in mul_triples.iter() {
1944 let (aVec, bVec, cVec) = *elm;
1945 let a = BigInt::from_slice(Plus, aVec);
1946 let b = BigInt::from_slice(Plus, bVec);
1947 let c = BigInt::from_slice(Plus, cVec);
1949 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1950 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1953 for elm in div_rem_quadruples.iter() {
1954 let (aVec, bVec, cVec, dVec) = *elm;
1955 let a = BigInt::from_slice(Plus, aVec);
1956 let b = BigInt::from_slice(Plus, bVec);
1957 let c = BigInt::from_slice(Plus, cVec);
1958 let d = BigInt::from_slice(Plus, dVec);
1961 check(&a, &b, &c, &d);
1968 fn check(a: int, b: int, c: int) {
1969 let big_a: BigInt = IntConvertible::from_int(a);
1970 let big_b: BigInt = IntConvertible::from_int(b);
1971 let big_c: BigInt = IntConvertible::from_int(c);
1973 assert_eq!(big_a.gcd(&big_b), big_c);
1988 fn check(a: int, b: int, c: int) {
1989 let big_a: BigInt = IntConvertible::from_int(a);
1990 let big_b: BigInt = IntConvertible::from_int(b);
1991 let big_c: BigInt = IntConvertible::from_int(c);
1993 assert_eq!(big_a.lcm(&big_b), big_c);
2008 assert_eq!((-One::one::<BigInt>()).abs_sub(&One::one()), Zero::zero());
2009 assert_eq!(One::one::<BigInt>().abs_sub(&One::one()), Zero::zero());
2010 assert_eq!(One::one::<BigInt>().abs_sub(&Zero::zero()), One::one());
2011 assert_eq!(One::one::<BigInt>().abs_sub(&-One::one::<BigInt>()),
2012 IntConvertible::from_int(2));
2016 fn test_to_str_radix() {
2017 fn check(n: int, ans: &str) {
2018 assert!(ans == IntConvertible::from_int::<BigInt>(n).to_str_radix(10));
2029 fn test_from_str_radix() {
2030 fn check(s: &str, ans: Option<int>) {
2031 let ans = ans.map_move(|n| IntConvertible::from_int::<BigInt>(n));
2032 assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2034 check("10", Some(10));
2035 check("1", Some(1));
2036 check("0", Some(0));
2037 check("-1", Some(-1));
2038 check("-10", Some(-10));
2045 assert!(-BigInt::new(Plus, ~[1, 1, 1]) ==
2046 BigInt::new(Minus, ~[1, 1, 1]));
2047 assert!(-BigInt::new(Minus, ~[1, 1, 1]) ==
2048 BigInt::new(Plus, ~[1, 1, 1]));
2049 assert_eq!(-Zero::zero::<BigInt>(), Zero::zero::<BigInt>());