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:
BigInt requires Swift 5.0. It also requires that the Int and UInt types be 64 bit types.
dependencies: [
.package(url: "https://github.com/leif-ibsen/BigInt", from: "1.4.3"),
]
// From an integer
let a = BInt(27)
// From string literals
let b = BInt("123456789012345678901234567890")!
let c = BInt("1234567890abcdef1234567890abcdef", radix: 16)!
// From magnitude and sign
let m: Limbs = [1, 2, 3]
let d = BInt(m) // d = 1020847100762815390427017310442723737601
let e = BInt(m, true) // e = -1020847100762815390427017310442723737601
// From a big-endian 2's complement byte array
let f = BInt(signed: [255, 255, 127]) // f = -129
// From a big-endian magnitude byte array
let g = BInt(magnitude: [255, 255, 127]) // g = 16777087
// Random value with specified bitwidth
let h = BInt(bitWidth: 43) // For example h = 3965245974702 (=0b111001101100111011000100111110100010101110)
// Random value less than a given value
let i = h.randomLessThan() // For example i = 583464003284
let x = BInt(16777087)
// To double
let d = x.asDouble() // d = 16777087.0
// To strings
let s1 = x.asString() // s1 = "16777087"
let s2 = x.asString(radix: 16) // s2 = "ffff7f"
// To big-endian magnitude byte array
let b1 = x.asMagnitudeBytes() // b1 = [255, 255, 127]
// To big-endian 2's complement byte array
let b2 = x.asSignedBytes() // b2 = [0, 255, 255, 127]
To assess the performance of BigInt, the execution times for a number of common operations were measured on an iMac 2021, Apple M1 chip. 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).
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() | 23 uSec | 31 uSec |
As signed bytes | c2000.asSignedBytes() | 0.23 uSec | 1.0 uSec |
Bitwise and | a1000 & b1000 | 0.16 uSec | 0.076 uSec |
Bitwise or | a1000 | b1000 | 0.17 uSec | 0.051 uSec |
Bitwise xor | a1000 ^ b1000 | 0.17 uSec | 0.048 uSec |
Bitwise not | ~c2000 | 0.10 uSec | 0.13 uSec |
Test bit | c2000.testBit(701) | 0.0038 uSec | 0.0058 uSec |
Flip bit | c2000.flipBit(701) | 0.0078 uSec | 0.069 uSec |
Set bit | c2000.setBit(701) | 0.0023 uSec | 0.088 uSec |
Clear bit | c2000.clearBit(701) | 0.0046 uSec | 0.072 uSec |
Addition | a1000 + b1000 | 0.096 uSec | 0.12 uSec |
Subtraction | a1000 - b1000 | 0.11 uSec | 0.25 uSec |
Multiplication | a1000 * b1000 | 0.32 uSec | 0.73 uSec |
Division | c2000 / a1000 | 2.8 uSec | 3.4 uSec |
Modulus | c2000.mod(a1000) | 2.8 uSec | 3.5 uSec |
Inverse modulus | c2000.modInverse(p1000) | 0.60 mSec | 0.17 mSec |
Modular exponentiation | a1000.expMod(b1000, c2000) | 3.8 mSec | 2.3 mSec |
Equal | c2000 + 1 == c2000 | 0.00095 uSec | 0.019 uSec |
Less than | b1000 + 1 < b1000 | 0.012 uSec | 0.011 uSec |
Shift 1 left | c2000 <<= 1 | 0.094 uSec | 0.060 uSec |
Shift 1 right | c2000 >>= 1 | 0.11 uSec | 0.058 uSec |
Shift 100 left | c2000 <<= 100 | 0.17 uSec | 0.045 uSec |
Shift 100 right | c2000 >>= 100 | 0.14 uSec | 0.060 uSec |
Is probably prime | p1000.isProbablyPrime() | 6.2 mSec | 12 mSec |
Make probable 1000 bit prime | BInt.probablePrime(1000) | 55 mSec | 34 mSec |
Next probable prime | c2000.nextPrime() | 780 mSec | 510 mSec |
Primorial | BInt.primorial(100000) | 16 mSec | n.a. |
Binomial | BInt.binomial(100000, 10000) | 26 mSec | n.a. |
Factorial | BInt.factorial(100000) | 70 mSec | n.a. |
Fibonacci | BInt.fibonacci(100000) | 0.75 mSec | n.a. |
Greatest common divisor | a1000.gcd(b1000) | 37 uSec | 31 uSec |
Extended gcd | a1000.gcdExtended(b1000) | 0.82 mSec | n.a. |
Least common multiple | a1000.lcm(b1000) | 42 uSec | n.a. |
Make random number | c2000.randomLessThan() | 0.50 uSec | 0.49 uSec |
Square | c2000 ** 2 | 0.88 uSec | 0.99 uSec |
Square root | c2000.sqrt() | 22 uSec | 139 uSec |
Square root and remainder | c2000.sqrtRemainder() | 18 uSec | n.a. |
Is perfect square | (c2000 * c2000).isPerfectSquare() | 22 uSec | n.a. |
Square root modulo | b1000.sqrtMod(p1000) | 2.3 mSec | n.a. |
Power | c2000 ** 111 | 2.3 mSec | n.a. |
Root | c2000.root(111) | 21 uSec | n.a. |
Root and remainder | c2000.rootRemainder(111) | 22 uSec | n.a. |
Is perfect root | c2000.isPerfectRoot() | 17 mSec | n.a. |
Jacobi symbol | c2000.jacobiSymbol(p1000) | 0.36 mSec | n.a. |
Kronecker symbol | c2000.kroneckerSymbol(p1000) | 0.35 mSec | n.a. |
a1000 = 3187705437890850041662973758105262878153514794996698172406519277876060364087986868049465132757493318066301987043192958841748826350731448419937544810921786918975580180410200630645469411588934094075222404396990984350815153163569041641732160380739556436955287671287935796642478260435292021117614349253825 b1000 = 9159373012373110951130589007821321098436345855865428979299172149373720601254669552044211236974571462005332583657082428026625366060511329189733296464187785766230514564038057370938741745651937465362625449921195096442684523511715110908407508139315000469851121118117438147266381183636498494901233452870695 c2000 = 1190583332681083129323588684910845359379915367459759242106618067261956856381281184752008892106576666833853411939711280970145570546868549934865719229538926506588929417873149597614787608112658086250354719939407543740242931571462165384138560315454455247539461818779966171917173966217706187439870264672508450210272481951994459523586160979759782950984370978171111340529321052541588344733968902238813379990628157732181128074253104347868153860527298911917508606081710893794973605227829729403843750412766366804402629686458092685235454222856584200220355212623917637542398554907364450159627359316156463617143173 p1000 (probably a prime) = 7662841304438384296568220077355872003841475576593385710590818274399706072141018649398767137142090308734613594718593893634649122767374115742644499040193270857876678047220373151142747088797516044505739487695946446362769947024029728822155570722524629197074319602110260674029276185098937139753025851896997
Algorithms from the following books and papers have been used in the implementation. There are references in the source code where appropriate.
link |
Stars: 5 |
Last commit: 1 week ago |
Changes in release 1.4.3:
Two new 'quotientAndRemainder' functions for computing the quotient and remainder when dividing a BInt value by an Int value.
Better performance when mixing BInt values and Int values in arithmetic operations.
Swiftpack is being maintained by Petr Pavlik | @ptrpavlik | @swiftpackco | API | Analytics