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(), None);
452     assert_eq!((-&big_num).to_f32(), Some(f32::MIN));
453     assert_eq!(((-&big_num) - 1u8).to_f32(), None);
454 
455     assert_eq!(((BigInt::one() << 128u8) - 1u8).to_f32(), None);
456     assert_eq!((BigInt::one() << 128u8).to_f32(), None);
457     assert_eq!((-((BigInt::one() << 128u8) - 1u8)).to_f32(), None);
458     assert_eq!((-(BigInt::one() << 128u8)).to_f32(), None);
459 }
460 
461 #[test]
462 #[allow(clippy::float_cmp)]
test_convert_f64()463 fn test_convert_f64() {
464     fn check(b1: &BigInt, f: f64) {
465         let b2 = BigInt::from_f64(f).unwrap();
466         assert_eq!(b1, &b2);
467         assert_eq!(b1.to_f64().unwrap(), f);
468         let neg_b1 = -b1;
469         let neg_b2 = BigInt::from_f64(-f).unwrap();
470         assert_eq!(neg_b1, neg_b2);
471         assert_eq!(neg_b1.to_f64().unwrap(), -f);
472     }
473 
474     check(&BigInt::zero(), 0.0);
475     check(&BigInt::one(), 1.0);
476     check(&BigInt::from(u32::MAX), pow(2.0_f64, 32) - 1.0);
477     check(&BigInt::from(1u64 << 32), pow(2.0_f64, 32));
478     check(&BigInt::from_slice(Plus, &[0, 0, 1]), pow(2.0_f64, 64));
479     check(
480         &((BigInt::one() << 100) + (BigInt::one() << 152)),
481         pow(2.0_f64, 100) + pow(2.0_f64, 152),
482     );
483     check(&(BigInt::one() << 1023), pow(2.0_f64, 1023));
484     check(&(BigInt::from((1u64 << 53) - 1) << (1024 - 53)), f64::MAX);
485 
486     // keeping all 53 digits with the bits at different offsets to the BigDigits
487     let x: u64 = 0b0000000000011110111110110111111101110111101111011111011011011101;
488     let mut f = x as f64;
489     let mut b = BigInt::from(x);
490     for _ in 0..128 {
491         check(&b, f);
492         f *= 2.0;
493         b <<= 1;
494     }
495 
496     // test rounding up with the bits at different offsets to the BigDigits
497     let mut f = ((1u64 << 54) - 1) as f64;
498     let mut b = BigInt::from(1u64 << 54);
499     for _ in 0..128 {
500         assert_eq!(b.to_f64(), Some(f));
501         f *= 2.0;
502         b <<= 1;
503     }
504 
505     // rounding
506     assert_eq!(
507         BigInt::from_f64(-f64::consts::PI),
508         Some(BigInt::from(-3i32))
509     );
510     assert_eq!(BigInt::from_f64(-f64::consts::E), Some(BigInt::from(-2i32)));
511     assert_eq!(BigInt::from_f64(-0.99999), Some(BigInt::zero()));
512     assert_eq!(BigInt::from_f64(-0.5), Some(BigInt::zero()));
513     assert_eq!(BigInt::from_f64(-0.0), Some(BigInt::zero()));
514     assert_eq!(
515         BigInt::from_f64(f64::MIN_POSITIVE / 2.0),
516         Some(BigInt::zero())
517     );
518     assert_eq!(BigInt::from_f64(f64::MIN_POSITIVE), Some(BigInt::zero()));
519     assert_eq!(BigInt::from_f64(0.5), Some(BigInt::zero()));
520     assert_eq!(BigInt::from_f64(0.99999), Some(BigInt::zero()));
521     assert_eq!(BigInt::from_f64(f64::consts::E), Some(BigInt::from(2u32)));
522     assert_eq!(BigInt::from_f64(f64::consts::PI), Some(BigInt::from(3u32)));
523 
524     // special float values
525     assert_eq!(BigInt::from_f64(f64::NAN), None);
526     assert_eq!(BigInt::from_f64(f64::INFINITY), None);
527     assert_eq!(BigInt::from_f64(f64::NEG_INFINITY), None);
528 
529     // largest BigInt that will round to a finite f64 value
530     let big_num = (BigInt::one() << 1024u16) - 1u8 - (BigInt::one() << (1024u16 - 54));
531     assert_eq!(big_num.to_f64(), Some(f64::MAX));
532     assert_eq!((&big_num + 1u8).to_f64(), None);
533     assert_eq!((-&big_num).to_f64(), Some(f64::MIN));
534     assert_eq!(((-&big_num) - 1u8).to_f64(), None);
535 
536     assert_eq!(((BigInt::one() << 1024u16) - 1u8).to_f64(), None);
537     assert_eq!((BigInt::one() << 1024u16).to_f64(), None);
538     assert_eq!((-((BigInt::one() << 1024u16) - 1u8)).to_f64(), None);
539     assert_eq!((-(BigInt::one() << 1024u16)).to_f64(), None);
540 }
541 
542 #[test]
test_convert_to_biguint()543 fn test_convert_to_biguint() {
544     fn check(n: BigInt, ans_1: BigUint) {
545         assert_eq!(n.to_biguint().unwrap(), ans_1);
546         assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
547     }
548     let zero: BigInt = Zero::zero();
549     let unsigned_zero: BigUint = Zero::zero();
550     let positive = BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3]));
551     let negative = -&positive;
552 
553     check(zero, unsigned_zero);
554     check(positive, BigUint::new(vec![1, 2, 3]));
555 
556     assert_eq!(negative.to_biguint(), None);
557 }
558 
559 #[test]
test_convert_from_uint()560 fn test_convert_from_uint() {
561     macro_rules! check {
562         ($ty:ident, $max:expr) => {
563             assert_eq!(BigInt::from($ty::zero()), BigInt::zero());
564             assert_eq!(BigInt::from($ty::one()), BigInt::one());
565             assert_eq!(BigInt::from($ty::MAX - $ty::one()), $max - BigInt::one());
566             assert_eq!(BigInt::from($ty::MAX), $max);
567         };
568     }
569 
570     check!(u8, BigInt::from_slice(Plus, &[u8::MAX as u32]));
571     check!(u16, BigInt::from_slice(Plus, &[u16::MAX as u32]));
572     check!(u32, BigInt::from_slice(Plus, &[u32::MAX]));
573     check!(u64, BigInt::from_slice(Plus, &[u32::MAX, u32::MAX]));
574     check!(
575         u128,
576         BigInt::from_slice(Plus, &[u32::MAX, u32::MAX, u32::MAX, u32::MAX])
577     );
578     check!(usize, BigInt::from(usize::MAX as u64));
579 }
580 
581 #[test]
test_convert_from_int()582 fn test_convert_from_int() {
583     macro_rules! check {
584         ($ty:ident, $min:expr, $max:expr) => {
585             assert_eq!(BigInt::from($ty::MIN), $min);
586             assert_eq!(BigInt::from($ty::MIN + $ty::one()), $min + BigInt::one());
587             assert_eq!(BigInt::from(-$ty::one()), -BigInt::one());
588             assert_eq!(BigInt::from($ty::zero()), BigInt::zero());
589             assert_eq!(BigInt::from($ty::one()), BigInt::one());
590             assert_eq!(BigInt::from($ty::MAX - $ty::one()), $max - BigInt::one());
591             assert_eq!(BigInt::from($ty::MAX), $max);
592         };
593     }
594 
595     check!(
596         i8,
597         BigInt::from_slice(Minus, &[1 << 7]),
598         BigInt::from_slice(Plus, &[i8::MAX as u32])
599     );
600     check!(
601         i16,
602         BigInt::from_slice(Minus, &[1 << 15]),
603         BigInt::from_slice(Plus, &[i16::MAX as u32])
604     );
605     check!(
606         i32,
607         BigInt::from_slice(Minus, &[1 << 31]),
608         BigInt::from_slice(Plus, &[i32::MAX as u32])
609     );
610     check!(
611         i64,
612         BigInt::from_slice(Minus, &[0, 1 << 31]),
613         BigInt::from_slice(Plus, &[u32::MAX, i32::MAX as u32])
614     );
615     check!(
616         i128,
617         BigInt::from_slice(Minus, &[0, 0, 0, 1 << 31]),
618         BigInt::from_slice(Plus, &[u32::MAX, u32::MAX, u32::MAX, i32::MAX as u32])
619     );
620     check!(
621         isize,
622         BigInt::from(isize::MIN as i64),
623         BigInt::from(isize::MAX as i64)
624     );
625 }
626 
627 #[test]
test_convert_from_biguint()628 fn test_convert_from_biguint() {
629     assert_eq!(BigInt::from(BigUint::zero()), BigInt::zero());
630     assert_eq!(BigInt::from(BigUint::one()), BigInt::one());
631     assert_eq!(
632         BigInt::from(BigUint::from_slice(&[1, 2, 3])),
633         BigInt::from_slice(Plus, &[1, 2, 3])
634     );
635 }
636 
637 #[test]
test_add()638 fn test_add() {
639     for elm in SUM_TRIPLES.iter() {
640         let (a_vec, b_vec, c_vec) = *elm;
641         let a = BigInt::from_slice(Plus, a_vec);
642         let b = BigInt::from_slice(Plus, b_vec);
643         let c = BigInt::from_slice(Plus, c_vec);
644         let (na, nb, nc) = (-&a, -&b, -&c);
645 
646         assert_op!(a + b == c);
647         assert_op!(b + a == c);
648         assert_op!(c + na == b);
649         assert_op!(c + nb == a);
650         assert_op!(a + nc == nb);
651         assert_op!(b + nc == na);
652         assert_op!(na + nb == nc);
653         assert_op!(a + na == BigInt::zero());
654 
655         assert_assign_op!(a += b == c);
656         assert_assign_op!(b += a == c);
657         assert_assign_op!(c += na == b);
658         assert_assign_op!(c += nb == a);
659         assert_assign_op!(a += nc == nb);
660         assert_assign_op!(b += nc == na);
661         assert_assign_op!(na += nb == nc);
662         assert_assign_op!(a += na == BigInt::zero());
663     }
664 }
665 
666 #[test]
test_sub()667 fn test_sub() {
668     for elm in SUM_TRIPLES.iter() {
669         let (a_vec, b_vec, c_vec) = *elm;
670         let a = BigInt::from_slice(Plus, a_vec);
671         let b = BigInt::from_slice(Plus, b_vec);
672         let c = BigInt::from_slice(Plus, c_vec);
673         let (na, nb, nc) = (-&a, -&b, -&c);
674 
675         assert_op!(c - a == b);
676         assert_op!(c - b == a);
677         assert_op!(nb - a == nc);
678         assert_op!(na - b == nc);
679         assert_op!(b - na == c);
680         assert_op!(a - nb == c);
681         assert_op!(nc - na == nb);
682         assert_op!(a - a == BigInt::zero());
683 
684         assert_assign_op!(c -= a == b);
685         assert_assign_op!(c -= b == a);
686         assert_assign_op!(nb -= a == nc);
687         assert_assign_op!(na -= b == nc);
688         assert_assign_op!(b -= na == c);
689         assert_assign_op!(a -= nb == c);
690         assert_assign_op!(nc -= na == nb);
691         assert_assign_op!(a -= a == BigInt::zero());
692     }
693 }
694 
695 #[test]
test_mul()696 fn test_mul() {
697     for elm in MUL_TRIPLES.iter() {
698         let (a_vec, b_vec, c_vec) = *elm;
699         let a = BigInt::from_slice(Plus, a_vec);
700         let b = BigInt::from_slice(Plus, b_vec);
701         let c = BigInt::from_slice(Plus, c_vec);
702         let (na, nb, nc) = (-&a, -&b, -&c);
703 
704         assert_op!(a * b == c);
705         assert_op!(b * a == c);
706         assert_op!(na * nb == c);
707 
708         assert_op!(na * b == nc);
709         assert_op!(nb * a == nc);
710 
711         assert_assign_op!(a *= b == c);
712         assert_assign_op!(b *= a == c);
713         assert_assign_op!(na *= nb == c);
714 
715         assert_assign_op!(na *= b == nc);
716         assert_assign_op!(nb *= a == nc);
717     }
718 
719     for elm in DIV_REM_QUADRUPLES.iter() {
720         let (a_vec, b_vec, c_vec, d_vec) = *elm;
721         let a = BigInt::from_slice(Plus, a_vec);
722         let b = BigInt::from_slice(Plus, b_vec);
723         let c = BigInt::from_slice(Plus, c_vec);
724         let d = BigInt::from_slice(Plus, d_vec);
725 
726         assert!(a == &b * &c + &d);
727         assert!(a == &c * &b + &d);
728     }
729 }
730 
731 #[test]
test_div_mod_floor()732 fn test_div_mod_floor() {
733     fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
734         let (d, m) = a.div_mod_floor(b);
735         assert_eq!(d, a.div_floor(b));
736         assert_eq!(m, a.mod_floor(b));
737         if !m.is_zero() {
738             assert_eq!(m.sign(), b.sign());
739         }
740         assert!(m.abs() <= b.abs());
741         assert!(*a == b * &d + &m);
742         assert!(d == *ans_d);
743         assert!(m == *ans_m);
744     }
745 
746     fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
747         if m.is_zero() {
748             check_sub(a, b, d, m);
749             check_sub(a, &b.neg(), &d.neg(), m);
750             check_sub(&a.neg(), b, &d.neg(), m);
751             check_sub(&a.neg(), &b.neg(), d, m);
752         } else {
753             let one: BigInt = One::one();
754             check_sub(a, b, d, m);
755             check_sub(a, &b.neg(), &(d.neg() - &one), &(m - b));
756             check_sub(&a.neg(), b, &(d.neg() - &one), &(b - m));
757             check_sub(&a.neg(), &b.neg(), d, &m.neg());
758         }
759     }
760 
761     for elm in MUL_TRIPLES.iter() {
762         let (a_vec, b_vec, c_vec) = *elm;
763         let a = BigInt::from_slice(Plus, a_vec);
764         let b = BigInt::from_slice(Plus, b_vec);
765         let c = BigInt::from_slice(Plus, c_vec);
766 
767         if !a.is_zero() {
768             check(&c, &a, &b, &Zero::zero());
769         }
770         if !b.is_zero() {
771             check(&c, &b, &a, &Zero::zero());
772         }
773     }
774 
775     for elm in DIV_REM_QUADRUPLES.iter() {
776         let (a_vec, b_vec, c_vec, d_vec) = *elm;
777         let a = BigInt::from_slice(Plus, a_vec);
778         let b = BigInt::from_slice(Plus, b_vec);
779         let c = BigInt::from_slice(Plus, c_vec);
780         let d = BigInt::from_slice(Plus, d_vec);
781 
782         if !b.is_zero() {
783             check(&a, &b, &c, &d);
784         }
785     }
786 }
787 
788 #[test]
test_div_rem()789 fn test_div_rem() {
790     fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
791         let (q, r) = a.div_rem(b);
792         if !r.is_zero() {
793             assert_eq!(r.sign(), a.sign());
794         }
795         assert!(r.abs() <= b.abs());
796         assert!(*a == b * &q + &r);
797         assert!(q == *ans_q);
798         assert!(r == *ans_r);
799 
800         let (a, b, ans_q, ans_r) = (a.clone(), b.clone(), ans_q.clone(), ans_r.clone());
801         assert_op!(a / b == ans_q);
802         assert_op!(a % b == ans_r);
803         assert_assign_op!(a /= b == ans_q);
804         assert_assign_op!(a %= b == ans_r);
805     }
806 
807     fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
808         check_sub(a, b, q, r);
809         check_sub(a, &b.neg(), &q.neg(), r);
810         check_sub(&a.neg(), b, &q.neg(), &r.neg());
811         check_sub(&a.neg(), &b.neg(), q, &r.neg());
812     }
813     for elm in MUL_TRIPLES.iter() {
814         let (a_vec, b_vec, c_vec) = *elm;
815         let a = BigInt::from_slice(Plus, a_vec);
816         let b = BigInt::from_slice(Plus, b_vec);
817         let c = BigInt::from_slice(Plus, c_vec);
818 
819         if !a.is_zero() {
820             check(&c, &a, &b, &Zero::zero());
821         }
822         if !b.is_zero() {
823             check(&c, &b, &a, &Zero::zero());
824         }
825     }
826 
827     for elm in DIV_REM_QUADRUPLES.iter() {
828         let (a_vec, b_vec, c_vec, d_vec) = *elm;
829         let a = BigInt::from_slice(Plus, a_vec);
830         let b = BigInt::from_slice(Plus, b_vec);
831         let c = BigInt::from_slice(Plus, c_vec);
832         let d = BigInt::from_slice(Plus, d_vec);
833 
834         if !b.is_zero() {
835             check(&a, &b, &c, &d);
836         }
837     }
838 }
839 
840 #[test]
test_div_ceil()841 fn test_div_ceil() {
842     fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt) {
843         assert_eq!(a.div_ceil(b), *ans_d);
844     }
845 
846     fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
847         if m.is_zero() {
848             check_sub(a, b, d);
849             check_sub(a, &b.neg(), &d.neg());
850             check_sub(&a.neg(), b, &d.neg());
851             check_sub(&a.neg(), &b.neg(), d);
852         } else {
853             check_sub(a, b, &(d + 1));
854             check_sub(a, &b.neg(), &d.neg());
855             check_sub(&a.neg(), b, &d.neg());
856             check_sub(&a.neg(), &b.neg(), &(d + 1));
857         }
858     }
859 
860     for elm in MUL_TRIPLES.iter() {
861         let (a_vec, b_vec, c_vec) = *elm;
862         let a = BigInt::from_slice(Plus, a_vec);
863         let b = BigInt::from_slice(Plus, b_vec);
864         let c = BigInt::from_slice(Plus, c_vec);
865 
866         if !a.is_zero() {
867             check(&c, &a, &b, &Zero::zero());
868         }
869         if !b.is_zero() {
870             check(&c, &b, &a, &Zero::zero());
871         }
872     }
873 
874     for elm in DIV_REM_QUADRUPLES.iter() {
875         let (a_vec, b_vec, c_vec, d_vec) = *elm;
876         let a = BigInt::from_slice(Plus, a_vec);
877         let b = BigInt::from_slice(Plus, b_vec);
878         let c = BigInt::from_slice(Plus, c_vec);
879         let d = BigInt::from_slice(Plus, d_vec);
880 
881         if !b.is_zero() {
882             check(&a, &b, &c, &d);
883         }
884     }
885 }
886 
887 #[test]
test_checked_add()888 fn test_checked_add() {
889     for elm in SUM_TRIPLES.iter() {
890         let (a_vec, b_vec, c_vec) = *elm;
891         let a = BigInt::from_slice(Plus, a_vec);
892         let b = BigInt::from_slice(Plus, b_vec);
893         let c = BigInt::from_slice(Plus, c_vec);
894 
895         assert!(a.checked_add(&b).unwrap() == c);
896         assert!(b.checked_add(&a).unwrap() == c);
897         assert!(c.checked_add(&(-&a)).unwrap() == b);
898         assert!(c.checked_add(&(-&b)).unwrap() == a);
899         assert!(a.checked_add(&(-&c)).unwrap() == (-&b));
900         assert!(b.checked_add(&(-&c)).unwrap() == (-&a));
901         assert!((-&a).checked_add(&(-&b)).unwrap() == (-&c));
902         assert!(a.checked_add(&(-&a)).unwrap() == BigInt::zero());
903     }
904 }
905 
906 #[test]
test_checked_sub()907 fn test_checked_sub() {
908     for elm in SUM_TRIPLES.iter() {
909         let (a_vec, b_vec, c_vec) = *elm;
910         let a = BigInt::from_slice(Plus, a_vec);
911         let b = BigInt::from_slice(Plus, b_vec);
912         let c = BigInt::from_slice(Plus, c_vec);
913 
914         assert!(c.checked_sub(&a).unwrap() == b);
915         assert!(c.checked_sub(&b).unwrap() == a);
916         assert!((-&b).checked_sub(&a).unwrap() == (-&c));
917         assert!((-&a).checked_sub(&b).unwrap() == (-&c));
918         assert!(b.checked_sub(&(-&a)).unwrap() == c);
919         assert!(a.checked_sub(&(-&b)).unwrap() == c);
920         assert!((-&c).checked_sub(&(-&a)).unwrap() == (-&b));
921         assert!(a.checked_sub(&a).unwrap() == BigInt::zero());
922     }
923 }
924 
925 #[test]
test_checked_mul()926 fn test_checked_mul() {
927     for elm in MUL_TRIPLES.iter() {
928         let (a_vec, b_vec, c_vec) = *elm;
929         let a = BigInt::from_slice(Plus, a_vec);
930         let b = BigInt::from_slice(Plus, b_vec);
931         let c = BigInt::from_slice(Plus, c_vec);
932 
933         assert!(a.checked_mul(&b).unwrap() == c);
934         assert!(b.checked_mul(&a).unwrap() == c);
935 
936         assert!((-&a).checked_mul(&b).unwrap() == -&c);
937         assert!((-&b).checked_mul(&a).unwrap() == -&c);
938     }
939 
940     for elm in DIV_REM_QUADRUPLES.iter() {
941         let (a_vec, b_vec, c_vec, d_vec) = *elm;
942         let a = BigInt::from_slice(Plus, a_vec);
943         let b = BigInt::from_slice(Plus, b_vec);
944         let c = BigInt::from_slice(Plus, c_vec);
945         let d = BigInt::from_slice(Plus, d_vec);
946 
947         assert!(a == b.checked_mul(&c).unwrap() + &d);
948         assert!(a == c.checked_mul(&b).unwrap() + &d);
949     }
950 }
951 #[test]
test_checked_div()952 fn test_checked_div() {
953     for elm in MUL_TRIPLES.iter() {
954         let (a_vec, b_vec, c_vec) = *elm;
955         let a = BigInt::from_slice(Plus, a_vec);
956         let b = BigInt::from_slice(Plus, b_vec);
957         let c = BigInt::from_slice(Plus, c_vec);
958 
959         if !a.is_zero() {
960             assert!(c.checked_div(&a).unwrap() == b);
961             assert!((-&c).checked_div(&(-&a)).unwrap() == b);
962             assert!((-&c).checked_div(&a).unwrap() == -&b);
963         }
964         if !b.is_zero() {
965             assert!(c.checked_div(&b).unwrap() == a);
966             assert!((-&c).checked_div(&(-&b)).unwrap() == a);
967             assert!((-&c).checked_div(&b).unwrap() == -&a);
968         }
969 
970         assert!(c.checked_div(&Zero::zero()).is_none());
971         assert!((-&c).checked_div(&Zero::zero()).is_none());
972     }
973 }
974 
975 #[test]
test_gcd()976 fn test_gcd() {
977     fn check(a: isize, b: isize, c: isize) {
978         let big_a: BigInt = FromPrimitive::from_isize(a).unwrap();
979         let big_b: BigInt = FromPrimitive::from_isize(b).unwrap();
980         let big_c: BigInt = FromPrimitive::from_isize(c).unwrap();
981 
982         assert_eq!(big_a.gcd(&big_b), big_c);
983         assert_eq!(big_a.extended_gcd(&big_b).gcd, big_c);
984         assert_eq!(big_a.gcd_lcm(&big_b).0, big_c);
985         assert_eq!(big_a.extended_gcd_lcm(&big_b).0.gcd, big_c);
986     }
987 
988     check(10, 2, 2);
989     check(10, 3, 1);
990     check(0, 3, 3);
991     check(3, 3, 3);
992     check(56, 42, 14);
993     check(3, -3, 3);
994     check(-6, 3, 3);
995     check(-4, -2, 2);
996 }
997 
998 #[test]
test_lcm()999 fn test_lcm() {
1000     fn check(a: isize, b: isize, c: isize) {
1001         let big_a: BigInt = FromPrimitive::from_isize(a).unwrap();
1002         let big_b: BigInt = FromPrimitive::from_isize(b).unwrap();
1003         let big_c: BigInt = FromPrimitive::from_isize(c).unwrap();
1004 
1005         assert_eq!(big_a.lcm(&big_b), big_c);
1006         assert_eq!(big_a.gcd_lcm(&big_b).1, big_c);
1007         assert_eq!(big_a.extended_gcd_lcm(&big_b).1, big_c);
1008     }
1009 
1010     check(0, 0, 0);
1011     check(1, 0, 0);
1012     check(0, 1, 0);
1013     check(1, 1, 1);
1014     check(-1, 1, 1);
1015     check(1, -1, 1);
1016     check(-1, -1, 1);
1017     check(8, 9, 72);
1018     check(11, 5, 55);
1019 }
1020 
1021 #[test]
test_next_multiple_of()1022 fn test_next_multiple_of() {
1023     assert_eq!(
1024         BigInt::from(16).next_multiple_of(&BigInt::from(8)),
1025         BigInt::from(16)
1026     );
1027     assert_eq!(
1028         BigInt::from(23).next_multiple_of(&BigInt::from(8)),
1029         BigInt::from(24)
1030     );
1031     assert_eq!(
1032         BigInt::from(16).next_multiple_of(&BigInt::from(-8)),
1033         BigInt::from(16)
1034     );
1035     assert_eq!(
1036         BigInt::from(23).next_multiple_of(&BigInt::from(-8)),
1037         BigInt::from(16)
1038     );
1039     assert_eq!(
1040         BigInt::from(-16).next_multiple_of(&BigInt::from(8)),
1041         BigInt::from(-16)
1042     );
1043     assert_eq!(
1044         BigInt::from(-23).next_multiple_of(&BigInt::from(8)),
1045         BigInt::from(-16)
1046     );
1047     assert_eq!(
1048         BigInt::from(-16).next_multiple_of(&BigInt::from(-8)),
1049         BigInt::from(-16)
1050     );
1051     assert_eq!(
1052         BigInt::from(-23).next_multiple_of(&BigInt::from(-8)),
1053         BigInt::from(-24)
1054     );
1055 }
1056 
1057 #[test]
test_prev_multiple_of()1058 fn test_prev_multiple_of() {
1059     assert_eq!(
1060         BigInt::from(16).prev_multiple_of(&BigInt::from(8)),
1061         BigInt::from(16)
1062     );
1063     assert_eq!(
1064         BigInt::from(23).prev_multiple_of(&BigInt::from(8)),
1065         BigInt::from(16)
1066     );
1067     assert_eq!(
1068         BigInt::from(16).prev_multiple_of(&BigInt::from(-8)),
1069         BigInt::from(16)
1070     );
1071     assert_eq!(
1072         BigInt::from(23).prev_multiple_of(&BigInt::from(-8)),
1073         BigInt::from(24)
1074     );
1075     assert_eq!(
1076         BigInt::from(-16).prev_multiple_of(&BigInt::from(8)),
1077         BigInt::from(-16)
1078     );
1079     assert_eq!(
1080         BigInt::from(-23).prev_multiple_of(&BigInt::from(8)),
1081         BigInt::from(-24)
1082     );
1083     assert_eq!(
1084         BigInt::from(-16).prev_multiple_of(&BigInt::from(-8)),
1085         BigInt::from(-16)
1086     );
1087     assert_eq!(
1088         BigInt::from(-23).prev_multiple_of(&BigInt::from(-8)),
1089         BigInt::from(-16)
1090     );
1091 }
1092 
1093 #[test]
test_abs_sub()1094 fn test_abs_sub() {
1095     let zero: BigInt = Zero::zero();
1096     let one: BigInt = One::one();
1097     assert_eq!((-&one).abs_sub(&one), zero);
1098     let one: BigInt = One::one();
1099     let zero: BigInt = Zero::zero();
1100     assert_eq!(one.abs_sub(&one), zero);
1101     let one: BigInt = One::one();
1102     let zero: BigInt = Zero::zero();
1103     assert_eq!(one.abs_sub(&zero), one);
1104     let one: BigInt = One::one();
1105     let two: BigInt = FromPrimitive::from_isize(2).unwrap();
1106     assert_eq!(one.abs_sub(&-&one), two);
1107 }
1108 
1109 #[test]
test_from_str_radix()1110 fn test_from_str_radix() {
1111     fn check(s: &str, ans: Option<isize>) {
1112         let ans = ans.map(|n| {
1113             let x: BigInt = FromPrimitive::from_isize(n).unwrap();
1114             x
1115         });
1116         assert_eq!(BigInt::from_str_radix(s, 10).ok(), ans);
1117     }
1118     check("10", Some(10));
1119     check("1", Some(1));
1120     check("0", Some(0));
1121     check("-1", Some(-1));
1122     check("-10", Some(-10));
1123     check("+10", Some(10));
1124     check("--7", None);
1125     check("++5", None);
1126     check("+-9", None);
1127     check("-+3", None);
1128     check("Z", None);
1129     check("_", None);
1130 
1131     // issue 10522, this hit an edge case that caused it to
1132     // attempt to allocate a vector of size (-1u) == huge.
1133     let x: BigInt = format!("1{}", repeat("0").take(36).collect::<String>())
1134         .parse()
1135         .unwrap();
1136     let _y = x.to_string();
1137 }
1138 
1139 #[test]
test_lower_hex()1140 fn test_lower_hex() {
1141     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1142     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1143 
1144     assert_eq!(format!("{:x}", a), "a");
1145     assert_eq!(format!("{:x}", hello), "-48656c6c6f20776f726c6421");
1146     assert_eq!(format!("{:♥>+#8x}", a), "♥♥♥♥+0xa");
1147 }
1148 
1149 #[test]
test_upper_hex()1150 fn test_upper_hex() {
1151     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1152     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1153 
1154     assert_eq!(format!("{:X}", a), "A");
1155     assert_eq!(format!("{:X}", hello), "-48656C6C6F20776F726C6421");
1156     assert_eq!(format!("{:♥>+#8X}", a), "♥♥♥♥+0xA");
1157 }
1158 
1159 #[test]
test_binary()1160 fn test_binary() {
1161     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1162     let hello = BigInt::parse_bytes(b"-224055342307539", 10).unwrap();
1163 
1164     assert_eq!(format!("{:b}", a), "1010");
1165     assert_eq!(
1166         format!("{:b}", hello),
1167         "-110010111100011011110011000101101001100011010011"
1168     );
1169     assert_eq!(format!("{:♥>+#8b}", a), "♥+0b1010");
1170 }
1171 
1172 #[test]
test_octal()1173 fn test_octal() {
1174     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1175     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1176 
1177     assert_eq!(format!("{:o}", a), "12");
1178     assert_eq!(format!("{:o}", hello), "-22062554330674403566756233062041");
1179     assert_eq!(format!("{:♥>+#8o}", a), "♥♥♥+0o12");
1180 }
1181 
1182 #[test]
test_display()1183 fn test_display() {
1184     let a = BigInt::parse_bytes(b"A", 16).unwrap();
1185     let hello = BigInt::parse_bytes(b"-22405534230753963835153736737", 10).unwrap();
1186 
1187     assert_eq!(format!("{}", a), "10");
1188     assert_eq!(format!("{}", hello), "-22405534230753963835153736737");
1189     assert_eq!(format!("{:♥>+#8}", a), "♥♥♥♥♥+10");
1190 }
1191 
1192 #[test]
test_neg()1193 fn test_neg() {
1194     assert!(-BigInt::new(Plus, vec![1, 1, 1]) == BigInt::new(Minus, vec![1, 1, 1]));
1195     assert!(-BigInt::new(Minus, vec![1, 1, 1]) == BigInt::new(Plus, vec![1, 1, 1]));
1196     let zero: BigInt = Zero::zero();
1197     assert_eq!(-&zero, zero);
1198 }
1199 
1200 #[test]
test_negative_shr()1201 fn test_negative_shr() {
1202     assert_eq!(BigInt::from(-1) >> 1, BigInt::from(-1));
1203     assert_eq!(BigInt::from(-2) >> 1, BigInt::from(-1));
1204     assert_eq!(BigInt::from(-3) >> 1, BigInt::from(-2));
1205     assert_eq!(BigInt::from(-3) >> 2, BigInt::from(-1));
1206 }
1207 
1208 #[test]
test_iter_sum()1209 fn test_iter_sum() {
1210     let result: BigInt = FromPrimitive::from_isize(-1234567).unwrap();
1211     let data: Vec<BigInt> = vec![
1212         FromPrimitive::from_i32(-1000000).unwrap(),
1213         FromPrimitive::from_i32(-200000).unwrap(),
1214         FromPrimitive::from_i32(-30000).unwrap(),
1215         FromPrimitive::from_i32(-4000).unwrap(),
1216         FromPrimitive::from_i32(-500).unwrap(),
1217         FromPrimitive::from_i32(-60).unwrap(),
1218         FromPrimitive::from_i32(-7).unwrap(),
1219     ];
1220 
1221     assert_eq!(result, data.iter().sum::<BigInt>());
1222     assert_eq!(result, data.into_iter().sum::<BigInt>());
1223 }
1224 
1225 #[test]
test_iter_product()1226 fn test_iter_product() {
1227     let data: Vec<BigInt> = vec![
1228         FromPrimitive::from_i32(1001).unwrap(),
1229         FromPrimitive::from_i32(-1002).unwrap(),
1230         FromPrimitive::from_i32(1003).unwrap(),
1231         FromPrimitive::from_i32(-1004).unwrap(),
1232         FromPrimitive::from_i32(1005).unwrap(),
1233     ];
1234     let result = data.get(0).unwrap()
1235         * data.get(1).unwrap()
1236         * data.get(2).unwrap()
1237         * data.get(3).unwrap()
1238         * data.get(4).unwrap();
1239 
1240     assert_eq!(result, data.iter().product::<BigInt>());
1241     assert_eq!(result, data.into_iter().product::<BigInt>());
1242 }
1243 
1244 #[test]
test_iter_sum_generic()1245 fn test_iter_sum_generic() {
1246     let result: BigInt = FromPrimitive::from_isize(-1234567).unwrap();
1247     let data = vec![-1000000, -200000, -30000, -4000, -500, -60, -7];
1248 
1249     assert_eq!(result, data.iter().sum::<BigInt>());
1250     assert_eq!(result, data.into_iter().sum::<BigInt>());
1251 }
1252 
1253 #[test]
test_iter_product_generic()1254 fn test_iter_product_generic() {
1255     let data = vec![1001, -1002, 1003, -1004, 1005];
1256     let result = data[0].to_bigint().unwrap()
1257         * data[1].to_bigint().unwrap()
1258         * data[2].to_bigint().unwrap()
1259         * data[3].to_bigint().unwrap()
1260         * data[4].to_bigint().unwrap();
1261 
1262     assert_eq!(result, data.iter().product::<BigInt>());
1263     assert_eq!(result, data.into_iter().product::<BigInt>());
1264 }
1265 
1266 #[test]
test_pow()1267 fn test_pow() {
1268     let one = BigInt::from(1i32);
1269     let two = BigInt::from(2i32);
1270     let four = BigInt::from(4i32);
1271     let eight = BigInt::from(8i32);
1272     let minus_two = BigInt::from(-2i32);
1273     macro_rules! check {
1274         ($t:ty) => {
1275             assert_eq!(Pow::pow(&two, 0 as $t), one);
1276             assert_eq!(Pow::pow(&two, 1 as $t), two);
1277             assert_eq!(Pow::pow(&two, 2 as $t), four);
1278             assert_eq!(Pow::pow(&two, 3 as $t), eight);
1279             assert_eq!(Pow::pow(&two, &(3 as $t)), eight);
1280             assert_eq!(Pow::pow(&minus_two, 0 as $t), one, "-2^0");
1281             assert_eq!(Pow::pow(&minus_two, 1 as $t), minus_two, "-2^1");
1282             assert_eq!(Pow::pow(&minus_two, 2 as $t), four, "-2^2");
1283             assert_eq!(Pow::pow(&minus_two, 3 as $t), -&eight, "-2^3");
1284         };
1285     }
1286     check!(u8);
1287     check!(u16);
1288     check!(u32);
1289     check!(u64);
1290     check!(usize);
1291 }
1292