Description

The BigInt package provides arbitrary-precision integer arithmetic in Swift. Its functionality is comparable to that of the Java BigInteger class. It falls in the following categories:

• Arithmetic: add, subtract, multiply, divide and remainder
• Comparison: the six standard operators == != < <= > >=
• Shifting: logical left shift and rigth shift
• Logical: bitwise and, or, xor, and not
• Modulo: normal modulus, inverse modulus, and modular exponentiation
• Conversion: to string, to magnitude byte array, and to 2's complement byte array
• Primes: prime number testing and probable prime number generation
• Miscellaneous: random number generation, greatest common divisor, n-th root, square root modulo an odd prime, and Jacobi symbol

BigInt requires Swift 5.0.

Usage

In your projects Package.swift file add a dependency like
``` dependencies: [ // Dependencies declare other packages that this package depends on. .package(url: "https://github.com/leif-ibsen/BigInt", from: "1.1.1"), ], ```

Performance

To assess the performance of BigInt, the execution times for a number of common operations were measured on a MacBook Pro 2018, 2,2 GHz 6-Core Intel Core i7. Each execution time was then compared to the execution time for the same operation in Java using the BigInteger class. The results are in the table below. It shows the operation being measured and the time it took in Swift and in Java (in microseconds or milliseconds).

Based on these measurements it seems that Java BigInteger is roughly 2-5 times faster than Swift BigInt.

Four large numbers 'a1000', 'b1000', 'c2000' and 'p1000' were used throughout the measurements. Their actual values are shown under the table.

Operation	Swift code	Swift time	Java time
As string	c2000.asString()	89 uSec	59 uSec
As magnitude bytes	c2000.asMagnitudeBytes()	0.42 uSec	0.45 uSec
Bitwise and	a1000 & b1000	0.48 uSec	0.065 uSec
Bitwise or	a1000 | b1000	0.46 uSec	0.066 uSec
Bitwise xor	a1000 ^ b1000	0.47 uSec	0.088 uSec
Bitwise not	~c2000	0.22 uSec	0.14 uSec
Test bit	c2000.testBit(701)	0.0010 uSec	0.0040 uSec
Flip bit	c2000.flipBit(701)	0.0055 uSec	0.12 uSec
Set bit	c2000.setBit(701)	0.0046 uSec	0.099 uSec
Clear bit	c2000.clearBit(701)	0.0043 uSec	0.092 uSec
Addition	a1000 + b1000	0.19 uSec	0.051 uSec
Subtraction	a1000 - b1000	0.26 uSec	0.077 uSec
Multiplication	a1000 * b1000	0.64 uSec	0.37 uSec
Division	c2000 / a1000	8.1 uSec	2.7 uSec
Modulus	c2000.mod(a1000)	8.1 uSec	2.7 uSec
Inverse modulus	c2000.modInverse(p1000)	1.8 mSec	0.25 mSec
Modular exponentiation	a1000.expMod(b1000, c2000)	6.9 mSec	2.0 mSec
Equal	c2000 + 1 == c2000	0.0016 uSec	0.027 uSec
Less than	b1000 + 1 < b1000	0.020 uSec	0.016 uSec
Shift 1 left	c2000 <<= 1	0.22 uSec	0.076 uSec
Shift 1 right	c2000 >>= 1	0.22 uSec	0.082 uSec
Shift 100 left	c2000 <<= 100	0.42 uSec	0.063 uSec
Shift 100 right	c2000 >>= 100	0.26 uSec	0.067 uSec
Is probably prime	p1000.isProbablyPrime()	11 mSec	10 mSec
Make probable 1000 bit prime	BInt.probablePrime(1000)	100 mSec	42 mSec
Greatest common divisor	a1000.gcd(b1000)	0.26 mSec	0.066 mSec
Make random number	c2000.randomLessThan()	9.4 uSec	0.97 uSec
Square root modulo	b1000.sqrtMod(p1000)	4.5 mSec	n.a.

a1000 = 3187705437890850041662973758105262878153514794996698172406519277876060364087986868049465132757493318066301987043192958841748826350731448419937544810921786918975580180410200630645469411588934094075222404396990984350815153163569041641732160380739556436955287671287935796642478260435292021117614349253825
b1000 = 9159373012373110951130589007821321098436345855865428979299172149373720601254669552044211236974571462005332583657082428026625366060511329189733296464187785766230514564038057370938741745651937465362625449921195096442684523511715110908407508139315000469851121118117438147266381183636498494901233452870695
c2000 = 1190583332681083129323588684910845359379915367459759242106618067261956856381281184752008892106576666833853411939711280970145570546868549934865719229538926506588929417873149597614787608112658086250354719939407543740242931571462165384138560315454455247539461818779966171917173966217706187439870264672508450210272481951994459523586160979759782950984370978171111340529321052541588344733968902238813379990628157732181128074253104347868153860527298911917508606081710893794973605227829729403843750412766366804402629686458092685235454222856584200220355212623917637542398554907364450159627359316156463617143173
p1000 (probably a prime) = 7662841304438384296568220077355872003841475576593385710590818274399706072141018649398767137142090308734613594718593893634649122767374115742644499040193270857876678047220373151142747088797516044505739487695946446362769947024029728822155570722524629197074319602110260674029276185098937139753025851896997

References

Algorithms from the following books have been used in the implementation. There are references in the source code where appropriate.

• Donald E. Knuth: Seminumerical Algorithms. Addison-Wesley 1971
• Crandall and Pomerance: Prime Numbers - A Computational Perspective. Second Edition, Springer 2005
• Henry S. Warren, Jr: Hacker's Delight. Second Edition, Addison-Wesley 2013
• Menezes, Oorschot, Vanstone: Handbook of Applied Cryptography. CRC Press 1996

Acknowledgement

The BitSieve class used in the implementation is a translation to Swift of the corresponding class from Java BigInteger. The GCD algorithm and the Karatsuba and ToomCook multiplication algorithms are modelled after the corresponding algorithms in Java BigInteger.