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
andBigInt
, 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
andHashable
- 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
String
s 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.
- All functionality from