attaswift/BigInt - Githubissues

Overview
API Documentation
License
Requirements and Integration
Implementation Notes
- Why is there no generic BigInt<Digit> type?
Calculation Samples

Overview

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): Modular exponentiation (right-to-left binary method). Vanilla exponentiation is also available.
n.inverse(modulus): Multiplicative inverse in modulo arithmetic (extended Euclidean algorithm).
n.isPrime(): 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.

API Documentation

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

License

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.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")
```

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][magnitude] 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), *)
}

print(factorial(10))
==> 362880

print(factorial(100))
==> 93326215443944152681699238856266700490715968264381621468592963895217599993229915
    6089414639761565182862536979208272237582511852109168640000000000000000000000

print(factorial(1000))
==> 40238726007709377354370243392300398571937486421071463254379991042993851239862902
    05920442084869694048004799886101971960586316668729948085589013238296699445909974
    24504087073759918823627727188732519779505950995276120874975462497043601418278094
    64649629105639388743788648733711918104582578364784997701247663288983595573543251
    31853239584630755574091142624174743493475534286465766116677973966688202912073791
    43853719588249808126867838374559731746136085379534524221586593201928090878297308
    43139284440328123155861103697680135730421616874760967587134831202547858932076716
    91324484262361314125087802080002616831510273418279777047846358681701643650241536
    91398281264810213092761244896359928705114964975419909342221566832572080821333186
    11681155361583654698404670897560290095053761647584772842188967964624494516076535
    34081989013854424879849599533191017233555566021394503997362807501378376153071277
    61926849034352625200015888535147331611702103968175921510907788019393178114194545
    25722386554146106289218796022383897147608850627686296714667469756291123408243920
    81601537808898939645182632436716167621791689097799119037540312746222899880051954
    44414282012187361745992642956581746628302955570299024324153181617210465832036786
    90611726015878352075151628422554026517048330422614397428693306169089796848259012
    54583271682264580665267699586526822728070757813918581788896522081643483448259932
    66043367660176999612831860788386150279465955131156552036093988180612138558600301
    43569452722420634463179746059468257310379008402443243846565724501440282188525247
    09351906209290231364932734975655139587205596542287497740114133469627154228458623
    77387538230483865688976461927383814900140767310446640259899490222221765904339901
    88601856652648506179970235619389701786004081188972991831102117122984590164192106
    88843871218556461249607987229085192968193723886426148396573822911231250241866493
    53143970137428531926649875337218940694281434118520158014123344828015051399694290
    15348307764456909907315243327828826986460278986432113908350621709500259738986355
    42771967428222487575867657523442202075736305694988250879689281627538488633969099
    59826280956121450994871701244516461260379029309120889086942028510640182154399457
    15680594187274899809425474217358240106367740459574178516082923013535808184009699
    63725242305608559037006242712434169090041536901059339838357779394109700277534720
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000

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
    81980956747087187419914435169914161116601678883358611076800743580556055714173922
    08406194264346635072293912609713085260354070700055888678514690878149253177960273
    775659537560220378850112471985434373425534121373466492101182463962031

let q = generatePrime(1024)
==> 17072954422657145489547308812333368925007949054501204983863958355897172093173783
    10108226596943999553784252564650624766276133157586733504784616138305701168410157
    80784336308507083874651158029602582993233111593356512531869546706885170044355115
    669728424124141763799008880327106952436883614887277350838425336156327

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
    15454966720907712515917481418981591379647635391260569349099666410127279690367978
    81184375533755888994370640857883754985364288413796100527262763202679037134021810
    57933883525572232242690805678883227791774442041516929419640051653934584376704034
    63953169772816907280591934423237977258358097846511079947337857778137177570668391
    57455417707100275487770399281417352829897118140972240757708561027087217205975220
    02207275447810167397968435583004676293892340103729490987263776871467057582629588
    916498579594964478080508868267360515953225283461208420137

let e: BigUInt = 65537
let phi = (p - 1) * (q - 1)
let d = e.inverse(phi)!     // d * e % phi == 1
==> 13964664343869014759736350480776837992604500903989703383202366291905558996277719
    77822086142456362972689566985925179681282432115598451765899180050962461295573831
    37069237934291884106584820998146965085531433195106686745474222222620986858696591
    69836532468835154412554521152103642453158895363417640676611704542784576974374954
    45789456921660619938185093118762690200980720312508614337759620606992462563490422
    76669559556568917533268479190948959560397579572761529852891246283539604545691244
    89999692877158676643042118662613875863504016129837099223040687512684532694527109
    80742873307409704484365002175294665608486688146261327793

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
    68818568737

let cyphertext = encrypt(secret, key: publicKey)
==> 95186982543485985200666516508066093880038842892337880561554910904277290917831453
    54854954722744805432145474047391353716305176389470779020645959135298322520888633
    61674945129099575943384767330342554525120384485469428048962027149169876127890306
    77028183904699491962050888974524603226290836984166164759586952419343589385279641
    47999991283152843977988979846238236160274201261075188190509539751990119132013021
    74866638595734222867005089157198503204192264814750832072844208520394603054901706
    06024394731371973402595826456435944968439153664617188570808940022471990638468783
    49208193955207336172861151720299024935127021719852700882

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
    68818568737

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 }
}

digits
==> π ≈ 3.14159265358979323846264338327950288419716939937510582097494459230781640628
    62089986280348253421170679821480865132823066470938446095505822317253594081284811
    17450284102701938521105559644622948954930381964428810975665933446128475648233786
    78316527120190914564856692346034861045432664821339360726024914127372458700660631
    55881748815209209628292540917153643678925903600113305305488204665213841469519415
    11609433057270365759591953092186117381932611793105118548074462379962749567351885
    75272489122793818301194912983367336244065664308602139494639522473719070217986094
    37027705392171762931767523846748184676694051320005681271452635608277857713427577
    89609173637178721468440901224953430146549585371050792279689258923542019956112129
    02196086403441815981362977477130996051870721134999999837297804995105973173281609
    63185950244594553469083026425223082533446850352619311881710100031378387528865875
    33208381420617177669147303598253490428755468731159562863882353787593751957781857
    780532171226806613001927876611195909216420198

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