Swiftpack.co - leif-ibsen/BigInt as Swift Package

Swiftpack.co is a collection of thousands of indexed Swift packages. Search packages.
See all packages published by leif-ibsen.
leif-ibsen/BigInt 1.4.3
Arbitrary-precision integer arithmetic in Swift
⭐️ 5
🕓 1 week ago
.package(url: "https://github.com/leif-ibsen/BigInt.git", from: "1.4.3")

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, remainder and exponentiation
  • 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 double, to integer, to string, to magnitude byte array, and to 2's complement byte array
  • Primes: prime number testing, probable prime number generation and primorial
  • Miscellaneous: random number generation, greatest common divisor, least common multiple, n-th root, square root modulo an odd prime, Jacobi symbol, Kronecker symbol, Factorial function, Binomial function, Fibonacci- and Lucas numbers

BigInt requires Swift 5.0. It also requires that the Int and UInt types be 64 bit types.

Usage

In your projects Package.swift file add a dependency like
  dependencies: [
  .package(url: "https://github.com/leif-ibsen/BigInt", from: "1.4.3"),
  ]

Examples

Creating BInt's

  // 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

Converting BInt's

  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]

Performance

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.

OperationSwift codeSwift timeJava time
As stringc2000.asString()23 uSec31 uSec
As signed bytesc2000.asSignedBytes()0.23 uSec1.0 uSec
Bitwise anda1000 & b10000.16 uSec0.076 uSec
Bitwise ora1000 | b10000.17 uSec0.051 uSec
Bitwise xora1000 ^ b10000.17 uSec0.048 uSec
Bitwise not~c20000.10 uSec0.13 uSec
Test bitc2000.testBit(701)0.0038 uSec0.0058 uSec
Flip bitc2000.flipBit(701)0.0078 uSec0.069 uSec
Set bitc2000.setBit(701)0.0023 uSec0.088 uSec
Clear bitc2000.clearBit(701)0.0046 uSec0.072 uSec
Additiona1000 + b10000.096 uSec0.12 uSec
Subtractiona1000 - b10000.11 uSec0.25 uSec
Multiplicationa1000 * b10000.32 uSec0.73 uSec
Divisionc2000 / a10002.8 uSec3.4 uSec
Modulusc2000.mod(a1000)2.8 uSec3.5 uSec
Inverse modulusc2000.modInverse(p1000)0.60 mSec0.17 mSec
Modular exponentiationa1000.expMod(b1000, c2000)3.8 mSec2.3 mSec
Equalc2000 + 1 == c20000.00095 uSec0.019 uSec
Less thanb1000 + 1 < b10000.012 uSec0.011 uSec
Shift 1 leftc2000 <<= 10.094 uSec0.060 uSec
Shift 1 rightc2000 >>= 10.11 uSec0.058 uSec
Shift 100 leftc2000 <<= 1000.17 uSec0.045 uSec
Shift 100 rightc2000 >>= 1000.14 uSec0.060 uSec
Is probably primep1000.isProbablyPrime()6.2 mSec12 mSec
Make probable 1000 bit primeBInt.probablePrime(1000)55 mSec34 mSec
Next probable primec2000.nextPrime()780 mSec510 mSec
PrimorialBInt.primorial(100000)16 mSecn.a.
BinomialBInt.binomial(100000, 10000)26 mSecn.a.
FactorialBInt.factorial(100000)70 mSecn.a.
FibonacciBInt.fibonacci(100000)0.75 mSecn.a.
Greatest common divisora1000.gcd(b1000)37 uSec31 uSec
Extended gcda1000.gcdExtended(b1000)0.82 mSecn.a.
Least common multiplea1000.lcm(b1000)42 uSecn.a.
Make random numberc2000.randomLessThan()0.50 uSec0.49 uSec
Squarec2000 ** 20.88 uSec0.99 uSec
Square rootc2000.sqrt()22 uSec139 uSec
Square root and remainderc2000.sqrtRemainder()18 uSecn.a.
Is perfect square(c2000 * c2000).isPerfectSquare()22 uSecn.a.
Square root modulob1000.sqrtMod(p1000)2.3 mSecn.a.
Powerc2000 ** 1112.3 mSecn.a.
Rootc2000.root(111)21 uSecn.a.
Root and remainderc2000.rootRemainder(111)22 uSecn.a.
Is perfect rootc2000.isPerfectRoot()17 mSecn.a.
Jacobi symbolc2000.jacobiSymbol(p1000)0.36 mSecn.a.
Kronecker symbolc2000.kroneckerSymbol(p1000)0.35 mSecn.a.

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

References

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

  • [BRENT] - Brent and Zimmermann: Modern Computer Arithmetic, 2010
  • [BURNIKEL] - Burnikel and Ziegler: Fast Recursive Division, October 1998
  • [CRANDALL] - Crandall and Pomerance: Prime Numbers - A Computational Perspective. Second Edition, Springer 2005
  • [GRANLUND] - Moller and Granlund: Improved Division by Invariant Integers, 2011
  • [HANDBOOK] - Menezes, Oorschot, Vanstone: Handbook of Applied Cryptography. CRC Press 1996
  • [KNUTH] - Donald E. Knuth: Seminumerical Algorithms. Addison-Wesley 1971

Algorithms

Some of the algorithms used in BigInt are described below.

Multiplication

  • Schonhage-Strassen FFT based algorithm for numbers above 384000 bits
  • ToomCook-3 algorithm for numbers above 12800 bits
  • Karatsuba algorithm for numbers above 6400 bits
  • Basecase - Knuth algorithm M

Division and Remainder

  • Burnikel-Ziegler algorithm for divisors above 3840 bits provided the dividend has at least 3840 bits more than the divisor
  • Basecase - Knuth algorithm D

Greatest Common Divisor

Lehmer's algorithm [KNUTH] chapter 4.5.2, with binary GCD basecase.

Modular Exponentiation

Sliding window algorithm 14.85 from [HANDBOOK] using Barrett reduction for exponents with fewer than 2048 bits and Montgomery reduction for larger exponents.

Inverse Modulus

Extended Euclid algorithm 2.1.4 from [CRANDALL].

Square Root

Algorithm 1.12 (SqrtRem) from [BRENT] with algorithm 9.2.11 from [CRANDALL] as basecase.

Square Root Modulo a Prime Number

Algorithm 2.3.8 from [CRANDALL].

Prime Number Test

Miller-Rabin test.

Prime Number Generation

The algorithm from Java BigInteger translated to Swift.

Factorial

The 'SplitRecursive' algorithm from Peter Luschny: https://www.luschny.de

Fibonacci

The 'fastDoubling' algorithm from Project Nayuki: https://www.nayuki.io

Jacobi and Kronecker symbols

Algorithm 2.3.5 from [CRANDALL].

GitHub

link
Stars: 5
Last commit: 1 week ago
jonrohan Something's broken? Yell at me @ptrpavlik. Praise and feedback (and money) is also welcome.

Release Notes

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