Debian Codegraph @

.cargo/vendor/num-bigint/tests/bigint.rs

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