Swiftpack.co - Package - attaswift/BigInt


Swift 3 License Platform

Build Status Code Coverage Carthage compatible Version


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

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.

API Documentation

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


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

Requirements and Integration

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.0 | 5.0.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 except for arc4random_buf in BigUInt Random.swift, 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.0.0")
  • CocoaPods: Put this in your Podfile:

    pod 'BigInt', '~> 5.0'
  • Carthage: Put this in your Cartfile:

    github "attaswift/BigInt" ~> 5.0

Implementation notes

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 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 and a sign bit, both of which are accessible as public read-write properties.

Why is there no generic BigInt<Digit> type?

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.

Calculation Samples

Obligatory Factorial Demo

It is easy to use BigInt to calculate the factorial function for any integer:

import BigInt

func factorial(_ n: Int) -> BigInt {
    return (1 ... n).map { BigInt($0) }.reduce(BigInt(1), *)

==> 362880

==> 93326215443944152681699238856266700490715968264381621468592963895217599993229915

==> 40238726007709377354370243392300398571937486421071463254379991042993851239862902

Well, I guess that's all right, but it's not very interesting. Let's try something more useful.

RSA Cryptography

The BigInt module provides all necessary parts to implement an (overly) simple RSA cryptography system.

Let's start with a simple function that generates a random n-bit prime. The module includes a function to generate random integers of a specific size, and also an isPrime method that performs the Miller–Rabin primality test. These are all we need:

func generatePrime(_ width: Int) -> BigUInt {
    while true {
        var random = BigUInt.randomInteger(withExactWidth: width)
        random |= BigUInt(1)
        if random.isPrime() {
            return random

let p = generatePrime(1024)
==> 13308187650642192396256419911012544845370493728424936791561478318443071617242872

let q = generatePrime(1024)
==> 17072954422657145489547308812333368925007949054501204983863958355897172093173783

Cool! Now that we have two large primes, we can produce an RSA public/private keypair out of them.

typealias Key = (modulus: BigUInt, exponent: BigUInt)

let n = p * q
==> 22721008120758282530010953362926306641542233757318103044313144976976529789946696

let e: BigUInt = 65537
let phi = (p - 1) * (q - 1)
let d = e.inverse(phi)!     // d * e % phi == 1
==> 13964664343869014759736350480776837992604500903989703383202366291905558996277719

let publicKey: Key = (n, e)
let privateKey: Key = (n, d)

In RSA, modular exponentiation is used to encrypt (and decrypt) messages.

func encrypt(_ message: BigUInt, key: Key) -> BigUInt {
    return message.power(key.exponent, modulus: key.modulus)

Let's try out our new keypair by converting a string into UTF-8, interpreting the resulting binary representation as a big integer, and encrypting it with the public key. BigUInt has an initializer that takes an NSData, so this is pretty easy to do:

let secret: BigUInt = BigUInt("Arbitrary precision arithmetic is fun!".dataUsingEncoding(NSUTF8StringEncoding)!)
==> 83323446846105976078466731524728681905293067701804838925389198929123912971229457

let cyphertext = encrypt(secret, key: publicKey)
==> 95186982543485985200666516508066093880038842892337880561554910904277290917831453

Well, it looks encrypted all right, but can we get the original message back? In theory, encrypting the cyphertext with the private key returns the original message. Let's see:

let plaintext = encrypt(cyphertext, key: privateKey)
==> 83323446846105976078466731524728681905293067701804838925389198929123912971229457

let received = String(data: plaintext.serialize(), encoding: NSUTF8StringEncoding)
==> "Arbitrary precision arithmetic is fun!"

Yay! This is truly terrific, but please don't use this example code in an actual cryptography system. RSA has lots of subtle (and some not so subtle) complications that we ignored to keep this example short.

Calculating the Digits of π

Another fun activity to try with BigInts is to generate the digits of π. Let's try implementing Jeremy Gibbon's spigot algorithm. This is a rather slow algorithm as π-generators go, but it makes up for it with its grooviness factor: it's remarkably short, it only uses (big) integer arithmetic, and every iteration produces a single new digit in the base-10 representation of π. This naturally leads to an implementation as an infinite GeneratorType:

func digitsOfPi() -> AnyGenerator<Int> {
    var q: BigUInt = 1
    var r: BigUInt = 180
    var t: BigUInt = 60
    var i: UInt64 = 2 // Does not overflow until digit #826_566_842
    return AnyIterator {
        let u: UInt64 = 3 * (3 * i + 1) * (3 * i + 2)
        let y = (q.multiplied(byDigit: 27 * i - 12) + 5 * r) / (5 * t)
        (q, r, t) = (
            10 * q.multiplied(byDigit: i * (2 * i - 1)),
            10 * (q.multiplied(byDigit: 5 * i - 2) + r - y * t).multiplied(byDigit: u),
            t.multiplied(byDigit: u))
        i += 1
        return Int(y[0])

Well, that was surprisingly easy. But does it work? Of course it does!

var digits = "π ≈ "
var count = 0
for digit in digitsOfPi() {
    assert(digit < 10)
    digits += String(digit)
    count += 1
    if count == 1 { digits += "." }
    if count == 1000 { break }

==> π ≈ 3.14159265358979323846264338327950288419716939937510582097494459230781640628

Now go and have some fun with big integers on your own!


Stars: 555


Used By

Total: 0


- 2020-03-17 01:15:32

This release contains the following changes:

Added support to serialize/deserialize BigInt in a manner similar to BigUInt

5.0.0 - 2019-08-25 08:34:06

This release contains the following changes:

  • Swift 5 compatibility
  • There were no functional changes.

4.0.0 - 2019-04-05 18:55:44

This release contains the following changes:

  • Swift 5.0 compatibility for Linux and macOS
  • Remove SipHash dependency

There were no functional changes.

3.1.0 - 2018-06-08 12:36:43

This release contains the following changes:

  • Swift 4.1 compatibility for Linux and macOS
  • Fix warnings for Swift 4.1

There were no functional changes.

3.0.2 - 2017-12-25 16:34:55

3.0.2 (2017-12-25)

This release contains the following packaging fix:

  • Fixed product definitions in Package.swift not to create a duplicate library. (Issue #37)

There were no functional changes.

3.0.1 - 2017-10-10 15:18:29

This release contains the following bug fixes:

  • Issue #27 — changing scope of kind and storage to be fileprivate
  • Making subscript method of BigUInt public

3.0.0 - 2017-09-07 12:18:31

This is a major release upgrading BigInt to the new integer protocols introduced in Swift 4 as part of SE-0104, Protocol-oriented integers.

  • Adopting the new protocols involved major, breaking changes throughout the API. These aren't individually listed here.
  • The BigUInt struct now provides inline storage for big integers that fit inside two words. This optimization speeds up conversions from built-in fixed-width integer types, amongst other frequent operations.
  • BigInt and BigUInt implements the new Codable protocol. In both cases, values are encoded in an unkeyed container starting with a string indicating the sign ("+" or "-"), followed by a sequence of 64-bit unsigned integers representing component words, from least to most significant.
  • New method: BigInt.modulo, contributed by @FabioTacke.
  • BigUInt does not implement Collection in this release. The collection of words is available in the standard read-only words property. Direct public access to collection methods have been removed; if you have been manipulating big integers using collection methods, you need to rewrite your code. If you have a usecase that isn't covered by the public API, please submit a PR adding the missing functionality. (Public read-write access to the underlying storage inside BigUInt will not be restored, though.)

BigInt is now part of the Attaswift project. The bundle identifiers in the supplied Xcode project have been updated accordingly.

Note that the URL for the package's Git repository has changed; please update your references.

2.1.2 - 2017-02-03 13:02:51

This release contains the following bugfix:

  • Issue #12: The iOS target in the supplied Xcode project file no longer copies extraneous files as resources into the framework bundle. The set of such files included generate-docs.sh, which led to App Store rejections for apps that build BigInt using the project file. (Thanks to @arrrnas and @wuftymerguftyguff)

No source-level changes were made.

2.1.1 - 2016-11-23 09:40:06

This release restores support for iOS 8.0 and macOS 10.9.

2.1.0 - 2016-11-16 01:28:54

This release contains the following changes:

  • BigInt now uses the SipHash hashing algorithm instead of implementing its own hashing.
  • The SipHash package has been added as a required dependency. I suggest you use a dependency manager.
  • Minimum deployment targets have been bumped to iOS 9.0 and macOS 10.0 to match those of SipHash.
  • BigInt now requires Swift 3.0.1, included in Xcode 8.1.
  • The Xcode project file has been regenerated from scratch, with new names for targets and schemes.
  • The bundle identifiers of frameworks generated from the Xcode project file have been changed to hu.lorentey.BigInt.<platform>.

2.0.1 - 2016-11-08 15:11:27

This release contains the following bugfixes:

  • The Swift version number is now correctly set in all targets (PR #7 by @mAu888).
  • BigInt now builds on Linux (PR #5 by @ratranqu).
  • Building BigInt with the Swift Package Manager bundled with Swift 3.0.1 works correctly.

Additionally, Foundation imports that weren't actually needed were removed from sources.

2.0.0 - 2016-09-20 15:32:16

This release updates the project for Swift 3.0, including adapting the API to the new naming conventions.

Further changes:

  • The behavior of BigUInt.gcd when one of the arguments is zero has been fixed; the result in this case is now equal to the other argument.
  • BigInt now conforms to Strideable, IntegerArithmetic, SignedNumber and AbsoluteValuable.
  • BigUInt now conforms to Strideable, IntegerArithmetic and BitwiseOperations.

1.3.0 - 2016-03-23 15:09:47

This release updates the project to require Swift 2.2 and Xcode 7.3. There have been no other changes.

1.2.3 - 2016-01-12 06:32:53

This release adds experimental support for the Swift Package Manager and Swift 2.2. There were no source-level changes.

1.2.2 - 2016-01-08 21:20:01

This release fixes version numbers embedded in build products.

1.2.1 - 2016-01-07 16:36:04

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

1.2.0: Integrations - 2016-01-06 16:45:26

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 - 2016-01-06 15:25:58

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 - 2016-01-04 02:53:50

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.