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