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