]> git.lizzy.rs Git - rust.git/blob - src/libnum/bigint.rs
auto merge of #15422 : steveklabnik/rust/guide_compound_data_types, r=brson
[rust.git] / src / libnum / bigint.rs
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.
4 //
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.
10
11 /*!
12
13 A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
14
15 A `BigUint` is represented as an array of `BigDigit`s.
16 A `BigInt` is a combination of `BigUint` and `Sign`.
17 */
18
19 use Integer;
20 use rand::Rng;
21
22 use std::{cmp, fmt};
23 use std::default::Default;
24 use std::from_str::FromStr;
25 use std::num::CheckedDiv;
26 use std::num::{ToPrimitive, FromPrimitive};
27 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
28 use std::string::String;
29 use std::{uint, i64, u64};
30
31 /**
32 A `BigDigit` is a `BigUint`'s composing element.
33 */
34 pub type BigDigit = u32;
35
36 /**
37 A `DoubleBigDigit` is the internal type used to do the computations.  Its
38 size is the double of the size of `BigDigit`.
39 */
40 pub type DoubleBigDigit = u64;
41
42 pub static ZERO_BIG_DIGIT: BigDigit = 0;
43 static ZERO_VEC: [BigDigit, ..1] = [ZERO_BIG_DIGIT];
44
45 pub mod BigDigit {
46     use super::BigDigit;
47     use super::DoubleBigDigit;
48
49     // `DoubleBigDigit` size dependent
50     pub static bits: uint = 32;
51
52     pub static base: DoubleBigDigit = 1 << bits;
53     static lo_mask: DoubleBigDigit = (-1 as DoubleBigDigit) >> bits;
54
55     #[inline]
56     fn get_hi(n: DoubleBigDigit) -> BigDigit { (n >> bits) as BigDigit }
57     #[inline]
58     fn get_lo(n: DoubleBigDigit) -> BigDigit { (n & lo_mask) as BigDigit }
59
60     /// Split one `DoubleBigDigit` into two `BigDigit`s.
61     #[inline]
62     pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
63         (get_hi(n), get_lo(n))
64     }
65
66     /// Join two `BigDigit`s into one `DoubleBigDigit`
67     #[inline]
68     pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
69         (lo as DoubleBigDigit) | ((hi as DoubleBigDigit) << bits)
70     }
71 }
72
73 /**
74 A big unsigned integer type.
75
76 A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
77 `(a + b * BigDigit::base + c * BigDigit::base^2)`.
78 */
79 #[deriving(Clone)]
80 pub struct BigUint {
81     data: Vec<BigDigit>
82 }
83
84 impl PartialEq for BigUint {
85     #[inline]
86     fn eq(&self, other: &BigUint) -> bool {
87         match self.cmp(other) { Equal => true, _ => false }
88     }
89 }
90 impl Eq for BigUint {}
91
92 impl PartialOrd for BigUint {
93     #[inline]
94     fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
95         Some(self.cmp(other))
96     }
97 }
98
99 impl Ord for BigUint {
100     #[inline]
101     fn cmp(&self, other: &BigUint) -> Ordering {
102         let (s_len, o_len) = (self.data.len(), other.data.len());
103         if s_len < o_len { return Less; }
104         if s_len > o_len { return Greater;  }
105
106         for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
107             if self_i < other_i { return Less; }
108             if self_i > other_i { return Greater; }
109         }
110         return Equal;
111     }
112 }
113
114 impl Default for BigUint {
115     #[inline]
116     fn default() -> BigUint { Zero::zero() }
117 }
118
119 impl fmt::Show for BigUint {
120     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
121         write!(f, "{}", self.to_str_radix(10))
122     }
123 }
124
125 impl FromStr for BigUint {
126     #[inline]
127     fn from_str(s: &str) -> Option<BigUint> {
128         FromStrRadix::from_str_radix(s, 10)
129     }
130 }
131
132 impl Num for BigUint {}
133
134 impl BitAnd<BigUint, BigUint> for BigUint {
135     fn bitand(&self, other: &BigUint) -> BigUint {
136         BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
137     }
138 }
139
140 impl BitOr<BigUint, BigUint> for BigUint {
141     fn bitor(&self, other: &BigUint) -> BigUint {
142         let zeros = ZERO_VEC.iter().cycle();
143         let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
144         let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
145             |(ai, bi)| *ai | *bi
146         ).collect();
147         return BigUint::new(ored);
148     }
149 }
150
151 impl BitXor<BigUint, BigUint> for BigUint {
152     fn bitxor(&self, other: &BigUint) -> BigUint {
153         let zeros = ZERO_VEC.iter().cycle();
154         let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
155         let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
156             |(ai, bi)| *ai ^ *bi
157         ).collect();
158         return BigUint::new(xored);
159     }
160 }
161
162 impl Shl<uint, BigUint> for BigUint {
163     #[inline]
164     fn shl(&self, rhs: &uint) -> BigUint {
165         let n_unit = *rhs / BigDigit::bits;
166         let n_bits = *rhs % BigDigit::bits;
167         return self.shl_unit(n_unit).shl_bits(n_bits);
168     }
169 }
170
171 impl Shr<uint, BigUint> for BigUint {
172     #[inline]
173     fn shr(&self, rhs: &uint) -> BigUint {
174         let n_unit = *rhs / BigDigit::bits;
175         let n_bits = *rhs % BigDigit::bits;
176         return self.shr_unit(n_unit).shr_bits(n_bits);
177     }
178 }
179
180 impl Zero for BigUint {
181     #[inline]
182     fn zero() -> BigUint { BigUint::new(Vec::new()) }
183
184     #[inline]
185     fn is_zero(&self) -> bool { self.data.is_empty() }
186 }
187
188 impl One for BigUint {
189     #[inline]
190     fn one() -> BigUint { BigUint::new(vec!(1)) }
191 }
192
193 impl Unsigned for BigUint {}
194
195 impl Add<BigUint, BigUint> for BigUint {
196     fn add(&self, other: &BigUint) -> BigUint {
197         let zeros = ZERO_VEC.iter().cycle();
198         let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
199
200         let mut carry = 0;
201         let mut sum: Vec<BigDigit> =  a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
202             let (hi, lo) = BigDigit::from_doublebigdigit(
203                 (*ai as DoubleBigDigit) + (*bi as DoubleBigDigit) + (carry as DoubleBigDigit));
204             carry = hi;
205             lo
206         }).collect();
207         if carry != 0 { sum.push(carry); }
208         return BigUint::new(sum);
209     }
210 }
211
212 impl Sub<BigUint, BigUint> for BigUint {
213     fn sub(&self, other: &BigUint) -> BigUint {
214         let new_len = cmp::max(self.data.len(), other.data.len());
215         let zeros = ZERO_VEC.iter().cycle();
216         let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
217
218         let mut borrow = 0i;
219         let diff: Vec<BigDigit> =  a.take(new_len).zip(b).map(|(ai, bi)| {
220             let (hi, lo) = BigDigit::from_doublebigdigit(
221                 BigDigit::base
222                     + (*ai as DoubleBigDigit)
223                     - (*bi as DoubleBigDigit)
224                     - (borrow as DoubleBigDigit)
225             );
226             /*
227             hi * (base) + lo == 1*(base) + ai - bi - borrow
228             => ai - bi - borrow < 0 <=> hi == 0
229             */
230             borrow = if hi == 0 { 1 } else { 0 };
231             lo
232         }).collect();
233
234         assert!(borrow == 0,
235                 "Cannot subtract other from self because other is larger than self.");
236         return BigUint::new(diff);
237     }
238 }
239
240 impl Mul<BigUint, BigUint> for BigUint {
241     fn mul(&self, other: &BigUint) -> BigUint {
242         if self.is_zero() || other.is_zero() { return Zero::zero(); }
243
244         let (s_len, o_len) = (self.data.len(), other.data.len());
245         if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]);  }
246         if o_len == 1 { return mul_digit(self,  other.data.as_slice()[0]); }
247
248         // Using Karatsuba multiplication
249         // (a1 * base + a0) * (b1 * base + b0)
250         // = a1*b1 * base^2 +
251         //   (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
252         //   a0*b0
253         let half_len = cmp::max(s_len, o_len) / 2;
254         let (s_hi, s_lo) = cut_at(self,  half_len);
255         let (o_hi, o_lo) = cut_at(other, half_len);
256
257         let ll = s_lo * o_lo;
258         let hh = s_hi * o_hi;
259         let mm = {
260             let (s1, n1) = sub_sign(s_hi, s_lo);
261             let (s2, n2) = sub_sign(o_hi, o_lo);
262             match (s1, s2) {
263                 (Equal, _) | (_, Equal) => hh + ll,
264                 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
265                 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
266             }
267         };
268
269         return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
270
271
272         fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
273             if n == 0 { return Zero::zero(); }
274             if n == 1 { return (*a).clone(); }
275
276             let mut carry = 0;
277             let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
278                 let (hi, lo) = BigDigit::from_doublebigdigit(
279                     (*ai as DoubleBigDigit) * (n as DoubleBigDigit) + (carry as DoubleBigDigit)
280                 );
281                 carry = hi;
282                 lo
283             }).collect();
284             if carry != 0 { prod.push(carry); }
285             return BigUint::new(prod);
286         }
287
288         #[inline]
289         fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
290             let mid = cmp::min(a.data.len(), n);
291             return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
292                     BigUint::from_slice(a.data.slice(0, mid)));
293         }
294
295         #[inline]
296         fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
297             match a.cmp(&b) {
298                 Less    => (Less,    b - a),
299                 Greater => (Greater, a - b),
300                 _       => (Equal,   Zero::zero())
301             }
302         }
303     }
304 }
305
306 impl Div<BigUint, BigUint> for BigUint {
307     #[inline]
308     fn div(&self, other: &BigUint) -> BigUint {
309         let (q, _) = self.div_rem(other);
310         return q;
311     }
312 }
313
314 impl Rem<BigUint, BigUint> for BigUint {
315     #[inline]
316     fn rem(&self, other: &BigUint) -> BigUint {
317         let (_, r) = self.div_rem(other);
318         return r;
319     }
320 }
321
322 impl Neg<BigUint> for BigUint {
323     #[inline]
324     fn neg(&self) -> BigUint { fail!() }
325 }
326
327 impl CheckedAdd for BigUint {
328     #[inline]
329     fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
330         return Some(self.add(v));
331     }
332 }
333
334 impl CheckedSub for BigUint {
335     #[inline]
336     fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
337         if *self < *v {
338             return None;
339         }
340         return Some(self.sub(v));
341     }
342 }
343
344 impl CheckedMul for BigUint {
345     #[inline]
346     fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
347         return Some(self.mul(v));
348     }
349 }
350
351 impl CheckedDiv for BigUint {
352     #[inline]
353     fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
354         if v.is_zero() {
355             return None;
356         }
357         return Some(self.div(v));
358     }
359 }
360
361 impl Integer for BigUint {
362     #[inline]
363     fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
364         self.div_mod_floor(other)
365     }
366
367     #[inline]
368     fn div_floor(&self, other: &BigUint) -> BigUint {
369         let (d, _) = self.div_mod_floor(other);
370         return d;
371     }
372
373     #[inline]
374     fn mod_floor(&self, other: &BigUint) -> BigUint {
375         let (_, m) = self.div_mod_floor(other);
376         return m;
377     }
378
379     fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
380         if other.is_zero() { fail!() }
381         if self.is_zero() { return (Zero::zero(), Zero::zero()); }
382         if *other == One::one() { return ((*self).clone(), Zero::zero()); }
383
384         match self.cmp(other) {
385             Less    => return (Zero::zero(), (*self).clone()),
386             Equal   => return (One::one(), Zero::zero()),
387             Greater => {} // Do nothing
388         }
389
390         let mut shift = 0;
391         let mut n = *other.data.last().unwrap();
392         while n < (1 << BigDigit::bits - 2) {
393             n <<= 1;
394             shift += 1;
395         }
396         assert!(shift < BigDigit::bits);
397         let (d, m) = div_mod_floor_inner(self << shift, other << shift);
398         return (d, m >> shift);
399
400
401         fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
402             let mut m = a;
403             let mut d: BigUint = Zero::zero();
404             let mut n = 1;
405             while m >= b {
406                 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
407                 let mut d0 = d0;
408                 let mut prod = b * d0;
409                 while prod > m {
410                     // FIXME(#5992): assignment operator overloads
411                     // d0 -= d_unit
412                     d0   = d0 - d_unit;
413                     // FIXME(#5992): assignment operator overloads
414                     // prod -= b_unit;
415                     prod = prod - b_unit
416                 }
417                 if d0.is_zero() {
418                     n = 2;
419                     continue;
420                 }
421                 n = 1;
422                 // FIXME(#5992): assignment operator overloads
423                 // d += d0;
424                 d = d + d0;
425                 // FIXME(#5992): assignment operator overloads
426                 // m -= prod;
427                 m = m - prod;
428             }
429             return (d, m);
430         }
431
432
433         fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
434             -> (BigUint, BigUint, BigUint) {
435             if a.data.len() < n {
436                 return (Zero::zero(), Zero::zero(), (*a).clone());
437             }
438
439             let an = a.data.tailn(a.data.len() - n);
440             let bn = *b.data.last().unwrap();
441             let mut d = Vec::with_capacity(an.len());
442             let mut carry = 0;
443             for elt in an.iter().rev() {
444                 let ai = BigDigit::to_doublebigdigit(carry, *elt);
445                 let di = ai / (bn as DoubleBigDigit);
446                 assert!(di < BigDigit::base);
447                 carry = (ai % (bn as DoubleBigDigit)) as BigDigit;
448                 d.push(di as BigDigit)
449             }
450             d.reverse();
451
452             let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
453             if shift == 0 {
454                 return (BigUint::new(d), One::one(), (*b).clone());
455             }
456             let one: BigUint = One::one();
457             return (BigUint::new(d).shl_unit(shift),
458                     one.shl_unit(shift),
459                     b.shl_unit(shift));
460         }
461     }
462
463     /**
464      * Calculates the Greatest Common Divisor (GCD) of the number and `other`
465      *
466      * The result is always positive
467      */
468     #[inline]
469     fn gcd(&self, other: &BigUint) -> BigUint {
470         // Use Euclid's algorithm
471         let mut m = (*self).clone();
472         let mut n = (*other).clone();
473         while !m.is_zero() {
474             let temp = m;
475             m = n % temp;
476             n = temp;
477         }
478         return n;
479     }
480
481     /**
482      * Calculates the Lowest Common Multiple (LCM) of the number and `other`
483      */
484     #[inline]
485     fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
486
487     /// Returns `true` if the number can be divided by `other` without leaving a remainder
488     #[inline]
489     fn divides(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
490
491     /// Returns `true` if the number is divisible by `2`
492     #[inline]
493     fn is_even(&self) -> bool {
494         // Considering only the last digit.
495         match self.data.as_slice().head() {
496             Some(x) => x.is_even(),
497             None => true
498         }
499     }
500
501     /// Returns `true` if the number is not divisible by `2`
502     #[inline]
503     fn is_odd(&self) -> bool { !self.is_even() }
504 }
505
506 impl ToPrimitive for BigUint {
507     #[inline]
508     fn to_i64(&self) -> Option<i64> {
509         self.to_u64().and_then(|n| {
510             // If top bit of u64 is set, it's too large to convert to i64.
511             if n >> 63 == 0 {
512                 Some(n as i64)
513             } else {
514                 None
515             }
516         })
517     }
518
519     // `DoubleBigDigit` size dependent
520     #[inline]
521     fn to_u64(&self) -> Option<u64> {
522         match self.data.len() {
523             0 => Some(0),
524             1 => Some(self.data.as_slice()[0] as u64),
525             2 => Some(BigDigit::to_doublebigdigit(self.data.as_slice()[1], self.data.as_slice()[0])
526                       as u64),
527             _ => None
528         }
529     }
530 }
531
532 impl FromPrimitive for BigUint {
533     #[inline]
534     fn from_i64(n: i64) -> Option<BigUint> {
535         if n > 0 {
536             FromPrimitive::from_u64(n as u64)
537         } else if n == 0 {
538             Some(Zero::zero())
539         } else {
540             None
541         }
542     }
543
544     // `DoubleBigDigit` size dependent
545     #[inline]
546     fn from_u64(n: u64) -> Option<BigUint> {
547         let n = match BigDigit::from_doublebigdigit(n) {
548             (0,  0)  => Zero::zero(),
549             (0,  n0) => BigUint::new(vec!(n0)),
550             (n1, n0) => BigUint::new(vec!(n0, n1))
551         };
552         Some(n)
553     }
554 }
555
556 /// A generic trait for converting a value to a `BigUint`.
557 pub trait ToBigUint {
558     /// Converts the value of `self` to a `BigUint`.
559     fn to_biguint(&self) -> Option<BigUint>;
560 }
561
562 impl ToBigUint for BigInt {
563     #[inline]
564     fn to_biguint(&self) -> Option<BigUint> {
565         if self.sign == Plus {
566             Some(self.data.clone())
567         } else if self.sign == Zero {
568             Some(Zero::zero())
569         } else {
570             None
571         }
572     }
573 }
574
575 impl ToBigUint for BigUint {
576     #[inline]
577     fn to_biguint(&self) -> Option<BigUint> {
578         Some(self.clone())
579     }
580 }
581
582 macro_rules! impl_to_biguint(
583     ($T:ty, $from_ty:path) => {
584         impl ToBigUint for $T {
585             #[inline]
586             fn to_biguint(&self) -> Option<BigUint> {
587                 $from_ty(*self)
588             }
589         }
590     }
591 )
592
593 impl_to_biguint!(int,  FromPrimitive::from_int)
594 impl_to_biguint!(i8,   FromPrimitive::from_i8)
595 impl_to_biguint!(i16,  FromPrimitive::from_i16)
596 impl_to_biguint!(i32,  FromPrimitive::from_i32)
597 impl_to_biguint!(i64,  FromPrimitive::from_i64)
598 impl_to_biguint!(uint, FromPrimitive::from_uint)
599 impl_to_biguint!(u8,   FromPrimitive::from_u8)
600 impl_to_biguint!(u16,  FromPrimitive::from_u16)
601 impl_to_biguint!(u32,  FromPrimitive::from_u32)
602 impl_to_biguint!(u64,  FromPrimitive::from_u64)
603
604 impl ToStrRadix for BigUint {
605     fn to_str_radix(&self, radix: uint) -> String {
606         assert!(1 < radix && radix <= 16, "The radix must be within (1, 16]");
607         let (base, max_len) = get_radix_base(radix);
608         if base == BigDigit::base {
609             return fill_concat(self.data.as_slice(), radix, max_len)
610         }
611         return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
612
613         fn convert_base(n: &BigUint, base: DoubleBigDigit) -> Vec<BigDigit> {
614             let divider    = base.to_biguint().unwrap();
615             let mut result = Vec::new();
616             let mut m      = n.clone();
617             while m >= divider {
618                 let (d, m0) = m.div_mod_floor(&divider);
619                 result.push(m0.to_uint().unwrap() as BigDigit);
620                 m = d;
621             }
622             if !m.is_zero() {
623                 result.push(m.to_uint().unwrap() as BigDigit);
624             }
625             return result;
626         }
627
628         fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> String {
629             if v.is_empty() {
630                 return "0".to_string()
631             }
632             let mut s = String::with_capacity(v.len() * l);
633             for n in v.iter().rev() {
634                 let ss = (*n as uint).to_str_radix(radix);
635                 s.push_str("0".repeat(l - ss.len()).as_slice());
636                 s.push_str(ss.as_slice());
637             }
638             s.as_slice().trim_left_chars('0').to_string()
639         }
640     }
641 }
642
643 impl FromStrRadix for BigUint {
644     /// Creates and initializes a `BigUint`.
645     #[inline]
646     fn from_str_radix(s: &str, radix: uint) -> Option<BigUint> {
647         BigUint::parse_bytes(s.as_bytes(), radix)
648     }
649 }
650
651 impl BigUint {
652     /// Creates and initializes a `BigUint`.
653     ///
654     /// The digits are be in base 2^32.
655     #[inline]
656     pub fn new(mut digits: Vec<BigDigit>) -> BigUint {
657         // omit trailing zeros
658         let new_len = digits.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
659         digits.truncate(new_len);
660         BigUint { data: digits }
661     }
662
663     /// Creates and initializes a `BigUint`.
664     ///
665     /// The digits are be in base 2^32.
666     #[inline]
667     pub fn from_slice(slice: &[BigDigit]) -> BigUint {
668         BigUint::new(Vec::from_slice(slice))
669     }
670
671     /// Creates and initializes a `BigUint`.
672     pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
673         let (base, unit_len) = get_radix_base(radix);
674         let base_num = match base.to_biguint() {
675             Some(base_num) => base_num,
676             None => { return None; }
677         };
678
679         let mut end             = buf.len();
680         let mut n: BigUint      = Zero::zero();
681         let mut power: BigUint  = One::one();
682         loop {
683             let start = cmp::max(end, unit_len) - unit_len;
684             match uint::parse_bytes(buf.slice(start, end), radix) {
685                 Some(d) => {
686                     let d: Option<BigUint> = FromPrimitive::from_uint(d);
687                     match d {
688                         Some(d) => {
689                             // FIXME(#5992): assignment operator overloads
690                             // n += d * power;
691                             n = n + d * power;
692                         }
693                         None => { return None; }
694                     }
695                 }
696                 None => { return None; }
697             }
698             if end <= unit_len {
699                 return Some(n);
700             }
701             end -= unit_len;
702             // FIXME(#5992): assignment operator overloads
703             // power *= base_num;
704             power = power * base_num;
705         }
706     }
707
708     #[inline]
709     fn shl_unit(&self, n_unit: uint) -> BigUint {
710         if n_unit == 0 || self.is_zero() { return (*self).clone(); }
711
712         BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
713     }
714
715     #[inline]
716     fn shl_bits(&self, n_bits: uint) -> BigUint {
717         if n_bits == 0 || self.is_zero() { return (*self).clone(); }
718
719         let mut carry = 0;
720         let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
721             let (hi, lo) = BigDigit::from_doublebigdigit(
722                 (*elem as DoubleBigDigit) << n_bits | (carry as DoubleBigDigit)
723             );
724             carry = hi;
725             lo
726         }).collect();
727         if carry != 0 { shifted.push(carry); }
728         return BigUint::new(shifted);
729     }
730
731     #[inline]
732     fn shr_unit(&self, n_unit: uint) -> BigUint {
733         if n_unit == 0 { return (*self).clone(); }
734         if self.data.len() < n_unit { return Zero::zero(); }
735         return BigUint::from_slice(
736             self.data.slice(n_unit, self.data.len())
737         );
738     }
739
740     #[inline]
741     fn shr_bits(&self, n_bits: uint) -> BigUint {
742         if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
743
744         let mut borrow = 0;
745         let mut shifted_rev = Vec::with_capacity(self.data.len());
746         for elem in self.data.iter().rev() {
747             shifted_rev.push((*elem >> n_bits) | borrow);
748             borrow = *elem << (BigDigit::bits - n_bits);
749         }
750         let shifted = { shifted_rev.reverse(); shifted_rev };
751         return BigUint::new(shifted);
752     }
753
754     /// Determines the fewest bits necessary to express the `BigUint`.
755     pub fn bits(&self) -> uint {
756         if self.is_zero() { return 0; }
757         let zeros = self.data.last().unwrap().leading_zeros();
758         return self.data.len()*BigDigit::bits - (zeros as uint);
759     }
760 }
761
762 // `DoubleBigDigit` size dependent
763 #[inline]
764 fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
765     match radix {
766         2  => (4294967296, 32),
767         3  => (3486784401, 20),
768         4  => (4294967296, 16),
769         5  => (1220703125, 13),
770         6  => (2176782336, 12),
771         7  => (1977326743, 11),
772         8  => (1073741824, 10),
773         9  => (3486784401, 10),
774         10 => (1000000000, 9),
775         11 => (2357947691, 9),
776         12 => (429981696,  8),
777         13 => (815730721,  8),
778         14 => (1475789056, 8),
779         15 => (2562890625, 8),
780         16 => (4294967296, 8),
781         _  => fail!("The radix must be within (1, 16]")
782     }
783 }
784
785 /// A Sign is a `BigInt`'s composing element.
786 #[deriving(PartialEq, PartialOrd, Eq, Ord, Clone, Show)]
787 pub enum Sign { Minus, Zero, Plus }
788
789 impl Neg<Sign> for Sign {
790     /// Negate Sign value.
791     #[inline]
792     fn neg(&self) -> Sign {
793         match *self {
794           Minus => Plus,
795           Zero  => Zero,
796           Plus  => Minus
797         }
798     }
799 }
800
801 /// A big signed integer type.
802 #[deriving(Clone)]
803 pub struct BigInt {
804     sign: Sign,
805     data: BigUint
806 }
807
808 impl PartialEq for BigInt {
809     #[inline]
810     fn eq(&self, other: &BigInt) -> bool {
811         self.cmp(other) == Equal
812     }
813 }
814
815 impl Eq for BigInt {}
816
817 impl PartialOrd for BigInt {
818     #[inline]
819     fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
820         Some(self.cmp(other))
821     }
822 }
823
824 impl Ord for BigInt {
825     #[inline]
826     fn cmp(&self, other: &BigInt) -> Ordering {
827         let scmp = self.sign.cmp(&other.sign);
828         if scmp != Equal { return scmp; }
829
830         match self.sign {
831             Zero  => Equal,
832             Plus  => self.data.cmp(&other.data),
833             Minus => other.data.cmp(&self.data),
834         }
835     }
836 }
837
838 impl Default for BigInt {
839     #[inline]
840     fn default() -> BigInt { Zero::zero() }
841 }
842
843 impl fmt::Show for BigInt {
844     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
845         write!(f, "{}", self.to_str_radix(10))
846     }
847 }
848
849 impl FromStr for BigInt {
850     #[inline]
851     fn from_str(s: &str) -> Option<BigInt> {
852         FromStrRadix::from_str_radix(s, 10)
853     }
854 }
855
856 impl Num for BigInt {}
857
858 impl Shl<uint, BigInt> for BigInt {
859     #[inline]
860     fn shl(&self, rhs: &uint) -> BigInt {
861         BigInt::from_biguint(self.sign, self.data << *rhs)
862     }
863 }
864
865 impl Shr<uint, BigInt> for BigInt {
866     #[inline]
867     fn shr(&self, rhs: &uint) -> BigInt {
868         BigInt::from_biguint(self.sign, self.data >> *rhs)
869     }
870 }
871
872 impl Zero for BigInt {
873     #[inline]
874     fn zero() -> BigInt {
875         BigInt::from_biguint(Zero, Zero::zero())
876     }
877
878     #[inline]
879     fn is_zero(&self) -> bool { self.sign == Zero }
880 }
881
882 impl One for BigInt {
883     #[inline]
884     fn one() -> BigInt {
885         BigInt::from_biguint(Plus, One::one())
886     }
887 }
888
889 impl Signed for BigInt {
890     #[inline]
891     fn abs(&self) -> BigInt {
892         match self.sign {
893             Plus | Zero => self.clone(),
894             Minus => BigInt::from_biguint(Plus, self.data.clone())
895         }
896     }
897
898     #[inline]
899     fn abs_sub(&self, other: &BigInt) -> BigInt {
900         if *self <= *other { Zero::zero() } else { *self - *other }
901     }
902
903     #[inline]
904     fn signum(&self) -> BigInt {
905         match self.sign {
906             Plus  => BigInt::from_biguint(Plus, One::one()),
907             Minus => BigInt::from_biguint(Minus, One::one()),
908             Zero  => Zero::zero(),
909         }
910     }
911
912     #[inline]
913     fn is_positive(&self) -> bool { self.sign == Plus }
914
915     #[inline]
916     fn is_negative(&self) -> bool { self.sign == Minus }
917 }
918
919 impl Add<BigInt, BigInt> for BigInt {
920     #[inline]
921     fn add(&self, other: &BigInt) -> BigInt {
922         match (self.sign, other.sign) {
923             (Zero, _)      => other.clone(),
924             (_,    Zero)   => self.clone(),
925             (Plus, Plus)   => BigInt::from_biguint(Plus, self.data + other.data),
926             (Plus, Minus)  => self - (-*other),
927             (Minus, Plus)  => other - (-*self),
928             (Minus, Minus) => -((-self) + (-*other))
929         }
930     }
931 }
932
933 impl Sub<BigInt, BigInt> for BigInt {
934     #[inline]
935     fn sub(&self, other: &BigInt) -> BigInt {
936         match (self.sign, other.sign) {
937             (Zero, _)    => -other,
938             (_,    Zero) => self.clone(),
939             (Plus, Plus) => match self.data.cmp(&other.data) {
940                 Less    => BigInt::from_biguint(Minus, other.data - self.data),
941                 Greater => BigInt::from_biguint(Plus, self.data - other.data),
942                 Equal   => Zero::zero()
943             },
944             (Plus, Minus) => self + (-*other),
945             (Minus, Plus) => -((-self) + *other),
946             (Minus, Minus) => (-other) - (-*self)
947         }
948     }
949 }
950
951 impl Mul<BigInt, BigInt> for BigInt {
952     #[inline]
953     fn mul(&self, other: &BigInt) -> BigInt {
954         match (self.sign, other.sign) {
955             (Zero, _)     | (_,     Zero)  => Zero::zero(),
956             (Plus, Plus)  | (Minus, Minus) => {
957                 BigInt::from_biguint(Plus, self.data * other.data)
958             },
959             (Plus, Minus) | (Minus, Plus) => {
960                 BigInt::from_biguint(Minus, self.data * other.data)
961             }
962         }
963     }
964 }
965
966 impl Div<BigInt, BigInt> for BigInt {
967     #[inline]
968     fn div(&self, other: &BigInt) -> BigInt {
969         let (q, _) = self.div_rem(other);
970         q
971     }
972 }
973
974 impl Rem<BigInt, BigInt> for BigInt {
975     #[inline]
976     fn rem(&self, other: &BigInt) -> BigInt {
977         let (_, r) = self.div_rem(other);
978         r
979     }
980 }
981
982 impl Neg<BigInt> for BigInt {
983     #[inline]
984     fn neg(&self) -> BigInt {
985         BigInt::from_biguint(self.sign.neg(), self.data.clone())
986     }
987 }
988
989 impl CheckedAdd for BigInt {
990     #[inline]
991     fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
992         return Some(self.add(v));
993     }
994 }
995
996 impl CheckedSub for BigInt {
997     #[inline]
998     fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
999         return Some(self.sub(v));
1000     }
1001 }
1002
1003 impl CheckedMul for BigInt {
1004     #[inline]
1005     fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1006         return Some(self.mul(v));
1007     }
1008 }
1009
1010 impl CheckedDiv for BigInt {
1011     #[inline]
1012     fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1013         if v.is_zero() {
1014             return None;
1015         }
1016         return Some(self.div(v));
1017     }
1018 }
1019
1020
1021 impl Integer for BigInt {
1022     #[inline]
1023     fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1024         // r.sign == self.sign
1025         let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1026         let d = BigInt::from_biguint(Plus, d_ui);
1027         let r = BigInt::from_biguint(Plus, r_ui);
1028         match (self.sign, other.sign) {
1029             (_,    Zero)   => fail!(),
1030             (Plus, Plus)  | (Zero, Plus)  => ( d,  r),
1031             (Plus, Minus) | (Zero, Minus) => (-d,  r),
1032             (Minus, Plus)                 => (-d, -r),
1033             (Minus, Minus)                => ( d, -r)
1034         }
1035     }
1036
1037     #[inline]
1038     fn div_floor(&self, other: &BigInt) -> BigInt {
1039         let (d, _) = self.div_mod_floor(other);
1040         d
1041     }
1042
1043     #[inline]
1044     fn mod_floor(&self, other: &BigInt) -> BigInt {
1045         let (_, m) = self.div_mod_floor(other);
1046         m
1047     }
1048
1049     fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1050         // m.sign == other.sign
1051         let (d_ui, m_ui) = self.data.div_rem(&other.data);
1052         let d = BigInt::from_biguint(Plus, d_ui);
1053         let m = BigInt::from_biguint(Plus, m_ui);
1054         match (self.sign, other.sign) {
1055             (_,    Zero)   => fail!(),
1056             (Plus, Plus)  | (Zero, Plus)  => (d, m),
1057             (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1058                 (-d, Zero::zero())
1059             } else {
1060                 (-d - One::one(), m + *other)
1061             },
1062             (Minus, Plus) => if m.is_zero() {
1063                 (-d, Zero::zero())
1064             } else {
1065                 (-d - One::one(), other - m)
1066             },
1067             (Minus, Minus) => (d, -m)
1068         }
1069     }
1070
1071     /**
1072      * Calculates the Greatest Common Divisor (GCD) of the number and `other`
1073      *
1074      * The result is always positive
1075      */
1076     #[inline]
1077     fn gcd(&self, other: &BigInt) -> BigInt {
1078         BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1079     }
1080
1081     /**
1082      * Calculates the Lowest Common Multiple (LCM) of the number and `other`
1083      */
1084     #[inline]
1085     fn lcm(&self, other: &BigInt) -> BigInt {
1086         BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1087     }
1088
1089     /// Returns `true` if the number can be divided by `other` without leaving a remainder
1090     #[inline]
1091     fn divides(&self, other: &BigInt) -> bool { self.data.divides(&other.data) }
1092
1093     /// Returns `true` if the number is divisible by `2`
1094     #[inline]
1095     fn is_even(&self) -> bool { self.data.is_even() }
1096
1097     /// Returns `true` if the number is not divisible by `2`
1098     #[inline]
1099     fn is_odd(&self) -> bool { self.data.is_odd() }
1100 }
1101
1102 impl ToPrimitive for BigInt {
1103     #[inline]
1104     fn to_i64(&self) -> Option<i64> {
1105         match self.sign {
1106             Plus  => self.data.to_i64(),
1107             Zero  => Some(0),
1108             Minus => {
1109                 self.data.to_u64().and_then(|n| {
1110                     let m: u64 = 1 << 63;
1111                     if n < m {
1112                         Some(-(n as i64))
1113                     } else if n == m {
1114                         Some(i64::MIN)
1115                     } else {
1116                         None
1117                     }
1118                 })
1119             }
1120         }
1121     }
1122
1123     #[inline]
1124     fn to_u64(&self) -> Option<u64> {
1125         match self.sign {
1126             Plus => self.data.to_u64(),
1127             Zero => Some(0),
1128             Minus => None
1129         }
1130     }
1131 }
1132
1133 impl FromPrimitive for BigInt {
1134     #[inline]
1135     fn from_i64(n: i64) -> Option<BigInt> {
1136         if n > 0 {
1137             FromPrimitive::from_u64(n as u64).and_then(|n| {
1138                 Some(BigInt::from_biguint(Plus, n))
1139             })
1140         } else if n < 0 {
1141             FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1142                 |n| {
1143                     Some(BigInt::from_biguint(Minus, n))
1144                 })
1145         } else {
1146             Some(Zero::zero())
1147         }
1148     }
1149
1150     #[inline]
1151     fn from_u64(n: u64) -> Option<BigInt> {
1152         if n == 0 {
1153             Some(Zero::zero())
1154         } else {
1155             FromPrimitive::from_u64(n).and_then(|n| {
1156                 Some(BigInt::from_biguint(Plus, n))
1157             })
1158         }
1159     }
1160 }
1161
1162 /// A generic trait for converting a value to a `BigInt`.
1163 pub trait ToBigInt {
1164     /// Converts the value of `self` to a `BigInt`.
1165     fn to_bigint(&self) -> Option<BigInt>;
1166 }
1167
1168 impl ToBigInt for BigInt {
1169     #[inline]
1170     fn to_bigint(&self) -> Option<BigInt> {
1171         Some(self.clone())
1172     }
1173 }
1174
1175 impl ToBigInt for BigUint {
1176     #[inline]
1177     fn to_bigint(&self) -> Option<BigInt> {
1178         if self.is_zero() {
1179             Some(Zero::zero())
1180         } else {
1181             Some(BigInt { sign: Plus, data: self.clone() })
1182         }
1183     }
1184 }
1185
1186 macro_rules! impl_to_bigint(
1187     ($T:ty, $from_ty:path) => {
1188         impl ToBigInt for $T {
1189             #[inline]
1190             fn to_bigint(&self) -> Option<BigInt> {
1191                 $from_ty(*self)
1192             }
1193         }
1194     }
1195 )
1196
1197 impl_to_bigint!(int,  FromPrimitive::from_int)
1198 impl_to_bigint!(i8,   FromPrimitive::from_i8)
1199 impl_to_bigint!(i16,  FromPrimitive::from_i16)
1200 impl_to_bigint!(i32,  FromPrimitive::from_i32)
1201 impl_to_bigint!(i64,  FromPrimitive::from_i64)
1202 impl_to_bigint!(uint, FromPrimitive::from_uint)
1203 impl_to_bigint!(u8,   FromPrimitive::from_u8)
1204 impl_to_bigint!(u16,  FromPrimitive::from_u16)
1205 impl_to_bigint!(u32,  FromPrimitive::from_u32)
1206 impl_to_bigint!(u64,  FromPrimitive::from_u64)
1207
1208 impl ToStrRadix for BigInt {
1209     #[inline]
1210     fn to_str_radix(&self, radix: uint) -> String {
1211         match self.sign {
1212             Plus  => self.data.to_str_radix(radix),
1213             Zero  => "0".to_string(),
1214             Minus => format!("-{}", self.data.to_str_radix(radix)),
1215         }
1216     }
1217 }
1218
1219 impl FromStrRadix for BigInt {
1220     /// Creates and initializes a BigInt.
1221     #[inline]
1222     fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1223         BigInt::parse_bytes(s.as_bytes(), radix)
1224     }
1225 }
1226
1227 pub trait RandBigInt {
1228     /// Generate a random `BigUint` of the given bit size.
1229     fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1230
1231     /// Generate a random BigInt of the given bit size.
1232     fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1233
1234     /// Generate a random `BigUint` less than the given bound. Fails
1235     /// when the bound is zero.
1236     fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1237
1238     /// Generate a random `BigUint` within the given range. The lower
1239     /// bound is inclusive; the upper bound is exclusive. Fails when
1240     /// the upper bound is not greater than the lower bound.
1241     fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1242
1243     /// Generate a random `BigInt` within the given range. The lower
1244     /// bound is inclusive; the upper bound is exclusive. Fails when
1245     /// the upper bound is not greater than the lower bound.
1246     fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1247 }
1248
1249 impl<R: Rng> RandBigInt for R {
1250     fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1251         let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1252         let mut data = Vec::with_capacity(digits+1);
1253         for _ in range(0, digits) {
1254             data.push(self.gen());
1255         }
1256         if rem > 0 {
1257             let final_digit: BigDigit = self.gen();
1258             data.push(final_digit >> (BigDigit::bits - rem));
1259         }
1260         BigUint::new(data)
1261     }
1262
1263     fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1264         // Generate a random BigUint...
1265         let biguint = self.gen_biguint(bit_size);
1266         // ...and then randomly assign it a Sign...
1267         let sign = if biguint.is_zero() {
1268             // ...except that if the BigUint is zero, we need to try
1269             // again with probability 0.5. This is because otherwise,
1270             // the probability of generating a zero BigInt would be
1271             // double that of any other number.
1272             if self.gen() {
1273                 return self.gen_bigint(bit_size);
1274             } else {
1275                 Zero
1276             }
1277         } else if self.gen() {
1278             Plus
1279         } else {
1280             Minus
1281         };
1282         BigInt::from_biguint(sign, biguint)
1283     }
1284
1285     fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1286         assert!(!bound.is_zero());
1287         let bits = bound.bits();
1288         loop {
1289             let n = self.gen_biguint(bits);
1290             if n < *bound { return n; }
1291         }
1292     }
1293
1294     fn gen_biguint_range(&mut self,
1295                          lbound: &BigUint,
1296                          ubound: &BigUint)
1297                          -> BigUint {
1298         assert!(*lbound < *ubound);
1299         return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1300     }
1301
1302     fn gen_bigint_range(&mut self,
1303                         lbound: &BigInt,
1304                         ubound: &BigInt)
1305                         -> BigInt {
1306         assert!(*lbound < *ubound);
1307         let delta = (*ubound - *lbound).to_biguint().unwrap();
1308         return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1309     }
1310 }
1311
1312 impl BigInt {
1313     /// Creates and initializes a BigInt.
1314     ///
1315     /// The digits are be in base 2^32.
1316     #[inline]
1317     pub fn new(sign: Sign, digits: Vec<BigDigit>) -> BigInt {
1318         BigInt::from_biguint(sign, BigUint::new(digits))
1319     }
1320
1321     /// Creates and initializes a `BigInt`.
1322     ///
1323     /// The digits are be in base 2^32.
1324     #[inline]
1325     pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1326         if sign == Zero || data.is_zero() {
1327             return BigInt { sign: Zero, data: Zero::zero() };
1328         }
1329         BigInt { sign: sign, data: data }
1330     }
1331
1332     /// Creates and initializes a `BigInt`.
1333     #[inline]
1334     pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1335         BigInt::from_biguint(sign, BigUint::from_slice(slice))
1336     }
1337
1338     /// Creates and initializes a `BigInt`.
1339     pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigInt> {
1340         if buf.is_empty() { return None; }
1341         let mut sign  = Plus;
1342         let mut start = 0;
1343         if buf[0] == ('-' as u8) {
1344             sign  = Minus;
1345             start = 1;
1346         }
1347         return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1348             .map(|bu| BigInt::from_biguint(sign, bu));
1349     }
1350
1351     /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1352     #[inline]
1353     pub fn to_biguint(&self) -> Option<BigUint> {
1354         match self.sign {
1355             Plus => Some(self.data.clone()),
1356             Zero => Some(Zero::zero()),
1357             Minus => None
1358         }
1359     }
1360 }
1361
1362 #[cfg(test)]
1363 mod biguint_tests {
1364     use Integer;
1365     use super::{BigDigit, BigUint, ToBigUint};
1366     use super::{Plus, BigInt, RandBigInt, ToBigInt};
1367
1368     use std::cmp::{Less, Equal, Greater};
1369     use std::from_str::FromStr;
1370     use std::i64;
1371     use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1372     use std::num::{ToPrimitive, FromPrimitive};
1373     use std::num::CheckedDiv;
1374     use std::rand::task_rng;
1375     use std::u64;
1376
1377     #[test]
1378     fn test_from_slice() {
1379         fn check(slice: &[BigDigit], data: &[BigDigit]) {
1380             assert!(data == BigUint::from_slice(slice).data.as_slice());
1381         }
1382         check([1], [1]);
1383         check([0, 0, 0], []);
1384         check([1, 2, 0, 0], [1, 2]);
1385         check([0, 0, 1, 2], [0, 0, 1, 2]);
1386         check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1387         check([-1], [-1]);
1388     }
1389
1390     #[test]
1391     fn test_cmp() {
1392         let data: Vec<BigUint> = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1]  ]
1393             .iter().map(|v| BigUint::from_slice(*v)).collect();
1394         for (i, ni) in data.iter().enumerate() {
1395             for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1396                 let j = j0 + i;
1397                 if i == j {
1398                     assert_eq!(ni.cmp(nj), Equal);
1399                     assert_eq!(nj.cmp(ni), Equal);
1400                     assert_eq!(ni, nj);
1401                     assert!(!(ni != nj));
1402                     assert!(ni <= nj);
1403                     assert!(ni >= nj);
1404                     assert!(!(ni < nj));
1405                     assert!(!(ni > nj));
1406                 } else {
1407                     assert_eq!(ni.cmp(nj), Less);
1408                     assert_eq!(nj.cmp(ni), Greater);
1409
1410                     assert!(!(ni == nj));
1411                     assert!(ni != nj);
1412
1413                     assert!(ni <= nj);
1414                     assert!(!(ni >= nj));
1415                     assert!(ni < nj);
1416                     assert!(!(ni > nj));
1417
1418                     assert!(!(nj <= ni));
1419                     assert!(nj >= ni);
1420                     assert!(!(nj < ni));
1421                     assert!(nj > ni);
1422                 }
1423             }
1424         }
1425     }
1426
1427     #[test]
1428     fn test_bitand() {
1429         fn check(left: &[BigDigit],
1430                  right: &[BigDigit],
1431                  expected: &[BigDigit]) {
1432             assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1433                        BigUint::from_slice(expected));
1434         }
1435         check([], [], []);
1436         check([268, 482, 17],
1437               [964, 54],
1438               [260, 34]);
1439     }
1440
1441     #[test]
1442     fn test_bitor() {
1443         fn check(left: &[BigDigit],
1444                  right: &[BigDigit],
1445                  expected: &[BigDigit]) {
1446             assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1447                        BigUint::from_slice(expected));
1448         }
1449         check([], [], []);
1450         check([268, 482, 17],
1451               [964, 54],
1452               [972, 502, 17]);
1453     }
1454
1455     #[test]
1456     fn test_bitxor() {
1457         fn check(left: &[BigDigit],
1458                  right: &[BigDigit],
1459                  expected: &[BigDigit]) {
1460             assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1461                        BigUint::from_slice(expected));
1462         }
1463         check([], [], []);
1464         check([268, 482, 17],
1465               [964, 54],
1466               [712, 468, 17]);
1467     }
1468
1469     #[test]
1470     fn test_shl() {
1471         fn check(s: &str, shift: uint, ans: &str) {
1472             let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1473             let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1474             assert_eq!(bu.as_slice(), ans);
1475         }
1476
1477         check("0", 3, "0");
1478         check("1", 3, "8");
1479
1480         check("1\
1481                0000\
1482                0000\
1483                0000\
1484                0001\
1485                0000\
1486                0000\
1487                0000\
1488                0001",
1489               3,
1490               "8\
1491                0000\
1492                0000\
1493                0000\
1494                0008\
1495                0000\
1496                0000\
1497                0000\
1498                0008");
1499         check("1\
1500                0000\
1501                0001\
1502                0000\
1503                0001",
1504               2,
1505               "4\
1506                0000\
1507                0004\
1508                0000\
1509                0004");
1510         check("1\
1511                0001\
1512                0001",
1513               1,
1514               "2\
1515                0002\
1516                0002");
1517
1518         check("\
1519               4000\
1520               0000\
1521               0000\
1522               0000",
1523               3,
1524               "2\
1525               0000\
1526               0000\
1527               0000\
1528               0000");
1529         check("4000\
1530               0000",
1531               2,
1532               "1\
1533               0000\
1534               0000");
1535         check("4000",
1536               2,
1537               "1\
1538               0000");
1539
1540         check("4000\
1541               0000\
1542               0000\
1543               0000",
1544               67,
1545               "2\
1546               0000\
1547               0000\
1548               0000\
1549               0000\
1550               0000\
1551               0000\
1552               0000\
1553               0000");
1554         check("4000\
1555               0000",
1556               35,
1557               "2\
1558               0000\
1559               0000\
1560               0000\
1561               0000");
1562         check("4000",
1563               19,
1564               "2\
1565               0000\
1566               0000");
1567
1568         check("fedc\
1569               ba98\
1570               7654\
1571               3210\
1572               fedc\
1573               ba98\
1574               7654\
1575               3210",
1576               4,
1577               "f\
1578               edcb\
1579               a987\
1580               6543\
1581               210f\
1582               edcb\
1583               a987\
1584               6543\
1585               2100");
1586         check("88887777666655554444333322221111", 16,
1587               "888877776666555544443333222211110000");
1588     }
1589
1590     #[test]
1591     fn test_shr() {
1592         fn check(s: &str, shift: uint, ans: &str) {
1593             let opt_biguint: Option<BigUint> =
1594                 FromStrRadix::from_str_radix(s, 16);
1595             let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1596             assert_eq!(bu.as_slice(), ans);
1597         }
1598
1599         check("0", 3, "0");
1600         check("f", 3, "1");
1601
1602         check("1\
1603               0000\
1604               0000\
1605               0000\
1606               0001\
1607               0000\
1608               0000\
1609               0000\
1610               0001",
1611               3,
1612               "2000\
1613               0000\
1614               0000\
1615               0000\
1616               2000\
1617               0000\
1618               0000\
1619               0000");
1620         check("1\
1621               0000\
1622               0001\
1623               0000\
1624               0001",
1625               2,
1626               "4000\
1627               0000\
1628               4000\
1629               0000");
1630         check("1\
1631               0001\
1632               0001",
1633               1,
1634               "8000\
1635               8000");
1636
1637         check("2\
1638               0000\
1639               0000\
1640               0000\
1641               0001\
1642               0000\
1643               0000\
1644               0000\
1645               0001",
1646               67,
1647               "4000\
1648               0000\
1649               0000\
1650               0000");
1651         check("2\
1652               0000\
1653               0001\
1654               0000\
1655               0001",
1656               35,
1657               "4000\
1658               0000");
1659         check("2\
1660               0001\
1661               0001",
1662               19,
1663               "4000");
1664
1665         check("1\
1666               0000\
1667               0000\
1668               0000\
1669               0000",
1670               1,
1671               "8000\
1672               0000\
1673               0000\
1674               0000");
1675         check("1\
1676               0000\
1677               0000",
1678               1,
1679               "8000\
1680               0000");
1681         check("1\
1682               0000",
1683               1,
1684               "8000");
1685         check("f\
1686               edcb\
1687               a987\
1688               6543\
1689               210f\
1690               edcb\
1691               a987\
1692               6543\
1693               2100",
1694               4,
1695               "fedc\
1696               ba98\
1697               7654\
1698               3210\
1699               fedc\
1700               ba98\
1701               7654\
1702               3210");
1703
1704         check("888877776666555544443333222211110000", 16,
1705               "88887777666655554444333322221111");
1706     }
1707
1708     // `DoubleBigDigit` size dependent
1709     #[test]
1710     fn test_convert_i64() {
1711         fn check(b1: BigUint, i: i64) {
1712             let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1713             assert!(b1 == b2);
1714             assert!(b1.to_i64().unwrap() == i);
1715         }
1716
1717         check(Zero::zero(), 0);
1718         check(One::one(), 1);
1719         check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1720
1721         check(BigUint::new(vec!(           )), 0);
1722         check(BigUint::new(vec!( 1         )), (1 << (0*BigDigit::bits)));
1723         check(BigUint::new(vec!(-1         )), (1 << (1*BigDigit::bits)) - 1);
1724         check(BigUint::new(vec!( 0,  1     )), (1 << (1*BigDigit::bits)));
1725         check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1726
1727         assert_eq!(i64::MIN.to_biguint(), None);
1728         assert_eq!(BigUint::new(vec!(-1, -1    )).to_i64(), None);
1729         assert_eq!(BigUint::new(vec!( 0,  0,  1)).to_i64(), None);
1730         assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1731     }
1732
1733     // `DoubleBigDigit` size dependent
1734     #[test]
1735     fn test_convert_u64() {
1736         fn check(b1: BigUint, u: u64) {
1737             let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1738             assert!(b1 == b2);
1739             assert!(b1.to_u64().unwrap() == u);
1740         }
1741
1742         check(Zero::zero(), 0);
1743         check(One::one(), 1);
1744         check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1745         check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1746
1747         check(BigUint::new(vec!(      )), 0);
1748         check(BigUint::new(vec!( 1    )), (1 << (0*BigDigit::bits)));
1749         check(BigUint::new(vec!(-1    )), (1 << (1*BigDigit::bits)) - 1);
1750         check(BigUint::new(vec!( 0,  1)), (1 << (1*BigDigit::bits)));
1751         check(BigUint::new(vec!(-1, -1)), u64::MAX);
1752
1753         assert_eq!(BigUint::new(vec!( 0,  0,  1)).to_u64(), None);
1754         assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1755     }
1756
1757     #[test]
1758     fn test_convert_to_bigint() {
1759         fn check(n: BigUint, ans: BigInt) {
1760             assert_eq!(n.to_bigint().unwrap(), ans);
1761             assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1762         }
1763         check(Zero::zero(), Zero::zero());
1764         check(BigUint::new(vec!(1,2,3)),
1765               BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1766     }
1767
1768     static sum_triples: &'static [(&'static [BigDigit],
1769                                    &'static [BigDigit],
1770                                    &'static [BigDigit])] = &[
1771         (&[],          &[],       &[]),
1772         (&[],          &[ 1],     &[ 1]),
1773         (&[ 1],        &[ 1],     &[ 2]),
1774         (&[ 1],        &[ 1,  1], &[ 2,  1]),
1775         (&[ 1],        &[-1],     &[ 0,  1]),
1776         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
1777         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
1778         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
1779         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
1780     ];
1781
1782     #[test]
1783     fn test_add() {
1784         for elm in sum_triples.iter() {
1785             let (a_vec, b_vec, c_vec) = *elm;
1786             let a = BigUint::from_slice(a_vec);
1787             let b = BigUint::from_slice(b_vec);
1788             let c = BigUint::from_slice(c_vec);
1789
1790             assert!(a + b == c);
1791             assert!(b + a == c);
1792         }
1793     }
1794
1795     #[test]
1796     fn test_sub() {
1797         for elm in sum_triples.iter() {
1798             let (a_vec, b_vec, c_vec) = *elm;
1799             let a = BigUint::from_slice(a_vec);
1800             let b = BigUint::from_slice(b_vec);
1801             let c = BigUint::from_slice(c_vec);
1802
1803             assert!(c - a == b);
1804             assert!(c - b == a);
1805         }
1806     }
1807
1808     #[test]
1809     #[should_fail]
1810     fn test_sub_fail_on_underflow() {
1811         let (a, b) : (BigUint, BigUint) = (Zero::zero(), One::one());
1812         a - b;
1813     }
1814
1815     static mul_triples: &'static [(&'static [BigDigit],
1816                                    &'static [BigDigit],
1817                                    &'static [BigDigit])] = &[
1818         (&[],               &[],               &[]),
1819         (&[],               &[ 1],             &[]),
1820         (&[ 2],             &[],               &[]),
1821         (&[ 1],             &[ 1],             &[1]),
1822         (&[ 2],             &[ 3],             &[ 6]),
1823         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
1824         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
1825         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
1826         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
1827         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
1828         (&[-1],             &[-1],             &[ 1, -2]),
1829         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
1830         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
1831         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
1832         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
1833         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
1834         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
1835         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
1836         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
1837         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
1838         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
1839     ];
1840
1841     static div_rem_quadruples: &'static [(&'static [BigDigit],
1842                                            &'static [BigDigit],
1843                                            &'static [BigDigit],
1844                                            &'static [BigDigit])]
1845         = &[
1846             (&[ 1],        &[ 2], &[],               &[1]),
1847             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
1848             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1849             (&[ 0,  1],    &[-1], &[1],              &[1]),
1850             (&[-1, -1],    &[-2], &[2, 1],           &[3])
1851         ];
1852
1853     #[test]
1854     fn test_mul() {
1855         for elm in mul_triples.iter() {
1856             let (a_vec, b_vec, c_vec) = *elm;
1857             let a = BigUint::from_slice(a_vec);
1858             let b = BigUint::from_slice(b_vec);
1859             let c = BigUint::from_slice(c_vec);
1860
1861             assert!(a * b == c);
1862             assert!(b * a == c);
1863         }
1864
1865         for elm in div_rem_quadruples.iter() {
1866             let (a_vec, b_vec, c_vec, d_vec) = *elm;
1867             let a = BigUint::from_slice(a_vec);
1868             let b = BigUint::from_slice(b_vec);
1869             let c = BigUint::from_slice(c_vec);
1870             let d = BigUint::from_slice(d_vec);
1871
1872             assert!(a == b * c + d);
1873             assert!(a == c * b + d);
1874         }
1875     }
1876
1877     #[test]
1878     fn test_div_rem() {
1879         for elm in mul_triples.iter() {
1880             let (a_vec, b_vec, c_vec) = *elm;
1881             let a = BigUint::from_slice(a_vec);
1882             let b = BigUint::from_slice(b_vec);
1883             let c = BigUint::from_slice(c_vec);
1884
1885             if !a.is_zero() {
1886                 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1887             }
1888             if !b.is_zero() {
1889                 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1890             }
1891         }
1892
1893         for elm in div_rem_quadruples.iter() {
1894             let (a_vec, b_vec, c_vec, d_vec) = *elm;
1895             let a = BigUint::from_slice(a_vec);
1896             let b = BigUint::from_slice(b_vec);
1897             let c = BigUint::from_slice(c_vec);
1898             let d = BigUint::from_slice(d_vec);
1899
1900             if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1901         }
1902     }
1903
1904     #[test]
1905     fn test_checked_add() {
1906         for elm in sum_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);
1911
1912             assert!(a.checked_add(&b).unwrap() == c);
1913             assert!(b.checked_add(&a).unwrap() == c);
1914         }
1915     }
1916
1917     #[test]
1918     fn test_checked_sub() {
1919         for elm in sum_triples.iter() {
1920             let (aVec, bVec, cVec) = *elm;
1921             let a = BigUint::from_slice(aVec);
1922             let b = BigUint::from_slice(bVec);
1923             let c = BigUint::from_slice(cVec);
1924
1925             assert!(c.checked_sub(&a).unwrap() == b);
1926             assert!(c.checked_sub(&b).unwrap() == a);
1927
1928             if a > c {
1929                 assert!(a.checked_sub(&c).is_none());
1930             }
1931             if b > c {
1932                 assert!(b.checked_sub(&c).is_none());
1933             }
1934         }
1935     }
1936
1937     #[test]
1938     fn test_checked_mul() {
1939         for elm in mul_triples.iter() {
1940             let (aVec, bVec, cVec) = *elm;
1941             let a = BigUint::from_slice(aVec);
1942             let b = BigUint::from_slice(bVec);
1943             let c = BigUint::from_slice(cVec);
1944
1945             assert!(a.checked_mul(&b).unwrap() == c);
1946             assert!(b.checked_mul(&a).unwrap() == c);
1947         }
1948
1949         for elm in div_rem_quadruples.iter() {
1950             let (aVec, bVec, cVec, dVec) = *elm;
1951             let a = BigUint::from_slice(aVec);
1952             let b = BigUint::from_slice(bVec);
1953             let c = BigUint::from_slice(cVec);
1954             let d = BigUint::from_slice(dVec);
1955
1956             assert!(a == b.checked_mul(&c).unwrap() + d);
1957             assert!(a == c.checked_mul(&b).unwrap() + d);
1958         }
1959     }
1960
1961     #[test]
1962     fn test_checked_div() {
1963         for elm in mul_triples.iter() {
1964             let (aVec, bVec, cVec) = *elm;
1965             let a = BigUint::from_slice(aVec);
1966             let b = BigUint::from_slice(bVec);
1967             let c = BigUint::from_slice(cVec);
1968
1969             if !a.is_zero() {
1970                 assert!(c.checked_div(&a).unwrap() == b);
1971             }
1972             if !b.is_zero() {
1973                 assert!(c.checked_div(&b).unwrap() == a);
1974             }
1975
1976             assert!(c.checked_div(&Zero::zero()).is_none());
1977         }
1978     }
1979
1980     #[test]
1981     fn test_gcd() {
1982         fn check(a: uint, b: uint, c: uint) {
1983             let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
1984             let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
1985             let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
1986
1987             assert_eq!(big_a.gcd(&big_b), big_c);
1988         }
1989
1990         check(10, 2, 2);
1991         check(10, 3, 1);
1992         check(0, 3, 3);
1993         check(3, 3, 3);
1994         check(56, 42, 14);
1995     }
1996
1997     #[test]
1998     fn test_lcm() {
1999         fn check(a: uint, b: uint, c: uint) {
2000             let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2001             let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2002             let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2003
2004             assert_eq!(big_a.lcm(&big_b), big_c);
2005         }
2006
2007         check(1, 0, 0);
2008         check(0, 1, 0);
2009         check(1, 1, 1);
2010         check(8, 9, 72);
2011         check(11, 5, 55);
2012         check(99, 17, 1683);
2013     }
2014
2015     #[test]
2016     fn test_is_even() {
2017         let one: BigUint = FromStr::from_str("1").unwrap();
2018         let two: BigUint = FromStr::from_str("2").unwrap();
2019         let thousand: BigUint = FromStr::from_str("1000").unwrap();
2020         let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
2021         let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
2022         assert!(one.is_odd());
2023         assert!(two.is_even());
2024         assert!(thousand.is_even());
2025         assert!(big.is_even());
2026         assert!(bigger.is_odd());
2027         assert!((one << 64).is_even());
2028         assert!(((one << 64) + one).is_odd());
2029     }
2030
2031     fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, String)>)> {
2032         let bits = BigDigit::bits;
2033         vec!(( Zero::zero(), vec!(
2034             (2, "0".to_string()), (3, "0".to_string())
2035         )), ( BigUint::from_slice([ 0xff ]), vec!(
2036             (2,  "11111111".to_string()),
2037             (3,  "100110".to_string()),
2038             (4,  "3333".to_string()),
2039             (5,  "2010".to_string()),
2040             (6,  "1103".to_string()),
2041             (7,  "513".to_string()),
2042             (8,  "377".to_string()),
2043             (9,  "313".to_string()),
2044             (10, "255".to_string()),
2045             (11, "212".to_string()),
2046             (12, "193".to_string()),
2047             (13, "168".to_string()),
2048             (14, "143".to_string()),
2049             (15, "120".to_string()),
2050             (16, "ff".to_string())
2051         )), ( BigUint::from_slice([ 0xfff ]), vec!(
2052             (2,  "111111111111".to_string()),
2053             (4,  "333333".to_string()),
2054             (16, "fff".to_string())
2055         )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2056             (2,
2057              format!("10{}1", "0".repeat(bits - 1))),
2058             (4,
2059              format!("2{}1", "0".repeat(bits / 2 - 1))),
2060             (10, match bits {
2061                 32 => "8589934593".to_string(),
2062                 16 => "131073".to_string(),
2063                 _ => fail!()
2064             }),
2065             (16,
2066              format!("2{}1", "0".repeat(bits / 4 - 1)))
2067         )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2068             (2,
2069              format!("11{}10{}1",
2070                      "0".repeat(bits - 2),
2071                      "0".repeat(bits - 1))),
2072             (4,
2073              format!("3{}2{}1",
2074                      "0".repeat(bits / 2 - 1),
2075                      "0".repeat(bits / 2 - 1))),
2076             (10, match bits {
2077                 32 => "55340232229718589441".to_string(),
2078                 16 => "12885032961".to_string(),
2079                 _ => fail!()
2080             }),
2081             (16,
2082              format!("3{}2{}1",
2083                      "0".repeat(bits / 4 - 1),
2084                      "0".repeat(bits / 4 - 1)))
2085         )) )
2086     }
2087
2088     #[test]
2089     fn test_to_str_radix() {
2090         let r = to_str_pairs();
2091         for num_pair in r.iter() {
2092             let &(ref n, ref rs) = num_pair;
2093             for str_pair in rs.iter() {
2094                 let &(ref radix, ref str) = str_pair;
2095                 assert_eq!(n.to_str_radix(*radix).as_slice(),
2096                            str.as_slice());
2097             }
2098         }
2099     }
2100
2101     #[test]
2102     fn test_from_str_radix() {
2103         let r = to_str_pairs();
2104         for num_pair in r.iter() {
2105             let &(ref n, ref rs) = num_pair;
2106             for str_pair in rs.iter() {
2107                 let &(ref radix, ref str) = str_pair;
2108                 assert_eq!(n,
2109                            &FromStrRadix::from_str_radix(str.as_slice(),
2110                                                          *radix).unwrap());
2111             }
2112         }
2113
2114         let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2115         assert_eq!(zed, None);
2116         let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2117         assert_eq!(blank, None);
2118         let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2119                                                                       10);
2120         assert_eq!(minus_one, None);
2121     }
2122
2123     #[test]
2124     fn test_factor() {
2125         fn factor(n: uint) -> BigUint {
2126             let mut f: BigUint = One::one();
2127             for i in range(2, n + 1) {
2128                 // FIXME(#5992): assignment operator overloads
2129                 // f *= FromPrimitive::from_uint(i);
2130                 f = f * FromPrimitive::from_uint(i).unwrap();
2131             }
2132             return f;
2133         }
2134
2135         fn check(n: uint, s: &str) {
2136             let n = factor(n);
2137             let ans = match FromStrRadix::from_str_radix(s, 10) {
2138                 Some(x) => x, None => fail!()
2139             };
2140             assert_eq!(n, ans);
2141         }
2142
2143         check(3, "6");
2144         check(10, "3628800");
2145         check(20, "2432902008176640000");
2146         check(30, "265252859812191058636308480000000");
2147     }
2148
2149     #[test]
2150     fn test_bits() {
2151         assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2152         let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2153         assert_eq!(n.bits(), 0);
2154         let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2155         assert_eq!(n.bits(), 1);
2156         let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2157         assert_eq!(n.bits(), 2);
2158         let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2159         assert_eq!(n.bits(), 39);
2160         let one: BigUint = One::one();
2161         assert_eq!((one << 426).bits(), 427);
2162     }
2163
2164     #[test]
2165     fn test_rand() {
2166         let mut rng = task_rng();
2167         let _n: BigUint = rng.gen_biguint(137);
2168         assert!(rng.gen_biguint(0).is_zero());
2169     }
2170
2171     #[test]
2172     fn test_rand_range() {
2173         let mut rng = task_rng();
2174
2175         for _ in range(0u, 10) {
2176             assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2177                                             &FromPrimitive::from_uint(237).unwrap()),
2178                        FromPrimitive::from_uint(236).unwrap());
2179         }
2180
2181         let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2182         let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2183         for _ in range(0u, 1000) {
2184             let n: BigUint = rng.gen_biguint_below(&u);
2185             assert!(n < u);
2186
2187             let n: BigUint = rng.gen_biguint_range(&l, &u);
2188             assert!(n >= l);
2189             assert!(n < u);
2190         }
2191     }
2192
2193     #[test]
2194     #[should_fail]
2195     fn test_zero_rand_range() {
2196         task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2197                                      &FromPrimitive::from_uint(54).unwrap());
2198     }
2199
2200     #[test]
2201     #[should_fail]
2202     fn test_negative_rand_range() {
2203         let mut rng = task_rng();
2204         let l = FromPrimitive::from_uint(2352).unwrap();
2205         let u = FromPrimitive::from_uint(3513).unwrap();
2206         // Switching u and l should fail:
2207         let _n: BigUint = rng.gen_biguint_range(&u, &l);
2208     }
2209 }
2210
2211 #[cfg(test)]
2212 mod bigint_tests {
2213     use Integer;
2214     use super::{BigDigit, BigUint, ToBigUint};
2215     use super::{Sign, Minus, Zero, Plus, BigInt, RandBigInt, ToBigInt};
2216
2217     use std::cmp::{Less, Equal, Greater};
2218     use std::i64;
2219     use std::num::CheckedDiv;
2220     use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2221     use std::num::{ToPrimitive, FromPrimitive};
2222     use std::rand::task_rng;
2223     use std::u64;
2224
2225     #[test]
2226     fn test_from_biguint() {
2227         fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2228             let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2229             let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2230             assert_eq!(inp, ans);
2231         }
2232         check(Plus, 1, Plus, 1);
2233         check(Plus, 0, Zero, 0);
2234         check(Minus, 1, Minus, 1);
2235         check(Zero, 1, Zero, 0);
2236     }
2237
2238     #[test]
2239     fn test_cmp() {
2240         let vs = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2241         let mut nums = Vec::new();
2242         for s in vs.iter().rev() {
2243             nums.push(BigInt::from_slice(Minus, *s));
2244         }
2245         nums.push(Zero::zero());
2246         nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2247
2248         for (i, ni) in nums.iter().enumerate() {
2249             for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2250                 let j = i + j0;
2251                 if i == j {
2252                     assert_eq!(ni.cmp(nj), Equal);
2253                     assert_eq!(nj.cmp(ni), Equal);
2254                     assert_eq!(ni, nj);
2255                     assert!(!(ni != nj));
2256                     assert!(ni <= nj);
2257                     assert!(ni >= nj);
2258                     assert!(!(ni < nj));
2259                     assert!(!(ni > nj));
2260                 } else {
2261                     assert_eq!(ni.cmp(nj), Less);
2262                     assert_eq!(nj.cmp(ni), Greater);
2263
2264                     assert!(!(ni == nj));
2265                     assert!(ni != nj);
2266
2267                     assert!(ni <= nj);
2268                     assert!(!(ni >= nj));
2269                     assert!(ni < nj);
2270                     assert!(!(ni > nj));
2271
2272                     assert!(!(nj <= ni));
2273                     assert!(nj >= ni);
2274                     assert!(!(nj < ni));
2275                     assert!(nj > ni);
2276                 }
2277             }
2278         }
2279     }
2280
2281     #[test]
2282     fn test_convert_i64() {
2283         fn check(b1: BigInt, i: i64) {
2284             let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2285             assert!(b1 == b2);
2286             assert!(b1.to_i64().unwrap() == i);
2287         }
2288
2289         check(Zero::zero(), 0);
2290         check(One::one(), 1);
2291         check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2292         check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2293
2294         assert_eq!(
2295             (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2296             None);
2297
2298         assert_eq!(
2299             BigInt::from_biguint(Plus,  BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2300             None);
2301
2302         assert_eq!(
2303             BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2304             None);
2305
2306         assert_eq!(
2307             BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2308             None);
2309     }
2310
2311     #[test]
2312     fn test_convert_u64() {
2313         fn check(b1: BigInt, u: u64) {
2314             let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2315             assert!(b1 == b2);
2316             assert!(b1.to_u64().unwrap() == u);
2317         }
2318
2319         check(Zero::zero(), 0);
2320         check(One::one(), 1);
2321         check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2322         check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2323
2324         assert_eq!(
2325             BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2326             None);
2327
2328         let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2329         assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2330         assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2331     }
2332
2333     #[test]
2334     fn test_convert_to_biguint() {
2335         fn check(n: BigInt, ans_1: BigUint) {
2336             assert_eq!(n.to_biguint().unwrap(), ans_1);
2337             assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2338         }
2339         let zero: BigInt = Zero::zero();
2340         let unsigned_zero: BigUint = Zero::zero();
2341         let positive = BigInt::from_biguint(
2342             Plus, BigUint::new(vec!(1,2,3)));
2343         let negative = -positive;
2344
2345         check(zero, unsigned_zero);
2346         check(positive, BigUint::new(vec!(1,2,3)));
2347
2348         assert_eq!(negative.to_biguint(), None);
2349     }
2350
2351     static sum_triples: &'static [(&'static [BigDigit],
2352                                    &'static [BigDigit],
2353                                    &'static [BigDigit])] = &[
2354         (&[],          &[],       &[]),
2355         (&[],          &[ 1],     &[ 1]),
2356         (&[ 1],        &[ 1],     &[ 2]),
2357         (&[ 1],        &[ 1,  1], &[ 2,  1]),
2358         (&[ 1],        &[-1],     &[ 0,  1]),
2359         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
2360         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
2361         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
2362         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
2363     ];
2364
2365     #[test]
2366     fn test_add() {
2367         for elm in sum_triples.iter() {
2368             let (a_vec, b_vec, c_vec) = *elm;
2369             let a = BigInt::from_slice(Plus, a_vec);
2370             let b = BigInt::from_slice(Plus, b_vec);
2371             let c = BigInt::from_slice(Plus, c_vec);
2372
2373             assert!(a + b == c);
2374             assert!(b + a == c);
2375             assert!(c + (-a) == b);
2376             assert!(c + (-b) == a);
2377             assert!(a + (-c) == (-b));
2378             assert!(b + (-c) == (-a));
2379             assert!((-a) + (-b) == (-c))
2380             assert!(a + (-a) == Zero::zero());
2381         }
2382     }
2383
2384     #[test]
2385     fn test_sub() {
2386         for elm in sum_triples.iter() {
2387             let (a_vec, b_vec, c_vec) = *elm;
2388             let a = BigInt::from_slice(Plus, a_vec);
2389             let b = BigInt::from_slice(Plus, b_vec);
2390             let c = BigInt::from_slice(Plus, c_vec);
2391
2392             assert!(c - a == b);
2393             assert!(c - b == a);
2394             assert!((-b) - a == (-c))
2395             assert!((-a) - b == (-c))
2396             assert!(b - (-a) == c);
2397             assert!(a - (-b) == c);
2398             assert!((-c) - (-a) == (-b));
2399             assert!(a - a == Zero::zero());
2400         }
2401     }
2402
2403     static mul_triples: &'static [(&'static [BigDigit],
2404                                    &'static [BigDigit],
2405                                    &'static [BigDigit])] = &[
2406         (&[],               &[],               &[]),
2407         (&[],               &[ 1],             &[]),
2408         (&[ 2],             &[],               &[]),
2409         (&[ 1],             &[ 1],             &[1]),
2410         (&[ 2],             &[ 3],             &[ 6]),
2411         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
2412         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
2413         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
2414         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
2415         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
2416         (&[-1],             &[-1],             &[ 1, -2]),
2417         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
2418         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
2419         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
2420         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
2421         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
2422         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
2423         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
2424         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
2425         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
2426         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
2427     ];
2428
2429     static div_rem_quadruples: &'static [(&'static [BigDigit],
2430                                           &'static [BigDigit],
2431                                           &'static [BigDigit],
2432                                           &'static [BigDigit])]
2433         = &[
2434             (&[ 1],        &[ 2], &[],               &[1]),
2435             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
2436             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2437             (&[ 0,  1],    &[-1], &[1],              &[1]),
2438             (&[-1, -1],    &[-2], &[2, 1],           &[3])
2439         ];
2440
2441     #[test]
2442     fn test_mul() {
2443         for elm in mul_triples.iter() {
2444             let (a_vec, b_vec, c_vec) = *elm;
2445             let a = BigInt::from_slice(Plus, a_vec);
2446             let b = BigInt::from_slice(Plus, b_vec);
2447             let c = BigInt::from_slice(Plus, c_vec);
2448
2449             assert!(a * b == c);
2450             assert!(b * a == c);
2451
2452             assert!((-a) * b == -c);
2453             assert!((-b) * a == -c);
2454         }
2455
2456         for elm in div_rem_quadruples.iter() {
2457             let (a_vec, b_vec, c_vec, d_vec) = *elm;
2458             let a = BigInt::from_slice(Plus, a_vec);
2459             let b = BigInt::from_slice(Plus, b_vec);
2460             let c = BigInt::from_slice(Plus, c_vec);
2461             let d = BigInt::from_slice(Plus, d_vec);
2462
2463             assert!(a == b * c + d);
2464             assert!(a == c * b + d);
2465         }
2466     }
2467
2468     #[test]
2469     fn test_div_mod_floor() {
2470         fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2471             let (d, m) = a.div_mod_floor(b);
2472             if !m.is_zero() {
2473                 assert_eq!(m.sign, b.sign);
2474             }
2475             assert!(m.abs() <= b.abs());
2476             assert!(*a == b * d + m);
2477             assert!(d == *ans_d);
2478             assert!(m == *ans_m);
2479         }
2480
2481         fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2482             if m.is_zero() {
2483                 check_sub(a, b, d, m);
2484                 check_sub(a, &b.neg(), &d.neg(), m);
2485                 check_sub(&a.neg(), b, &d.neg(), m);
2486                 check_sub(&a.neg(), &b.neg(), d, m);
2487             } else {
2488                 check_sub(a, b, d, m);
2489                 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2490                 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2491                 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2492             }
2493         }
2494
2495         for elm in mul_triples.iter() {
2496             let (a_vec, b_vec, c_vec) = *elm;
2497             let a = BigInt::from_slice(Plus, a_vec);
2498             let b = BigInt::from_slice(Plus, b_vec);
2499             let c = BigInt::from_slice(Plus, c_vec);
2500
2501             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2502             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2503         }
2504
2505         for elm in div_rem_quadruples.iter() {
2506             let (a_vec, b_vec, c_vec, d_vec) = *elm;
2507             let a = BigInt::from_slice(Plus, a_vec);
2508             let b = BigInt::from_slice(Plus, b_vec);
2509             let c = BigInt::from_slice(Plus, c_vec);
2510             let d = BigInt::from_slice(Plus, d_vec);
2511
2512             if !b.is_zero() {
2513                 check(&a, &b, &c, &d);
2514             }
2515         }
2516     }
2517
2518
2519     #[test]
2520     fn test_div_rem() {
2521         fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2522             let (q, r) = a.div_rem(b);
2523             if !r.is_zero() {
2524                 assert_eq!(r.sign, a.sign);
2525             }
2526             assert!(r.abs() <= b.abs());
2527             assert!(*a == b * q + r);
2528             assert!(q == *ans_q);
2529             assert!(r == *ans_r);
2530         }
2531
2532         fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2533             check_sub(a, b, q, r);
2534             check_sub(a, &b.neg(), &q.neg(), r);
2535             check_sub(&a.neg(), b, &q.neg(), &r.neg());
2536             check_sub(&a.neg(), &b.neg(), q, &r.neg());
2537         }
2538         for elm in mul_triples.iter() {
2539             let (a_vec, b_vec, c_vec) = *elm;
2540             let a = BigInt::from_slice(Plus, a_vec);
2541             let b = BigInt::from_slice(Plus, b_vec);
2542             let c = BigInt::from_slice(Plus, c_vec);
2543
2544             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2545             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2546         }
2547
2548         for elm in div_rem_quadruples.iter() {
2549             let (a_vec, b_vec, c_vec, d_vec) = *elm;
2550             let a = BigInt::from_slice(Plus, a_vec);
2551             let b = BigInt::from_slice(Plus, b_vec);
2552             let c = BigInt::from_slice(Plus, c_vec);
2553             let d = BigInt::from_slice(Plus, d_vec);
2554
2555             if !b.is_zero() {
2556                 check(&a, &b, &c, &d);
2557             }
2558         }
2559     }
2560
2561     #[test]
2562     fn test_checked_add() {
2563         for elm in sum_triples.iter() {
2564             let (aVec, bVec, cVec) = *elm;
2565             let a = BigInt::from_slice(Plus, aVec);
2566             let b = BigInt::from_slice(Plus, bVec);
2567             let c = BigInt::from_slice(Plus, cVec);
2568
2569             assert!(a.checked_add(&b).unwrap() == c);
2570             assert!(b.checked_add(&a).unwrap() == c);
2571             assert!(c.checked_add(&(-a)).unwrap() == b);
2572             assert!(c.checked_add(&(-b)).unwrap() == a);
2573             assert!(a.checked_add(&(-c)).unwrap() == (-b));
2574             assert!(b.checked_add(&(-c)).unwrap() == (-a));
2575             assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2576             assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2577         }
2578     }
2579
2580     #[test]
2581     fn test_checked_sub() {
2582         for elm in sum_triples.iter() {
2583             let (aVec, bVec, cVec) = *elm;
2584             let a = BigInt::from_slice(Plus, aVec);
2585             let b = BigInt::from_slice(Plus, bVec);
2586             let c = BigInt::from_slice(Plus, cVec);
2587
2588             assert!(c.checked_sub(&a).unwrap() == b);
2589             assert!(c.checked_sub(&b).unwrap() == a);
2590             assert!((-b).checked_sub(&a).unwrap() == (-c))
2591             assert!((-a).checked_sub(&b).unwrap() == (-c))
2592             assert!(b.checked_sub(&(-a)).unwrap() == c);
2593             assert!(a.checked_sub(&(-b)).unwrap() == c);
2594             assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2595             assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2596         }
2597     }
2598
2599     #[test]
2600     fn test_checked_mul() {
2601         for elm in mul_triples.iter() {
2602             let (aVec, bVec, cVec) = *elm;
2603             let a = BigInt::from_slice(Plus, aVec);
2604             let b = BigInt::from_slice(Plus, bVec);
2605             let c = BigInt::from_slice(Plus, cVec);
2606
2607             assert!(a.checked_mul(&b).unwrap() == c);
2608             assert!(b.checked_mul(&a).unwrap() == c);
2609
2610             assert!((-a).checked_mul(&b).unwrap() == -c);
2611             assert!((-b).checked_mul(&a).unwrap() == -c);
2612         }
2613
2614         for elm in div_rem_quadruples.iter() {
2615             let (aVec, bVec, cVec, dVec) = *elm;
2616             let a = BigInt::from_slice(Plus, aVec);
2617             let b = BigInt::from_slice(Plus, bVec);
2618             let c = BigInt::from_slice(Plus, cVec);
2619             let d = BigInt::from_slice(Plus, dVec);
2620
2621             assert!(a == b.checked_mul(&c).unwrap() + d);
2622             assert!(a == c.checked_mul(&b).unwrap() + d);
2623         }
2624     }
2625     #[test]
2626     fn test_checked_div() {
2627         for elm in mul_triples.iter() {
2628             let (aVec, bVec, cVec) = *elm;
2629             let a = BigInt::from_slice(Plus, aVec);
2630             let b = BigInt::from_slice(Plus, bVec);
2631             let c = BigInt::from_slice(Plus, cVec);
2632
2633             if !a.is_zero() {
2634                 assert!(c.checked_div(&a).unwrap() == b);
2635                 assert!((-c).checked_div(&(-a)).unwrap() == b);
2636                 assert!((-c).checked_div(&a).unwrap() == -b);
2637             }
2638             if !b.is_zero() {
2639                 assert!(c.checked_div(&b).unwrap() == a);
2640                 assert!((-c).checked_div(&(-b)).unwrap() == a);
2641                 assert!((-c).checked_div(&b).unwrap() == -a);
2642             }
2643
2644             assert!(c.checked_div(&Zero::zero()).is_none());
2645             assert!((-c).checked_div(&Zero::zero()).is_none());
2646         }
2647     }
2648
2649     #[test]
2650     fn test_gcd() {
2651         fn check(a: int, b: int, c: int) {
2652             let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2653             let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2654             let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2655
2656             assert_eq!(big_a.gcd(&big_b), big_c);
2657         }
2658
2659         check(10, 2, 2);
2660         check(10, 3, 1);
2661         check(0, 3, 3);
2662         check(3, 3, 3);
2663         check(56, 42, 14);
2664         check(3, -3, 3);
2665         check(-6, 3, 3);
2666         check(-4, -2, 2);
2667     }
2668
2669     #[test]
2670     fn test_lcm() {
2671         fn check(a: int, b: int, c: int) {
2672             let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2673             let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2674             let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2675
2676             assert_eq!(big_a.lcm(&big_b), big_c);
2677         }
2678
2679         check(1, 0, 0);
2680         check(0, 1, 0);
2681         check(1, 1, 1);
2682         check(-1, 1, 1);
2683         check(1, -1, 1);
2684         check(-1, -1, 1);
2685         check(8, 9, 72);
2686         check(11, 5, 55);
2687     }
2688
2689     #[test]
2690     fn test_abs_sub() {
2691         let zero: BigInt = Zero::zero();
2692         let one: BigInt = One::one();
2693         assert_eq!((-one).abs_sub(&one), zero);
2694         let one: BigInt = One::one();
2695         let zero: BigInt = Zero::zero();
2696         assert_eq!(one.abs_sub(&one), zero);
2697         let one: BigInt = One::one();
2698         let zero: BigInt = Zero::zero();
2699         assert_eq!(one.abs_sub(&zero), one);
2700         let one: BigInt = One::one();
2701         let two: BigInt = FromPrimitive::from_int(2).unwrap();
2702         assert_eq!(one.abs_sub(&-one), two);
2703     }
2704
2705     #[test]
2706     fn test_to_str_radix() {
2707         fn check(n: int, ans: &str) {
2708             let n: BigInt = FromPrimitive::from_int(n).unwrap();
2709             assert!(ans == n.to_str_radix(10).as_slice());
2710         }
2711         check(10, "10");
2712         check(1, "1");
2713         check(0, "0");
2714         check(-1, "-1");
2715         check(-10, "-10");
2716     }
2717
2718
2719     #[test]
2720     fn test_from_str_radix() {
2721         fn check(s: &str, ans: Option<int>) {
2722             let ans = ans.map(|n| {
2723                 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2724                 x
2725             });
2726             assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2727         }
2728         check("10", Some(10));
2729         check("1", Some(1));
2730         check("0", Some(0));
2731         check("-1", Some(-1));
2732         check("-10", Some(-10));
2733         check("Z", None);
2734         check("_", None);
2735
2736         // issue 10522, this hit an edge case that caused it to
2737         // attempt to allocate a vector of size (-1u) == huge.
2738         let x: BigInt =
2739             from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
2740         let _y = x.to_string();
2741     }
2742
2743     #[test]
2744     fn test_neg() {
2745         assert!(-BigInt::new(Plus,  vec!(1, 1, 1)) ==
2746             BigInt::new(Minus, vec!(1, 1, 1)));
2747         assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2748             BigInt::new(Plus,  vec!(1, 1, 1)));
2749         let zero: BigInt = Zero::zero();
2750         assert_eq!(-zero, zero);
2751     }
2752
2753     #[test]
2754     fn test_rand() {
2755         let mut rng = task_rng();
2756         let _n: BigInt = rng.gen_bigint(137);
2757         assert!(rng.gen_bigint(0).is_zero());
2758     }
2759
2760     #[test]
2761     fn test_rand_range() {
2762         let mut rng = task_rng();
2763
2764         for _ in range(0u, 10) {
2765             assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2766                                             &FromPrimitive::from_uint(237).unwrap()),
2767                        FromPrimitive::from_uint(236).unwrap());
2768         }
2769
2770         fn check(l: BigInt, u: BigInt) {
2771             let mut rng = task_rng();
2772             for _ in range(0u, 1000) {
2773                 let n: BigInt = rng.gen_bigint_range(&l, &u);
2774                 assert!(n >= l);
2775                 assert!(n < u);
2776             }
2777         }
2778         let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2779         let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2780         check( l.clone(),  u.clone());
2781         check(-l.clone(),  u.clone());
2782         check(-u.clone(), -l.clone());
2783     }
2784
2785     #[test]
2786     #[should_fail]
2787     fn test_zero_rand_range() {
2788         task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2789                                     &FromPrimitive::from_int(54).unwrap());
2790     }
2791
2792     #[test]
2793     #[should_fail]
2794     fn test_negative_rand_range() {
2795         let mut rng = task_rng();
2796         let l = FromPrimitive::from_uint(2352).unwrap();
2797         let u = FromPrimitive::from_uint(3513).unwrap();
2798         // Switching u and l should fail:
2799         let _n: BigInt = rng.gen_bigint_range(&u, &l);
2800     }
2801 }
2802
2803 #[cfg(test)]
2804 mod bench {
2805     extern crate test;
2806     use self::test::Bencher;
2807     use super::BigUint;
2808     use std::iter;
2809     use std::mem::replace;
2810     use std::num::{FromPrimitive, Zero, One};
2811
2812     fn factorial(n: uint) -> BigUint {
2813         let mut f: BigUint = One::one();
2814         for i in iter::range_inclusive(1, n) {
2815             f = f * FromPrimitive::from_uint(i).unwrap();
2816         }
2817         f
2818     }
2819
2820     fn fib(n: uint) -> BigUint {
2821         let mut f0: BigUint = Zero::zero();
2822         let mut f1: BigUint = One::one();
2823         for _ in range(0, n) {
2824             let f2 = f0 + f1;
2825             f0 = replace(&mut f1, f2);
2826         }
2827         f0
2828     }
2829
2830     #[bench]
2831     fn factorial_100(b: &mut Bencher) {
2832         b.iter(|| {
2833             factorial(100);
2834         });
2835     }
2836
2837     #[bench]
2838     fn fib_100(b: &mut Bencher) {
2839         b.iter(|| {
2840             fib(100);
2841         });
2842     }
2843
2844     #[bench]
2845     fn to_string(b: &mut Bencher) {
2846         let fac = factorial(100);
2847         let fib = fib(100);
2848         b.iter(|| {
2849             fac.to_string();
2850         });
2851         b.iter(|| {
2852             fib.to_string();
2853         });
2854     }
2855
2856     #[bench]
2857     fn shr(b: &mut Bencher) {
2858         let n = { let one : BigUint = One::one(); one << 1000 };
2859         b.iter(|| {
2860             let mut m = n.clone();
2861             for _ in range(0u, 10) {
2862                 m = m >> 1;
2863             }
2864         })
2865     }
2866 }