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