- Notifications
You must be signed in to change notification settings - Fork114
Arbitrary-precision arithmetic in pure Swift
License
attaswift/BigInt
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
This repository providesinteger types of arbitrary width implementedin 100% pure Swift. The underlying representation is in base 2^64, usingArray<UInt64>.
This module is handy when you need an integer type that's wider thanUIntMax, butyou don't want to addThe GNU Multiple Precision Arithmetic Libraryas a dependency.
Two big integer types are included:BigUInt andBigInt,the latter being the signed variant.Both of these are Swift structs with copy-on-write value semantics, and they can be used muchlike any other integer type.
The library provides implementations for some of the most frequently useful functions onbig integers, including
All functionality from
ComparableandHashableThe full set of arithmetic operators:
+,-,*,/,%,+=,-=,*=,/=,%=- Addition andsubtraction have variants that allow forshifting 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.) - Afused multiply-add method is also available, along with otherspecial-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.dividereturns the quotient andremainder 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 toconvert
NSDatato big integers and vice versa.Support forgenerating random integers of specified maximum width or magnitude.
Radix conversion to/from
Strings andbig integers up to base 36 (using repeated divisions).- Big integers use this to implement
StringLiteralConvertible(in base 10).
- Big integers use this to implement
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 becompetitive with GMP at all, even when I happened to implement an algorithm with same asymptoticbehavior 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 bugsin it.
Generated API docs are available athttps://attaswift.github.io/BigInt/.
BigInt can be used, distributed and modified underthe MIT license.
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, soit 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.swiftmanifest:.package(url:"https://github.com/attaswift/BigInt.git", from:"5.4.0")
BigUInt is aMutableCollectionType of its 64-bit digits, with the least significantdigit at index 0. As a convenience,BigUInt allows you to subscript it with indexes ator above itscount.The subscript operator returns 0 for out-of-boundgets andautomatically extends the array on out-of-boundsets. This makes memory management simpler.
BigInt is just a tiny wrapper around aBigUInt [absolute value][magnitude] and asign bit, both of which are accessible as public read-write properties.
The types provided byBigInt are not parametric—this is very much intentional, asSwift generics cost us dearly at runtime in this use case. In every approach I tried,making arbitrary-precision arithmetic operations work with a genericDigit type parameterresulted in code that was literallyten times slower. If you can make the algorithms genericwithout 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 genericimplementations for arbitrary-width arithmetic operations. (Polynomial division and decimal basesare two examples.) The library already implements double-digit multiplication and division asextension methods on a protocol with an associated type requirement; this has not measurably affectedperformance. Unfortunately, the same is not true forBigUInt's methods.
Of course, as a last resort, we could just duplicate the code to create a separategeneric variant that was slower but more flexible.
It is easy to useBigInt to calculate the factorial function for any integer:
import BigIntfunc 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.
TheBigInt module provides all necessary parts to implement an (overly)simpleRSA cryptography system.
Let's start with a simple function that generates a random n-bit prime. The moduleincludes a function to generate random integers of a specific size, and also anisPrime 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 keypairout 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, interpretingthe resulting binary representation as a big integer, and encrypting it with thepublic key.BigUInt has an initializer that takes anNSData, so this is prettyeasy 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 actualcryptography system. RSA has lots of subtle (and some not so subtle) complicationsthat we ignored to keep this example short.
Another fun activity to try withBigInts is to generate the digits of π.Let's try implementingJeremy Gibbon's spigot algorithm.This is a rather slow algorithm as π-generators go, but it makes up for it with its groovinessfactor: it's remarkably short, it only uses (big) integer arithmetic, and every iterationproduces a single new digit in the base-10 representation of π. This naturally leads to animplementation as an infiniteGeneratorType:
func digitsOfPi()->AnyGenerator<Int>{varq:BigUInt=1varr:BigUInt=180vart:BigUInt=60vari:UInt64=2 // Does not overflow until digit #826_566_842returnAnyIterator{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!
About
Arbitrary-precision arithmetic in pure Swift
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
Uh oh!
There was an error while loading.Please reload this page.