]> git.proxmox.com Git - rustc.git/blob - src/libstd/bigint.rs
projects / rustc.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Imported Upstream version 0.6
[rustc.git] / src / libstd / 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 use core::cmp::{Eq, Ord};
20 use core::num::{IntConvertible, Zero, One};
21 use core::*;
22
23 /**
24 A BigDigit is a BigUint's composing element.
25
26 A BigDigit is half the size of machine word size.
27 */
28 #[cfg(target_arch = "x86")]
29 #[cfg(target_arch = "arm")]
30 #[cfg(target_arch = "mips")]
31 pub type BigDigit = u16;
32
33 /**
34 A BigDigit is a BigUint's composing element.
35
36 A BigDigit is half the size of machine word size.
37 */
38 #[cfg(target_arch = "x86_64")]
39 pub type BigDigit = u32;
40
41 pub mod BigDigit {
42 use bigint::BigDigit;
43
44 #[cfg(target_arch = "x86")]
45 #[cfg(target_arch = "arm")]
46 #[cfg(target_arch = "mips")]
47 pub static bits: uint = 16;
48
49 #[cfg(target_arch = "x86_64")]
50 pub static bits: uint = 32;
51
52 pub static base: uint = 1 << bits;
53 priv static hi_mask: uint = (-1 as uint) << bits;
54 priv static lo_mask: uint = (-1 as uint) >> bits;
55
56 priv fn get_hi(n: uint) -> BigDigit { (n >> bits) as BigDigit }
57 priv fn get_lo(n: uint) -> BigDigit { (n & lo_mask) as BigDigit }
58
59 /// Split one machine sized unsigned integer into two BigDigits.
60 pub fn from_uint(n: uint) -> (BigDigit, BigDigit) {
61 (get_hi(n), get_lo(n))
62 }
63
64 /// Join two BigDigits into one machine sized unsigned integer
65 pub fn to_uint(hi: BigDigit, lo: BigDigit) -> uint {
66 (lo as uint) | ((hi as uint) << bits)
67 }
68 }
69
70 /**
71 A big unsigned integer type.
72
73 A BigUint-typed value BigUint { data: @[a, b, c] } represents a number
74 (a + b * BigDigit::base + c * BigDigit::base^2).
75 */
76 pub struct BigUint {
77 priv data: ~[BigDigit]
78 }
79
80 impl Eq for BigUint {
81 fn eq(&self, other: &BigUint) -> bool { self.cmp(other) == 0 }
82 fn ne(&self, other: &BigUint) -> bool { self.cmp(other) != 0 }
83 }
84
85 impl Ord for BigUint {
86 fn lt(&self, other: &BigUint) -> bool { self.cmp(other) < 0 }
87 fn le(&self, other: &BigUint) -> bool { self.cmp(other) <= 0 }
88 fn ge(&self, other: &BigUint) -> bool { self.cmp(other) >= 0 }
89 fn gt(&self, other: &BigUint) -> bool { self.cmp(other) > 0 }
90 }
91
92 impl ToStr for BigUint {
93 fn to_str(&self) -> ~str { self.to_str_radix(10) }
94 }
95
96 impl from_str::FromStr for BigUint {
97 fn from_str(s: &str) -> Option<BigUint> {
98 BigUint::from_str_radix(s, 10)
99 }
100 }
101
102 impl Shl<uint, BigUint> for BigUint {
103 fn shl(&self, rhs: &uint) -> BigUint {
104 let n_unit = *rhs / BigDigit::bits;
105 let n_bits = *rhs % BigDigit::bits;
106 return self.shl_unit(n_unit).shl_bits(n_bits);
107 }
108 }
109
110 impl Shr<uint, BigUint> for BigUint {
111 fn shr(&self, rhs: &uint) -> BigUint {
112 let n_unit = *rhs / BigDigit::bits;
113 let n_bits = *rhs % BigDigit::bits;
114 return self.shr_unit(n_unit).shr_bits(n_bits);
115 }
116 }
117
118 impl Zero for BigUint {
119 fn zero() -> BigUint { BigUint::new(~[]) }
120 }
121
122 impl One for BigUint {
123 pub fn one() -> BigUint { BigUint::new(~[1]) }
124 }
125
126 impl Add<BigUint, BigUint> for BigUint {
127 fn add(&self, other: &BigUint) -> BigUint {
128 let new_len = uint::max(self.data.len(), other.data.len());
129
130 let mut carry = 0;
131 let sum = do vec::from_fn(new_len) |i| {
132 let ai = if i < self.data.len() { self.data[i] } else { 0 };
133 let bi = if i < other.data.len() { other.data[i] } else { 0 };
134 let (hi, lo) = BigDigit::from_uint(
135 (ai as uint) + (bi as uint) + (carry as uint)
136 );
137 carry = hi;
138 lo
139 };
140 if carry == 0 { return BigUint::new(sum) };
141 return BigUint::new(sum + [carry]);
142 }
143 }
144
145 impl Sub<BigUint, BigUint> for BigUint {
146 fn sub(&self, other: &BigUint) -> BigUint {
147 let new_len = uint::max(self.data.len(), other.data.len());
148
149 let mut borrow = 0;
150 let diff = do vec::from_fn(new_len) |i| {
151 let ai = if i < self.data.len() { self.data[i] } else { 0 };
152 let bi = if i < other.data.len() { other.data[i] } else { 0 };
153 let (hi, lo) = BigDigit::from_uint(
154 (BigDigit::base) +
155 (ai as uint) - (bi as uint) - (borrow as uint)
156 );
157 /*
158 hi * (base) + lo == 1*(base) + ai - bi - borrow
159 => ai - bi - borrow < 0 <=> hi == 0
160 */
161 borrow = if hi == 0 { 1 } else { 0 };
162 lo
163 };
164
165 assert!(borrow == 0); // <=> assert!((self >= other));
166 return BigUint::new(diff);
167 }
168 }
169
170 impl Mul<BigUint, BigUint> for BigUint {
171 fn mul(&self, other: &BigUint) -> BigUint {
172 if self.is_zero() || other.is_zero() { return Zero::zero(); }
173
174 let s_len = self.data.len(), o_len = other.data.len();
175 if s_len == 1 { return mul_digit(other, self.data[0]); }
176 if o_len == 1 { return mul_digit(self, other.data[0]); }
177
178 // Using Karatsuba multiplication
179 // (a1 * base + a0) * (b1 * base + b0)
180 // = a1*b1 * base^2 +
181 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
182 // a0*b0
183 let half_len = uint::max(s_len, o_len) / 2;
184 let (sHi, sLo) = cut_at(self, half_len);
185 let (oHi, oLo) = cut_at(other, half_len);
186
187 let ll = sLo * oLo;
188 let hh = sHi * oHi;
189 let mm = {
190 let (s1, n1) = sub_sign(sHi, sLo);
191 let (s2, n2) = sub_sign(oHi, oLo);
192 if s1 * s2 < 0 {
193 hh + ll + (n1 * n2)
194 } else if s1 * s2 > 0 {
195 hh + ll - (n1 * n2)
196 } else {
197 hh + ll
198 }
199 };
200
201 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
202
203 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
204 if n == 0 { return Zero::zero(); }
205 if n == 1 { return copy *a; }
206
207 let mut carry = 0;
208 let prod = do vec::map(a.data) |ai| {
209 let (hi, lo) = BigDigit::from_uint(
210 (*ai as uint) * (n as uint) + (carry as uint)
211 );
212 carry = hi;
213 lo
214 };
215 if carry == 0 { return BigUint::new(prod) };
216 return BigUint::new(prod + [carry]);
217 }
218
219 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
220 let mid = uint::min(a.data.len(), n);
221 return (BigUint::from_slice(vec::slice(a.data, mid,
222 a.data.len())),
223 BigUint::from_slice(vec::slice(a.data, 0, mid)));
224 }
225
226 fn sub_sign(a: BigUint, b: BigUint) -> (int, BigUint) {
227 match a.cmp(&b) {
228 s if s < 0 => (s, b - a),
229 s if s > 0 => (s, a - b),
230 _ => (0, Zero::zero())
231 }
232 }
233 }
234 }
235
236 impl Div<BigUint, BigUint> for BigUint {
237 fn div(&self, other: &BigUint) -> BigUint {
238 let (d, _) = self.divmod(other);
239 return d;
240 }
241 }
242
243 impl Modulo<BigUint, BigUint> for BigUint {
244 fn modulo(&self, other: &BigUint) -> BigUint {
245 let (_, m) = self.divmod(other);
246 return m;
247 }
248 }
249
250 impl Neg<BigUint> for BigUint {
251 fn neg(&self) -> BigUint { fail!() }
252 }
253
254 impl IntConvertible for BigUint {
255 fn to_int(&self) -> int {
256 uint::min(self.to_uint(), int::max_value as uint) as int
257 }
258
259 fn from_int(n: int) -> BigUint {
260 if (n < 0) { Zero::zero() } else { BigUint::from_uint(n as uint) }
261 }
262 }
263
264 pub impl BigUint {
265 /// Creates and initializes an BigUint.
266 pub fn new(v: ~[BigDigit]) -> BigUint {
267 // omit trailing zeros
268 let new_len = v.rposition(|n| *n != 0).map_default(0, |p| *p + 1);
269
270 if new_len == v.len() { return BigUint { data: v }; }
271 let mut v = v;
272 unsafe { v.truncate(new_len); }
273 return BigUint { data: v };
274 }
275
276 /// Creates and initializes an BigUint.
277 pub fn from_uint(n: uint) -> BigUint {
278 match BigDigit::from_uint(n) {
279 (0, 0) => Zero::zero(),
280 (0, n0) => BigUint::new(~[n0]),
281 (n1, n0) => BigUint::new(~[n0, n1])
282 }
283 }
284
285 /// Creates and initializes an BigUint.
286 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
287 return BigUint::new(vec::from_slice(slice));
288 }
289
290 /// Creates and initializes an BigUint.
291 pub fn from_str_radix(s: &str, radix: uint)
292 -> Option<BigUint> {
293 BigUint::parse_bytes(str::to_bytes(s), radix)
294 }
295
296 /// Creates and initializes an BigUint.
297 pub fn parse_bytes(buf: &[u8], radix: uint)
298 -> Option<BigUint> {
299 let (base, unit_len) = get_radix_base(radix);
300 let base_num: BigUint = BigUint::from_uint(base);
301
302 let mut end = buf.len();
303 let mut n: BigUint = Zero::zero();
304 let mut power: BigUint = One::one();
305 loop {
306 let start = uint::max(end, unit_len) - unit_len;
307 match uint::parse_bytes(vec::slice(buf, start, end), radix) {
308 Some(d) => n += BigUint::from_uint(d) * power,
309 None => return None
310 }
311 if end <= unit_len {
312 return Some(n);
313 }
314 end -= unit_len;
315 power *= base_num;
316 }
317 }
318
319 fn abs(&self) -> BigUint { copy *self }
320
321 /// Compare two BigUint value.
322 fn cmp(&self, other: &BigUint) -> int {
323 let s_len = self.data.len(), o_len = other.data.len();
324 if s_len < o_len { return -1; }
325 if s_len > o_len { return 1; }
326
327 for self.data.eachi_reverse |i, elm| {
328 match (*elm, other.data[i]) {
329 (l, r) if l < r => return -1,
330 (l, r) if l > r => return 1,
331 _ => loop
332 };
333 }
334 return 0;
335 }
336
337 fn divmod(&self, other: &BigUint) -> (BigUint, BigUint) {
338 if other.is_zero() { fail!() }
339 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
340 if *other == One::one() { return (copy *self, Zero::zero()); }
341
342 match self.cmp(other) {
343 s if s < 0 => return (Zero::zero(), copy *self),
344 0 => return (One::one(), Zero::zero()),
345 _ => {} // Do nothing
346 }
347
348 let mut shift = 0;
349 let mut n = *other.data.last();
350 while n < (1 << BigDigit::bits - 2) {
351 n <<= 1;
352 shift += 1;
353 }
354 assert!(shift < BigDigit::bits);
355 let (d, m) = divmod_inner(self << shift, other << shift);
356 return (d, m >> shift);
357
358 fn divmod_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
359 let mut r = a;
360 let mut d = Zero::zero::<BigUint>();
361 let mut n = 1;
362 while r >= b {
363 let mut (d0, d_unit, b_unit) = div_estimate(&r, &b, n);
364 let mut prod = b * d0;
365 while prod > r {
366 d0 -= d_unit;
367 prod -= b_unit;
368 }
369 if d0.is_zero() {
370 n = 2;
371 loop;
372 }
373 n = 1;
374 d += d0;
375 r -= prod;
376 }
377 return (d, r);
378 }
379
380 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
381 -> (BigUint, BigUint, BigUint) {
382 if a.data.len() < n {
383 return (Zero::zero(), Zero::zero(), copy *a);
384 }
385
386 let an = vec::slice(a.data, a.data.len() - n, a.data.len());
387 let bn = *b.data.last();
388 let mut d = ~[];
389 let mut carry = 0;
390 for an.each_reverse |elt| {
391 let ai = BigDigit::to_uint(carry, *elt);
392 let di = ai / (bn as uint);
393 assert!(di < BigDigit::base);
394 carry = (ai % (bn as uint)) as BigDigit;
395 d = ~[di as BigDigit] + d;
396 }
397
398 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
399 if shift == 0 {
400 return (BigUint::new(d), One::one(), copy *b);
401 }
402 return (BigUint::from_slice(d).shl_unit(shift),
403 One::one::<BigUint>().shl_unit(shift),
404 b.shl_unit(shift));
405 }
406 }
407
408 fn quot(&self, other: &BigUint) -> BigUint {
409 let (q, _) = self.quotrem(other);
410 return q;
411 }
412 fn rem(&self, other: &BigUint) -> BigUint {
413 let (_, r) = self.quotrem(other);
414 return r;
415 }
416 fn quotrem(&self, other: &BigUint) -> (BigUint, BigUint) {
417 self.divmod(other)
418 }
419
420 fn is_zero(&self) -> bool { self.data.is_empty() }
421 fn is_not_zero(&self) -> bool { !self.data.is_empty() }
422 fn is_positive(&self) -> bool { self.is_not_zero() }
423 fn is_negative(&self) -> bool { false }
424 fn is_nonpositive(&self) -> bool { self.is_zero() }
425 fn is_nonnegative(&self) -> bool { true }
426
427 fn to_uint(&self) -> uint {
428 match self.data.len() {
429 0 => 0,
430 1 => self.data[0] as uint,
431 2 => BigDigit::to_uint(self.data[1], self.data[0]),
432 _ => uint::max_value
433 }
434 }
435
436 fn to_str_radix(&self, radix: uint) -> ~str {
437 assert!(1 < radix && radix <= 16);
438 let (base, max_len) = get_radix_base(radix);
439 if base == BigDigit::base {
440 return fill_concat(self.data, radix, max_len)
441 }
442 return fill_concat(convert_base(copy *self, base), radix, max_len);
443
444 fn convert_base(n: BigUint, base: uint) -> ~[BigDigit] {
445 let divider = BigUint::from_uint(base);
446 let mut result = ~[];
447 let mut r = n;
448 while r > divider {
449 let (d, r0) = r.divmod(&divider);
450 result += [r0.to_uint() as BigDigit];
451 r = d;
452 }
453 if r.is_not_zero() {
454 result += [r.to_uint() as BigDigit];
455 }
456 return result;
457 }
458
459 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> ~str {
460 if v.is_empty() { return ~"0" }
461 let s = str::concat(vec::reversed(v).map(|n| {
462 let s = uint::to_str_radix(*n as uint, radix);
463 str::from_chars(vec::from_elem(l - s.len(), '0')) + s
464 }));
465 str::trim_left_chars(s, ['0']).to_owned()
466 }
467 }
468
469 priv fn shl_unit(self, n_unit: uint) -> BigUint {
470 if n_unit == 0 || self.is_zero() { return self; }
471
472 return BigUint::new(vec::from_elem(n_unit, 0) + self.data);
473 }
474
475 priv fn shl_bits(self, n_bits: uint) -> BigUint {
476 if n_bits == 0 || self.is_zero() { return self; }
477
478 let mut carry = 0;
479 let shifted = do vec::map(self.data) |elem| {
480 let (hi, lo) = BigDigit::from_uint(
481 (*elem as uint) << n_bits | (carry as uint)
482 );
483 carry = hi;
484 lo
485 };
486 if carry == 0 { return BigUint::new(shifted); }
487 return BigUint::new(shifted + [carry]);
488 }
489
490 priv fn shr_unit(self, n_unit: uint) -> BigUint {
491 if n_unit == 0 { return self; }
492 if self.data.len() < n_unit { return Zero::zero(); }
493 return BigUint::from_slice(
494 vec::slice(self.data, n_unit, self.data.len())
495 );
496 }
497
498 priv fn shr_bits(self, n_bits: uint) -> BigUint {
499 if n_bits == 0 || self.data.is_empty() { return self; }
500
501 let mut borrow = 0;
502 let mut shifted = ~[];
503 for self.data.each_reverse |elem| {
504 shifted = ~[(*elem >> n_bits) | borrow] + shifted;
505 borrow = *elem << (uint::bits - n_bits);
506 }
507 return BigUint::new(shifted);
508 }
509 }
510
511 #[cfg(target_arch = "x86_64")]
512 priv fn get_radix_base(radix: uint) -> (uint, uint) {
513 assert!(1 < radix && radix <= 16);
514 match radix {
515 2 => (4294967296, 32),
516 3 => (3486784401, 20),
517 4 => (4294967296, 16),
518 5 => (1220703125, 13),
519 6 => (2176782336, 12),
520 7 => (1977326743, 11),
521 8 => (1073741824, 10),
522 9 => (3486784401, 10),
523 10 => (1000000000, 9),
524 11 => (2357947691, 9),
525 12 => (429981696, 8),
526 13 => (815730721, 8),
527 14 => (1475789056, 8),
528 15 => (2562890625, 8),
529 16 => (4294967296, 8),
530 _ => fail!()
531 }
532 }
533
534 #[cfg(target_arch = "arm")]
535 #[cfg(target_arch = "x86")]
536 #[cfg(target_arch = "mips")]
537 priv fn get_radix_base(radix: uint) -> (uint, uint) {
538 assert!(1 < radix && radix <= 16);
539 match radix {
540 2 => (65536, 16),
541 3 => (59049, 10),
542 4 => (65536, 8),
543 5 => (15625, 6),
544 6 => (46656, 6),
545 7 => (16807, 5),
546 8 => (32768, 5),
547 9 => (59049, 5),
548 10 => (10000, 4),
549 11 => (14641, 4),
550 12 => (20736, 4),
551 13 => (28561, 4),
552 14 => (38416, 4),
553 15 => (50625, 4),
554 16 => (65536, 4),
555 _ => fail!()
556 }
557 }
558
559 /// A Sign is a BigInt's composing element.
560 #[deriving(Eq)]
561 pub enum Sign { Minus, Zero, Plus }
562
563 impl Ord for Sign {
564 fn lt(&self, other: &Sign) -> bool { self.cmp(other) < 0 }
565 fn le(&self, other: &Sign) -> bool { self.cmp(other) <= 0 }
566 fn ge(&self, other: &Sign) -> bool { self.cmp(other) >= 0 }
567 fn gt(&self, other: &Sign) -> bool { self.cmp(other) > 0 }
568 }
569
570 pub impl Sign {
571 /// Compare two Sign.
572 fn cmp(&self, other: &Sign) -> int {
573 match (*self, *other) {
574 (Minus, Minus) | (Zero, Zero) | (Plus, Plus) => 0,
575 (Minus, Zero) | (Minus, Plus) | (Zero, Plus) => -1,
576 _ => 1
577 }
578 }
579
580 /// Negate Sign value.
581 fn neg(&self) -> Sign {
582 match *self {
583 Minus => Plus,
584 Zero => Zero,
585 Plus => Minus
586 }
587 }
588 }
589
590 /// A big signed integer type.
591 pub struct BigInt {
592 priv sign: Sign,
593 priv data: BigUint
594 }
595
596 impl Eq for BigInt {
597 fn eq(&self, other: &BigInt) -> bool { self.cmp(other) == 0 }
598 fn ne(&self, other: &BigInt) -> bool { self.cmp(other) != 0 }
599 }
600
601 impl Ord for BigInt {
602 fn lt(&self, other: &BigInt) -> bool { self.cmp(other) < 0 }
603 fn le(&self, other: &BigInt) -> bool { self.cmp(other) <= 0 }
604 fn ge(&self, other: &BigInt) -> bool { self.cmp(other) >= 0 }
605 fn gt(&self, other: &BigInt) -> bool { self.cmp(other) > 0 }
606 }
607
608 impl ToStr for BigInt {
609 fn to_str(&self) -> ~str { self.to_str_radix(10) }
610 }
611
612 impl from_str::FromStr for BigInt {
613 fn from_str(s: &str) -> Option<BigInt> {
614 BigInt::from_str_radix(s, 10)
615 }
616 }
617
618 impl Shl<uint, BigInt> for BigInt {
619 fn shl(&self, rhs: &uint) -> BigInt {
620 BigInt::from_biguint(self.sign, self.data << *rhs)
621 }
622 }
623
624 impl Shr<uint, BigInt> for BigInt {
625 fn shr(&self, rhs: &uint) -> BigInt {
626 BigInt::from_biguint(self.sign, self.data >> *rhs)
627 }
628 }
629
630 impl Zero for BigInt {
631 pub fn zero() -> BigInt {
632 BigInt::from_biguint(Zero, Zero::zero())
633 }
634 }
635
636 impl One for BigInt {
637 pub fn one() -> BigInt {
638 BigInt::from_biguint(Plus, One::one())
639 }
640 }
641
642 impl Add<BigInt, BigInt> for BigInt {
643 fn add(&self, other: &BigInt) -> BigInt {
644 match (self.sign, other.sign) {
645 (Zero, _) => copy *other,
646 (_, Zero) => copy *self,
647 (Plus, Plus) => BigInt::from_biguint(Plus,
648 self.data + other.data),
649 (Plus, Minus) => self - (-*other),
650 (Minus, Plus) => other - (-*self),
651 (Minus, Minus) => -((-self) + (-*other))
652 }
653 }
654 }
655
656 impl Sub<BigInt, BigInt> for BigInt {
657 fn sub(&self, other: &BigInt) -> BigInt {
658 match (self.sign, other.sign) {
659 (Zero, _) => -other,
660 (_, Zero) => copy *self,
661 (Plus, Plus) => match self.data.cmp(&other.data) {
662 s if s < 0 =>
663 BigInt::from_biguint(Minus, other.data - self.data),
664 s if s > 0 =>
665 BigInt::from_biguint(Plus, self.data - other.data),
666 _ =>
667 Zero::zero()
668 },
669 (Plus, Minus) => self + (-*other),
670 (Minus, Plus) => -((-self) + *other),
671 (Minus, Minus) => (-other) - (-*self)
672 }
673 }
674 }
675
676 impl Mul<BigInt, BigInt> for BigInt {
677 fn mul(&self, other: &BigInt) -> BigInt {
678 match (self.sign, other.sign) {
679 (Zero, _) | (_, Zero) => Zero::zero(),
680 (Plus, Plus) | (Minus, Minus) => {
681 BigInt::from_biguint(Plus, self.data * other.data)
682 },
683 (Plus, Minus) | (Minus, Plus) => {
684 BigInt::from_biguint(Minus, self.data * other.data)
685 }
686 }
687 }
688 }
689
690 impl Div<BigInt, BigInt> for BigInt {
691 fn div(&self, other: &BigInt) -> BigInt {
692 let (d, _) = self.divmod(other);
693 return d;
694 }
695 }
696
697 impl Modulo<BigInt, BigInt> for BigInt {
698 fn modulo(&self, other: &BigInt) -> BigInt {
699 let (_, m) = self.divmod(other);
700 return m;
701 }
702 }
703
704 impl Neg<BigInt> for BigInt {
705 fn neg(&self) -> BigInt {
706 BigInt::from_biguint(self.sign.neg(), copy self.data)
707 }
708 }
709
710 impl IntConvertible for BigInt {
711 fn to_int(&self) -> int {
712 match self.sign {
713 Plus => uint::min(self.to_uint(), int::max_value as uint) as int,
714 Zero => 0,
715 Minus => uint::min((-self).to_uint(),
716 (int::max_value as uint) + 1) as int
717 }
718 }
719
720 fn from_int(n: int) -> BigInt {
721 if n > 0 {
722 return BigInt::from_biguint(Plus, BigUint::from_uint(n as uint));
723 }
724 if n < 0 {
725 return BigInt::from_biguint(
726 Minus, BigUint::from_uint(uint::max_value - (n as uint) + 1)
727 );
728 }
729 return Zero::zero();
730 }
731 }
732
733 pub impl BigInt {
734 /// Creates and initializes an BigInt.
735 pub fn new(sign: Sign, v: ~[BigDigit]) -> BigInt {
736 BigInt::from_biguint(sign, BigUint::new(v))
737 }
738
739 /// Creates and initializes an BigInt.
740 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
741 if sign == Zero || data.is_zero() {
742 return BigInt { sign: Zero, data: Zero::zero() };
743 }
744 return BigInt { sign: sign, data: data };
745 }
746
747 /// Creates and initializes an BigInt.
748 pub fn from_uint(n: uint) -> BigInt {
749 if n == 0 { return Zero::zero(); }
750 return BigInt::from_biguint(Plus, BigUint::from_uint(n));
751 }
752
753 /// Creates and initializes an BigInt.
754 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
755 BigInt::from_biguint(sign, BigUint::from_slice(slice))
756 }
757
758 /// Creates and initializes an BigInt.
759 pub fn from_str_radix(s: &str, radix: uint)
760 -> Option<BigInt> {
761 BigInt::parse_bytes(str::to_bytes(s), radix)
762 }
763
764 /// Creates and initializes an BigInt.
765 pub fn parse_bytes(buf: &[u8], radix: uint)
766 -> Option<BigInt> {
767 if buf.is_empty() { return None; }
768 let mut sign = Plus;
769 let mut start = 0;
770 if buf[0] == ('-' as u8) {
771 sign = Minus;
772 start = 1;
773 }
774 return BigUint::parse_bytes(vec::slice(buf, start, buf.len()), radix)
775 .map(|bu| BigInt::from_biguint(sign, *bu));
776 }
777
778 fn abs(&self) -> BigInt {
779 BigInt::from_biguint(Plus, copy self.data)
780 }
781
782 fn cmp(&self, other: &BigInt) -> int {
783 let ss = self.sign, os = other.sign;
784 if ss < os { return -1; }
785 if ss > os { return 1; }
786
787 assert!(ss == os);
788 match ss {
789 Zero => 0,
790 Plus => self.data.cmp(&other.data),
791 Minus => self.data.cmp(&other.data).neg(),
792 }
793 }
794
795 fn divmod(&self, other: &BigInt) -> (BigInt, BigInt) {
796 // m.sign == other.sign
797 let (d_ui, m_ui) = self.data.divmod(&other.data);
798 let d = BigInt::from_biguint(Plus, d_ui),
799 m = BigInt::from_biguint(Plus, m_ui);
800 match (self.sign, other.sign) {
801 (_, Zero) => fail!(),
802 (Plus, Plus) | (Zero, Plus) => (d, m),
803 (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
804 (-d, Zero::zero())
805 } else {
806 (-d - One::one(), m + *other)
807 },
808 (Minus, Plus) => if m.is_zero() {
809 (-d, Zero::zero())
810 } else {
811 (-d - One::one(), other - m)
812 },
813 (Minus, Minus) => (d, -m)
814 }
815 }
816
817 fn quot(&self, other: &BigInt) -> BigInt {
818 let (q, _) = self.quotrem(other);
819 return q;
820 }
821 fn rem(&self, other: &BigInt) -> BigInt {
822 let (_, r) = self.quotrem(other);
823 return r;
824 }
825
826 fn quotrem(&self, other: &BigInt) -> (BigInt, BigInt) {
827 // r.sign == self.sign
828 let (q_ui, r_ui) = self.data.quotrem(&other.data);
829 let q = BigInt::from_biguint(Plus, q_ui);
830 let r = BigInt::from_biguint(Plus, r_ui);
831 match (self.sign, other.sign) {
832 (_, Zero) => fail!(),
833 (Plus, Plus) | (Zero, Plus) => ( q, r),
834 (Plus, Minus) | (Zero, Minus) => (-q, r),
835 (Minus, Plus) => (-q, -r),
836 (Minus, Minus) => ( q, -r)
837 }
838 }
839
840 fn is_zero(&self) -> bool { self.sign == Zero }
841 fn is_not_zero(&self) -> bool { self.sign != Zero }
842 fn is_positive(&self) -> bool { self.sign == Plus }
843 fn is_negative(&self) -> bool { self.sign == Minus }
844 fn is_nonpositive(&self) -> bool { self.sign != Plus }
845 fn is_nonnegative(&self) -> bool { self.sign != Minus }
846
847 fn to_uint(&self) -> uint {
848 match self.sign {
849 Plus => self.data.to_uint(),
850 Zero => 0,
851 Minus => 0
852 }
853 }
854
855 fn to_str_radix(&self, radix: uint) -> ~str {
856 match self.sign {
857 Plus => self.data.to_str_radix(radix),
858 Zero => ~"0",
859 Minus => ~"-" + self.data.to_str_radix(radix)
860 }
861 }
862 }
863
864 #[cfg(test)]
865 mod biguint_tests {
866
867 use core::*;
868 use core::num::{IntConvertible, Zero, One};
869 use super::{BigUint, BigDigit};
870
871 #[test]
872 fn test_from_slice() {
873 fn check(slice: &[BigDigit], data: &[BigDigit]) {
874 assert!(data == BigUint::from_slice(slice).data);
875 }
876 check(~[1], ~[1]);
877 check(~[0, 0, 0], ~[]);
878 check(~[1, 2, 0, 0], ~[1, 2]);
879 check(~[0, 0, 1, 2], ~[0, 0, 1, 2]);
880 check(~[0, 0, 1, 2, 0, 0], ~[0, 0, 1, 2]);
881 check(~[-1], ~[-1]);
882 }
883
884 #[test]
885 fn test_cmp() {
886 let data = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ]
887 .map(|v| BigUint::from_slice(*v));
888 for data.eachi |i, ni| {
889 for vec::slice(data, i, data.len()).eachi |j0, nj| {
890 let j = j0 + i;
891 if i == j {
892 assert!(ni.cmp(nj) == 0);
893 assert!(nj.cmp(ni) == 0);
894 assert!(ni == nj);
895 assert!(!(ni != nj));
896 assert!(ni <= nj);
897 assert!(ni >= nj);
898 assert!(!(ni < nj));
899 assert!(!(ni > nj));
900 } else {
901 assert!(ni.cmp(nj) < 0);
902 assert!(nj.cmp(ni) > 0);
903
904 assert!(!(ni == nj));
905 assert!(ni != nj);
906
907 assert!(ni <= nj);
908 assert!(!(ni >= nj));
909 assert!(ni < nj);
910 assert!(!(ni > nj));
911
912 assert!(!(nj <= ni));
913 assert!(nj >= ni);
914 assert!(!(nj < ni));
915 assert!(nj > ni);
916 }
917 }
918 }
919 }
920
921 #[test]
922 fn test_shl() {
923 fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
924 assert!(BigUint::new(v) << shift == BigUint::new(ans));
925 }
926
927 check(~[], 3, ~[]);
928 check(~[1, 1, 1], 3, ~[1 << 3, 1 << 3, 1 << 3]);
929 check(~[1 << (BigDigit::bits - 2)], 2, ~[0, 1]);
930 check(~[1 << (BigDigit::bits - 2)], 3, ~[0, 2]);
931 check(~[1 << (BigDigit::bits - 2)], 3 + BigDigit::bits, ~[0, 0, 2]);
932
933 test_shl_bits();
934
935 #[cfg(target_arch = "x86_64")]
936 fn test_shl_bits() {
937 check(~[0x7654_3210, 0xfedc_ba98,
938 0x7654_3210, 0xfedc_ba98], 4,
939 ~[0x6543_2100, 0xedcb_a987,
940 0x6543_210f, 0xedcb_a987, 0xf]);
941 check(~[0x2222_1111, 0x4444_3333,
942 0x6666_5555, 0x8888_7777], 16,
943 ~[0x1111_0000, 0x3333_2222,
944 0x5555_4444, 0x7777_6666, 0x8888]);
945 }
946
947 #[cfg(target_arch = "arm")]
948 #[cfg(target_arch = "x86")]
949 #[cfg(target_arch = "mips")]
950 fn test_shl_bits() {
951 check(~[0x3210, 0x7654, 0xba98, 0xfedc,
952 0x3210, 0x7654, 0xba98, 0xfedc], 4,
953 ~[0x2100, 0x6543, 0xa987, 0xedcb,
954 0x210f, 0x6543, 0xa987, 0xedcb, 0xf]);
955 check(~[0x1111, 0x2222, 0x3333, 0x4444,
956 0x5555, 0x6666, 0x7777, 0x8888], 16,
957 ~[0x0000, 0x1111, 0x2222, 0x3333,
958 0x4444, 0x5555, 0x6666, 0x7777, 0x8888]);
959 }
960
961 }
962
963 #[test]
964 #[ignore(cfg(target_arch = "x86"))]
965 #[ignore(cfg(target_arch = "arm"))]
966 #[ignore(cfg(target_arch = "mips"))]
967 fn test_shr() {
968 fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
969 assert!(BigUint::new(v) >> shift == BigUint::new(ans));
970 }
971
972 check(~[], 3, ~[]);
973 check(~[1, 1, 1], 3,
974 ~[1 << (BigDigit::bits - 3), 1 << (BigDigit::bits - 3)]);
975 check(~[1 << 2], 2, ~[1]);
976 check(~[1, 2], 3, ~[1 << (BigDigit::bits - 2)]);
977 check(~[1, 1, 2], 3 + BigDigit::bits, ~[1 << (BigDigit::bits - 2)]);
978 test_shr_bits();
979
980 #[cfg(target_arch = "x86_64")]
981 fn test_shr_bits() {
982 check(~[0x6543_2100, 0xedcb_a987,
983 0x6543_210f, 0xedcb_a987, 0xf], 4,
984 ~[0x7654_3210, 0xfedc_ba98,
985 0x7654_3210, 0xfedc_ba98]);
986 check(~[0x1111_0000, 0x3333_2222,
987 0x5555_4444, 0x7777_6666, 0x8888], 16,
988 ~[0x2222_1111, 0x4444_3333,
989 0x6666_5555, 0x8888_7777]);
990 }
991
992 #[cfg(target_arch = "arm")]
993 #[cfg(target_arch = "x86")]
994 #[cfg(target_arch = "mips")]
995 fn test_shr_bits() {
996 check(~[0x2100, 0x6543, 0xa987, 0xedcb,
997 0x210f, 0x6543, 0xa987, 0xedcb, 0xf], 4,
998 ~[0x3210, 0x7654, 0xba98, 0xfedc,
999 0x3210, 0x7654, 0xba98, 0xfedc]);
1000 check(~[0x0000, 0x1111, 0x2222, 0x3333,
1001 0x4444, 0x5555, 0x6666, 0x7777, 0x8888], 16,
1002 ~[0x1111, 0x2222, 0x3333, 0x4444,
1003 0x5555, 0x6666, 0x7777, 0x8888]);
1004 }
1005 }
1006
1007 #[test]
1008 fn test_convert_int() {
1009 fn check(v: ~[BigDigit], i: int) {
1010 let b = BigUint::new(v);
1011 assert!(b == IntConvertible::from_int(i));
1012 assert!(b.to_int() == i);
1013 }
1014
1015 check(~[], 0);
1016 check(~[1], 1);
1017 check(~[-1], (uint::max_value >> BigDigit::bits) as int);
1018 check(~[ 0, 1], ((uint::max_value >> BigDigit::bits) + 1) as int);
1019 check(~[-1, -1 >> 1], int::max_value);
1020
1021 assert!(BigUint::new(~[0, -1]).to_int() == int::max_value);
1022 assert!(BigUint::new(~[0, 0, 1]).to_int() == int::max_value);
1023 assert!(BigUint::new(~[0, 0, -1]).to_int() == int::max_value);
1024 }
1025
1026 #[test]
1027 fn test_convert_uint() {
1028 fn check(v: ~[BigDigit], u: uint) {
1029 let b = BigUint::new(v);
1030 assert!(b == BigUint::from_uint(u));
1031 assert!(b.to_uint() == u);
1032 }
1033
1034 check(~[], 0);
1035 check(~[ 1], 1);
1036 check(~[-1], uint::max_value >> BigDigit::bits);
1037 check(~[ 0, 1], (uint::max_value >> BigDigit::bits) + 1);
1038 check(~[ 0, -1], uint::max_value << BigDigit::bits);
1039 check(~[-1, -1], uint::max_value);
1040
1041 assert!(BigUint::new(~[0, 0, 1]).to_uint() == uint::max_value);
1042 assert!(BigUint::new(~[0, 0, -1]).to_uint() == uint::max_value);
1043 }
1044
1045 static sum_triples: &'static [(&'static [BigDigit],
1046 &'static [BigDigit],
1047 &'static [BigDigit])] = &[
1048 (&[], &[], &[]),
1049 (&[], &[ 1], &[ 1]),
1050 (&[ 1], &[ 1], &[ 2]),
1051 (&[ 1], &[ 1, 1], &[ 2, 1]),
1052 (&[ 1], &[-1], &[ 0, 1]),
1053 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1054 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1055 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1056 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1057 ];
1058
1059 #[test]
1060 fn test_add() {
1061 for sum_triples.each |elm| {
1062 let (aVec, bVec, cVec) = *elm;
1063 let a = BigUint::from_slice(aVec);
1064 let b = BigUint::from_slice(bVec);
1065 let c = BigUint::from_slice(cVec);
1066
1067 assert!(a + b == c);
1068 assert!(b + a == c);
1069 }
1070 }
1071
1072 #[test]
1073 fn test_sub() {
1074 for sum_triples.each |elm| {
1075 let (aVec, bVec, cVec) = *elm;
1076 let a = BigUint::from_slice(aVec);
1077 let b = BigUint::from_slice(bVec);
1078 let c = BigUint::from_slice(cVec);
1079
1080 assert!(c - a == b);
1081 assert!(c - b == a);
1082 }
1083 }
1084
1085 static mul_triples: &'static [(&'static [BigDigit],
1086 &'static [BigDigit],
1087 &'static [BigDigit])] = &[
1088 (&[], &[], &[]),
1089 (&[], &[ 1], &[]),
1090 (&[ 2], &[], &[]),
1091 (&[ 1], &[ 1], &[1]),
1092 (&[ 2], &[ 3], &[ 6]),
1093 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1094 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1095 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1096 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1097 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1098 (&[-1], &[-1], &[ 1, -2]),
1099 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1100 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1101 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1102 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1103 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1104 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1105 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1106 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1107 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1108 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1109 ];
1110
1111 static divmod_quadruples: &'static [(&'static [BigDigit],
1112 &'static [BigDigit],
1113 &'static [BigDigit],
1114 &'static [BigDigit])]
1115 = &[
1116 (&[ 1], &[ 2], &[], &[1]),
1117 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1118 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1119 (&[ 0, 1], &[-1], &[1], &[1]),
1120 (&[-1, -1], &[-2], &[2, 1], &[3])
1121 ];
1122
1123 #[test]
1124 fn test_mul() {
1125 for mul_triples.each |elm| {
1126 let (aVec, bVec, cVec) = *elm;
1127 let a = BigUint::from_slice(aVec);
1128 let b = BigUint::from_slice(bVec);
1129 let c = BigUint::from_slice(cVec);
1130
1131 assert!(a * b == c);
1132 assert!(b * a == c);
1133 }
1134
1135 for divmod_quadruples.each |elm| {
1136 let (aVec, bVec, cVec, dVec) = *elm;
1137 let a = BigUint::from_slice(aVec);
1138 let b = BigUint::from_slice(bVec);
1139 let c = BigUint::from_slice(cVec);
1140 let d = BigUint::from_slice(dVec);
1141
1142 assert!(a == b * c + d);
1143 assert!(a == c * b + d);
1144 }
1145 }
1146
1147 #[test]
1148 fn test_divmod() {
1149 for mul_triples.each |elm| {
1150 let (aVec, bVec, cVec) = *elm;
1151 let a = BigUint::from_slice(aVec);
1152 let b = BigUint::from_slice(bVec);
1153 let c = BigUint::from_slice(cVec);
1154
1155 if a.is_not_zero() {
1156 assert!(c.divmod(&a) == (b, Zero::zero()));
1157 }
1158 if b.is_not_zero() {
1159 assert!(c.divmod(&b) == (a, Zero::zero()));
1160 }
1161 }
1162
1163 for divmod_quadruples.each |elm| {
1164 let (aVec, bVec, cVec, dVec) = *elm;
1165 let a = BigUint::from_slice(aVec);
1166 let b = BigUint::from_slice(bVec);
1167 let c = BigUint::from_slice(cVec);
1168 let d = BigUint::from_slice(dVec);
1169
1170 if b.is_not_zero() { assert!(a.divmod(&b) == (c, d)); }
1171 }
1172 }
1173
1174 fn to_str_pairs() -> ~[ (BigUint, ~[(uint, ~str)]) ] {
1175 let bits = BigDigit::bits;
1176 ~[( Zero::zero(), ~[
1177 (2, ~"0"), (3, ~"0")
1178 ]), ( BigUint::from_slice([ 0xff ]), ~[
1179 (2, ~"11111111"),
1180 (3, ~"100110"),
1181 (4, ~"3333"),
1182 (5, ~"2010"),
1183 (6, ~"1103"),
1184 (7, ~"513"),
1185 (8, ~"377"),
1186 (9, ~"313"),
1187 (10, ~"255"),
1188 (11, ~"212"),
1189 (12, ~"193"),
1190 (13, ~"168"),
1191 (14, ~"143"),
1192 (15, ~"120"),
1193 (16, ~"ff")
1194 ]), ( BigUint::from_slice([ 0xfff ]), ~[
1195 (2, ~"111111111111"),
1196 (4, ~"333333"),
1197 (16, ~"fff")
1198 ]), ( BigUint::from_slice([ 1, 2 ]), ~[
1199 (2,
1200 ~"10" +
1201 str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1202 (4,
1203 ~"2" +
1204 str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1205 (10, match bits {
1206 32 => ~"8589934593", 16 => ~"131073", _ => fail!()
1207 }),
1208 (16,
1209 ~"2" +
1210 str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1211 ]), ( BigUint::from_slice([ 1, 2, 3 ]), ~[
1212 (2,
1213 ~"11" +
1214 str::from_chars(vec::from_elem(bits - 2, '0')) + "10" +
1215 str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1216 (4,
1217 ~"3" +
1218 str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "2" +
1219 str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1220 (10, match bits {
1221 32 => ~"55340232229718589441",
1222 16 => ~"12885032961",
1223 _ => fail!()
1224 }),
1225 (16, ~"3" +
1226 str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "2" +
1227 str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1228 ]) ]
1229 }
1230
1231 #[test]
1232 fn test_to_str_radix() {
1233 for to_str_pairs().each |num_pair| {
1234 let &(n, rs) = num_pair;
1235 for rs.each |str_pair| {
1236 let &(radix, str) = str_pair;
1237 assert!(n.to_str_radix(radix) == str);
1238 }
1239 }
1240 }
1241
1242 #[test]
1243 fn test_from_str_radix() {
1244 for to_str_pairs().each |num_pair| {
1245 let &(n, rs) = num_pair;
1246 for rs.each |str_pair| {
1247 let &(radix, str) = str_pair;
1248 assert!(Some(n) == BigUint::from_str_radix(str, radix));
1249 }
1250 }
1251
1252 assert!(BigUint::from_str_radix(~"Z", 10) == None);
1253 assert!(BigUint::from_str_radix(~"_", 2) == None);
1254 assert!(BigUint::from_str_radix(~"-1", 10) == None);
1255 }
1256
1257 #[test]
1258 fn test_factor() {
1259 fn factor(n: uint) -> BigUint {
1260 let mut f= One::one::<BigUint>();
1261 for uint::range(2, n + 1) |i| {
1262 f *= BigUint::from_uint(i);
1263 }
1264 return f;
1265 }
1266
1267 fn check(n: uint, s: &str) {
1268 let n = factor(n);
1269 let ans = match BigUint::from_str_radix(s, 10) {
1270 Some(x) => x, None => fail!()
1271 };
1272 assert!(n == ans);
1273 }
1274
1275 check(3, "6");
1276 check(10, "3628800");
1277 check(20, "2432902008176640000");
1278 check(30, "265252859812191058636308480000000");
1279 }
1280 }
1281
1282 #[cfg(test)]
1283 mod bigint_tests {
1284 use super::{BigInt, BigUint, BigDigit, Sign, Minus, Zero, Plus};
1285
1286 use core::*;
1287 use core::num::{IntConvertible, Zero, One};
1288
1289 #[test]
1290 fn test_from_biguint() {
1291 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
1292 let inp = BigInt::from_biguint(inp_s, BigUint::from_uint(inp_n));
1293 let ans = BigInt { sign: ans_s, data: BigUint::from_uint(ans_n)};
1294 assert!(inp == ans);
1295 }
1296 check(Plus, 1, Plus, 1);
1297 check(Plus, 0, Zero, 0);
1298 check(Minus, 1, Minus, 1);
1299 check(Zero, 1, Zero, 0);
1300 }
1301
1302 #[test]
1303 fn test_cmp() {
1304 let vs = [ &[2], &[1, 1], &[2, 1], &[1, 1, 1] ];
1305 let mut nums = vec::reversed(vs)
1306 .map(|s| BigInt::from_slice(Minus, *s));
1307 nums.push(Zero::zero());
1308 nums.push_all_move(vs.map(|s| BigInt::from_slice(Plus, *s)));
1309
1310 for nums.eachi |i, ni| {
1311 for vec::slice(nums, i, nums.len()).eachi |j0, nj| {
1312 let j = i + j0;
1313 if i == j {
1314 assert!(ni.cmp(nj) == 0);
1315 assert!(nj.cmp(ni) == 0);
1316 assert!(ni == nj);
1317 assert!(!(ni != nj));
1318 assert!(ni <= nj);
1319 assert!(ni >= nj);
1320 assert!(!(ni < nj));
1321 assert!(!(ni > nj));
1322 } else {
1323 assert!(ni.cmp(nj) < 0);
1324 assert!(nj.cmp(ni) > 0);
1325
1326 assert!(!(ni == nj));
1327 assert!(ni != nj);
1328
1329 assert!(ni <= nj);
1330 assert!(!(ni >= nj));
1331 assert!(ni < nj);
1332 assert!(!(ni > nj));
1333
1334 assert!(!(nj <= ni));
1335 assert!(nj >= ni);
1336 assert!(!(nj < ni));
1337 assert!(nj > ni);
1338 }
1339 }
1340 }
1341 }
1342
1343 #[test]
1344 fn test_convert_int() {
1345 fn check(b: BigInt, i: int) {
1346 assert!(b == IntConvertible::from_int(i));
1347 assert!(b.to_int() == i);
1348 }
1349
1350 check(Zero::zero(), 0);
1351 check(One::one(), 1);
1352 check(BigInt::from_biguint(
1353 Plus, BigUint::from_uint(int::max_value as uint)
1354 ), int::max_value);
1355
1356 assert!(BigInt::from_biguint(
1357 Plus, BigUint::from_uint(int::max_value as uint + 1)
1358 ).to_int() == int::max_value);
1359 assert!(BigInt::from_biguint(
1360 Plus, BigUint::new(~[1, 2, 3])
1361 ).to_int() == int::max_value);
1362
1363 check(BigInt::from_biguint(
1364 Minus, BigUint::from_uint(-int::min_value as uint)
1365 ), int::min_value);
1366 assert!(BigInt::from_biguint(
1367 Minus, BigUint::from_uint(-int::min_value as uint + 1)
1368 ).to_int() == int::min_value);
1369 assert!(BigInt::from_biguint(
1370 Minus, BigUint::new(~[1, 2, 3])
1371 ).to_int() == int::min_value);
1372 }
1373
1374 #[test]
1375 fn test_convert_uint() {
1376 fn check(b: BigInt, u: uint) {
1377 assert!(b == BigInt::from_uint(u));
1378 assert!(b.to_uint() == u);
1379 }
1380
1381 check(Zero::zero(), 0);
1382 check(One::one(), 1);
1383
1384 check(
1385 BigInt::from_biguint(Plus, BigUint::from_uint(uint::max_value)),
1386 uint::max_value);
1387 assert!(BigInt::from_biguint(
1388 Plus, BigUint::new(~[1, 2, 3])
1389 ).to_uint() == uint::max_value);
1390
1391 assert!(BigInt::from_biguint(
1392 Minus, BigUint::from_uint(uint::max_value)
1393 ).to_uint() == 0);
1394 assert!(BigInt::from_biguint(
1395 Minus, BigUint::new(~[1, 2, 3])
1396 ).to_uint() == 0);
1397 }
1398
1399 static sum_triples: &'static [(&'static [BigDigit],
1400 &'static [BigDigit],
1401 &'static [BigDigit])] = &[
1402 (&[], &[], &[]),
1403 (&[], &[ 1], &[ 1]),
1404 (&[ 1], &[ 1], &[ 2]),
1405 (&[ 1], &[ 1, 1], &[ 2, 1]),
1406 (&[ 1], &[-1], &[ 0, 1]),
1407 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1408 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1409 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1410 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1411 ];
1412
1413 #[test]
1414 fn test_add() {
1415 for sum_triples.each |elm| {
1416 let (aVec, bVec, cVec) = *elm;
1417 let a = BigInt::from_slice(Plus, aVec);
1418 let b = BigInt::from_slice(Plus, bVec);
1419 let c = BigInt::from_slice(Plus, cVec);
1420
1421 assert!(a + b == c);
1422 assert!(b + a == c);
1423 assert!(c + (-a) == b);
1424 assert!(c + (-b) == a);
1425 assert!(a + (-c) == (-b));
1426 assert!(b + (-c) == (-a));
1427 assert!((-a) + (-b) == (-c));
1428 assert!(a + (-a) == Zero::zero());
1429 }
1430 }
1431
1432 #[test]
1433 fn test_sub() {
1434 for sum_triples.each |elm| {
1435 let (aVec, bVec, cVec) = *elm;
1436 let a = BigInt::from_slice(Plus, aVec);
1437 let b = BigInt::from_slice(Plus, bVec);
1438 let c = BigInt::from_slice(Plus, cVec);
1439
1440 assert!(c - a == b);
1441 assert!(c - b == a);
1442 assert!((-b) - a == (-c));
1443 assert!((-a) - b == (-c));
1444 assert!(b - (-a) == c);
1445 assert!(a - (-b) == c);
1446 assert!((-c) - (-a) == (-b));
1447 assert!(a - a == Zero::zero());
1448 }
1449 }
1450
1451 static mul_triples: &'static [(&'static [BigDigit],
1452 &'static [BigDigit],
1453 &'static [BigDigit])] = &[
1454 (&[], &[], &[]),
1455 (&[], &[ 1], &[]),
1456 (&[ 2], &[], &[]),
1457 (&[ 1], &[ 1], &[1]),
1458 (&[ 2], &[ 3], &[ 6]),
1459 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1460 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1461 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1462 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1463 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1464 (&[-1], &[-1], &[ 1, -2]),
1465 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1466 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1467 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1468 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1469 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1470 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1471 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1472 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1473 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1474 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1475 ];
1476
1477 static divmod_quadruples: &'static [(&'static [BigDigit],
1478 &'static [BigDigit],
1479 &'static [BigDigit],
1480 &'static [BigDigit])]
1481 = &[
1482 (&[ 1], &[ 2], &[], &[1]),
1483 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1484 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1485 (&[ 0, 1], &[-1], &[1], &[1]),
1486 (&[-1, -1], &[-2], &[2, 1], &[3])
1487 ];
1488
1489 #[test]
1490 fn test_mul() {
1491 for mul_triples.each |elm| {
1492 let (aVec, bVec, cVec) = *elm;
1493 let a = BigInt::from_slice(Plus, aVec);
1494 let b = BigInt::from_slice(Plus, bVec);
1495 let c = BigInt::from_slice(Plus, cVec);
1496
1497 assert!(a * b == c);
1498 assert!(b * a == c);
1499
1500 assert!((-a) * b == -c);
1501 assert!((-b) * a == -c);
1502 }
1503
1504 for divmod_quadruples.each |elm| {
1505 let (aVec, bVec, cVec, dVec) = *elm;
1506 let a = BigInt::from_slice(Plus, aVec);
1507 let b = BigInt::from_slice(Plus, bVec);
1508 let c = BigInt::from_slice(Plus, cVec);
1509 let d = BigInt::from_slice(Plus, dVec);
1510
1511 assert!(a == b * c + d);
1512 assert!(a == c * b + d);
1513 }
1514 }
1515
1516 #[test]
1517 fn test_divmod() {
1518 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
1519 let (d, m) = a.divmod(b);
1520 if m.is_not_zero() {
1521 assert!(m.sign == b.sign);
1522 }
1523 assert!(m.abs() <= b.abs());
1524 assert!(*a == b * d + m);
1525 assert!(d == *ans_d);
1526 assert!(m == *ans_m);
1527 }
1528
1529 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
1530 if m.is_zero() {
1531 check_sub(a, b, d, m);
1532 check_sub(a, &b.neg(), &d.neg(), m);
1533 check_sub(&a.neg(), b, &d.neg(), m);
1534 check_sub(&a.neg(), &b.neg(), d, m);
1535 } else {
1536 check_sub(a, b, d, m);
1537 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
1538 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
1539 check_sub(&a.neg(), &b.neg(), d, &m.neg());
1540 }
1541 }
1542
1543 for mul_triples.each |elm| {
1544 let (aVec, bVec, cVec) = *elm;
1545 let a = BigInt::from_slice(Plus, aVec);
1546 let b = BigInt::from_slice(Plus, bVec);
1547 let c = BigInt::from_slice(Plus, cVec);
1548
1549 if a.is_not_zero() { check(&c, &a, &b, &Zero::zero()); }
1550 if b.is_not_zero() { check(&c, &b, &a, &Zero::zero()); }
1551 }
1552
1553 for divmod_quadruples.each |elm| {
1554 let (aVec, bVec, cVec, dVec) = *elm;
1555 let a = BigInt::from_slice(Plus, aVec);
1556 let b = BigInt::from_slice(Plus, bVec);
1557 let c = BigInt::from_slice(Plus, cVec);
1558 let d = BigInt::from_slice(Plus, dVec);
1559
1560 if b.is_not_zero() {
1561 check(&a, &b, &c, &d);
1562 }
1563 }
1564 }
1565
1566
1567 #[test]
1568 fn test_quotrem() {
1569 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
1570 let (q, r) = a.quotrem(b);
1571 if r.is_not_zero() {
1572 assert!(r.sign == a.sign);
1573 }
1574 assert!(r.abs() <= b.abs());
1575 assert!(*a == b * q + r);
1576 assert!(q == *ans_q);
1577 assert!(r == *ans_r);
1578 }
1579
1580 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
1581 check_sub(a, b, q, r);
1582 check_sub(a, &b.neg(), &q.neg(), r);
1583 check_sub(&a.neg(), b, &q.neg(), &r.neg());
1584 check_sub(&a.neg(), &b.neg(), q, &r.neg());
1585 }
1586 for mul_triples.each |elm| {
1587 let (aVec, bVec, cVec) = *elm;
1588 let a = BigInt::from_slice(Plus, aVec);
1589 let b = BigInt::from_slice(Plus, bVec);
1590 let c = BigInt::from_slice(Plus, cVec);
1591
1592 if a.is_not_zero() { check(&c, &a, &b, &Zero::zero()); }
1593 if b.is_not_zero() { check(&c, &b, &a, &Zero::zero()); }
1594 }
1595
1596 for divmod_quadruples.each |elm| {
1597 let (aVec, bVec, cVec, dVec) = *elm;
1598 let a = BigInt::from_slice(Plus, aVec);
1599 let b = BigInt::from_slice(Plus, bVec);
1600 let c = BigInt::from_slice(Plus, cVec);
1601 let d = BigInt::from_slice(Plus, dVec);
1602
1603 if b.is_not_zero() {
1604 check(&a, &b, &c, &d);
1605 }
1606 }
1607 }
1608
1609 #[test]
1610 fn test_to_str_radix() {
1611 fn check(n: int, ans: &str) {
1612 assert!(ans == IntConvertible::from_int::<BigInt>(
1613 n).to_str_radix(10));
1614 }
1615 check(10, "10");
1616 check(1, "1");
1617 check(0, "0");
1618 check(-1, "-1");
1619 check(-10, "-10");
1620 }
1621
1622
1623 #[test]
1624 fn test_from_str_radix() {
1625 fn check(s: &str, ans: Option<int>) {
1626 let ans = ans.map(|&n| IntConvertible::from_int(n));
1627 assert!(BigInt::from_str_radix(s, 10) == ans);
1628 }
1629 check("10", Some(10));
1630 check("1", Some(1));
1631 check("0", Some(0));
1632 check("-1", Some(-1));
1633 check("-10", Some(-10));
1634 check("Z", None);
1635 check("_", None);
1636 }
1637
1638 #[test]
1639 fn test_neg() {
1640 assert!(-BigInt::new(Plus, ~[1, 1, 1]) ==
1641 BigInt::new(Minus, ~[1, 1, 1]));
1642 assert!(-BigInt::new(Minus, ~[1, 1, 1]) ==
1643 BigInt::new(Plus, ~[1, 1, 1]));
1644 assert!(-Zero::zero::<BigInt>() == Zero::zero::<BigInt>());
1645 }
1646 }
1647
backport for Debian buster