« Changelog History


BigInt v1.0.0 Release Notes

Release Date: 2016-01-04 // over 8 years ago

  • 🚀 This is the first release of the BigInt module, providing arbitrary precision integer arithmetic operations in pure Swift.

    Two big integer types are included: BigUInt and BigInt, the latter being the signed variant. Both of these are Swift structs with copy-on-write value semantics, and they can be used much like any other integer type.

    The library provides implementations for some of the most frequently useful functions on big integers, including

    • All functionality from Comparable and Hashable
    • The full set of arithmetic operators: +, -, *, /, %, +=, -=, *=, /=, %=
    • ➕ Addition and subtraction have variants that allow for shifting the digits of the second operand on the fly.
    • Unsigned subtraction will trap when the result would be negative. (There are variants that return an overflow flag.)
    • Multiplication uses brute force for numbers up to 1024 digits, then switches to Karatsuba's recursive method. 👀 (This limit is configurable, see BigUInt.directMultiplicationLimit.) A fused multiply-add method is also available.
    • Division uses Knuth's Algorithm D, with its 3/2 digits wide quotient approximation. It will trap when the divisor is zero. BigUInt.divmod returns the quotient and remainder at once; this is faster than calculating them separately.
    • Bitwise operators: ~, |, &, ^, |=, &=, ^=, plus the following read-only properties:
    • width: the minimum number of bits required to store the integer,
    • trailingZeroBitCount: the number of trailing zero bits in the binary representation,
    • leadingZeroBitCount: the number of leading zero bits (when the last digit isn't full),
    • Shift operators: >>, <<, >>=, <<=
    • Left shifts need to allocate memory to extend the digit array, so it's probably not a good idea to left shift a BigUInt by 250 bits.
    • Radix conversion between Strings and big integers up to base 36 (using repeated divisions).
    • Big integers use this to implement StringLiteralConvertible (in base 10).
    • sqrt(n): The square root of an integer (using Newton's method)
    • ✅ BigUInt.gcd(n, m): The greatest common divisor of two integers (Stein's algorithm)
    • BigUInt.powmod(base, exponent, modulus): Modular exponentiation (right-to-left binary method):

    The implementations are intended to be reasonably efficient, but they are unlikely to be competitive with GMP at all, even when I happened to implement an algorithm with same asymptotic behavior as GMP. (I haven't performed a comparison benchmark, though.)

    ✅ The library has 100% unit test coverage.