num-bigint

chore: Release num-bigint version 0.5.1

• Fixed a regression in the B-Z division algorithm.

Contributors: @cuviper

chore: Release num-bigint version 0.5.0

• Upgrade to rand v0.10 and/or v0.9, and split rand_core.
  • The former rand feature is now split into multiple features, rand_0_9, rand_core_0_9, rand_0_10, and rand_core_0_10, depending on the version and feature set you need.
  • The RandBigInt extension trait is now split into BigRng09 and BigRng010 for each version.
  • The gen_* methods are deprecated in favor of new random_* methods.
  • This is also a value-breaking release, as rand defines it.

Contributors: @bionicles, @cuviper, @divergentdave

chore: Release num-bigint version 0.4.8

• Fixed a regression in the B-Z division algorithm.

Contributors: @cuviper

chore: Release num-bigint version 0.4.7

• Inline single-digit values. This reduces heap allocations, and also enables const ONE, const NEG_ONE, and const fn new_const.
• Use divide and conquer in to_radix_digits, also implementing the Burnikel-Ziegler algorithm to speed up large divisions in general.
• Implement LowerBounded for BigUint.

Contributors: @cp289, @cuviper, @hkalbasi, @mikem8891, @pRizz, @tyilo, @xtqqczze

chore: Release num-bigint version 0.4.6

• Fixed compilation on x86_64-unknown-linux-gnux32.

Contributors: @cuviper, @ralphtandetzky, @yhx-12243

chore: Release num-bigint version 0.4.5

• Upgrade to 2021 edition, MSRV 1.60
• Add const ZERO and implement num_traits::ConstZero
• Add modinv methods for the modular inverse
• Optimize multiplication with imbalanced operands
• Optimize scalar division on x86 and x86-64

Contributors: @cuviper, @joelonsql, @waywardmonkeys

• Implemented From<bool> for BigInt and BigUint.
• Implemented num_traits::Euclid and CheckedEuclid for BigInt and BigUint.
• Implemented ties-to-even for BigInt and BigUint::to_f32 and to_f64.
• Implemented num_traits::FromBytes and ToBytes for BigInt and BigUint.
• Limited pre-allocation from serde size hints against potential OOM.
• Miscellaneous other code cleanups and maintenance tasks.

Contributors: @AaronKutch, @archseer, @cuviper, @dramforever, @icecream17, @icedrocket, @janmarthedal, @jaybosamiya, @OliveIsAWord, @PatrickNorton, @smoelius, @waywardmonkeys

• GHSA-v935-pqmr-g8v9: Fix unexpected panics in multiplication.

Contributors: @arvidn, @cuviper, @guidovranken

• Use explicit Integer::div_ceil to avoid the new unstable method.

Contributors: @catenacyber, @cuviper

• Fixed scalar divide-by-zero panics.
• Implemented DoubleEndedIterator for U32Digits and U64Digits.
• Optimized multiplication to avoid unnecessary allocations.
• Optimized string formatting for very large values.

Contributors: @cuviper, @PatrickNorton

Breaking Changes

• Updated public dependences on arbitrary, quickcheck, and rand:
  • arbitrary support has been updated to 1.0, requiring Rust 1.40.
  • quickcheck support has been updated to 1.0, requiring Rust 1.46.
  • rand support has been updated to 0.8, requiring Rust 1.36.
• Debug now shows plain numeric values for BigInt and BigUint, rather than the raw list of internal digits.

Contributors: @cuviper, @Gelbpunkt

• [Use explicit Integer::div_ceil to avoid the new unstable method.][219]

Contributors: @catenacyber, @cuviper

• The new BigUint methods count_ones and trailing_ones return the number of 1 bits in the entire value or just its least-significant tail, respectively.
• The new BigInt and BigUint methods bit and set_bit will read and write individual bits of the value. For negative BigInt, bits are determined as if they were in the two's complement representation.
• The from_radix_le and from_radix_be methods now accept empty buffers to represent zero.
• BigInt and BigUint can now iterate digits as u32 or u64, regardless of the actual internal digit size.

Contributors: @BartMassey, @cuviper, @janmarthedal, @sebastianv89, @Speedy37

• Addition and subtraction now uses intrinsics for performance on x86 and x86_64 when built with Rust 1.33 or later.
• Conversions to_f32 and to_f64 now return infinity for very large numbers, rather than None. This does preserve the sign too, so a large negative BigInt will convert to negative infinity.
• The optional arbitrary feature implements arbitrary::Arbitrary, distinct from quickcheck::Arbitrary.
• The division algorithm has been optimized to reduce the number of temporary allocations and improve the internal guesses at each step.
• BigInt and BigUint will opportunistically shrink capacity if the internal vector is much larger than needed.

Contributors: @cuviper, @e00E, @ejmahler, @notoria, @tczajka

Enhancements

