BigInt

• Overview
• API Documentation
• License
• Requirements and Integration
• Implementation Notes
  • Why is there no generic BigInt<Digit> type?
• Calculation Samples
  • Obligatory factorial demo
  • RSA Cryptography
  • Calculating the Digits of π

<!-- [](https://codecov.io/github/attaswift/BigInt?branch=master) -->

<a name="overview">Overview</a>

This repository provides integer types of arbitrary width implemented in 100% pure Swift. The underlying representation is in base 2^64, using Array<UInt64>.

This module is handy when you need an integer type that's wider than UIntMax, but you don't want to add The GNU Multiple Precision Arithmetic Library as a dependency.

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, along with other special-case variants.
  • Division uses Knuth's Algorithm D, with its 3/2 digits wide quotient approximation. It will trap when the divisor is zero.
  • BigUInt.divide returns the quotient and remainder at once; this is faster than calculating them separately.

• Bitwise operators: ~, |, &, ^, |=, &=, ^=, plus the following read-only properties:

  • bitWidth: 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: >>, <<, >>=, <<=

• Methods to convert NSData to big integers and vice versa.

• Support for generating random integers of specified maximum width or magnitude.

• Radix conversion to/from 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).

• [base.power(exponent, modulus)][powmod]: Modular exponentiation (right-to-left binary method). [Vanilla exponentiation][power] is also available.

• [n.inverse(modulus)][inverse]: Multiplicative inverse in modulo arithmetic (extended Euclidean algorithm).

• [n.isPrime()][prime]: Miller–Rabin primality test.

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. Sadly this does not imply that there are no bugs in it.

<a name="api">API Documentation</a>

Generated API docs are available at https://attaswift.github.io/BigInt/.

<a name="license">License</a>

BigInt can be used, distributed and modified under the MIT license.

<a name="integration">Requirements and Integration</a>

BigInt 4.0.0 requires Swift 4.2 (The last version with support for Swift 3.x was BigInt 2.1.0. The last version with support for Swift 2 was BigInt 1.3.0.)

| Swift Version | last BigInt Version| | ------------- |:-------------------| | 3.x | 2.1.0 | | 4.0 | 3.1.0 | | 4.2 | 4.0.0 | | 5.x | 5.4.0 |

BigInt deploys to macOS 10.10, iOS 9, watchOS 2 and tvOS 9. It has been tested on the latest OS releases only---however, as the module uses very few platform-provided APIs, there should be very few issues with earlier versions.

BigInt uses no APIs specific to Apple platforms, so it should be easy to port it to other operating systems.

Setup instructions:

• Swift Package Manager: Although the Package Manager is still in its infancy, BigInt provides experimental support for it. Add this to the dependency section of your Package.swift manifest:

  .package(url: "https://github.com/attaswift/BigInt.git", from: "5.4.0")
  

<a name="notes">Implementation notes</a>

BigUInt is a MutableCollectionType of its 64-bit digits, with the least significant digit at index 0. As a convenience, BigUInt allows you to subscript it with indexes at or above its count. [The subscript operator][subscript] returns 0 for out-of-bound gets and automatically extends the array on out-of-bound sets. This makes memory management simpler.

BigInt is just a tiny wrapper around a BigUInt [absolute value][magnitude] and a [sign bit][negative], both of which are accessible as public read-write properties.

<a name="generics">Why is there no generic BigInt<Digit> type?</a>

The types provided by BigInt are not parametric—this is very much intentional, as Swift generics cost us dearly at runtime in this use case. In every approach I tried, making arbitrary-precision arithmetic operations work with a generic Digit type parameter resulted in code that was literally ten times slower. If you can make the algorithms generic without such a huge performance hit, please enlighten me!

This is an area that I plan to investigate more, as it would be useful to have generic implementations for arbitrary-width arithmetic operations. (Polynomial division and decimal bases are two examples.) The library already implements double-digit multiplication and division as extension methods on a protocol with an associated type requirement; this has not measurably affected performance. Unfortunately, the same is not true for BigUInt's methods.

Of course, as a last resort, we could just duplicate the code to create a separate generic variant that was slower but more flexible.

[powmo