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

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 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. It also requires that the Int and UInt types be 64 bit types.

Usage

  dependencies: [
  .package(url: "https://github.com/leif-ibsen/BigInt", from: "1.2.8"),
  ]

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.

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.

• [BRENT] - Brent and Zimmermann: Modern Computer Arithmetic, 2010
• [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

Acknowledgement

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