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

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.3.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.3.0")

• CocoaPods: Put this in your Podfile:

  pod'BigInt','~> 5.3'

• Carthage: Put this in your Cartfile:

  github "attaswift/BigInt" ~> 5.3
  

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))==>362880print(factorial(100))==>933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000print(factorial(1000))==>402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

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{whiletrue{varrandom=BigUInt.randomInteger(withExactWidth: width)
random |=BigUInt(1)if random.isPrime(){return random
}}}letp=generatePrime(1024)==>133081876506421923962564199110125448453704937284249367915614783184430716172428728198095674708718741991443516991416111660167888335861107680074358055605571417392208406194264346635072293912609713085260354070700055888678514690878149253177960273775659537560220378850112471985434373425534121373466492101182463962031letq=generatePrime(1024)==>170729544226571454895473088123333689250079490545012049838639583558971720931737831010822659694399955378425256465062476627613315758673350478461613830570116841015780784336308507083874651158029602582993233111593356512531869546706885170044355115669728424124141763799008880327106952436883614887277350838425336156327

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

typealiasKey=(modulus:BigUInt, exponent:BigUInt)letn= p * q
==>22721008120758282530010953362926306641542233757318103044313144976976529789946696154549667209077125159174814189815913796476353912605693490996664101272796903679788118437553375588899437064085788375498536428841379610052726276320267903713402181057933883525572232242690805678883227791774442041516929419640051653934584376704034639531697728169072805919344232379772583580978465110799473378577781371775706683915745541770710027548777039928141735282989711814097224075770856102708721720597522002207275447810167397968435583004676293892340103729490987263776871467057582629588916498579594964478080508868267360515953225283461208420137lete:BigUInt=65537letphi=(p -1)*(q -1)letd= e.inverse(phi)! // d * e % phi == 1
==>1396466434386901475973635048077683799260450090398970338320236629190555899627771977822086142456362972689566985925179681282432115598451765899180050962461295573831370692379342918841065848209981469650855314331951066867454742222226209868586965916983653246883515441255452115210364245315889536341764067661170454278457697437495445789456921660619938185093118762690200980720312508614337759620606992462563490422766695595565689175332684791909489595603975795727615298528912462835396045456912448999969287715867664304211866261387586350401612983709922304068751268453269452710980742873307409704484365002175294665608486688146261327793letpublicKey:Key=(n, e)letprivateKey: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:

letsecret:BigUInt=BigUInt("Arbitrary precision arithmetic is fun!".dataUsingEncoding(NSUTF8StringEncoding)!)==>8332344684610597607846673152472868190529306770180483892538919892912391297122945768818568737letcyphertext=encrypt(secret, key: publicKey)==>9518698254348598520066651650806609388003884289233788056155491090427729091783145354854954722744805432145474047391353716305176389470779020645959135298322520888633616749451290995759433847673303425545251203844854694280489620271491698761278903067702818390469949196205088897452460322629083698416616475958695241934358938527964147999991283152843977988979846238236160274201261075188190509539751990119132013021748666385957342228670050891571985032041922648147508320728442085203946030549017060602439473137197340259582645643594496843915366461718857080894002247199063846878349208193955207336172861151720299024935127021719852700882

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:

letplaintext=encrypt(cyphertext, key: privateKey)==>8332344684610597607846673152472868190529306770180483892538919892912391297122945768818568737letreceived=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>{varq:BigUInt=1varr:BigUInt=180vart:BigUInt=60vari:UInt64=2 // Does not overflow until digit #826_566_842
returnAnyIterator{letu:UInt64=3*(3* i +1)*(3* i +2)lety=(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 +=1returnInt(y[0])}}

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

vardigits="π ≈ "varcount=0fordigitindigitsOfPi(){assert(digit <10)
digits +=String(digit)
count +=1if count ==1{ digits +="."}if count ==1000{break}}
digits
==> π ≈3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198

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