• The internal BigDigit may now be either u32 or u64, although that implementation detail is not exposed in the API. For now, this is chosen to match the target pointer size, but may change in the future.
• No-std is now supported with the alloc crate on Rust 1.36.
• Pow is now implemented for bigint values, not just references.
• TryFrom is now implemented on Rust 1.34 and later, converting signed integers to unsigned, and narrowing big integers to primitives.
• Shl and Shr are now implemented for a variety of shift types.
• A new trailing_zeros() returns the number of consecutive zeros from the least significant bit.
• The new BigInt::magnitude and into_parts methods give access to its BigUint part as the magnitude.

Breaking Changes

• num-bigint now requires Rust 1.31 or greater.
  • The "i128" opt-in feature was removed, now always available.
• Updated public dependences:
  • rand support has been updated to 0.7, requiring Rust 1.32.
  • quickcheck support has been updated to 0.9, requiring Rust 1.34.
• Removed impl Neg for BigUint, which only ever panicked.
• Bit counts are now u64 instead of usize.

Contributors: @cuviper, @dignifiedquire, @hansihe, @kpcyrd, @milesand, @tech6hutch

• Fix the promotion of negative isize in BigInt assign-ops.

Contributors: @cuviper, @HactarCE

• Updated the autocfg build dependency to 1.0.

Contributors: @cuviper, @tspiteri

• The new BigUint::to_u32_digits method returns the number as a little-endian vector of base-2³² digits. The same method on BigInt also returns the sign.
• BigUint::modpow now applies a modulus even for exponent 1, which also affects BigInt::modpow.
• BigInt::modpow now returns the correct sign for negative bases with even exponents.

Contributors: @alex-ozdemir, @cuviper, @dingelish, @Speedy37, @youknowone

• Pow is now implemented for BigUint exponents.
• The optional quickcheck feature enables implementations of Arbitrary.
• See the full comparison for performance enhancements and more!

Contributors: @cuviper, @lcnr, @maxbla, @mikelodder7, @mikong, @TheLetterTheta, @tspiteri, @XAMPPRocky, @youknowone

• The Roots implementations now use better initial guesses.
• Fixed to_signed_bytes_* for some positive numbers, where the most-significant byte is 0x80 and the rest are 0.

Contributors: @cuviper, @leodasvacas

• RandBigInt now uses Rng::fill_bytes to improve performance, instead of repeated gen::<u32> calls. The also affects the implementations of the other rand traits. This may potentially change the values produced by some seeded RNGs on previous versions, but the values were tested to be stable with ChaChaRng, IsaacRng, and XorShiftRng.
• BigInt and BigUint now implement num_integer::Roots.
• BigInt and BigUint now implement num_traits::Pow.
• BigInt and BigUint now implement operators with 128-bit integers.

Contributors: @cuviper, @dignifiedquire, @mancabizjak, @Robbepop, @TheIronBorn, @thomwiggers

Enhancements

• BigInt and BigUint now implement Product and Sum for iterators of any item that we can Mul and Add, respectively. For example, a factorial can now be simply: let f: BigUint = (1u32..1000).product();
• BigInt now supports two's-complement logic operations, namely BitAnd, BitOr, BitXor, and Not. These act conceptually as if each number had an infinite prefix of 0 or 1 bits for positive or negative.
• BigInt now supports assignment operators like AddAssign.
• BigInt and BigUint now support conversions with i128 and u128, if sufficient compiler support is detected.
• BigInt and BigUint now implement rand's SampleUniform trait, and a custom RandomBits distribution samples by bit size.
• The release also includes other miscellaneous improvements to performance.

Breaking Changes

• num-bigint now requires rustc 1.15 or greater.
• The crate now has a std feature, and won't build without it. This is in preparation for someday supporting #![no_std] with alloc.
• The serde dependency has been updated to 1.0, still disabled by default. The rustc-serialize crate is no longer supported by num-bigint.
• The rand dependency has been updated to 0.5, now disabled by default. This requires rustc 1.22 or greater for rand's own requirement.
• Shr for BigInt now rounds down rather than toward zero, matching the behavior of the primitive integers for negative values.
• ParseBigIntError is now an opaque type.
• The big_digit module is no longer public, nor are the BigDigit and DoubleBigDigit types and ZERO_BIG_DIGIT constant that were re-exported in the crate root. Public APIs which deal in digits, like BigUint::from_slice, will now always be base-u32.

Contributors: @clarcharr, @cuviper, @dodomorandi, @tiehuis, @tspiteri

• Division with single-digit divisors is now much faster.
• The README now compares ramp, rug, rust-gmp, and apint.

Contributors: @cuviper, @Robbepop

• The new BigInt::modpow performs signed modular exponentiation, using the existing BigUint::modpow and rounding negatives similar to mod_floor.

Contributors: @cuviper

• num-bigint now has its own source repository at rust-num/num-bigint.
• lcm now avoids creating a large intermediate product.
• gcd now uses Stein's algorithm with faster shifts instead of division.
• rand support is now extended to 0.4 (while still allowing 0.3).

Contributors: @cuviper, @Emerentius, @ignatenkobrain, @mhogrefe