1 use num_bigint::Sign::Plus;
2 use num_bigint::{BigInt, ToBigInt};
3 use num_bigint::{BigUint, ToBigUint};
4 use num_integer::Integer;
5 
6 use std::cmp::Ordering::{Equal, Greater, Less};
7 use std::collections::hash_map::RandomState;
8 use std::hash::{BuildHasher, Hash, Hasher};
9 use std::i64;
10 use std::iter::repeat;
11 use std::str::FromStr;
12 use std::{f32, f64};
13 use std::{i128, u128};
14 use std::{u16, u32, u64, u8, usize};
15 
16 use num_traits::{
17     pow, CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, FromPrimitive, Num, One, Pow, ToPrimitive,
18     Zero,
19 };
20 
21 mod consts;
22 use crate::consts::*;
23 
24 #[macro_use]
25 mod macros;
26 
27 #[test]
test_from_bytes_be()28 fn test_from_bytes_be() {
29     fn check(s: &str, result: &str) {
30         assert_eq!(
31             BigUint::from_bytes_be(s.as_bytes()),
32             BigUint::parse_bytes(result.as_bytes(), 10).unwrap()
33         );
34     }
35     check("A", "65");
36     check("AA", "16705");
37     check("AB", "16706");
38     check("Hello world!", "22405534230753963835153736737");
39     assert_eq!(BigUint::from_bytes_be(&[]), BigUint::zero());
40 }
41 
42 #[test]
test_to_bytes_be()43 fn test_to_bytes_be() {
44     fn check(s: &str, result: &str) {
45         let b = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
46         assert_eq!(b.to_bytes_be(), s.as_bytes());
47     }
48     check("A", "65");
49     check("AA", "16705");
50     check("AB", "16706");
51     check("Hello world!", "22405534230753963835153736737");
52     let b: BigUint = Zero::zero();
53     assert_eq!(b.to_bytes_be(), [0]);
54 
55     // Test with leading/trailing zero bytes and a full BigDigit of value 0
56     let b = BigUint::from_str_radix("00010000000000000200", 16).unwrap();
57     assert_eq!(b.to_bytes_be(), [1, 0, 0, 0, 0, 0, 0, 2, 0]);
58 }
59 
60 #[test]
test_from_bytes_le()61 fn test_from_bytes_le() {
62     fn check(s: &str, result: &str) {
63         assert_eq!(
64             BigUint::from_bytes_le(s.as_bytes()),
65             BigUint::parse_bytes(result.as_bytes(), 10).unwrap()
66         );
67     }
68     check("A", "65");
69     check("AA", "16705");
70     check("BA", "16706");
71     check("!dlrow olleH", "22405534230753963835153736737");
72     assert_eq!(BigUint::from_bytes_le(&[]), BigUint::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 = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
79         assert_eq!(b.to_bytes_le(), s.as_bytes());
80     }
81     check("A", "65");
82     check("AA", "16705");
83     check("BA", "16706");
84     check("!dlrow olleH", "22405534230753963835153736737");
85     let b: BigUint = Zero::zero();
86     assert_eq!(b.to_bytes_le(), [0]);
87 
88     // Test with leading/trailing zero bytes and a full BigDigit of value 0
89     let b = BigUint::from_str_radix("00010000000000000200", 16).unwrap();
90     assert_eq!(b.to_bytes_le(), [0, 2, 0, 0, 0, 0, 0, 0, 1]);
91 }
92 
93 #[test]
test_cmp()94 fn test_cmp() {
95     let data: [&[_]; 7] = [&[], &[1], &[2], &[!0], &[0, 1], &[2, 1], &[1, 1, 1]];
96     let data: Vec<BigUint> = data.iter().map(|v| BigUint::from_slice(*v)).collect();
97     for (i, ni) in data.iter().enumerate() {
98         for (j0, nj) in data[i..].iter().enumerate() {
99             let j = j0 + i;
100             if i == j {
101                 assert_eq!(ni.cmp(nj), Equal);
102                 assert_eq!(nj.cmp(ni), Equal);
103                 assert_eq!(ni, nj);
104                 assert!(!(ni != nj));
105                 assert!(ni <= nj);
106                 assert!(ni >= nj);
107                 assert!(!(ni < nj));
108                 assert!(!(ni > nj));
109             } else {
110                 assert_eq!(ni.cmp(nj), Less);
111                 assert_eq!(nj.cmp(ni), Greater);
112 
113                 assert!(!(ni == nj));
114                 assert!(ni != nj);
115 
116                 assert!(ni <= nj);
117                 assert!(!(ni >= nj));
118                 assert!(ni < nj);
119                 assert!(!(ni > nj));
120 
121                 assert!(!(nj <= ni));
122                 assert!(nj >= ni);
123                 assert!(!(nj < ni));
124                 assert!(nj > ni);
125             }
126         }
127     }
128 }
129 
hash<T: Hash>(x: &T) -> u64130 fn hash<T: Hash>(x: &T) -> u64 {
131     let mut hasher = <RandomState as BuildHasher>::Hasher::new();
132     x.hash(&mut hasher);
133     hasher.finish()
134 }
135 
136 #[test]
test_hash()137 fn test_hash() {
138     use crate::hash;
139 
140     let a = BigUint::new(vec![]);
141     let b = BigUint::new(vec![0]);
142     let c = BigUint::new(vec![1]);
143     let d = BigUint::new(vec![1, 0, 0, 0, 0, 0]);
144     let e = BigUint::new(vec![0, 0, 0, 0, 0, 1]);
145     assert!(hash(&a) == hash(&b));
146     assert!(hash(&b) != hash(&c));
147     assert!(hash(&c) == hash(&d));
148     assert!(hash(&d) != hash(&e));
149 }
150 
151 // LEFT, RIGHT, AND, OR, XOR
152 const BIT_TESTS: &[(&[u32], &[u32], &[u32], &[u32], &[u32])] = &[
153     (&[], &[], &[], &[], &[]),
154     (&[1, 0, 1], &[1, 1], &[1], &[1, 1, 1], &[0, 1, 1]),
155     (&[1, 0, 1], &[0, 1, 1], &[0, 0, 1], &[1, 1, 1], &[1, 1]),
156     (
157         &[268, 482, 17],
158         &[964, 54],
159         &[260, 34],
160         &[972, 502, 17],
161         &[712, 468, 17],
162     ),
163 ];
164 
165 #[test]
test_bitand()166 fn test_bitand() {
167     for elm in BIT_TESTS {
168         let (a_vec, b_vec, c_vec, _, _) = *elm;
169         let a = BigUint::from_slice(a_vec);
170         let b = BigUint::from_slice(b_vec);
171         let c = BigUint::from_slice(c_vec);
172 
173         assert_op!(a & b == c);
174         assert_op!(b & a == c);
175         assert_assign_op!(a &= b == c);
176         assert_assign_op!(b &= a == c);
177     }
178 }
179 
180 #[test]
test_bitor()181 fn test_bitor() {
182     for elm in BIT_TESTS {
183         let (a_vec, b_vec, _, c_vec, _) = *elm;
184         let a = BigUint::from_slice(a_vec);
185         let b = BigUint::from_slice(b_vec);
186         let c = BigUint::from_slice(c_vec);
187 
188         assert_op!(a | b == c);
189         assert_op!(b | a == c);
190         assert_assign_op!(a |= b == c);
191         assert_assign_op!(b |= a == c);
192     }
193 }
194 
195 #[test]
test_bitxor()196 fn test_bitxor() {
197     for elm in BIT_TESTS {
198         let (a_vec, b_vec, _, _, c_vec) = *elm;
199         let a = BigUint::from_slice(a_vec);
200         let b = BigUint::from_slice(b_vec);
201         let c = BigUint::from_slice(c_vec);
202 
203         assert_op!(a ^ b == c);
204         assert_op!(b ^ a == c);
205         assert_op!(a ^ c == b);
206         assert_op!(c ^ a == b);
207         assert_op!(b ^ c == a);
208         assert_op!(c ^ b == a);
209         assert_assign_op!(a ^= b == c);
210         assert_assign_op!(b ^= a == c);
211         assert_assign_op!(a ^= c == b);
212         assert_assign_op!(c ^= a == b);
213         assert_assign_op!(b ^= c == a);
214         assert_assign_op!(c ^= b == a);
215     }
216 }
217 
218 #[test]
test_shl()219 fn test_shl() {
220     fn check(s: &str, shift: usize, ans: &str) {
221         let opt_biguint = BigUint::from_str_radix(s, 16).ok();
222         let mut bu_assign = opt_biguint.unwrap();
223         let bu = (bu_assign.clone() << shift).to_str_radix(16);
224         assert_eq!(bu, ans);
225         bu_assign <<= shift;
226         assert_eq!(bu_assign.to_str_radix(16), ans);
227     }
228 
229     check("0", 3, "0");
230     check("1", 3, "8");
231 
232     check(
233         "1\
234          0000\
235          0000\
236          0000\
237          0001\
238          0000\
239          0000\
240          0000\
241          0001",
242         3,
243         "8\
244          0000\
245          0000\
246          0000\
247          0008\
248          0000\
249          0000\
250          0000\
251          0008",
252     );
253     check(
254         "1\
255          0000\
256          0001\
257          0000\
258          0001",
259         2,
260         "4\
261          0000\
262          0004\
263          0000\
264          0004",
265     );
266     check(
267         "1\
268          0001\
269          0001",
270         1,
271         "2\
272          0002\
273          0002",
274     );
275 
276     check(
277         "\
278          4000\
279          0000\
280          0000\
281          0000",
282         3,
283         "2\
284          0000\
285          0000\
286          0000\
287          0000",
288     );
289     check(
290         "4000\
291          0000",
292         2,
293         "1\
294          0000\
295          0000",
296     );
297     check(
298         "4000",
299         2,
300         "1\
301          0000",
302     );
303 
304     check(
305         "4000\
306          0000\
307          0000\
308          0000",
309         67,
310         "2\
311          0000\
312          0000\
313          0000\
314          0000\
315          0000\
316          0000\
317          0000\
318          0000",
319     );
320     check(
321         "4000\
322          0000",
323         35,
324         "2\
325          0000\
326          0000\
327          0000\
328          0000",
329     );
330     check(
331         "4000",
332         19,
333         "2\
334          0000\
335          0000",
336     );
337 
338     check(
339         "fedc\
340          ba98\
341          7654\
342          3210\
343          fedc\
344          ba98\
345          7654\
346          3210",
347         4,
348         "f\
349          edcb\
350          a987\
351          6543\
352          210f\
353          edcb\
354          a987\
355          6543\
356          2100",
357     );
358     check(
359         "88887777666655554444333322221111",
360         16,
361         "888877776666555544443333222211110000",
362     );
363 }
364 
365 #[test]
test_shr()366 fn test_shr() {
367     fn check(s: &str, shift: usize, ans: &str) {
368         let opt_biguint = BigUint::from_str_radix(s, 16).ok();
369         let mut bu_assign = opt_biguint.unwrap();
370         let bu = (bu_assign.clone() >> shift).to_str_radix(16);
371         assert_eq!(bu, ans);
372         bu_assign >>= shift;
373         assert_eq!(bu_assign.to_str_radix(16), ans);
374     }
375 
376     check("0", 3, "0");
377     check("f", 3, "1");
378 
379     check(
380         "1\
381          0000\
382          0000\
383          0000\
384          0001\
385          0000\
386          0000\
387          0000\
388          0001",
389         3,
390         "2000\
391          0000\
392          0000\
393          0000\
394          2000\
395          0000\
396          0000\
397          0000",
398     );
399     check(
400         "1\
401          0000\
402          0001\
403          0000\
404          0001",
405         2,
406         "4000\
407          0000\
408          4000\
409          0000",
410     );
411     check(
412         "1\
413          0001\
414          0001",
415         1,
416         "8000\
417          8000",
418     );
419 
420     check(
421         "2\
422          0000\
423          0000\
424          0000\
425          0001\
426          0000\
427          0000\
428          0000\
429          0001",
430         67,
431         "4000\
432          0000\
433          0000\
434          0000",
435     );
436     check(
437         "2\
438          0000\
439          0001\
440          0000\
441          0001",
442         35,
443         "4000\
444          0000",
445     );
446     check(
447         "2\
448          0001\
449          0001",
450         19,
451         "4000",
452     );
453 
454     check(
455         "1\
456          0000\
457          0000\
458          0000\
459          0000",
460         1,
461         "8000\
462          0000\
463          0000\
464          0000",
465     );
466     check(
467         "1\
468          0000\
469          0000",
470         1,
471         "8000\
472          0000",
473     );
474     check(
475         "1\
476          0000",
477         1,
478         "8000",
479     );
480     check(
481         "f\
482          edcb\
483          a987\
484          6543\
485          210f\
486          edcb\
487          a987\
488          6543\
489          2100",
490         4,
491         "fedc\
492          ba98\
493          7654\
494          3210\
495          fedc\
496          ba98\
497          7654\
498          3210",
499     );
500 
501     check(
502         "888877776666555544443333222211110000",
503         16,
504         "88887777666655554444333322221111",
505     );
506 }
507 
508 // `DoubleBigDigit` size dependent
509 #[test]
test_convert_i64()510 fn test_convert_i64() {
511     fn check(b1: BigUint, i: i64) {
512         let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
513         assert_eq!(b1, b2);
514         assert_eq!(b1.to_i64().unwrap(), i);
515     }
516 
517     check(Zero::zero(), 0);
518     check(One::one(), 1);
519     check(i64::MAX.to_biguint().unwrap(), i64::MAX);
520 
521     check(BigUint::new(vec![]), 0);
522     check(BigUint::new(vec![1]), 1);
523     check(BigUint::new(vec![N1]), (1 << 32) - 1);
524     check(BigUint::new(vec![0, 1]), 1 << 32);
525     check(BigUint::new(vec![N1, N1 >> 1]), i64::MAX);
526 
527     assert_eq!(i64::MIN.to_biguint(), None);
528     assert_eq!(BigUint::new(vec![N1, N1]).to_i64(), None);
529     assert_eq!(BigUint::new(vec![0, 0, 1]).to_i64(), None);
530     assert_eq!(BigUint::new(vec![N1, N1, N1]).to_i64(), None);
531 }
532 
533 #[test]
test_convert_i128()534 fn test_convert_i128() {
535     fn check(b1: BigUint, i: i128) {
536         let b2: BigUint = FromPrimitive::from_i128(i).unwrap();
537         assert_eq!(b1, b2);
538         assert_eq!(b1.to_i128().unwrap(), i);
539     }
540 
541     check(Zero::zero(), 0);
542     check(One::one(), 1);
543     check(i128::MAX.to_biguint().unwrap(), i128::MAX);
544 
545     check(BigUint::new(vec![]), 0);
546     check(BigUint::new(vec![1]), 1);
547     check(BigUint::new(vec![N1]), (1 << 32) - 1);
548     check(BigUint::new(vec![0, 1]), 1 << 32);
549     check(BigUint::new(vec![N1, N1, N1, N1 >> 1]), i128::MAX);
550 
551     assert_eq!(i128::MIN.to_biguint(), None);
552     assert_eq!(BigUint::new(vec![N1, N1, N1, N1]).to_i128(), None);
553     assert_eq!(BigUint::new(vec![0, 0, 0, 0, 1]).to_i128(), None);
554     assert_eq!(BigUint::new(vec![N1, N1, N1, N1, N1]).to_i128(), None);
555 }
556 
557 // `DoubleBigDigit` size dependent
558 #[test]
test_convert_u64()559 fn test_convert_u64() {
560     fn check(b1: BigUint, u: u64) {
561         let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
562         assert_eq!(b1, b2);
563         assert_eq!(b1.to_u64().unwrap(), u);
564     }
565 
566     check(Zero::zero(), 0);
567     check(One::one(), 1);
568     check(u64::MIN.to_biguint().unwrap(), u64::MIN);
569     check(u64::MAX.to_biguint().unwrap(), u64::MAX);
570 
571     check(BigUint::new(vec![]), 0);
572     check(BigUint::new(vec![1]), 1);
573     check(BigUint::new(vec![N1]), (1 << 32) - 1);
574     check(BigUint::new(vec![0, 1]), 1 << 32);
575     check(BigUint::new(vec![N1, N1]), u64::MAX);
576 
577     assert_eq!(BigUint::new(vec![0, 0, 1]).to_u64(), None);
578     assert_eq!(BigUint::new(vec![N1, N1, N1]).to_u64(), None);
579 }
580 
581 #[test]
test_convert_u128()582 fn test_convert_u128() {
583     fn check(b1: BigUint, u: u128) {
584         let b2: BigUint = FromPrimitive::from_u128(u).unwrap();
585         assert_eq!(b1, b2);
586         assert_eq!(b1.to_u128().unwrap(), u);
587     }
588 
589     check(Zero::zero(), 0);
590     check(One::one(), 1);
591     check(u128::MIN.to_biguint().unwrap(), u128::MIN);
592     check(u128::MAX.to_biguint().unwrap(), u128::MAX);
593 
594     check(BigUint::new(vec![]), 0);
595     check(BigUint::new(vec![1]), 1);
596     check(BigUint::new(vec![N1]), (1 << 32) - 1);
597     check(BigUint::new(vec![0, 1]), 1 << 32);
598     check(BigUint::new(vec![N1, N1, N1, N1]), u128::MAX);
599 
600     assert_eq!(BigUint::new(vec![0, 0, 0, 0, 1]).to_u128(), None);
601     assert_eq!(BigUint::new(vec![N1, N1, N1, N1, N1]).to_u128(), None);
602 }
603 
604 #[test]
605 #[allow(clippy::float_cmp)]
test_convert_f32()606 fn test_convert_f32() {
607     fn check(b1: &BigUint, f: f32) {
608         let b2 = BigUint::from_f32(f).unwrap();
609         assert_eq!(b1, &b2);
610         assert_eq!(b1.to_f32().unwrap(), f);
611     }
612 
613     check(&BigUint::zero(), 0.0);
614     check(&BigUint::one(), 1.0);
615     check(&BigUint::from(u16::MAX), pow(2.0_f32, 16) - 1.0);
616     check(&BigUint::from(1u64 << 32), pow(2.0_f32, 32));
617     check(&BigUint::from_slice(&[0, 0, 1]), pow(2.0_f32, 64));
618     check(
619         &((BigUint::one() << 100) + (BigUint::one() << 123)),
620         pow(2.0_f32, 100) + pow(2.0_f32, 123),
621     );
622     check(&(BigUint::one() << 127), pow(2.0_f32, 127));
623     check(&(BigUint::from((1u64 << 24) - 1) << (128 - 24)), f32::MAX);
624 
625     // keeping all 24 digits with the bits at different offsets to the BigDigits
626     let x: u32 = 0b00000000101111011111011011011101;
627     let mut f = x as f32;
628     let mut b = BigUint::from(x);
629     for _ in 0..64 {
630         check(&b, f);
631         f *= 2.0;
632         b <<= 1;
633     }
634 
635     // this number when rounded to f64 then f32 isn't the same as when rounded straight to f32
636     let n: u64 = 0b0000000000111111111111111111111111011111111111111111111111111111;
637     assert!((n as f64) as f32 != n as f32);
638     assert_eq!(BigUint::from(n).to_f32(), Some(n as f32));
639 
640     // test rounding up with the bits at different offsets to the BigDigits
641     let mut f = ((1u64 << 25) - 1) as f32;
642     let mut b = BigUint::from(1u64 << 25);
643     for _ in 0..64 {
644         assert_eq!(b.to_f32(), Some(f));
645         f *= 2.0;
646         b <<= 1;
647     }
648 
649     // rounding
650     assert_eq!(BigUint::from_f32(-1.0), None);
651     assert_eq!(BigUint::from_f32(-0.99999), Some(BigUint::zero()));
652     assert_eq!(BigUint::from_f32(-0.5), Some(BigUint::zero()));
653     assert_eq!(BigUint::from_f32(-0.0), Some(BigUint::zero()));
654     assert_eq!(
655         BigUint::from_f32(f32::MIN_POSITIVE / 2.0),
656         Some(BigUint::zero())
657     );
658     assert_eq!(BigUint::from_f32(f32::MIN_POSITIVE), Some(BigUint::zero()));
659     assert_eq!(BigUint::from_f32(0.5), Some(BigUint::zero()));
660     assert_eq!(BigUint::from_f32(0.99999), Some(BigUint::zero()));
661     assert_eq!(BigUint::from_f32(f32::consts::E), Some(BigUint::from(2u32)));
662     assert_eq!(
663         BigUint::from_f32(f32::consts::PI),
664         Some(BigUint::from(3u32))
665     );
666 
667     // special float values
668     assert_eq!(BigUint::from_f32(f32::NAN), None);
669     assert_eq!(BigUint::from_f32(f32::INFINITY), None);
670     assert_eq!(BigUint::from_f32(f32::NEG_INFINITY), None);
671     assert_eq!(BigUint::from_f32(f32::MIN), None);
672 
673     // largest BigUint that will round to a finite f32 value
674     let big_num = (BigUint::one() << 128u8) - 1u8 - (BigUint::one() << (128u8 - 25));
675     assert_eq!(big_num.to_f32(), Some(f32::MAX));
676     assert_eq!((big_num + 1u8).to_f32(), Some(f32::INFINITY));
677 
678     assert_eq!(
679         ((BigUint::one() << 128u8) - 1u8).to_f32(),
680         Some(f32::INFINITY)
681     );
682     assert_eq!((BigUint::one() << 128u8).to_f32(), Some(f32::INFINITY));
683 }
684 
685 #[test]
686 #[allow(clippy::float_cmp)]
test_convert_f64()687 fn test_convert_f64() {
688     fn check(b1: &BigUint, f: f64) {
689         let b2 = BigUint::from_f64(f).unwrap();
690         assert_eq!(b1, &b2);
691         assert_eq!(b1.to_f64().unwrap(), f);
692     }
693 
694     check(&BigUint::zero(), 0.0);
695     check(&BigUint::one(), 1.0);
696     check(&BigUint::from(u32::MAX), pow(2.0_f64, 32) - 1.0);
697     check(&BigUint::from(1u64 << 32), pow(2.0_f64, 32));
698     check(&BigUint::from_slice(&[0, 0, 1]), pow(2.0_f64, 64));
699     check(
700         &((BigUint::one() << 100) + (BigUint::one() << 152)),
701         pow(2.0_f64, 100) + pow(2.0_f64, 152),
702     );
703     check(&(BigUint::one() << 1023), pow(2.0_f64, 1023));
704     check(&(BigUint::from((1u64 << 53) - 1) << (1024 - 53)), f64::MAX);
705 
706     // keeping all 53 digits with the bits at different offsets to the BigDigits
707     let x: u64 = 0b0000000000011110111110110111111101110111101111011111011011011101;
708     let mut f = x as f64;
709     let mut b = BigUint::from(x);
710     for _ in 0..128 {
711         check(&b, f);
712         f *= 2.0;
713         b <<= 1;
714     }
715 
716     // test rounding up with the bits at different offsets to the BigDigits
717     let mut f = ((1u64 << 54) - 1) as f64;
718     let mut b = BigUint::from(1u64 << 54);
719     for _ in 0..128 {
720         assert_eq!(b.to_f64(), Some(f));
721         f *= 2.0;
722         b <<= 1;
723     }
724 
725     // rounding
726     assert_eq!(BigUint::from_f64(-1.0), None);
727     assert_eq!(BigUint::from_f64(-0.99999), Some(BigUint::zero()));
728     assert_eq!(BigUint::from_f64(-0.5), Some(BigUint::zero()));
729     assert_eq!(BigUint::from_f64(-0.0), Some(BigUint::zero()));
730     assert_eq!(
731         BigUint::from_f64(f64::MIN_POSITIVE / 2.0),
732         Some(BigUint::zero())
733     );
734     assert_eq!(BigUint::from_f64(f64::MIN_POSITIVE), Some(BigUint::zero()));
735     assert_eq!(BigUint::from_f64(0.5), Some(BigUint::zero()));
736     assert_eq!(BigUint::from_f64(0.99999), Some(BigUint::zero()));
737     assert_eq!(BigUint::from_f64(f64::consts::E), Some(BigUint::from(2u32)));
738     assert_eq!(
739         BigUint::from_f64(f64::consts::PI),
740         Some(BigUint::from(3u32))
741     );
742 
743     // special float values
744     assert_eq!(BigUint::from_f64(f64::NAN), None);
745     assert_eq!(BigUint::from_f64(f64::INFINITY), None);
746     assert_eq!(BigUint::from_f64(f64::NEG_INFINITY), None);
747     assert_eq!(BigUint::from_f64(f64::MIN), None);
748 
749     // largest BigUint that will round to a finite f64 value
750     let big_num = (BigUint::one() << 1024u16) - 1u8 - (BigUint::one() << (1024u16 - 54));
751     assert_eq!(big_num.to_f64(), Some(f64::MAX));
752     assert_eq!((big_num + 1u8).to_f64(), Some(f64::INFINITY));
753 
754     assert_eq!(
755         ((BigUint::one() << 1024u16) - 1u8).to_f64(),
756         Some(f64::INFINITY)
757     );
758     assert_eq!((BigUint::one() << 1024u16).to_f64(), Some(f64::INFINITY));
759 }
760 
761 #[test]
test_convert_to_bigint()762 fn test_convert_to_bigint() {
763     fn check(n: BigUint, ans: BigInt) {
764         assert_eq!(n.to_bigint().unwrap(), ans);
765         assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
766     }
767     check(Zero::zero(), Zero::zero());
768     check(
769         BigUint::new(vec![1, 2, 3]),
770         BigInt::from_biguint(Plus, BigUint::new(vec![1, 2, 3])),
771     );
772 }
773 
774 #[test]
test_convert_from_uint()775 fn test_convert_from_uint() {
776     macro_rules! check {
777         ($ty:ident, $max:expr) => {
778             assert_eq!(BigUint::from($ty::zero()), BigUint::zero());
779             assert_eq!(BigUint::from($ty::one()), BigUint::one());
780             assert_eq!(BigUint::from($ty::MAX - $ty::one()), $max - BigUint::one());
781             assert_eq!(BigUint::from($ty::MAX), $max);
782         };
783     }
784 
785     check!(u8, BigUint::from_slice(&[u8::MAX as u32]));
786     check!(u16, BigUint::from_slice(&[u16::MAX as u32]));
787     check!(u32, BigUint::from_slice(&[u32::MAX]));
788     check!(u64, BigUint::from_slice(&[u32::MAX, u32::MAX]));
789     check!(
790         u128,
791         BigUint::from_slice(&[u32::MAX, u32::MAX, u32::MAX, u32::MAX])
792     );
793     check!(usize, BigUint::from(usize::MAX as u64));
794 }
795 
796 #[test]
test_add()797 fn test_add() {
798     for elm in SUM_TRIPLES.iter() {
799         let (a_vec, b_vec, c_vec) = *elm;
800         let a = BigUint::from_slice(a_vec);
801         let b = BigUint::from_slice(b_vec);
802         let c = BigUint::from_slice(c_vec);
803 
804         assert_op!(a + b == c);
805         assert_op!(b + a == c);
806         assert_assign_op!(a += b == c);
807         assert_assign_op!(b += a == c);
808     }
809 }
810 
811 #[test]
test_sub()812 fn test_sub() {
813     for elm in SUM_TRIPLES.iter() {
814         let (a_vec, b_vec, c_vec) = *elm;
815         let a = BigUint::from_slice(a_vec);
816         let b = BigUint::from_slice(b_vec);
817         let c = BigUint::from_slice(c_vec);
818 
819         assert_op!(c - a == b);
820         assert_op!(c - b == a);
821         assert_assign_op!(c -= a == b);
822         assert_assign_op!(c -= b == a);
823     }
824 }
825 
826 #[test]
827 #[should_panic]
test_sub_fail_on_underflow()828 fn test_sub_fail_on_underflow() {
829     let (a, b): (BigUint, BigUint) = (Zero::zero(), One::one());
830     let _ = a - b;
831 }
832 
833 #[test]
test_mul()834 fn test_mul() {
835     for elm in MUL_TRIPLES.iter() {
836         let (a_vec, b_vec, c_vec) = *elm;
837         let a = BigUint::from_slice(a_vec);
838         let b = BigUint::from_slice(b_vec);
839         let c = BigUint::from_slice(c_vec);
840 
841         assert_op!(a * b == c);
842         assert_op!(b * a == c);
843         assert_assign_op!(a *= b == c);
844         assert_assign_op!(b *= a == c);
845     }
846 
847     for elm in DIV_REM_QUADRUPLES.iter() {
848         let (a_vec, b_vec, c_vec, d_vec) = *elm;
849         let a = BigUint::from_slice(a_vec);
850         let b = BigUint::from_slice(b_vec);
851         let c = BigUint::from_slice(c_vec);
852         let d = BigUint::from_slice(d_vec);
853 
854         assert!(a == &b * &c + &d);
855         assert!(a == &c * &b + &d);
856     }
857 }
858 
859 #[test]
test_div_rem()860 fn test_div_rem() {
861     for elm in MUL_TRIPLES.iter() {
862         let (a_vec, b_vec, c_vec) = *elm;
863         let a = BigUint::from_slice(a_vec);
864         let b = BigUint::from_slice(b_vec);
865         let c = BigUint::from_slice(c_vec);
866 
867         if !a.is_zero() {
868             assert_op!(c / a == b);
869             assert_op!(c % a == BigUint::zero());
870             assert_assign_op!(c /= a == b);
871             assert_assign_op!(c %= a == BigUint::zero());
872             assert_eq!(c.div_rem(&a), (b.clone(), BigUint::zero()));
873         }
874         if !b.is_zero() {
875             assert_op!(c / b == a);
876             assert_op!(c % b == BigUint::zero());
877             assert_assign_op!(c /= b == a);
878             assert_assign_op!(c %= b == BigUint::zero());
879             assert_eq!(c.div_rem(&b), (a.clone(), BigUint::zero()));
880         }
881     }
882 
883     for elm in DIV_REM_QUADRUPLES.iter() {
884         let (a_vec, b_vec, c_vec, d_vec) = *elm;
885         let a = BigUint::from_slice(a_vec);
886         let b = BigUint::from_slice(b_vec);
887         let c = BigUint::from_slice(c_vec);
888         let d = BigUint::from_slice(d_vec);
889 
890         if !b.is_zero() {
891             assert_op!(a / b == c);
892             assert_op!(a % b == d);
893             assert_assign_op!(a /= b == c);
894             assert_assign_op!(a %= b == d);
895             assert!(a.div_rem(&b) == (c, d));
896         }
897     }
898 }
899 
900 #[test]
test_div_rem_big_multiple()901 fn test_div_rem_big_multiple() {
902     let a = BigUint::from(3u32).pow(100u32);
903     let a2 = &a * &a;
904 
905     let (div, rem) = a2.div_rem(&a);
906     assert_eq!(div, a);
907     assert!(rem.is_zero());
908 
909     let (div, rem) = (&a2 - 1u32).div_rem(&a);
910     assert_eq!(div, &a - 1u32);
911     assert_eq!(rem, &a - 1u32);
912 }
913 
914 #[test]
test_div_ceil()915 fn test_div_ceil() {
916     fn check(a: &BigUint, b: &BigUint, d: &BigUint, m: &BigUint) {
917         if m.is_zero() {
918             assert_eq!(a.div_ceil(b), *d);
919         } else {
920             assert_eq!(a.div_ceil(b), d + 1u32);
921         }
922     }
923 
924     for elm in MUL_TRIPLES.iter() {
925         let (a_vec, b_vec, c_vec) = *elm;
926         let a = BigUint::from_slice(a_vec);
927         let b = BigUint::from_slice(b_vec);
928         let c = BigUint::from_slice(c_vec);
929 
930         if !a.is_zero() {
931             check(&c, &a, &b, &Zero::zero());
932         }
933         if !b.is_zero() {
934             check(&c, &b, &a, &Zero::zero());
935         }
936     }
937 
938     for elm in DIV_REM_QUADRUPLES.iter() {
939         let (a_vec, b_vec, c_vec, d_vec) = *elm;
940         let a = BigUint::from_slice(a_vec);
941         let b = BigUint::from_slice(b_vec);
942         let c = BigUint::from_slice(c_vec);
943         let d = BigUint::from_slice(d_vec);
944 
945         if !b.is_zero() {
946             check(&a, &b, &c, &d);
947         }
948     }
949 }
950 
951 #[test]
test_checked_add()952 fn test_checked_add() {
953     for elm in SUM_TRIPLES.iter() {
954         let (a_vec, b_vec, c_vec) = *elm;
955         let a = BigUint::from_slice(a_vec);
956         let b = BigUint::from_slice(b_vec);
957         let c = BigUint::from_slice(c_vec);
958 
959         assert!(a.checked_add(&b).unwrap() == c);
960         assert!(b.checked_add(&a).unwrap() == c);
961     }
962 }
963 
964 #[test]
test_checked_sub()965 fn test_checked_sub() {
966     for elm in SUM_TRIPLES.iter() {
967         let (a_vec, b_vec, c_vec) = *elm;
968         let a = BigUint::from_slice(a_vec);
969         let b = BigUint::from_slice(b_vec);
970         let c = BigUint::from_slice(c_vec);
971 
972         assert!(c.checked_sub(&a).unwrap() == b);
973         assert!(c.checked_sub(&b).unwrap() == a);
974 
975         if a > c {
976             assert!(a.checked_sub(&c).is_none());
977         }
978         if b > c {
979             assert!(b.checked_sub(&c).is_none());
980         }
981     }
982 }
983 
984 #[test]
test_checked_mul()985 fn test_checked_mul() {
986     for elm in MUL_TRIPLES.iter() {
987         let (a_vec, b_vec, c_vec) = *elm;
988         let a = BigUint::from_slice(a_vec);
989         let b = BigUint::from_slice(b_vec);
990         let c = BigUint::from_slice(c_vec);
991 
992         assert!(a.checked_mul(&b).unwrap() == c);
993         assert!(b.checked_mul(&a).unwrap() == c);
994     }
995 
996     for elm in DIV_REM_QUADRUPLES.iter() {
997         let (a_vec, b_vec, c_vec, d_vec) = *elm;
998         let a = BigUint::from_slice(a_vec);
999         let b = BigUint::from_slice(b_vec);
1000         let c = BigUint::from_slice(c_vec);
1001         let d = BigUint::from_slice(d_vec);
1002 
1003         assert!(a == b.checked_mul(&c).unwrap() + &d);
1004         assert!(a == c.checked_mul(&b).unwrap() + &d);
1005     }
1006 }
1007 
1008 #[test]
test_mul_overflow()1009 fn test_mul_overflow() {
1010     // Test for issue #187 - overflow due to mac3 incorrectly sizing temporary
1011     let s = "531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502232636710047537552105951370000796528760829212940754539968588340162273730474622005920097370111";
1012     let a: BigUint = s.parse().unwrap();
1013     let b = a.clone();
1014     let _ = a.checked_mul(&b);
1015 }
1016 
1017 #[test]
test_checked_div()1018 fn test_checked_div() {
1019     for elm in MUL_TRIPLES.iter() {
1020         let (a_vec, b_vec, c_vec) = *elm;
1021         let a = BigUint::from_slice(a_vec);
1022         let b = BigUint::from_slice(b_vec);
1023         let c = BigUint::from_slice(c_vec);
1024 
1025         if !a.is_zero() {
1026             assert!(c.checked_div(&a).unwrap() == b);
1027         }
1028         if !b.is_zero() {
1029             assert!(c.checked_div(&b).unwrap() == a);
1030         }
1031 
1032         assert!(c.checked_div(&Zero::zero()).is_none());
1033     }
1034 }
1035 
1036 #[test]
test_gcd()1037 fn test_gcd() {
1038     fn check(a: usize, b: usize, c: usize) {
1039         let big_a: BigUint = FromPrimitive::from_usize(a).unwrap();
1040         let big_b: BigUint = FromPrimitive::from_usize(b).unwrap();
1041         let big_c: BigUint = FromPrimitive::from_usize(c).unwrap();
1042 
1043         assert_eq!(big_a.gcd(&big_b), big_c);
1044         assert_eq!(big_a.gcd_lcm(&big_b).0, big_c);
1045     }
1046 
1047     check(10, 2, 2);
1048     check(10, 3, 1);
1049     check(0, 3, 3);
1050     check(3, 3, 3);
1051     check(56, 42, 14);
1052 }
1053 
1054 #[test]
test_lcm()1055 fn test_lcm() {
1056     fn check(a: usize, b: usize, c: usize) {
1057         let big_a: BigUint = FromPrimitive::from_usize(a).unwrap();
1058         let big_b: BigUint = FromPrimitive::from_usize(b).unwrap();
1059         let big_c: BigUint = FromPrimitive::from_usize(c).unwrap();
1060 
1061         assert_eq!(big_a.lcm(&big_b), big_c);
1062         assert_eq!(big_a.gcd_lcm(&big_b).1, big_c);
1063     }
1064 
1065     check(0, 0, 0);
1066     check(1, 0, 0);
1067     check(0, 1, 0);
1068     check(1, 1, 1);
1069     check(8, 9, 72);
1070     check(11, 5, 55);
1071     check(99, 17, 1683);
1072 }
1073 
1074 #[test]
test_next_multiple_of()1075 fn test_next_multiple_of() {
1076     assert_eq!(
1077         BigUint::from(16u32).next_multiple_of(&BigUint::from(8u32)),
1078         BigUint::from(16u32)
1079     );
1080     assert_eq!(
1081         BigUint::from(23u32).next_multiple_of(&BigUint::from(8u32)),
1082         BigUint::from(24u32)
1083     );
1084 }
1085 
1086 #[test]
test_prev_multiple_of()1087 fn test_prev_multiple_of() {
1088     assert_eq!(
1089         BigUint::from(16u32).prev_multiple_of(&BigUint::from(8u32)),
1090         BigUint::from(16u32)
1091     );
1092     assert_eq!(
1093         BigUint::from(23u32).prev_multiple_of(&BigUint::from(8u32)),
1094         BigUint::from(16u32)
1095     );
1096 }
1097 
1098 #[test]
test_is_even()1099 fn test_is_even() {
1100     let one: BigUint = FromStr::from_str("1").unwrap();
1101     let two: BigUint = FromStr::from_str("2").unwrap();
1102     let thousand: BigUint = FromStr::from_str("1000").unwrap();
1103     let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
1104     let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
1105     assert!(one.is_odd());
1106     assert!(two.is_even());
1107     assert!(thousand.is_even());
1108     assert!(big.is_even());
1109     assert!(bigger.is_odd());
1110     assert!((&one << 64u8).is_even());
1111     assert!(((&one << 64u8) + one).is_odd());
1112 }
1113 
to_str_pairs() -> Vec<(BigUint, Vec<(u32, String)>)>1114 fn to_str_pairs() -> Vec<(BigUint, Vec<(u32, String)>)> {
1115     let bits = 32;
1116     vec![
1117         (
1118             Zero::zero(),
1119             vec![(2, "0".to_string()), (3, "0".to_string())],
1120         ),
1121         (
1122             BigUint::from_slice(&[0xff]),
1123             vec![
1124                 (2, "11111111".to_string()),
1125                 (3, "100110".to_string()),
1126                 (4, "3333".to_string()),
1127                 (5, "2010".to_string()),
1128                 (6, "1103".to_string()),
1129                 (7, "513".to_string()),
1130                 (8, "377".to_string()),
1131                 (9, "313".to_string()),
1132                 (10, "255".to_string()),
1133                 (11, "212".to_string()),
1134                 (12, "193".to_string()),
1135                 (13, "168".to_string()),
1136                 (14, "143".to_string()),
1137                 (15, "120".to_string()),
1138                 (16, "ff".to_string()),
1139             ],
1140         ),
1141         (
1142             BigUint::from_slice(&[0xfff]),
1143             vec![
1144                 (2, "111111111111".to_string()),
1145                 (4, "333333".to_string()),
1146                 (16, "fff".to_string()),
1147             ],
1148         ),
1149         (
1150             BigUint::from_slice(&[1, 2]),
1151             vec![
1152                 (
1153                     2,
1154                     format!("10{}1", repeat("0").take(bits - 1).collect::<String>()),
1155                 ),
1156                 (
1157                     4,
1158                     format!("2{}1", repeat("0").take(bits / 2 - 1).collect::<String>()),
1159                 ),
1160                 (
1161                     10,
1162                     match bits {
1163                         64 => "36893488147419103233".to_string(),
1164                         32 => "8589934593".to_string(),
1165                         16 => "131073".to_string(),
1166                         _ => panic!(),
1167                     },
1168                 ),
1169                 (
1170                     16,
1171                     format!("2{}1", repeat("0").take(bits / 4 - 1).collect::<String>()),
1172                 ),
1173             ],
1174         ),
1175         (
1176             BigUint::from_slice(&[1, 2, 3]),
1177             vec![
1178                 (
1179                     2,
1180                     format!(
1181                         "11{}10{}1",
1182                         repeat("0").take(bits - 2).collect::<String>(),
1183                         repeat("0").take(bits - 1).collect::<String>()
1184                     ),
1185                 ),
1186                 (
1187                     4,
1188                     format!(
1189                         "3{}2{}1",
1190                         repeat("0").take(bits / 2 - 1).collect::<String>(),
1191                         repeat("0").take(bits / 2 - 1).collect::<String>()
1192                     ),
1193                 ),
1194                 (
1195                     8,
1196                     match bits {
1197                         64 => "14000000000000000000004000000000000000000001".to_string(),
1198                         32 => "6000000000100000000001".to_string(),
1199                         16 => "140000400001".to_string(),
1200                         _ => panic!(),
1201                     },
1202                 ),
1203                 (
1204                     10,
1205                     match bits {
1206                         64 => "1020847100762815390427017310442723737601".to_string(),
1207                         32 => "55340232229718589441".to_string(),
1208                         16 => "12885032961".to_string(),
1209                         _ => panic!(),
1210                     },
1211                 ),
1212                 (
1213                     16,
1214                     format!(
1215                         "3{}2{}1",
1216                         repeat("0").take(bits / 4 - 1).collect::<String>(),
1217                         repeat("0").take(bits / 4 - 1).collect::<String>()
1218                     ),
1219                 ),
1220             ],
1221         ),
1222     ]
1223 }
1224 
1225 #[test]
test_to_str_radix()1226 fn test_to_str_radix() {
1227     let r = to_str_pairs();
1228     for num_pair in r.iter() {
1229         let &(ref n, ref rs) = num_pair;
1230         for str_pair in rs.iter() {
1231             let &(ref radix, ref str) = str_pair;
1232             assert_eq!(n.to_str_radix(*radix), *str);
1233         }
1234     }
1235 }
1236 
1237 #[test]
test_from_and_to_radix()1238 fn test_from_and_to_radix() {
1239     const GROUND_TRUTH: &[(&[u8], u32, &[u8])] = &[
1240         (b"0", 42, &[0]),
1241         (
1242             b"ffffeeffbb",
1243             2,
1244             &[
1245                 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
1246                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1247             ],
1248         ),
1249         (
1250             b"ffffeeffbb",
1251             3,
1252             &[
1253                 2, 2, 1, 1, 2, 1, 1, 2, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 1,
1254             ],
1255         ),
1256         (
1257             b"ffffeeffbb",
1258             4,
1259             &[3, 2, 3, 2, 3, 3, 3, 3, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3],
1260         ),
1261         (
1262             b"ffffeeffbb",
1263             5,
1264             &[0, 4, 3, 3, 1, 4, 2, 4, 1, 4, 4, 2, 3, 0, 0, 1, 2, 1],
1265         ),
1266         (
1267             b"ffffeeffbb",
1268             6,
1269             &[5, 5, 4, 5, 5, 0, 0, 1, 2, 5, 3, 0, 1, 0, 2, 2],
1270         ),
1271         (
1272             b"ffffeeffbb",
1273             7,
1274             &[4, 2, 3, 6, 0, 1, 6, 1, 6, 2, 0, 3, 2, 4, 1],
1275         ),
1276         (
1277             b"ffffeeffbb",
1278             8,
1279             &[3, 7, 6, 7, 7, 5, 3, 7, 7, 7, 7, 7, 7, 1],
1280         ),
1281         (b"ffffeeffbb", 9, &[8, 4, 5, 7, 0, 0, 3, 2, 0, 3, 0, 8, 3]),
1282         (b"ffffeeffbb", 10, &[5, 9, 5, 3, 1, 5, 0, 1, 5, 9, 9, 0, 1]),
1283         (b"ffffeeffbb", 11, &[10, 7, 6, 5, 2, 0, 3, 3, 3, 4, 9, 3]),
1284         (b"ffffeeffbb", 12, &[11, 8, 5, 10, 1, 10, 3, 1, 1, 9, 5, 1]),
1285         (b"ffffeeffbb", 13, &[0, 5, 7, 4, 6, 5, 6, 11, 8, 12, 7]),
1286         (b"ffffeeffbb", 14, &[11, 4, 4, 11, 8, 4, 6, 0, 3, 11, 3]),
1287         (b"ffffeeffbb", 15, &[5, 11, 13, 2, 1, 10, 2, 0, 9, 13, 1]),
1288         (b"ffffeeffbb", 16, &[11, 11, 15, 15, 14, 14, 15, 15, 15, 15]),
1289         (b"ffffeeffbb", 17, &[0, 2, 14, 12, 2, 14, 8, 10, 4, 9]),
1290         (b"ffffeeffbb", 18, &[17, 15, 5, 13, 10, 16, 16, 13, 9, 5]),
1291         (b"ffffeeffbb", 19, &[14, 13, 2, 8, 9, 0, 1, 14, 7, 3]),
1292         (b"ffffeeffbb", 20, &[15, 19, 3, 14, 0, 17, 19, 18, 2, 2]),
1293         (b"ffffeeffbb", 21, &[11, 5, 4, 13, 5, 18, 9, 1, 8, 1]),
1294         (b"ffffeeffbb", 22, &[21, 3, 7, 21, 15, 12, 17, 0, 20]),
1295         (b"ffffeeffbb", 23, &[21, 21, 6, 9, 10, 7, 21, 0, 14]),
1296         (b"ffffeeffbb", 24, &[11, 10, 19, 14, 22, 11, 17, 23, 9]),
1297         (b"ffffeeffbb", 25, &[20, 18, 21, 22, 21, 14, 3, 5, 7]),
1298         (b"ffffeeffbb", 26, &[13, 15, 24, 11, 17, 6, 23, 6, 5]),
1299         (b"ffffeeffbb", 27, &[17, 16, 7, 0, 21, 0, 3, 24, 3]),
1300         (b"ffffeeffbb", 28, &[11, 16, 11, 15, 14, 18, 13, 25, 2]),
1301         (b"ffffeeffbb", 29, &[6, 8, 7, 19, 14, 13, 21, 5, 2]),
1302         (b"ffffeeffbb", 30, &[5, 13, 18, 11, 10, 7, 8, 20, 1]),
1303         (b"ffffeeffbb", 31, &[22, 26, 15, 19, 8, 27, 29, 8, 1]),
1304         (b"ffffeeffbb", 32, &[27, 29, 31, 29, 30, 31, 31, 31]),
1305         (b"ffffeeffbb", 33, &[32, 20, 27, 12, 1, 12, 26, 25]),
1306         (b"ffffeeffbb", 34, &[17, 9, 16, 33, 13, 25, 31, 20]),
1307         (b"ffffeeffbb", 35, &[25, 32, 2, 25, 11, 4, 3, 17]),
1308         (b"ffffeeffbb", 36, &[35, 34, 5, 6, 32, 3, 1, 14]),
1309         (b"ffffeeffbb", 37, &[16, 21, 18, 4, 33, 19, 21, 11]),
1310         (b"ffffeeffbb", 38, &[33, 25, 19, 29, 20, 6, 23, 9]),
1311         (b"ffffeeffbb", 39, &[26, 27, 29, 23, 16, 18, 0, 8]),
1312         (b"ffffeeffbb", 40, &[35, 39, 30, 11, 16, 17, 28, 6]),
1313         (b"ffffeeffbb", 41, &[36, 30, 9, 18, 12, 19, 26, 5]),
1314         (b"ffffeeffbb", 42, &[11, 34, 37, 27, 1, 13, 32, 4]),
1315         (b"ffffeeffbb", 43, &[3, 24, 11, 2, 10, 40, 1, 4]),
1316         (b"ffffeeffbb", 44, &[43, 12, 40, 32, 3, 23, 19, 3]),
1317         (b"ffffeeffbb", 45, &[35, 38, 44, 18, 22, 18, 42, 2]),
1318         (b"ffffeeffbb", 46, &[21, 45, 18, 41, 17, 2, 24, 2]),
1319         (b"ffffeeffbb", 47, &[37, 37, 11, 12, 6, 0, 8, 2]),
1320         (b"ffffeeffbb", 48, &[11, 41, 40, 43, 5, 43, 41, 1]),
1321         (b"ffffeeffbb", 49, &[18, 45, 7, 13, 20, 21, 30, 1]),
1322         (b"ffffeeffbb", 50, &[45, 21, 5, 34, 21, 18, 20, 1]),
1323         (b"ffffeeffbb", 51, &[17, 6, 26, 22, 38, 24, 11, 1]),
1324         (b"ffffeeffbb", 52, &[39, 33, 38, 30, 46, 31, 3, 1]),
1325         (b"ffffeeffbb", 53, &[31, 7, 44, 23, 9, 32, 49]),
1326         (b"ffffeeffbb", 54, &[17, 35, 8, 37, 31, 18, 44]),
1327         (b"ffffeeffbb", 55, &[10, 52, 9, 48, 36, 39, 39]),
1328         (b"ffffeeffbb", 56, &[11, 50, 51, 22, 25, 36, 35]),
1329         (b"ffffeeffbb", 57, &[14, 55, 12, 43, 20, 3, 32]),
1330         (b"ffffeeffbb", 58, &[35, 18, 45, 56, 9, 51, 28]),
1331         (b"ffffeeffbb", 59, &[51, 28, 20, 26, 55, 3, 26]),
1332         (b"ffffeeffbb", 60, &[35, 6, 27, 46, 58, 33, 23]),
1333         (b"ffffeeffbb", 61, &[58, 7, 6, 54, 49, 20, 21]),
1334         (b"ffffeeffbb", 62, &[53, 59, 3, 14, 10, 22, 19]),
1335         (b"ffffeeffbb", 63, &[53, 50, 23, 4, 56, 36, 17]),
1336         (b"ffffeeffbb", 64, &[59, 62, 47, 59, 63, 63, 15]),
1337         (b"ffffeeffbb", 65, &[0, 53, 39, 4, 40, 37, 14]),
1338         (b"ffffeeffbb", 66, &[65, 59, 39, 1, 64, 19, 13]),
1339         (b"ffffeeffbb", 67, &[35, 14, 19, 16, 25, 10, 12]),
1340         (b"ffffeeffbb", 68, &[51, 38, 63, 50, 15, 8, 11]),
1341         (b"ffffeeffbb", 69, &[44, 45, 18, 58, 68, 12, 10]),
1342         (b"ffffeeffbb", 70, &[25, 51, 0, 60, 13, 24, 9]),
1343         (b"ffffeeffbb", 71, &[54, 30, 9, 65, 28, 41, 8]),
1344         (b"ffffeeffbb", 72, &[35, 35, 55, 54, 17, 64, 7]),
1345         (b"ffffeeffbb", 73, &[34, 4, 48, 40, 27, 19, 7]),
1346         (b"ffffeeffbb", 74, &[53, 47, 4, 56, 36, 51, 6]),
1347         (b"ffffeeffbb", 75, &[20, 56, 10, 72, 24, 13, 6]),
1348         (b"ffffeeffbb", 76, &[71, 31, 52, 60, 48, 53, 5]),
1349         (b"ffffeeffbb", 77, &[32, 73, 14, 63, 15, 21, 5]),
1350         (b"ffffeeffbb", 78, &[65, 13, 17, 32, 64, 68, 4]),
1351         (b"ffffeeffbb", 79, &[37, 56, 2, 56, 25, 41, 4]),
1352         (b"ffffeeffbb", 80, &[75, 59, 37, 41, 43, 15, 4]),
1353         (b"ffffeeffbb", 81, &[44, 68, 0, 21, 27, 72, 3]),
1354         (b"ffffeeffbb", 82, &[77, 35, 2, 74, 46, 50, 3]),
1355         (b"ffffeeffbb", 83, &[52, 51, 19, 76, 10, 30, 3]),
1356         (b"ffffeeffbb", 84, &[11, 80, 19, 19, 76, 10, 3]),
1357         (b"ffffeeffbb", 85, &[0, 82, 20, 14, 68, 77, 2]),
1358         (b"ffffeeffbb", 86, &[3, 12, 78, 37, 62, 61, 2]),
1359         (b"ffffeeffbb", 87, &[35, 12, 20, 8, 52, 46, 2]),
1360         (b"ffffeeffbb", 88, &[43, 6, 54, 42, 30, 32, 2]),
1361         (b"ffffeeffbb", 89, &[49, 52, 85, 21, 80, 18, 2]),
1362         (b"ffffeeffbb", 90, &[35, 64, 78, 24, 18, 6, 2]),
1363         (b"ffffeeffbb", 91, &[39, 17, 83, 63, 17, 85, 1]),
1364         (b"ffffeeffbb", 92, &[67, 22, 85, 79, 75, 74, 1]),
1365         (b"ffffeeffbb", 93, &[53, 60, 39, 29, 4, 65, 1]),
1366         (b"ffffeeffbb", 94, &[37, 89, 2, 72, 76, 55, 1]),
1367         (b"ffffeeffbb", 95, &[90, 74, 89, 9, 9, 47, 1]),
1368         (b"ffffeeffbb", 96, &[59, 20, 46, 35, 81, 38, 1]),
1369         (b"ffffeeffbb", 97, &[94, 87, 60, 71, 3, 31, 1]),
1370         (b"ffffeeffbb", 98, &[67, 22, 63, 50, 62, 23, 1]),
1371         (b"ffffeeffbb", 99, &[98, 6, 69, 12, 61, 16, 1]),
1372         (b"ffffeeffbb", 100, &[95, 35, 51, 10, 95, 9, 1]),
1373         (b"ffffeeffbb", 101, &[87, 27, 7, 8, 62, 3, 1]),
1374         (b"ffffeeffbb", 102, &[17, 3, 32, 79, 59, 99]),
1375         (b"ffffeeffbb", 103, &[30, 22, 90, 0, 87, 94]),
1376         (b"ffffeeffbb", 104, &[91, 68, 87, 68, 38, 90]),
1377         (b"ffffeeffbb", 105, &[95, 80, 54, 73, 15, 86]),
1378         (b"ffffeeffbb", 106, &[31, 30, 24, 16, 17, 82]),
1379         (b"ffffeeffbb", 107, &[51, 50, 10, 12, 42, 78]),
1380         (b"ffffeeffbb", 108, &[71, 71, 96, 78, 89, 74]),
1381         (b"ffffeeffbb", 109, &[33, 18, 93, 22, 50, 71]),
1382         (b"ffffeeffbb", 110, &[65, 53, 57, 88, 29, 68]),
1383         (b"ffffeeffbb", 111, &[53, 93, 67, 90, 27, 65]),
1384         (b"ffffeeffbb", 112, &[11, 109, 96, 65, 43, 62]),
1385         (b"ffffeeffbb", 113, &[27, 23, 106, 56, 76, 59]),
1386         (b"ffffeeffbb", 114, &[71, 84, 31, 112, 11, 57]),
1387         (b"ffffeeffbb", 115, &[90, 22, 1, 56, 76, 54]),
1388         (b"ffffeeffbb", 116, &[35, 38, 98, 57, 40, 52]),
1389         (b"ffffeeffbb", 117, &[26, 113, 115, 62, 17, 50]),
1390         (b"ffffeeffbb", 118, &[51, 14, 5, 18, 7, 48]),
1391         (b"ffffeeffbb", 119, &[102, 31, 110, 108, 8, 46]),
1392         (b"ffffeeffbb", 120, &[35, 93, 96, 50, 22, 44]),
1393         (b"ffffeeffbb", 121, &[87, 61, 2, 36, 47, 42]),
1394         (b"ffffeeffbb", 122, &[119, 64, 1, 22, 83, 40]),
1395         (b"ffffeeffbb", 123, &[77, 119, 32, 90, 6, 39]),
1396         (b"ffffeeffbb", 124, &[115, 122, 31, 79, 62, 37]),
1397         (b"ffffeeffbb", 125, &[95, 108, 47, 74, 3, 36]),
1398         (b"ffffeeffbb", 126, &[53, 25, 116, 39, 78, 34]),
1399         (b"ffffeeffbb", 127, &[22, 23, 125, 67, 35, 33]),
1400         (b"ffffeeffbb", 128, &[59, 127, 59, 127, 127, 31]),
1401         (b"ffffeeffbb", 129, &[89, 36, 1, 59, 100, 30]),
1402         (b"ffffeeffbb", 130, &[65, 91, 123, 89, 79, 29]),
1403         (b"ffffeeffbb", 131, &[58, 72, 39, 63, 65, 28]),
1404         (b"ffffeeffbb", 132, &[131, 62, 92, 82, 57, 27]),
1405         (b"ffffeeffbb", 133, &[109, 31, 51, 123, 55, 26]),
1406         (b"ffffeeffbb", 134, &[35, 74, 21, 27, 60, 25]),
1407         (b"ffffeeffbb", 135, &[125, 132, 49, 37, 70, 24]),
1408         (b"ffffeeffbb", 136, &[51, 121, 117, 133, 85, 23]),
1409         (b"ffffeeffbb", 137, &[113, 60, 135, 22, 107, 22]),
1410         (b"ffffeeffbb", 138, &[113, 91, 73, 93, 133, 21]),
1411         (b"ffffeeffbb", 139, &[114, 75, 102, 51, 26, 21]),
1412         (b"ffffeeffbb", 140, &[95, 25, 35, 16, 62, 20]),
1413         (b"ffffeeffbb", 141, &[131, 137, 16, 110, 102, 19]),
1414         (b"ffffeeffbb", 142, &[125, 121, 108, 34, 6, 19]),
1415         (b"ffffeeffbb", 143, &[65, 78, 138, 55, 55, 18]),
1416         (b"ffffeeffbb", 144, &[107, 125, 121, 15, 109, 17]),
1417         (b"ffffeeffbb", 145, &[35, 13, 122, 42, 22, 17]),
1418         (b"ffffeeffbb", 146, &[107, 38, 103, 123, 83, 16]),
1419         (b"ffffeeffbb", 147, &[116, 96, 71, 98, 2, 16]),
1420         (b"ffffeeffbb", 148, &[127, 23, 75, 99, 71, 15]),
1421         (b"ffffeeffbb", 149, &[136, 110, 53, 114, 144, 14]),
1422         (b"ffffeeffbb", 150, &[95, 140, 133, 130, 71, 14]),
1423         (b"ffffeeffbb", 151, &[15, 50, 29, 137, 0, 14]),
1424         (b"ffffeeffbb", 152, &[147, 15, 89, 121, 83, 13]),
1425         (b"ffffeeffbb", 153, &[17, 87, 93, 72, 17, 13]),
1426         (b"ffffeeffbb", 154, &[109, 113, 3, 133, 106, 12]),
1427         (b"ffffeeffbb", 155, &[115, 141, 120, 139, 44, 12]),
1428         (b"ffffeeffbb", 156, &[143, 45, 4, 82, 140, 11]),
1429         (b"ffffeeffbb", 157, &[149, 92, 15, 106, 82, 11]),
1430         (b"ffffeeffbb", 158, &[37, 107, 79, 46, 26, 11]),
1431         (b"ffffeeffbb", 159, &[137, 37, 146, 51, 130, 10]),
1432         (b"ffffeeffbb", 160, &[155, 69, 29, 115, 77, 10]),
1433         (b"ffffeeffbb", 161, &[67, 98, 46, 68, 26, 10]),
1434         (b"ffffeeffbb", 162, &[125, 155, 60, 63, 138, 9]),
1435         (b"ffffeeffbb", 163, &[96, 43, 118, 93, 90, 9]),
1436         (b"ffffeeffbb", 164, &[159, 99, 123, 152, 43, 9]),
1437         (b"ffffeeffbb", 165, &[65, 17, 1, 69, 163, 8]),
1438         (b"ffffeeffbb", 166, &[135, 108, 25, 165, 119, 8]),
1439         (b"ffffeeffbb", 167, &[165, 116, 164, 103, 77, 8]),
1440         (b"ffffeeffbb", 168, &[11, 166, 67, 44, 36, 8]),
1441         (b"ffffeeffbb", 169, &[65, 59, 71, 149, 164, 7]),
1442         (b"ffffeeffbb", 170, &[85, 83, 26, 76, 126, 7]),
1443         (b"ffffeeffbb", 171, &[71, 132, 140, 157, 88, 7]),
1444         (b"ffffeeffbb", 172, &[3, 6, 127, 47, 52, 7]),
1445         (b"ffffeeffbb", 173, &[122, 66, 53, 83, 16, 7]),
1446         (b"ffffeeffbb", 174, &[35, 6, 5, 88, 155, 6]),
1447         (b"ffffeeffbb", 175, &[95, 20, 84, 56, 122, 6]),
1448         (b"ffffeeffbb", 176, &[43, 91, 57, 159, 89, 6]),
1449         (b"ffffeeffbb", 177, &[110, 127, 54, 40, 58, 6]),
1450         (b"ffffeeffbb", 178, &[49, 115, 43, 47, 27, 6]),
1451         (b"ffffeeffbb", 179, &[130, 91, 4, 178, 175, 5]),
1452         (b"ffffeeffbb", 180, &[35, 122, 109, 70, 147, 5]),
1453         (b"ffffeeffbb", 181, &[94, 94, 4, 79, 119, 5]),
1454         (b"ffffeeffbb", 182, &[39, 54, 66, 19, 92, 5]),
1455         (b"ffffeeffbb", 183, &[119, 2, 143, 69, 65, 5]),
1456         (b"ffffeeffbb", 184, &[67, 57, 90, 44, 39, 5]),
1457         (b"ffffeeffbb", 185, &[90, 63, 141, 123, 13, 5]),
1458         (b"ffffeeffbb", 186, &[53, 123, 172, 119, 174, 4]),
1459         (b"ffffeeffbb", 187, &[153, 21, 68, 28, 151, 4]),
1460         (b"ffffeeffbb", 188, &[131, 138, 94, 32, 128, 4]),
1461         (b"ffffeeffbb", 189, &[179, 121, 156, 130, 105, 4]),
1462         (b"ffffeeffbb", 190, &[185, 179, 164, 131, 83, 4]),
1463         (b"ffffeeffbb", 191, &[118, 123, 37, 31, 62, 4]),
1464         (b"ffffeeffbb", 192, &[59, 106, 83, 16, 41, 4]),
1465         (b"ffffeeffbb", 193, &[57, 37, 47, 86, 20, 4]),
1466         (b"ffffeeffbb", 194, &[191, 140, 63, 45, 0, 4]),
1467         (b"ffffeeffbb", 195, &[65, 169, 83, 84, 175, 3]),
1468         (b"ffffeeffbb", 196, &[67, 158, 64, 6, 157, 3]),
1469         (b"ffffeeffbb", 197, &[121, 26, 167, 3, 139, 3]),
1470         (b"ffffeeffbb", 198, &[197, 151, 165, 75, 121, 3]),
1471         (b"ffffeeffbb", 199, &[55, 175, 36, 22, 104, 3]),
1472         (b"ffffeeffbb", 200, &[195, 167, 162, 38, 87, 3]),
1473         (b"ffffeeffbb", 201, &[35, 27, 136, 124, 70, 3]),
1474         (b"ffffeeffbb", 202, &[87, 64, 153, 76, 54, 3]),
1475         (b"ffffeeffbb", 203, &[151, 191, 14, 94, 38, 3]),
1476         (b"ffffeeffbb", 204, &[119, 103, 135, 175, 22, 3]),
1477         (b"ffffeeffbb", 205, &[200, 79, 123, 115, 7, 3]),
1478         (b"ffffeeffbb", 206, &[133, 165, 202, 115, 198, 2]),
1479         (b"ffffeeffbb", 207, &[44, 153, 193, 175, 184, 2]),
1480         (b"ffffeeffbb", 208, &[91, 190, 125, 86, 171, 2]),
1481         (b"ffffeeffbb", 209, &[109, 151, 34, 53, 158, 2]),
1482         (b"ffffeeffbb", 210, &[95, 40, 171, 74, 145, 2]),
1483         (b"ffffeeffbb", 211, &[84, 195, 162, 150, 132, 2]),
1484         (b"ffffeeffbb", 212, &[31, 15, 59, 68, 120, 2]),
1485         (b"ffffeeffbb", 213, &[125, 57, 127, 36, 108, 2]),
1486         (b"ffffeeffbb", 214, &[51, 132, 2, 55, 96, 2]),
1487         (b"ffffeeffbb", 215, &[175, 133, 177, 122, 84, 2]),
1488         (b"ffffeeffbb", 216, &[179, 35, 78, 23, 73, 2]),
1489         (b"ffffeeffbb", 217, &[53, 101, 208, 186, 61, 2]),
1490         (b"ffffeeffbb", 218, &[33, 9, 214, 179, 50, 2]),
1491         (b"ffffeeffbb", 219, &[107, 147, 175, 217, 39, 2]),
1492         (b"ffffeeffbb", 220, &[175, 81, 179, 79, 29, 2]),
1493         (b"ffffeeffbb", 221, &[0, 76, 95, 204, 18, 2]),
1494         (b"ffffeeffbb", 222, &[53, 213, 16, 150, 8, 2]),
1495         (b"ffffeeffbb", 223, &[158, 161, 42, 136, 221, 1]),
1496         (b"ffffeeffbb", 224, &[123, 54, 52, 162, 212, 1]),
1497         (b"ffffeeffbb", 225, &[170, 43, 151, 2, 204, 1]),
1498         (b"ffffeeffbb", 226, &[27, 68, 224, 105, 195, 1]),
1499         (b"ffffeeffbb", 227, &[45, 69, 157, 20, 187, 1]),
1500         (b"ffffeeffbb", 228, &[71, 213, 64, 199, 178, 1]),
1501         (b"ffffeeffbb", 229, &[129, 203, 66, 186, 170, 1]),
1502         (b"ffffeeffbb", 230, &[205, 183, 57, 208, 162, 1]),
1503         (b"ffffeeffbb", 231, &[32, 50, 164, 33, 155, 1]),
1504         (b"ffffeeffbb", 232, &[35, 135, 53, 123, 147, 1]),
1505         (b"ffffeeffbb", 233, &[209, 47, 89, 13, 140, 1]),
1506         (b"ffffeeffbb", 234, &[143, 56, 175, 168, 132, 1]),
1507         (b"ffffeeffbb", 235, &[225, 157, 216, 121, 125, 1]),
1508         (b"ffffeeffbb", 236, &[51, 66, 119, 105, 118, 1]),
1509         (b"ffffeeffbb", 237, &[116, 150, 26, 119, 111, 1]),
1510         (b"ffffeeffbb", 238, &[221, 15, 87, 162, 104, 1]),
1511         (b"ffffeeffbb", 239, &[234, 155, 214, 234, 97, 1]),
1512         (b"ffffeeffbb", 240, &[155, 46, 84, 96, 91, 1]),
1513         (b"ffffeeffbb", 241, &[187, 48, 90, 225, 84, 1]),
1514         (b"ffffeeffbb", 242, &[87, 212, 151, 140, 78, 1]),
1515         (b"ffffeeffbb", 243, &[206, 22, 189, 81, 72, 1]),
1516         (b"ffffeeffbb", 244, &[119, 93, 122, 48, 66, 1]),
1517         (b"ffffeeffbb", 245, &[165, 224, 117, 40, 60, 1]),
1518         (b"ffffeeffbb", 246, &[77, 121, 100, 57, 54, 1]),
1519         (b"ffffeeffbb", 247, &[52, 128, 242, 98, 48, 1]),
1520         (b"ffffeeffbb", 248, &[115, 247, 224, 164, 42, 1]),
1521         (b"ffffeeffbb", 249, &[218, 127, 223, 5, 37, 1]),
1522         (b"ffffeeffbb", 250, &[95, 54, 168, 118, 31, 1]),
1523         (b"ffffeeffbb", 251, &[121, 204, 240, 3, 26, 1]),
1524         (b"ffffeeffbb", 252, &[179, 138, 123, 162, 20, 1]),
1525         (b"ffffeeffbb", 253, &[21, 50, 1, 91, 15, 1]),
1526         (b"ffffeeffbb", 254, &[149, 11, 63, 40, 10, 1]),
1527         (b"ffffeeffbb", 255, &[170, 225, 247, 9, 5, 1]),
1528         (b"ffffeeffbb", 256, &[187, 255, 238, 255, 255]),
1529     ];
1530 
1531     for &(bigint, radix, inbaseradix_le) in GROUND_TRUTH.iter() {
1532         let bigint = BigUint::parse_bytes(bigint, 16).unwrap();
1533         // to_radix_le
1534         assert_eq!(bigint.to_radix_le(radix), inbaseradix_le);
1535         // to_radix_be
1536         let mut inbase_be = bigint.to_radix_be(radix);
1537         inbase_be.reverse(); // now le
1538         assert_eq!(inbase_be, inbaseradix_le);
1539         // from_radix_le
1540         assert_eq!(
1541             BigUint::from_radix_le(inbaseradix_le, radix).unwrap(),
1542             bigint
1543         );
1544         // from_radix_be
1545         let mut inbaseradix_be = Vec::from(inbaseradix_le);
1546         inbaseradix_be.reverse();
1547         assert_eq!(
1548             BigUint::from_radix_be(&inbaseradix_be, radix).unwrap(),
1549             bigint
1550         );
1551     }
1552 
1553     assert!(BigUint::from_radix_le(&[10, 100, 10], 50).is_none());
1554     assert_eq!(BigUint::from_radix_le(&[], 2), Some(BigUint::zero()));
1555     assert_eq!(BigUint::from_radix_be(&[], 2), Some(BigUint::zero()));
1556 }
1557 
1558 #[test]
test_from_str_radix()1559 fn test_from_str_radix() {
1560     let r = to_str_pairs();
1561     for num_pair in r.iter() {
1562         let &(ref n, ref rs) = num_pair;
1563         for str_pair in rs.iter() {
1564             let &(ref radix, ref str) = str_pair;
1565             assert_eq!(n, &BigUint::from_str_radix(str, *radix).unwrap());
1566         }
1567     }
1568 
1569     let zed = BigUint::from_str_radix("Z", 10).ok();
1570     assert_eq!(zed, None);
1571     let blank = BigUint::from_str_radix("_", 2).ok();
1572     assert_eq!(blank, None);
1573     let blank_one = BigUint::from_str_radix("_1", 2).ok();
1574     assert_eq!(blank_one, None);
1575     let plus_one = BigUint::from_str_radix("+1", 10).ok();
1576     assert_eq!(plus_one, Some(BigUint::from_slice(&[1])));
1577     let plus_plus_one = BigUint::from_str_radix("++1", 10).ok();
1578     assert_eq!(plus_plus_one, None);
1579     let minus_one = BigUint::from_str_radix("-1", 10).ok();
1580     assert_eq!(minus_one, None);
1581     let zero_plus_two = BigUint::from_str_radix("0+2", 10).ok();
1582     assert_eq!(zero_plus_two, None);
1583     let three = BigUint::from_str_radix("1_1", 2).ok();
1584     assert_eq!(three, Some(BigUint::from_slice(&[3])));
1585     let ff = BigUint::from_str_radix("1111_1111", 2).ok();
1586     assert_eq!(ff, Some(BigUint::from_slice(&[0xff])));
1587 }
1588 
1589 #[test]
test_all_str_radix()1590 fn test_all_str_radix() {
1591     let n = BigUint::new((0..10).collect());
1592     for radix in 2..37 {
1593         let s = n.to_str_radix(radix);
1594         let x = BigUint::from_str_radix(&s, radix);
1595         assert_eq!(x.unwrap(), n);
1596 
1597         let s = s.to_ascii_uppercase();
1598         let x = BigUint::from_str_radix(&s, radix);
1599         assert_eq!(x.unwrap(), n);
1600     }
1601 }
1602 
1603 #[test]
test_big_str()1604 fn test_big_str() {
1605     for n in 2..=20_u32 {
1606         let x: BigUint = BigUint::from(n).pow(10_000_u32);
1607         let s = x.to_string();
1608         let y: BigUint = s.parse().unwrap();
1609         assert_eq!(x, y);
1610     }
1611 }
1612 
1613 #[test]
test_lower_hex()1614 fn test_lower_hex() {
1615     let a = BigUint::parse_bytes(b"A", 16).unwrap();
1616     let hello = BigUint::parse_bytes(b"22405534230753963835153736737", 10).unwrap();
1617 
1618     assert_eq!(format!("{:x}", a), "a");
1619     assert_eq!(format!("{:x}", hello), "48656c6c6f20776f726c6421");
1620     assert_eq!(format!("{:♥>+#8x}", a), "♥♥♥♥+0xa");
1621 }
1622 
1623 #[test]
test_upper_hex()1624 fn test_upper_hex() {
1625     let a = BigUint::parse_bytes(b"A", 16).unwrap();
1626     let hello = BigUint::parse_bytes(b"22405534230753963835153736737", 10).unwrap();
1627 
1628     assert_eq!(format!("{:X}", a), "A");
1629     assert_eq!(format!("{:X}", hello), "48656C6C6F20776F726C6421");
1630     assert_eq!(format!("{:♥>+#8X}", a), "♥♥♥♥+0xA");
1631 }
1632 
1633 #[test]
test_binary()1634 fn test_binary() {
1635     let a = BigUint::parse_bytes(b"A", 16).unwrap();
1636     let hello = BigUint::parse_bytes(b"224055342307539", 10).unwrap();
1637 
1638     assert_eq!(format!("{:b}", a), "1010");
1639     assert_eq!(
1640         format!("{:b}", hello),
1641         "110010111100011011110011000101101001100011010011"
1642     );
1643     assert_eq!(format!("{:♥>+#8b}", a), "♥+0b1010");
1644 }
1645 
1646 #[test]
test_octal()1647 fn test_octal() {
1648     let a = BigUint::parse_bytes(b"A", 16).unwrap();
1649     let hello = BigUint::parse_bytes(b"22405534230753963835153736737", 10).unwrap();
1650 
1651     assert_eq!(format!("{:o}", a), "12");
1652     assert_eq!(format!("{:o}", hello), "22062554330674403566756233062041");
1653     assert_eq!(format!("{:♥>+#8o}", a), "♥♥♥+0o12");
1654 }
1655 
1656 #[test]
test_display()1657 fn test_display() {
1658     let a = BigUint::parse_bytes(b"A", 16).unwrap();
1659     let hello = BigUint::parse_bytes(b"22405534230753963835153736737", 10).unwrap();
1660 
1661     assert_eq!(format!("{}", a), "10");
1662     assert_eq!(format!("{}", hello), "22405534230753963835153736737");
1663     assert_eq!(format!("{:♥>+#8}", a), "♥♥♥♥♥+10");
1664 }
1665 
1666 #[test]
test_factor()1667 fn test_factor() {
1668     fn factor(n: usize) -> BigUint {
1669         let mut f: BigUint = One::one();
1670         for i in 2..=n {
1671             // FIXME(#5992): assignment operator overloads
1672             // f *= FromPrimitive::from_usize(i);
1673             let bu: BigUint = FromPrimitive::from_usize(i).unwrap();
1674             f *= bu;
1675         }
1676         f
1677     }
1678 
1679     fn check(n: usize, s: &str) {
1680         let n = factor(n);
1681         let ans = BigUint::from_str_radix(s, 10).unwrap();
1682         assert_eq!(n, ans);
1683     }
1684 
1685     check(3, "6");
1686     check(10, "3628800");
1687     check(20, "2432902008176640000");
1688     check(30, "265252859812191058636308480000000");
1689 }
1690 
1691 #[test]
test_bits()1692 fn test_bits() {
1693     assert_eq!(BigUint::new(vec![0, 0, 0, 0]).bits(), 0);
1694     let n: BigUint = FromPrimitive::from_usize(0).unwrap();
1695     assert_eq!(n.bits(), 0);
1696     let n: BigUint = FromPrimitive::from_usize(1).unwrap();
1697     assert_eq!(n.bits(), 1);
1698     let n: BigUint = FromPrimitive::from_usize(3).unwrap();
1699     assert_eq!(n.bits(), 2);
1700     let n: BigUint = BigUint::from_str_radix("4000000000", 16).unwrap();
1701     assert_eq!(n.bits(), 39);
1702     let one: BigUint = One::one();
1703     assert_eq!((one << 426u16).bits(), 427);
1704 }
1705 
1706 #[test]
test_iter_sum()1707 fn test_iter_sum() {
1708     let result: BigUint = FromPrimitive::from_isize(1234567).unwrap();
1709     let data: Vec<BigUint> = vec![
1710         FromPrimitive::from_u32(1000000).unwrap(),
1711         FromPrimitive::from_u32(200000).unwrap(),
1712         FromPrimitive::from_u32(30000).unwrap(),
1713         FromPrimitive::from_u32(4000).unwrap(),
1714         FromPrimitive::from_u32(500).unwrap(),
1715         FromPrimitive::from_u32(60).unwrap(),
1716         FromPrimitive::from_u32(7).unwrap(),
1717     ];
1718 
1719     assert_eq!(result, data.iter().sum::<BigUint>());
1720     assert_eq!(result, data.into_iter().sum::<BigUint>());
1721 }
1722 
1723 #[test]
test_iter_product()1724 fn test_iter_product() {
1725     let data: Vec<BigUint> = vec![
1726         FromPrimitive::from_u32(1001).unwrap(),
1727         FromPrimitive::from_u32(1002).unwrap(),
1728         FromPrimitive::from_u32(1003).unwrap(),
1729         FromPrimitive::from_u32(1004).unwrap(),
1730         FromPrimitive::from_u32(1005).unwrap(),
1731     ];
1732     let result = data.get(0).unwrap()
1733         * data.get(1).unwrap()
1734         * data.get(2).unwrap()
1735         * data.get(3).unwrap()
1736         * data.get(4).unwrap();
1737 
1738     assert_eq!(result, data.iter().product::<BigUint>());
1739     assert_eq!(result, data.into_iter().product::<BigUint>());
1740 }
1741 
1742 #[test]
test_iter_sum_generic()1743 fn test_iter_sum_generic() {
1744     let result: BigUint = FromPrimitive::from_isize(1234567).unwrap();
1745     let data = vec![1000000_u32, 200000, 30000, 4000, 500, 60, 7];
1746 
1747     assert_eq!(result, data.iter().sum::<BigUint>());
1748     assert_eq!(result, data.into_iter().sum::<BigUint>());
1749 }
1750 
1751 #[test]
test_iter_product_generic()1752 fn test_iter_product_generic() {
1753     let data = vec![1001_u32, 1002, 1003, 1004, 1005];
1754     let result = data[0].to_biguint().unwrap()
1755         * data[1].to_biguint().unwrap()
1756         * data[2].to_biguint().unwrap()
1757         * data[3].to_biguint().unwrap()
1758         * data[4].to_biguint().unwrap();
1759 
1760     assert_eq!(result, data.iter().product::<BigUint>());
1761     assert_eq!(result, data.into_iter().product::<BigUint>());
1762 }
1763 
1764 #[test]
test_pow()1765 fn test_pow() {
1766     let one = BigUint::from(1u32);
1767     let two = BigUint::from(2u32);
1768     let four = BigUint::from(4u32);
1769     let eight = BigUint::from(8u32);
1770     let tentwentyfour = BigUint::from(1024u32);
1771     let twentyfourtyeight = BigUint::from(2048u32);
1772     macro_rules! check {
1773         ($t:ty) => {
1774             assert_eq!(Pow::pow(&two, 0 as $t), one);
1775             assert_eq!(Pow::pow(&two, 1 as $t), two);
1776             assert_eq!(Pow::pow(&two, 2 as $t), four);
1777             assert_eq!(Pow::pow(&two, 3 as $t), eight);
1778             assert_eq!(Pow::pow(&two, 10 as $t), tentwentyfour);
1779             assert_eq!(Pow::pow(&two, 11 as $t), twentyfourtyeight);
1780             assert_eq!(Pow::pow(&two, &(11 as $t)), twentyfourtyeight);
1781         };
1782     }
1783     check!(u8);
1784     check!(u16);
1785     check!(u32);
1786     check!(u64);
1787     check!(u128);
1788     check!(usize);
1789 
1790     let pow_1e10000 = BigUint::from(10u32).pow(10_000_u32);
1791     let manual_1e10000 = repeat(10u32).take(10_000).product::<BigUint>();
1792     assert!(manual_1e10000 == pow_1e10000);
1793 }
1794 
1795 #[test]
test_trailing_zeros()1796 fn test_trailing_zeros() {
1797     assert!(BigUint::from(0u8).trailing_zeros().is_none());
1798     assert_eq!(BigUint::from(1u8).trailing_zeros().unwrap(), 0);
1799     assert_eq!(BigUint::from(2u8).trailing_zeros().unwrap(), 1);
1800     let x: BigUint = BigUint::one() << 128;
1801     assert_eq!(x.trailing_zeros().unwrap(), 128);
1802 }
1803 
1804 #[test]
test_trailing_ones()1805 fn test_trailing_ones() {
1806     assert_eq!(BigUint::from(0u8).trailing_ones(), 0);
1807     assert_eq!(BigUint::from(1u8).trailing_ones(), 1);
1808     assert_eq!(BigUint::from(2u8).trailing_ones(), 0);
1809     assert_eq!(BigUint::from(3u8).trailing_ones(), 2);
1810     let x: BigUint = (BigUint::from(3u8) << 128) | BigUint::from(3u8);
1811     assert_eq!(x.trailing_ones(), 2);
1812     let x: BigUint = (BigUint::one() << 128) - BigUint::one();
1813     assert_eq!(x.trailing_ones(), 128);
1814 }
1815 
1816 #[test]
test_count_ones()1817 fn test_count_ones() {
1818     assert_eq!(BigUint::from(0u8).count_ones(), 0);
1819     assert_eq!(BigUint::from(1u8).count_ones(), 1);
1820     assert_eq!(BigUint::from(2u8).count_ones(), 1);
1821     assert_eq!(BigUint::from(3u8).count_ones(), 2);
1822     let x: BigUint = (BigUint::from(3u8) << 128) | BigUint::from(3u8);
1823     assert_eq!(x.count_ones(), 4);
1824 }
1825 
1826 #[test]
test_bit()1827 fn test_bit() {
1828     assert!(!BigUint::from(0u8).bit(0));
1829     assert!(!BigUint::from(0u8).bit(100));
1830     assert!(!BigUint::from(42u8).bit(4));
1831     assert!(BigUint::from(42u8).bit(5));
1832     let x: BigUint = (BigUint::from(3u8) << 128) | BigUint::from(3u8);
1833     assert!(x.bit(129));
1834     assert!(!x.bit(130));
1835 }
1836 
1837 #[test]
test_set_bit()1838 fn test_set_bit() {
1839     let mut x = BigUint::from(3u8);
1840     x.set_bit(128, true);
1841     x.set_bit(129, true);
1842     assert_eq!(x, (BigUint::from(3u8) << 128) | BigUint::from(3u8));
1843     x.set_bit(0, false);
1844     x.set_bit(128, false);
1845     x.set_bit(130, false);
1846     assert_eq!(x, (BigUint::from(2u8) << 128) | BigUint::from(2u8));
1847     x.set_bit(129, false);
1848     x.set_bit(1, false);
1849     assert_eq!(x, BigUint::zero());
1850 }
1851