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