1 use num_bigint::BigUint;
2 use num_bigint::Sign::{Minus, NoSign, Plus};
3 use num_bigint::{BigInt, ToBigInt};
4 
5 use std::cmp::Ordering::{Equal, Greater, Less};
6 use std::collections::hash_map::RandomState;
7 use std::hash::{BuildHasher, Hash, Hasher};
8 use std::iter::repeat;
9 use std::ops::Neg;
10 use std::{f32, f64};
11 use std::{i128, u128};
12 use std::{i16, i32, i64, i8, isize};
13 use std::{u16, u32, u64, u8, usize};
14 
15 use num_integer::Integer;
16 use num_traits::{pow, FromPrimitive, Num, One, Pow, Signed, ToPrimitive, Zero};
17 
18 mod consts;
19 use crate::consts::*;
20 
21 #[macro_use]
22 mod macros;
23 
24 #[test]
test_from_bytes_be()25 fn test_from_bytes_be() {
26     fn check(s: &str, result: &str) {
27         assert_eq!(
28             BigInt::from_bytes_be(Plus, s.as_bytes()),
29             BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
30         );
31     }
32     check("A", "65");
33     check("AA", "16705");
34     check("AB", "16706");
35     check("Hello world!", "22405534230753963835153736737");
36     assert_eq!(BigInt::from_bytes_be(Plus, &[]), BigInt::zero());
37     assert_eq!(BigInt::from_bytes_be(Minus, &[]), BigInt::zero());
38 }
39 
40 #[test]
test_to_bytes_be()41 fn test_to_bytes_be() {
42     fn check(s: &str, result: &str) {
43         let b = BigInt::parse_bytes(result.as_bytes(), 10).unwrap();
44         let (sign, v) = b.to_bytes_be();
45         assert_eq!((Plus, s.as_bytes()), (sign, &*v));
46     }
47     check("A", "65");
48     check("AA", "16705");
49     check("AB", "16706");
50     check("Hello world!", "22405534230753963835153736737");
51     let b: BigInt = Zero::zero();
52     assert_eq!(b.to_bytes_be(), (NoSign, vec![0]));
53 
54     // Test with leading/trailing zero bytes and a full BigDigit of value 0
55     let b = BigInt::from_str_radix("00010000000000000200", 16).unwrap();
56     assert_eq!(b.to_bytes_be(), (Plus, vec![1, 0, 0, 0, 0, 0, 0, 2, 0]));
57 }
58 
59 #[test]
test_from_bytes_le()60 fn test_from_bytes_le() {
61     fn check(s: &str, result: &str) {
62         assert_eq!(
63             BigInt::from_bytes_le(Plus, s.as_bytes()),
64             BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
65         );
66     }
67     check("A", "65");
68     check("AA", "16705");
69     check("BA", "16706");
70     check("!dlrow olleH", "22405534230753963835153736737");
71     assert_eq!(BigInt::from_bytes_le(Plus, &[]), BigInt::zero());
72     assert_eq!(BigInt::from_bytes_le(Minus, &[]), BigInt::zero());
73 }
74 
75 #[test]
test_to_bytes_le()76 fn test_to_bytes_le() {
77     fn check(s: &str, result: &str) {
78         let b = BigInt::parse_bytes(result.as_bytes(), 10).unwrap();
79         let (sign, v) = b.to_bytes_le();
80         assert_eq!((Plus, s.as_bytes()), (sign, &*v));
81     }
82     check("A", "65");
83     check("AA", "16705");
84     check("BA", "16706");
85     check("!dlrow olleH", "22405534230753963835153736737");
86     let b: BigInt = Zero::zero();
87     assert_eq!(b.to_bytes_le(), (NoSign, vec![0]));
88 
89     // Test with leading/trailing zero bytes and a full BigDigit of value 0
90     let b = BigInt::from_str_radix("00010000000000000200", 16).unwrap();
91     assert_eq!(b.to_bytes_le(), (Plus, vec![0, 2, 0, 0, 0, 0, 0, 0, 1]));
92 }
93 
94 #[test]
test_to_signed_bytes_le()95 fn test_to_signed_bytes_le() {
96     fn check(s: &str, result: Vec<u8>) {
97         assert_eq!(
98             BigInt::parse_bytes(s.as_bytes(), 10)
99                 .unwrap()
100                 .to_signed_bytes_le(),
101             result
102         );
103     }
104 
105     check("0", vec![0]);
106     check("32767", vec![0xff, 0x7f]);
107     check("-1", vec![0xff]);
108     check("16777216", vec![0, 0, 0, 1]);
109     check("-100", vec![156]);
110     check("-8388608", vec![0, 0, 0x80]);
111     check("-192", vec![0x40, 0xff]);
112     check("128", vec![0x80, 0])
113 }
114 
115 #[test]
test_from_signed_bytes_le()116 fn test_from_signed_bytes_le() {
117     fn check(s: &[u8], result: &str) {
118         assert_eq!(
119             BigInt::from_signed_bytes_le(s),
120             BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
121         );
122     }
123 
124     check(&[], "0");
125     check(&[0], "0");
126     check(&[0; 10], "0");
127     check(&[0xff, 0x7f], "32767");
128     check(&[0xff], "-1");
129     check(&[0, 0, 0, 1], "16777216");
130     check(&[156], "-100");
131     check(&[0, 0, 0x80], "-8388608");
132     check(&[0xff; 10], "-1");
133     check(&[0x40, 0xff], "-192");
134 }
135 
136 #[test]
test_to_signed_bytes_be()137 fn test_to_signed_bytes_be() {
138     fn check(s: &str, result: Vec<u8>) {
139         assert_eq!(
140             BigInt::parse_bytes(s.as_bytes(), 10)
141                 .unwrap()
142                 .to_signed_bytes_be(),
143             result
144         );
145     }
146 
147     check("0", vec![0]);
148     check("32767", vec![0x7f, 0xff]);
149     check("-1", vec![255]);
150     check("16777216", vec![1, 0, 0, 0]);
151     check("-100", vec![156]);
152     check("-8388608", vec![128, 0, 0]);
153     check("-192", vec![0xff, 0x40]);
154     check("128", vec![0, 0x80]);
155 }
156 
157 #[test]
test_from_signed_bytes_be()158 fn test_from_signed_bytes_be() {
159     fn check(s: &[u8], result: &str) {
160         assert_eq!(
161             BigInt::from_signed_bytes_be(s),
162             BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
163         );
164     }
165 
166     check(&[], "0");
167     check(&[0], "0");
168     check(&[0; 10], "0");
169     check(&[127, 255], "32767");
170     check(&[255], "-1");
171     check(&[1, 0, 0, 0], "16777216");
172     check(&[156], "-100");
173     check(&[128, 0, 0], "-8388608");
174     check(&[255; 10], "-1");
175     check(&[0xff, 0x40], "-192");
176 }
177 
178 #[test]
test_signed_bytes_be_round_trip()179 fn test_signed_bytes_be_round_trip() {
180     for i in -0x1FFFF..0x20000 {
181         let n = BigInt::from(i);
182         assert_eq!(n, BigInt::from_signed_bytes_be(&n.to_signed_bytes_be()));
183     }
184 }
185 
186 #[test]
test_signed_bytes_le_round_trip()187 fn test_signed_bytes_le_round_trip() {
188     for i in -0x1FFFF..0x20000 {
189         let n = BigInt::from(i);
190         assert_eq!(n, BigInt::from_signed_bytes_le(&n.to_signed_bytes_le()));
191     }
192 }
193 
194 #[test]
test_cmp()195 fn test_cmp() {
196     let vs: [&[u32]; 4] = [&[2 as u32], &[1, 1], &[2, 1], &[1, 1, 1]];
197     let mut nums = Vec::new();
198     for s in vs.iter().rev() {
199         nums.push(BigInt::from_slice(Minus, *s));
200     }
201     nums.push(Zero::zero());
202     nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
203 
204     for (i, ni) in nums.iter().enumerate() {
205         for (j0, nj) in nums[i..].iter().enumerate() {
206             let j = i + j0;
207             if i == j {
208                 assert_eq!(ni.cmp(nj), Equal);
209                 assert_eq!(nj.cmp(ni), Equal);
210                 assert_eq!(ni, nj);
211                 assert!(!(ni != nj));
212                 assert!(ni <= nj);
213                 assert!(ni >= nj);
214                 assert!(!(ni < nj));
215                 assert!(!(ni > nj));
216             } else {
217                 assert_eq!(ni.cmp(nj), Less);
218                 assert_eq!(nj.cmp(ni), Greater);
219 
220                 assert!(!(ni == nj));
221                 assert!(ni != nj);
222 
223                 assert!(ni <= nj);
224                 assert!(!(ni >= nj));
225                 assert!(ni < nj);
226                 assert!(!(ni > nj));
227 
228                 assert!(!(nj <= ni));
229                 assert!(nj >= ni);
230                 assert!(!(nj < ni));
231                 assert!(nj > ni);
232             }
233         }
234     }
235 }
236 
hash<T: Hash>(x: &T) -> u64237 fn hash<T: Hash>(x: &T) -> u64 {
238     let mut hasher = <RandomState as BuildHasher>::Hasher::new();
239     x.hash(&mut hasher);
240     hasher.finish()
241 }
242 
243 #[test]
test_hash()244 fn test_hash() {
245     let a = BigInt::new(NoSign, vec![]);
246     let b = BigInt::new(NoSign, vec![0]);
247     let c = BigInt::new(Plus, vec![1]);
248     let d = BigInt::new(Plus, vec![1, 0, 0, 0, 0, 0]);
249     let e = BigInt::new(Plus, vec![0, 0, 0, 0, 0, 1]);
250     let f = BigInt::new(Minus, vec![1]);
251     assert!(hash(&a) == hash(&b));
252     assert!(hash(&b) != hash(&c));
253     assert!(hash(&c) == hash(&d));
254     assert!(hash(&d) != hash(&e));
255     assert!(hash(&c) != hash(&f));
256 }
257 
258 #[test]
test_convert_i64()259 fn test_convert_i64() {
260     fn check(b1: BigInt, i: i64) {
261         let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
262         assert!(b1 == b2);
263         assert!(b1.to_i64().unwrap() == i);
264     }
265 
266     check(Zero::zero(), 0);
267     check(One::one(), 1);
268     check(i64::MIN.to_bigint().unwrap(), i64::MIN);
269     check(i64::MAX.to_bigint().unwrap(), i64::MAX);
270 
271     assert_eq!((i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(), None);
272 
273     assert_eq!(
274         BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i64(),
275         None
276     );
277 
278     assert_eq!(
279         BigInt::from_biguint(Minus, BigUint::new(vec![1, 0, 0, 1 << 31])).to_i64(),
280         None
281     );
282 
283     assert_eq!(
284         BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i64(),
285         None
286     );
287 }
288 
289 #[test]
test_convert_i128()290 fn test_convert_i128() {
291     fn check(b1: BigInt, i: i128) {
292         let b2: BigInt = FromPrimitive::from_i128(i).unwrap();
293         assert!(b1 == b2);
294         assert!(b1.to_i128().unwrap() == i);
295     }
296 
297     check(Zero::zero(), 0);
298     check(One::one(), 1);
299     check(i128::MIN.to_bigint().unwrap(), i128::MIN);
300     check(i128::MAX.to_bigint().unwrap(), i128::MAX);
301 
302     assert_eq!((i128::MAX as u128 + 1).to_bigint().unwrap().to_i128(), None);
303 
304     assert_eq!(
305         BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i128(),
306         None
307     );
308 
309     assert_eq!(
310         BigInt::from_biguint(Minus, BigUint::new(vec![1, 0, 0, 1 << 31])).to_i128(),
311         None
312     );
313 
314     assert_eq!(
315         BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_i128(),
316         None
317     );
318 }
319 
320 #[test]
test_convert_u64()321 fn test_convert_u64() {
322     fn check(b1: BigInt, u: u64) {
323         let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
324         assert!(b1 == b2);
325         assert!(b1.to_u64().unwrap() == u);
326     }
327 
328     check(Zero::zero(), 0);
329     check(One::one(), 1);
330     check(u64::MIN.to_bigint().unwrap(), u64::MIN);
331     check(u64::MAX.to_bigint().unwrap(), u64::MAX);
332 
333     assert_eq!(
334         BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u64(),
335         None
336     );
337 
338     let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
339     assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
340     assert_eq!(
341         BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u64(),
342         None
343     );
344 }
345 
346 #[test]
test_convert_u128()347 fn test_convert_u128() {
348     fn check(b1: BigInt, u: u128) {
349         let b2: BigInt = FromPrimitive::from_u128(u).unwrap();
350         assert!(b1 == b2);
351         assert!(b1.to_u128().unwrap() == u);
352     }
353 
354     check(Zero::zero(), 0);
355     check(One::one(), 1);
356     check(u128::MIN.to_bigint().unwrap(), u128::MIN);
357     check(u128::MAX.to_bigint().unwrap(), u128::MAX);
358 
359     assert_eq!(
360         BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u128(),
361         None
362     );
363 
364     let max_value: BigUint = FromPrimitive::from_u128(u128::MAX).unwrap();
365     assert_eq!(BigInt::from_biguint(Minus, max_value).to_u128(), None);
366     assert_eq!(
367         BigInt::from_biguint(Minus, BigUint::new(vec![1, 2, 3, 4, 5])).to_u128(),
368         None
369     );
370 }
371 
372 #[test]
373 #[allow(clippy::float_cmp)]
test_convert_f32()374 fn test_convert_f32() {
375     fn check(b1: &BigInt, f: f32) {
376         let b2 = BigInt::from_f32(f).unwrap();
377         assert_eq!(b1, &b2);
378         assert_eq!(b1.to_f32().unwrap(), f);
379         let neg_b1 = -b1;
380         let neg_b2 = BigInt::from_f32(-f).unwrap();
381         assert_eq!(neg_b1, neg_b2);
382         assert_eq!(neg_b1.to_f32().unwrap(), -f);
383     }
384 
385     check(&BigInt::zero(), 0.0);
386     check(&BigInt::one(), 1.0);
387     check(&BigInt::from(u16::MAX), pow(2.0_f32, 16) - 1.0);
388     check(&BigInt::from(1u64 << 32), pow(2.0_f32, 32));
389     check(&BigInt::from_slice(Plus, &[0, 0, 1]), pow(2.0_f32, 64));
390     check(
391         &((BigInt::one() << 100) + (BigInt::one() << 123)),
392         pow(2.0_f32, 100) + pow(2.0_f32, 123),
393     );
394     check(&(BigInt::one() << 127), pow(2.0_f32, 127));
395     check(&(BigInt::from((1u64 << 24) - 1) << (128 - 24)), f32::MAX);
396 
397     // keeping all 24 digits with the bits at different offsets to the BigDigits
398     let x: u32 = 0b00000000101111011111011011011101;
399     let mut f = x as f32;
400     let mut b = BigInt::from(x);
401     for _ in 0..64 {
402         check(&b, f);
403         f *= 2.0;
404         b <<= 1;
405     }
406 
407     // this number when rounded to f64 then f32 isn't the same as when rounded straight to f32
408     let mut n: i64 = 0b0000000000111111111111111111111111011111111111111111111111111111;
409     assert!((n as f64) as f32 != n as f32);
410     assert_eq!(BigInt::from(n).to_f32(), Some(n as f32));
411     n = -n;
412     assert!((n as f64) as f32 != n as f32);
413     assert_eq!(BigInt::from(n).to_f32(), Some(n as f32));
414 
415     // test rounding up with the bits at different offsets to the BigDigits
416     let mut f = ((1u64 << 25) - 1) as f32;
417     let mut b = BigInt::from(1u64 << 25);
418     for _ in 0..64 {
419         assert_eq!(b.to_f32(), Some(f));
420         f *= 2.0;
421         b <<= 1;
422     }
423 
424     // rounding
425     assert_eq!(
426         BigInt::from_f32(-f32::consts::PI),
427         Some(BigInt::from(-3i32))
428     );
429     assert_eq!(BigInt::from_f32(-f32::consts::E), Some(BigInt::from(-2i32)));
430     assert_eq!(BigInt::from_f32(-0.99999), Some(BigInt::zero()));
431     assert_eq!(BigInt::from_f32(-0.5), Some(BigInt::zero()));
432     assert_eq!(BigInt::from_f32(-0.0), Some(BigInt::zero()));
433     assert_eq!(
434         BigInt::from_f32(f32::MIN_POSITIVE / 2.0),
435         Some(BigInt::zero())
436     );
437     assert_eq!(BigInt::from_f32(f32::MIN_POSITIVE), Some(BigInt::zero()));
438     assert_eq!(BigInt::from_f32(0.5), Some(BigInt::zero()));
439     assert_eq!(BigInt::from_f32(0.99999), Some(BigInt::zero()));
440     assert_eq!(BigInt::from_f32(f32::consts::E), Some(BigInt::from(2u32)));
441     assert_eq!(BigInt::from_f32(f32::consts::PI), Some(BigInt::from(3u32)));
442 
443     // special float values
444     assert_eq!(BigInt::from_f32(f32::NAN), None);
445     assert_eq!(BigInt::from_f32(f32::INFINITY), None);
446     assert_eq!(BigInt::from_f32(f32::NEG_INFINITY), None);
447 
448     // largest BigInt that will round to a finite f32 value
449     let big_num = (BigInt::one() << 128u8) - 1u8 - (BigInt::one() << (128u8 - 25));
450     assert_eq!(big_num.to_f32(), Some(f32::MAX));
451     assert_eq!((&big_num + 1u8).to_f32(), Some(f32::INFINITY));
452     assert_eq!((-&big_num).to_f32(), Some(f32::MIN));
453     assert_eq!(((-&big_num) - 1u8).to_f32(), Some(f32::NEG_INFINITY));
454 
455     assert_eq!(
456         ((BigInt::one() << 128u8) - 1u8).to_f32(),
457         Some(f32::INFINITY)
458     );
459     assert_eq!((BigInt::one() << 128u8).to_f32(), Some(f32::INFINITY));
460     assert_eq!(
461         (-((BigInt::one() << 128u8) - 1u8)).to_f32(),
462         Some(f32::NEG_INFINITY)
463     );
464     assert_eq!(
465         (-(BigInt::one() << 128u8)).to_f32(),
466         Some(f32::NEG_INFINITY)
467     );
468 }
469 
470 #[test]
471 #[allow(clippy::float_cmp)]
test_convert_f64()472 fn test_convert_f64() {
473     fn check(b1: &BigInt, f: f64) {
474         let b2 = BigInt::from_f64(f).unwrap();
475         assert_eq!(b1, &b2);
476         assert_eq!(b1.to_f64().unwrap(), f);
477         let neg_b1 = -b1;
478         let neg_b2 = BigInt::from_f64(-f).unwrap();
479         assert_eq!(neg_b1, neg_b2);
480         assert_eq!(neg_b1.to_f64().unwrap(), -f);
481     }
482 
483     check(&BigInt::zero(), 0.0);
484     check(&BigInt::one(), 1.0);
485     check(&BigInt::from(u32::MAX), pow(2.0_f64, 32) - 1.0);
486     check(&BigInt::from(1u64 << 32), pow(2.0_f64, 32));
487     check(&BigInt::from_slice(Plus, &[0, 0, 1]), pow(2.0_f64, 64));
488     check(
489         &((BigInt::one() << 100) + (BigInt::one() << 152)),
490         pow(2.0_f64, 100) + pow(2.0_f64, 152),
491     );
492     check(&(BigInt::one() << 1023), pow(2.0_f64, 1023));
493     check(&(BigInt::from((1u64 << 53) - 1) << (1024 - 53)), f64::MAX);
494 
495     // keeping all 53 digits with the bits at different offsets to the BigDigits
496     let x: u64 = 0b0000000000011110111110110111111101110111101111011111011011011101;
497     let mut f = x as f64;
498     let mut b = BigInt::from(x);
499     for _ in 0..128 {
500         check(&b, f);
501         f *= 2.0;
502         b <<= 1;
503     }
504 
505     // test rounding up with the bits at different offsets to the BigDigits
506     let mut f = ((1u64 << 54) - 1) as f64;
507     let mut b = BigInt::from(1u64 << 54);
508     for _ in 0..128 {
509         assert_eq!(b.to_f64(), Some(f));
510         f *= 2.0;
511         b <<= 1;
512     }
513 
514     // rounding
515     assert_eq!(
516         BigInt::from_f64(-f64::consts::PI),
517         Some(BigInt::from(-3i32))
518     );
519     assert_eq!(BigInt::from_f64(-f64::consts::E), Some(BigInt::from(-2i32)));
520     assert_eq!(BigInt::from_f64(-0.99999), Some(BigInt::zero()));
521     assert_eq!(BigInt::from_f64(-0.5), Some(BigInt::zero()));
522     assert_eq!(BigInt::from_f64(-0.0), Some(BigInt::zero()));
523     assert_eq!(
524         BigInt::from_f64(f64::MIN_POSITIVE / 2.0),
525         Some(BigInt::zero())
526     );
527     assert_eq!(BigInt::from_f64(f64::MIN_POSITIVE), Some(BigInt::zero()));
528     assert_eq!(BigInt::from_f64(0.5), Some(BigInt::zero()));
529     assert_eq!(BigInt::from_f64(0.99999), Some(BigInt::zero()));
530     assert_eq!(BigInt::from_f64(f64::consts::E), Some(BigInt::from(2u32)));
531     assert_eq!(BigInt::from_f64(f64::consts::PI), Some(BigInt::from(3u32)));
532 
533     // special float values
534     assert_eq!(BigInt::from_f64(f64::NAN), None);
535     assert_eq!(BigInt::from_f64(f64::INFINITY), None);
536     assert_eq!(BigInt::from_f64(f64::NEG_INFINITY), None);
537 
538     // largest BigInt that will round to a finite f64 value
539     let big_num = (BigInt::one() << 1024u16) - 1u8 - (BigInt::one() << (1024u16 - 54));
540     assert_eq!(big_num.to_f64(), Some(f64::MAX));
541     assert_eq!((&big_num + 1u8).to_f64(), Some(f64::INFINITY));
542     assert_eq!((-&big_num).to_f64(), Some(f64::MIN));
543     assert_eq!(((-&big_num) - 1u8).to_f64(), Some(f64::NEG_INFINITY));
544 
545     assert_eq!(
546         ((BigInt::one() << 1024u16) - 1u8).to_f64(),
547         Some(f64::INFINITY)
548     );
549     assert_eq!((BigInt::one() << 1024u16).to_f64(), Some(f64::INFINITY));
550     assert_eq!(
551         (-((BigInt::one() << 1024u16) - 1u8)).to_f64(),
552         Some(f64::NEG_INFINITY)
553     );
554     assert_eq!(
555         (-(BigInt::one() << 1024u16)).to_f64(),
556         Some(f64::NEG_INFINITY)
557     );
558 }
559 
560 #[test]
test_convert_to_biguint()561 fn test_convert_to_biguint() {
562     fn check(n: BigInt, ans_1: BigUint) {
563         assert_eq!(n.to_biguint().unwrap(), ans_1);
564         assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
565     }
566     let zero: BigInt = Zero::zero();
567     let unsigned_zero: BigUint = Zero::zero();
568     let positive = BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3]));
569     let negative = -&positive;
570 
571     check(zero, unsigned_zero);
572     check(positive, BigUint::new(vec![1, 2, 3]));
573 
574     assert_eq!(negative.to_biguint(), None);
575 }
576 
577 #[test]
test_convert_from_uint()578 fn test_convert_from_uint() {
579     macro_rules! check {
580         ($ty:ident, $max:expr) => {
581             assert_eq!(BigInt::from($ty::zero()), BigInt::zero());
582             assert_eq!(BigInt::from($ty::one()), BigInt::one());
583             assert_eq!(BigInt::from($ty::MAX - $ty::one()), $max - BigInt::one());
584             assert_eq!(BigInt::from($ty::MAX), $max);
585         };
586     }
587 
588     check!(u8, BigInt::from_slice(Plus, &[u8::MAX as u32]));
589     check!(u16, BigInt::from_slice(Plus, &[u16::MAX as u32]));
590     check!(u32, BigInt::from_slice(Plus, &[u32::MAX]));
591     check!(u64, BigInt::from_slice(Plus, &[u32::MAX, u32::MAX]));
592     check!(
593         u128,
594         BigInt::from_slice(Plus, &[u32::MAX, u32::MAX, u32::MAX, u32::MAX])
595     );
596     check!(usize, BigInt::from(usize::MAX as u64));
597 }
598 
599 #[test]
test_convert_from_int()600 fn test_convert_from_int() {
601     macro_rules! check {
602         ($ty:ident, $min:expr, $max:expr) => {
603             assert_eq!(BigInt::from($ty::MIN), $min);
604             assert_eq!(BigInt::from($ty::MIN + $ty::one()), $min + BigInt::one());
605             assert_eq!(BigInt::from(-$ty::one()), -BigInt::one());
606             assert_eq!(BigInt::from($ty::zero()), BigInt::zero());
607             assert_eq!(BigInt::from($ty::one()), BigInt::one());
608             assert_eq!(BigInt::from($ty::MAX - $ty::one()), $max - BigInt::one());
609             assert_eq!(BigInt::from($ty::MAX), $max);
610         };
611     }
612 
613     check!(
614         i8,
615         BigInt::from_slice(Minus, &[1 << 7]),
616         BigInt::from_slice(Plus, &[i8::MAX as u32])
617     );
618     check!(
619         i16,
620         BigInt::from_slice(Minus, &[1 << 15]),
621         BigInt::from_slice(Plus, &[i16::MAX as u32])
622     );
623     check!(
624         i32,
625         BigInt::from_slice(Minus, &[1 << 31]),
626         BigInt::from_slice(Plus, &[i32::MAX as u32])
627     );
628     check!(
629         i64,
630         BigInt::from_slice(Minus, &[0, 1 << 31]),
631         BigInt::from_slice(Plus, &[u32::MAX, i32::MAX as u32])
632     );
633     check!(
634         i128,
635         BigInt::from_slice(Minus, &[0, 0, 0, 1 << 31]),
636         BigInt::from_slice(Plus, &[u32::MAX, u32::MAX, u32::MAX, i32::MAX as u32])
637     );
638     check!(
639         isize,
640         BigInt::from(isize::MIN as i64),
641         BigInt::from(isize::MAX as i64)
642     );
643 }
644 
645 #[test]
test_convert_from_biguint()646 fn test_convert_from_biguint() {
647     assert_eq!(BigInt::from(BigUint::zero()), BigInt::zero());
648     assert_eq!(BigInt::from(BigUint::one()), BigInt::one());
649     assert_eq!(
650         BigInt::from(BigUint::from_slice(&[1, 2, 3])),
651         BigInt::from_slice(Plus, &[1, 2, 3])
652     );
653 }
654 
655 #[test]
test_add()656 fn test_add() {
657     for elm in SUM_TRIPLES.iter() {
658         let (a_vec, b_vec, c_vec) = *elm;
659         let a = BigInt::from_slice(Plus, a_vec);
660         let b = BigInt::from_slice(Plus, b_vec);
661         let c = BigInt::from_slice(Plus, c_vec);
662         let (na, nb, nc) = (-&a, -&b, -&c);
663 
664         assert_op!(a + b == c);
665         assert_op!(b + a == c);
666         assert_op!(c + na == b);
667         assert_op!(c + nb == a);
668         assert_op!(a + nc == nb);
669         assert_op!(b + nc == na);
670         assert_op!(na + nb == nc);
671         assert_op!(a + na == BigInt::zero());
672 
673         assert_assign_op!(a += b == c);
674         assert_assign_op!(b += a == c);
675         assert_assign_op!(c += na == b);
676         assert_assign_op!(c += nb == a);
677         assert_assign_op!(a += nc == nb);
678         assert_assign_op!(b += nc == na);
679         assert_assign_op!(na += nb == nc);
680         assert_assign_op!(a += na == BigInt::zero());
681     }
682 }
683 
684 #[test]
test_sub()685 fn test_sub() {
686     for elm in SUM_TRIPLES.iter() {
687         let (a_vec, b_vec, c_vec) = *elm;
688         let a = BigInt::from_slice(Plus, a_vec);
689         let b = BigInt::from_slice(Plus, b_vec);
690         let c = BigInt::from_slice(Plus, c_vec);
691         let (na, nb, nc) = (-&a, -&b, -&c);
692 
693         assert_op!(c - a == b);
694         assert_op!(c - b == a);
695         assert_op!(nb - a == nc);
696         assert_op!(na - b == nc);
697         assert_op!(b - na == c);
698         assert_op!(a - nb == c);
699         assert_op!(nc - na == nb);
700         assert_op!(a - a == BigInt::zero());
701 
702         assert_assign_op!(c -= a == b);
703         assert_assign_op!(c -= b == a);
704         assert_assign_op!(nb -= a == nc);
705         assert_assign_op!(na -= b == nc);
706         assert_assign_op!(b -= na == c);
707         assert_assign_op!(a -= nb == c);
708         assert_assign_op!(nc -= na == nb);
709         assert_assign_op!(a -= a == BigInt::zero());
710     }
711 }
712 
713 #[test]
test_mul()714 fn test_mul() {
715     for elm in MUL_TRIPLES.iter() {
716         let (a_vec, b_vec, c_vec) = *elm;
717         let a = BigInt::from_slice(Plus, a_vec);
718         let b = BigInt::from_slice(Plus, b_vec);
719         let c = BigInt::from_slice(Plus, c_vec);
720         let (na, nb, nc) = (-&a, -&b, -&c);
721 
722         assert_op!(a * b == c);
723         assert_op!(b * a == c);
724         assert_op!(na * nb == c);
725 
726         assert_op!(na * b == nc);
727         assert_op!(nb * a == nc);
728 
729         assert_assign_op!(a *= b == c);
730         assert_assign_op!(b *= a == c);
731         assert_assign_op!(na *= nb == c);
732 
733         assert_assign_op!(na *= b == nc);
734         assert_assign_op!(nb *= a == nc);
735     }
736 
737     for elm in DIV_REM_QUADRUPLES.iter() {
738         let (a_vec, b_vec, c_vec, d_vec) = *elm;
739         let a = BigInt::from_slice(Plus, a_vec);
740         let b = BigInt::from_slice(Plus, b_vec);
741         let c = BigInt::from_slice(Plus, c_vec);
742         let d = BigInt::from_slice(Plus, d_vec);
743 
744         assert!(a == &b * &c + &d);
745         assert!(a == &c * &b + &d);
746     }
747 }
748 
749 #[test]
test_div_mod_floor()750 fn test_div_mod_floor() {
751     fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
752         let (d, m) = a.div_mod_floor(b);
753         assert_eq!(d, a.div_floor(b));
754         assert_eq!(m, a.mod_floor(b));
755         if !m.is_zero() {
756             assert_eq!(m.sign(), b.sign());
757         }
758         assert!(m.abs() <= b.abs());
759         assert!(*a == b * &d + &m);
760         assert!(d == *ans_d);
761         assert!(m == *ans_m);
762     }
763 
764     fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
765         if m.is_zero() {
766             check_sub(a, b, d, m);
767             check_sub(a, &b.neg(), &d.neg(), m);
768             check_sub(&a.neg(), b, &d.neg(), m);
769             check_sub(&a.neg(), &b.neg(), d, m);
770         } else {
771             let one: BigInt = One::one();
772             check_sub(a, b, d, m);
773             check_sub(a, &b.neg(), &(d.neg() - &one), &(m - b));
774             check_sub(&a.neg(), b, &(d.neg() - &one), &(b - m));
775             check_sub(&a.neg(), &b.neg(), d, &m.neg());
776         }
777     }
778 
779     for elm in MUL_TRIPLES.iter() {
780         let (a_vec, b_vec, c_vec) = *elm;
781         let a = BigInt::from_slice(Plus, a_vec);
782         let b = BigInt::from_slice(Plus, b_vec);
783         let c = BigInt::from_slice(Plus, c_vec);
784 
785         if !a.is_zero() {
786             check(&c, &a, &b, &Zero::zero());
787         }
788         if !b.is_zero() {
789             check(&c, &b, &a, &Zero::zero());
790         }
791     }
792 
793     for elm in DIV_REM_QUADRUPLES.iter() {
794         let (a_vec, b_vec, c_vec, d_vec) = *elm;
795         let a = BigInt::from_slice(Plus, a_vec);
796         let b = BigInt::from_slice(Plus, b_vec);
797         let c = BigInt::from_slice(Plus, c_vec);
798         let d = BigInt::from_slice(Plus, d_vec);
799 
800         if !b.is_zero() {
801             check(&a, &b, &c, &d);
802         }
803     }
804 }
805 
806 #[test]
test_div_rem()807 fn test_div_rem() {
808     fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
809         let (q, r) = a.div_rem(b);
810         if !r.is_zero() {
811             assert_eq!(r.sign(), a.sign());
812         }
813         assert!(r.abs() <= b.abs());
814         assert!(*a == b * &q + &r);
815         assert!(q == *ans_q);
816         assert!(r == *ans_r);
817 
818         let (a, b, ans_q, ans_r) = (a.clone(), b.clone(), ans_q.clone(), ans_r.clone());
819         assert_op!(a / b == ans_q);
820         assert_op!(a % b == ans_r);
821         assert_assign_op!(a /= b == ans_q);
822         assert_assign_op!(a %= b == ans_r);
823     }
824 
825     fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
826         check_sub(a, b, q, r);
827         check_sub(a, &b.neg(), &q.neg(), r);
828         check_sub(&a.neg(), b, &q.neg(), &r.neg());
829         check_sub(&a.neg(), &b.neg(), q, &r.neg());
830     }
831     for elm in MUL_TRIPLES.iter() {
832         let (a_vec, b_vec, c_vec) = *elm;
833         let a = BigInt::from_slice(Plus, a_vec);
834         let b = BigInt::from_slice(Plus, b_vec);
835         let c = BigInt::from_slice(Plus, c_vec);
836 
837         if !a.is_zero() {
838             check(&c, &a, &b, &Zero::zero());
839         }
840         if !b.is_zero() {
841             check(&c, &b, &a, &Zero::zero());
842         }
843     }
844 
845     for elm in DIV_REM_QUADRUPLES.iter() {
846         let (a_vec, b_vec, c_vec, d_vec) = *elm;
847         let a = BigInt::from_slice(Plus, a_vec);
848         let b = BigInt::from_slice(Plus, b_vec);
849         let c = BigInt::from_slice(Plus, c_vec);
850         let d = BigInt::from_slice(Plus, d_vec);
851 
852         if !b.is_zero() {
853             check(&a, &b, &c, &d);
854         }
855     }
856 }
857 
858 #[test]
test_div_ceil()859 fn test_div_ceil() {
860     fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt) {
861         assert_eq!(a.div_ceil(b), *ans_d);
862     }
863 
864     fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
865         if m.is_zero() {
866             check_sub(a, b, d);
867             check_sub(a, &b.neg(), &d.neg());
868             check_sub(&a.neg(), b, &d.neg());
869             check_sub(&a.neg(), &b.neg(), d);
870         } else {
871             check_sub(a, b, &(d + 1));
872             check_sub(a, &b.neg(), &d.neg());
873             check_sub(&a.neg(), b, &d.neg());
874             check_sub(&a.neg(), &b.neg(), &(d + 1));
875         }
876     }
877 
878     for elm in MUL_TRIPLES.iter() {
879         let (a_vec, b_vec, c_vec) = *elm;
880         let a = BigInt::from_slice(Plus, a_vec);
881         let b = BigInt::from_slice(Plus, b_vec);
882         let c = BigInt::from_slice(Plus, c_vec);
883 
884         if !a.is_zero() {
885             check(&c, &a, &b, &Zero::zero());
886         }
887         if !b.is_zero() {
888             check(&c, &b, &a, &Zero::zero());
889         }
890     }
891 
892     for elm in DIV_REM_QUADRUPLES.iter() {
893         let (a_vec, b_vec, c_vec, d_vec) = *elm;
894         let a = BigInt::from_slice(Plus, a_vec);
895         let b = BigInt::from_slice(Plus, b_vec);
896         let c = BigInt::from_slice(Plus, c_vec);
897         let d = BigInt::from_slice(Plus, d_vec);
898 
899         if !b.is_zero() {
900             check(&a, &b, &c, &d);
901         }
902     }
903 }
904 
905 #[test]
test_checked_add()906 fn test_checked_add() {
907     for elm in SUM_TRIPLES.iter() {
908         let (a_vec, b_vec, c_vec) = *elm;
909         let a = BigInt::from_slice(Plus, a_vec);
910         let b = BigInt::from_slice(Plus, b_vec);
911         let c = BigInt::from_slice(Plus, c_vec);
912 
913         assert!(a.checked_add(&b).unwrap() == c);
914         assert!(b.checked_add(&a).unwrap() == c);
915         assert!(c.checked_add(&(-&a)).unwrap() == b);
916         assert!(c.checked_add(&(-&b)).unwrap() == a);
917         assert!(a.checked_add(&(-&c)).unwrap() == (-&b));
918         assert!(b.checked_add(&(-&c)).unwrap() == (-&a));
919         assert!((-&a).checked_add(&(-&b)).unwrap() == (-&c));
920         assert!(a.checked_add(&(-&a)).unwrap() == BigInt::zero());
921     }
922 }
923 
924 #[test]
test_checked_sub()925 fn test_checked_sub() {
926     for elm in SUM_TRIPLES.iter() {
927         let (a_vec, b_vec, c_vec) = *elm;
928         let a = BigInt::from_slice(Plus, a_vec);
929         let b = BigInt::from_slice(Plus, b_vec);
930         let c = BigInt::from_slice(Plus, c_vec);
931 
932         assert!(c.checked_sub(&a).unwrap() == b);
933         assert!(c.checked_sub(&b).unwrap() == a);
934         assert!((-&b).checked_sub(&a).unwrap() == (-&c));
935         assert!((-&a).checked_sub(&b).unwrap() == (-&c));
936         assert!(b.checked_sub(&(-&a)).unwrap() == c);
937         assert!(a.checked_sub(&(-&b)).unwrap() == c);
938         assert!((-&c).checked_sub(&(-&a)).unwrap() == (-&b));
939         assert!(a.checked_sub(&a).unwrap() == BigInt::zero());
940     }
941 }
942 
943 #[test]
test_checked_mul()944 fn test_checked_mul() {
945     for elm in MUL_TRIPLES.iter() {
946         let (a_vec, b_vec, c_vec) = *elm;
947         let a = BigInt::from_slice(Plus, a_vec);
948         let b = BigInt::from_slice(Plus, b_vec);
949         let c = BigInt::from_slice(Plus, c_vec);
950 
951         assert!(a.checked_mul(&b).unwrap() == c);
952         assert!(b.checked_mul(&a).unwrap() == c);
953 
954         assert!((-&a).checked_mul(&b).unwrap() == -&c);
955         assert!((-&b).checked_mul(&a).unwrap() == -&c);
956     }
957 
958     for elm in DIV_REM_QUADRUPLES.iter() {
959         let (a_vec, b_vec, c_vec, d_vec) = *elm;
960         let a = BigInt::from_slice(Plus, a_vec);
961         let b = BigInt::from_slice(Plus, b_vec);
962         let c = BigInt::from_slice(Plus, c_vec);
963         let d = BigInt::from_slice(Plus, d_vec);
964 
965         assert!(a == b.checked_mul(&c).unwrap() + &d);
966         assert!(a == c.checked_mul(&b).unwrap() + &d);
967     }
968 }
969 #[test]
test_checked_div()970 fn test_checked_div() {
971     for elm in MUL_TRIPLES.iter() {
972         let (a_vec, b_vec, c_vec) = *elm;
973         let a = BigInt::from_slice(Plus, a_vec);
974         let b = BigInt::from_slice(Plus, b_vec);
975         let c = BigInt::from_slice(Plus, c_vec);
976 
977         if !a.is_zero() {
978             assert!(c.checked_div(&a).unwrap() == b);
979             assert!((-&c).checked_div(&(-&a)).unwrap() == b);
980             assert!((-&c).checked_div(&a).unwrap() == -&b);
981         }
982         if !b.is_zero() {
983             assert!(c.checked_div(&b).unwrap() == a);
984             assert!((-&c).checked_div(&(-&b)).unwrap() == a);
985             assert!((-&c).checked_div(&b).unwrap() == -&a);
986         }
987 
988         assert!(c.checked_div(&Zero::zero()).is_none());
989         assert!((-&c).checked_div(&Zero::zero()).is_none());
990     }
991 }
992 
993 #[test]
test_gcd()994 fn test_gcd() {
995     fn check(a: isize, b: isize, c: isize) {
996         let big_a: BigInt = FromPrimitive::from_isize(a).unwrap();
997         let big_b: BigInt = FromPrimitive::from_isize(b).unwrap();
998         let big_c: BigInt = FromPrimitive::from_isize(c).unwrap();
999 
1000         assert_eq!(big_a.gcd(&big_b), big_c);
1001         assert_eq!(big_a.extended_gcd(&big_b).gcd, big_c);
1002         assert_eq!(big_a.gcd_lcm(&big_b).0, big_c);
1003         assert_eq!(big_a.extended_gcd_lcm(&big_b).0.gcd, big_c);
1004     }
1005 
1006     check(10, 2, 2);
1007     check(10, 3, 1);
1008     check(0, 3, 3);
1009     check(3, 3, 3);
1010     check(56, 42, 14);
1011     check(3, -3, 3);
1012     check(-6, 3, 3);
1013     check(-4, -2, 2);
1014 }
1015 
1016 #[test]
test_lcm()1017 fn test_lcm() {
1018     fn check(a: isize, b: isize, c: isize) {
1019         let big_a: BigInt = FromPrimitive::from_isize(a).unwrap();
1020         let big_b: BigInt = FromPrimitive::from_isize(b).unwrap();
1021         let big_c: BigInt = FromPrimitive::from_isize(c).unwrap();
1022 
1023         assert_eq!(big_a.lcm(&big_b), big_c);
1024         assert_eq!(big_a.gcd_lcm(&big_b).1, big_c);
1025         assert_eq!(big_a.extended_gcd_lcm(&big_b).1, big_c);
1026     }
1027 
1028     check(0, 0, 0);
1029     check(1, 0, 0);
1030     check(0, 1, 0);
1031     check(1, 1, 1);
1032     check(-1, 1, 1);
1033     check(1, -1, 1);
1034     check(-1, -1, 1);
1035     check(8, 9, 72);
1036     check(11, 5, 55);
1037 }
1038 
1039 #[test]
test_next_multiple_of()1040 fn test_next_multiple_of() {
1041     assert_eq!(
1042         BigInt::from(16).next_multiple_of(&BigInt::from(8)),
1043         BigInt::from(16)
1044     );
1045     assert_eq!(
1046         BigInt::from(23).next_multiple_of(&BigInt::from(8)),
1047         BigInt::from(24)
1048     );
1049     assert_eq!(
1050         BigInt::from(16).next_multiple_of(&BigInt::from(-8)),
1051         BigInt::from(16)
1052     );
1053     assert_eq!(
1054         BigInt::from(23).next_multiple_of(&BigInt::from(-8)),
1055         BigInt::from(16)
1056     );
1057     assert_eq!(
1058         BigInt::from(-16).next_multiple_of(&BigInt::from(8)),
1059         BigInt::from(-16)
1060     );
1061     assert_eq!(
1062         BigInt::from(-23).next_multiple_of(&BigInt::from(8)),
1063         BigInt::from(-16)
1064     );
1065     assert_eq!(
1066         BigInt::from(-16).next_multiple_of(&BigInt::from(-8)),
1067         BigInt::from(-16)
1068     );
1069     assert_eq!(
1070         BigInt::from(-23).next_multiple_of(&BigInt::from(-8)),
1071         BigInt::from(-24)
1072     );
1073 }
1074 
1075 #[test]
test_prev_multiple_of()1076 fn test_prev_multiple_of() {
1077     assert_eq!(
1078         BigInt::from(16).prev_multiple_of(&BigInt::from(8)),
1079         BigInt::from(16)
1080     );
1081     assert_eq!(
1082         BigInt::from(23).prev_multiple_of(&BigInt::from(8)),
1083         BigInt::from(16)
1084     );
1085     assert_eq!(
1086         BigInt::from(16).prev_multiple_of(&BigInt::from(-8)),
1087         BigInt::from(16)
1088     );
1089     assert_eq!(
1090         BigInt::from(23).prev_multiple_of(&BigInt::from(-8)),
1091         BigInt::from(24)
1092     );
1093     assert_eq!(
1094         BigInt::from(-16).prev_multiple_of(&BigInt::from(8)),
1095         BigInt::from(-16)
1096     );
1097     assert_eq!(
1098         BigInt::from(-23).prev_multiple_of(&BigInt::from(8)),
1099         BigInt::from(-24)
1100     );
1101     assert_eq!(
1102         BigInt::from(-16).prev_multiple_of(&BigInt::from(-8)),
1103         BigInt::from(-16)
1104     );
1105     assert_eq!(
1106         BigInt::from(-23).prev_multiple_of(&BigInt::from(-8)),
1107         BigInt::from(-16)
1108     );
1109 }
1110 
1111 #[test]
test_abs_sub()1112 fn test_abs_sub() {
1113     let zero: BigInt = Zero::zero();
1114     let one: BigInt = One::one();
1115     assert_eq!((-&one).abs_sub(&one), zero);
1116     let one: BigInt = One::one();
1117     let zero: BigInt = Zero::zero();
1118     assert_eq!(one.abs_sub(&one), zero);
1119     let one: BigInt = One::one();
1120     let zero: BigInt = Zero::zero();
1121     assert_eq!(one.abs_sub(&zero), one);
1122     let one: BigInt = One::one();
1123     let two: BigInt = FromPrimitive::from_isize(2).unwrap();
1124     assert_eq!(one.abs_sub(&-&one), two);
1125 }
1126 
1127 #[test]
test_from_str_radix()1128 fn test_from_str_radix() {
1129     fn check(s: &str, ans: Option<isize>) {
1130         let ans = ans.map(|n| {
1131             let x: BigInt = FromPrimitive::from_isize(n).unwrap();
1132             x
1133         });
1134         assert_eq!(BigInt::from_str_radix(s, 10).ok(), ans);
1135     }
1136     check("10", Some(10));
1137     check("1", Some(1));
1138     check("0", Some(0));
1139     check("-1", Some(-1));
1140     check("-10", Some(-10));
1141     check("+10", Some(10));
1142     check("--7", None);
1143     check("++5", None);
1144     check("+-9", None);
1145     check("-+3", None);
1146     check("Z", None);
1147     check("_", None);
1148 
1149     // issue 10522, this hit an edge case that caused it to
1150     // attempt to allocate a vector of size (-1u) == huge.
1151     let x: BigInt = format!("1{}", repeat("0").take(36).collect::<String>())
1152         .parse()
1153         .unwrap();
1154     let _y = x.to_string();
1155 }
1156 
1157 #[test]
test_lower_hex()1158 fn test_lower_hex() {
1159     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1160     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1161 
1162     assert_eq!(format!("{:x}", a), "a");
1163     assert_eq!(format!("{:x}", hello), "-48656c6c6f20776f726c6421");
1164     assert_eq!(format!("{:♥>+#8x}", a), "♥♥♥♥+0xa");
1165 }
1166 
1167 #[test]
test_upper_hex()1168 fn test_upper_hex() {
1169     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1170     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1171 
1172     assert_eq!(format!("{:X}", a), "A");
1173     assert_eq!(format!("{:X}", hello), "-48656C6C6F20776F726C6421");
1174     assert_eq!(format!("{:♥>+#8X}", a), "♥♥♥♥+0xA");
1175 }
1176 
1177 #[test]
test_binary()1178 fn test_binary() {
1179     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1180     let hello = BigInt::parse_bytes(b"-224055342307539", 10).unwrap();
1181 
1182     assert_eq!(format!("{:b}", a), "1010");
1183     assert_eq!(
1184         format!("{:b}", hello),
1185         "-110010111100011011110011000101101001100011010011"
1186     );
1187     assert_eq!(format!("{:♥>+#8b}", a), "♥+0b1010");
1188 }
1189 
1190 #[test]
test_octal()1191 fn test_octal() {
1192     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1193     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1194 
1195     assert_eq!(format!("{:o}", a), "12");
1196     assert_eq!(format!("{:o}", hello), "-22062554330674403566756233062041");
1197     assert_eq!(format!("{:♥>+#8o}", a), "♥♥♥+0o12");
1198 }
1199 
1200 #[test]
test_display()1201 fn test_display() {
1202     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1203     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1204 
1205     assert_eq!(format!("{}", a), "10");
1206     assert_eq!(format!("{}", hello), "-22405534230753963835153736737");
1207     assert_eq!(format!("{:♥>+#8}", a), "♥♥♥♥♥+10");
1208 }
1209 
1210 #[test]
test_neg()1211 fn test_neg() {
1212     assert!(-BigInt::new(Plus, vec![1, 1, 1]) == BigInt::new(Minus, vec![1, 1, 1]));
1213     assert!(-BigInt::new(Minus, vec![1, 1, 1]) == BigInt::new(Plus, vec![1, 1, 1]));
1214     let zero: BigInt = Zero::zero();
1215     assert_eq!(-&zero, zero);
1216 }
1217 
1218 #[test]
test_negative_shr()1219 fn test_negative_shr() {
1220     assert_eq!(BigInt::from(-1) >> 1, BigInt::from(-1));
1221     assert_eq!(BigInt::from(-2) >> 1, BigInt::from(-1));
1222     assert_eq!(BigInt::from(-3) >> 1, BigInt::from(-2));
1223     assert_eq!(BigInt::from(-3) >> 2, BigInt::from(-1));
1224 }
1225 
1226 #[test]
test_iter_sum()1227 fn test_iter_sum() {
1228     let result: BigInt = FromPrimitive::from_isize(-1234567).unwrap();
1229     let data: Vec<BigInt> = vec![
1230         FromPrimitive::from_i32(-1000000).unwrap(),
1231         FromPrimitive::from_i32(-200000).unwrap(),
1232         FromPrimitive::from_i32(-30000).unwrap(),
1233         FromPrimitive::from_i32(-4000).unwrap(),
1234         FromPrimitive::from_i32(-500).unwrap(),
1235         FromPrimitive::from_i32(-60).unwrap(),
1236         FromPrimitive::from_i32(-7).unwrap(),
1237     ];
1238 
1239     assert_eq!(result, data.iter().sum::<BigInt>());
1240     assert_eq!(result, data.into_iter().sum::<BigInt>());
1241 }
1242 
1243 #[test]
test_iter_product()1244 fn test_iter_product() {
1245     let data: Vec<BigInt> = vec![
1246         FromPrimitive::from_i32(1001).unwrap(),
1247         FromPrimitive::from_i32(-1002).unwrap(),
1248         FromPrimitive::from_i32(1003).unwrap(),
1249         FromPrimitive::from_i32(-1004).unwrap(),
1250         FromPrimitive::from_i32(1005).unwrap(),
1251     ];
1252     let result = data.get(0).unwrap()
1253         * data.get(1).unwrap()
1254         * data.get(2).unwrap()
1255         * data.get(3).unwrap()
1256         * data.get(4).unwrap();
1257 
1258     assert_eq!(result, data.iter().product::<BigInt>());
1259     assert_eq!(result, data.into_iter().product::<BigInt>());
1260 }
1261 
1262 #[test]
test_iter_sum_generic()1263 fn test_iter_sum_generic() {
1264     let result: BigInt = FromPrimitive::from_isize(-1234567).unwrap();
1265     let data = vec![-1000000, -200000, -30000, -4000, -500, -60, -7];
1266 
1267     assert_eq!(result, data.iter().sum::<BigInt>());
1268     assert_eq!(result, data.into_iter().sum::<BigInt>());
1269 }
1270 
1271 #[test]
test_iter_product_generic()1272 fn test_iter_product_generic() {
1273     let data = vec![1001, -1002, 1003, -1004, 1005];
1274     let result = data[0].to_bigint().unwrap()
1275         * data[1].to_bigint().unwrap()
1276         * data[2].to_bigint().unwrap()
1277         * data[3].to_bigint().unwrap()
1278         * data[4].to_bigint().unwrap();
1279 
1280     assert_eq!(result, data.iter().product::<BigInt>());
1281     assert_eq!(result, data.into_iter().product::<BigInt>());
1282 }
1283 
1284 #[test]
test_pow()1285 fn test_pow() {
1286     let one = BigInt::from(1i32);
1287     let two = BigInt::from(2i32);
1288     let four = BigInt::from(4i32);
1289     let eight = BigInt::from(8i32);
1290     let minus_two = BigInt::from(-2i32);
1291     macro_rules! check {
1292         ($t:ty) => {
1293             assert_eq!(Pow::pow(&two, 0 as $t), one);
1294             assert_eq!(Pow::pow(&two, 1 as $t), two);
1295             assert_eq!(Pow::pow(&two, 2 as $t), four);
1296             assert_eq!(Pow::pow(&two, 3 as $t), eight);
1297             assert_eq!(Pow::pow(&two, &(3 as $t)), eight);
1298             assert_eq!(Pow::pow(&minus_two, 0 as $t), one, "-2^0");
1299             assert_eq!(Pow::pow(&minus_two, 1 as $t), minus_two, "-2^1");
1300             assert_eq!(Pow::pow(&minus_two, 2 as $t), four, "-2^2");
1301             assert_eq!(Pow::pow(&minus_two, 3 as $t), -&eight, "-2^3");
1302         };
1303     }
1304     check!(u8);
1305     check!(u16);
1306     check!(u32);
1307     check!(u64);
1308     check!(usize);
1309 
1310     let pow_1e10000 = BigInt::from(10u32).pow(10_000_u32);
1311     let manual_1e10000 = repeat(10u32).take(10_000).product::<BigInt>();
1312     assert!(manual_1e10000 == pow_1e10000);
1313 }
1314 
1315 #[test]
test_bit()1316 fn test_bit() {
1317     // 12 = (1100)_2
1318     assert!(!BigInt::from(0b1100u8).bit(0));
1319     assert!(!BigInt::from(0b1100u8).bit(1));
1320     assert!(BigInt::from(0b1100u8).bit(2));
1321     assert!(BigInt::from(0b1100u8).bit(3));
1322     assert!(!BigInt::from(0b1100u8).bit(4));
1323     assert!(!BigInt::from(0b1100u8).bit(200));
1324     assert!(!BigInt::from(0b1100u8).bit(u64::MAX));
1325     // -12 = (...110100)_2
1326     assert!(!BigInt::from(-12i8).bit(0));
1327     assert!(!BigInt::from(-12i8).bit(1));
1328     assert!(BigInt::from(-12i8).bit(2));
1329     assert!(!BigInt::from(-12i8).bit(3));
1330     assert!(BigInt::from(-12i8).bit(4));
1331     assert!(BigInt::from(-12i8).bit(200));
1332     assert!(BigInt::from(-12i8).bit(u64::MAX));
1333 }
1334 
1335 #[test]
test_set_bit()1336 fn test_set_bit() {
1337     let mut x: BigInt;
1338 
1339     // zero
1340     x = BigInt::zero();
1341     x.set_bit(200, true);
1342     assert_eq!(x, BigInt::one() << 200);
1343     x = BigInt::zero();
1344     x.set_bit(200, false);
1345     assert_eq!(x, BigInt::zero());
1346 
1347     // positive numbers
1348     x = BigInt::from_biguint(Plus, BigUint::one() << 200);
1349     x.set_bit(10, true);
1350     x.set_bit(200, false);
1351     assert_eq!(x, BigInt::one() << 10);
1352     x.set_bit(10, false);
1353     x.set_bit(5, false);
1354     assert_eq!(x, BigInt::zero());
1355 
1356     // negative numbers
1357     x = BigInt::from(-12i8);
1358     x.set_bit(200, true);
1359     assert_eq!(x, BigInt::from(-12i8));
1360     x.set_bit(200, false);
1361     assert_eq!(
1362         x,
1363         BigInt::from_biguint(Minus, BigUint::from(12u8) | (BigUint::one() << 200))
1364     );
1365     x.set_bit(6, false);
1366     assert_eq!(
1367         x,
1368         BigInt::from_biguint(Minus, BigUint::from(76u8) | (BigUint::one() << 200))
1369     );
1370     x.set_bit(6, true);
1371     assert_eq!(
1372         x,
1373         BigInt::from_biguint(Minus, BigUint::from(12u8) | (BigUint::one() << 200))
1374     );
1375     x.set_bit(200, true);
1376     assert_eq!(x, BigInt::from(-12i8));
1377 
1378     x = BigInt::from_biguint(Minus, BigUint::one() << 30);
1379     x.set_bit(10, true);
1380     assert_eq!(
1381         x,
1382         BigInt::from_biguint(Minus, (BigUint::one() << 30) - (BigUint::one() << 10))
1383     );
1384 
1385     x = BigInt::from_biguint(Minus, BigUint::one() << 200);
1386     x.set_bit(40, true);
1387     assert_eq!(
1388         x,
1389         BigInt::from_biguint(Minus, (BigUint::one() << 200) - (BigUint::one() << 40))
1390     );
1391 
1392     x = BigInt::from_biguint(Minus, (BigUint::one() << 200) | (BigUint::one() << 100));
1393     x.set_bit(100, false);
1394     assert_eq!(
1395         x,
1396         BigInt::from_biguint(Minus, (BigUint::one() << 200) | (BigUint::one() << 101))
1397     );
1398 
1399     x = BigInt::from_biguint(Minus, (BigUint::one() << 63) | (BigUint::one() << 62));
1400     x.set_bit(62, false);
1401     assert_eq!(x, BigInt::from_biguint(Minus, BigUint::one() << 64));
1402 
1403     x = BigInt::from_biguint(Minus, (BigUint::one() << 200) - BigUint::one());
1404     x.set_bit(0, false);
1405     assert_eq!(x, BigInt::from_biguint(Minus, BigUint::one() << 200));
1406 }
1407