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.0.0"), ], ```
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 |
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.
Github
link |
Stars: 0 |
Help us keep the lights on
Dependencies
Used By
Total: 0
Releases
1.0.1 - Nov 27, 2019
Small performance improvements, and a bit operation bug fix
1.0.0 - Sep 17, 2019
Initial release