| 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 |
} |