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.8.0"),
]
// From an integer
let a = BInt(27)
// From a decimal value
let x = BInt(1.12345e30) // x = 1123450000000000064996914495488
// 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. The results are in the table below. It shows the operation being measured and the time it took (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 | Time |
---|---|---|
As string | c2000.asString() | 13 uSec |
As signed bytes | c2000.asSignedBytes() | 0.31 uSec |
Bitwise and | a1000 & b1000 | 0.087 uSec |
Bitwise or | a1000 | b1000 | 0.086 uSec |
Bitwise xor | a1000 ^ b1000 | 0.087 uSec |
Bitwise not | ~c2000 | 0.098 uSec |
Test bit | c2000.testBit(701) | 0.018 uSec |
Flip bit | c2000.flipBit(701) | 0.019 uSec |
Set bit | c2000.setBit(701) | 0.019 uSec |
Clear bit | c2000.clearBit(701) | 0.019 uSec |
Addition | a1000 + b1000 | 0.10 uSec |
Subtraction | a1000 - b1000 | 0.11 uSec |
Multiplication | a1000 * b1000 | 0.32 uSec |
Division | c2000 / a1000 | 2.5 uSec |
Modulus | c2000.mod(a1000) | 2.5 uSec |
Inverse modulus | c2000.modInverse(p1000) | 110 uSec |
Modular exponentiation | a1000.expMod(b1000, c2000) | 3.7 mSec |
Equal | c2000 + 1 == c2000 | 0.017 uSec |
Less than | b1000 + 1 < b1000 | 0.021 uSec |
Shift 1 left | c2000 <<= 1 | 0.10 uSec |
Shift 1 right | c2000 >>= 1 | 0.07 uSec |
Shift 100 left | c2000 <<= 100 | 0.15 uSec |
Shift 100 right | c2000 >>= 100 | 0.13 uSec |
Is probably prime | p1000.isProbablyPrime() | 6.1 mSec |
Make probable 1000 bit prime | BInt.probablePrime(1000) | 60 mSec |
Next probable prime | c2000.nextPrime() | 770 mSec |
Primorial | BInt.primorial(100000) | 16 mSec |
Binomial | BInt.binomial(100000, 10000) | 26 mSec |
Factorial | BInt.factorial(100000) | 68 mSec |
Fibonacci | BInt.fibonacci(100000) | 0.74 mSec |
Greatest common divisor | a1000.gcd(b1000) | 32 uSec |
Extended gcd | a1000.gcdExtended(b1000) | 90 uSec |
Least common multiple | a1000.lcm(b1000) | 35 uSec |
Make random number | c2000.randomLessThan() | 1.2 uSec |
Square | c2000 ** 2 | 0.83 uSec |
Square root | c2000.sqrt() | 14 uSec |
Square root and remainder | c2000.sqrtRemainder() | 14 uSec |
Is perfect square | (c2000 * c2000).isPerfectSquare() | 18 uSec |
Square root modulo | b1000.sqrtMod(p1000) | 1.7 mSec |
Power | c2000 ** 111 | 2.3 mSec |
Root | c2000.root(111) | 16 uSec |
Root and remainder | c2000.rootRemainder(111) | 18 uSec |
Is perfect root | c2000.isPerfectRoot() | 14 mSec |
Jacobi symbol | c2000.jacobiSymbol(p1000) | 0.15 mSec |
Kronecker symbol | c2000.kroneckerSymbol(p1000) | 0.15 mSec |
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: 12 |
Last commit: 3 days ago |
Performance improvements in release 1.8.0:
The 'gcdExtended' function is now implemented using using Lehmer's method. For 1000-bit numbers, it means that it now runs 5-6 times faster than before.
The 'modInverse' function now computes its result using the 'gcdExtended' function. For 1000-bit numbers, it means that it now runs 3-4 times faster than before.
Swiftpack is being maintained by Petr Pavlik | @ptrpavlik | @swiftpackco | API | Analytics