1.2.2

This release fixes version numbers embedded in build products.

1.2.1

This release simply removes the stray LICENSE.md file from iOS builds.

1.2.0: Integrations

With this release, BigInt supports watchOS and tvOS in addition to OS X and iOS. Deployment targets are as follows:

• OS X 10.9
• iOS 8
• watchOS 2
• tvOS 9

BigInt 1.2.0 also features support for both Carthage and CocoaPods deployments.

1.1.0: Fleshing things out

BigInt now contains enough functionality to pretend it's a respectable big integer lib. Some of the new additions since 1.0.0:

• Conversion to/from NSData
• Vanilla exponentiation
• Algorithm to find the multiplicative inverse of an integer in modulo arithmetic
• An implementation of the Miller-Rabin primality test
• Support for generating random big integers
• Better support for playgrounds in Xcode
• Documentation for all public API
• Fun new calculation samples

1.0.0: First Release

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,
  • trailingZeroes: the number of trailing zero bits in the binary representation,
  • leadingZeroes: 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 2^50 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.