BigInt

Contents:

• Usage
• Examples
• Performance
• Fractions
• Chinese Remainder Theorem
• References
• Algorithms

• Arithmetic: add, subtract, multiply, divide, remainder and exponentiation
• Comparison: the six standard operations == != < <= > >=
• 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 numbers, Lucas numbers and Bernoulli numbers
• Fractions: Standard arithmetic on fractions whose numerators and denominators are of unbounded size

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.13.0"),
  ]

Examples

Creating BInt's

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

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

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

Fractions

• The numerator and denominator have no common factors except 1
• The denominator is always positive
• Zero is represented as 0/1

Creating BFraction's

• Specifying the numerator and denominator explicitly f.ex. BFraction(17, 4)
• Specifying the decimal value explictly f.ex. BFraction(4.25)
• Using a string representation f.ex. BFraction("4.25")! or equivalently BFraction("425E-2")!

Converting BFraction's

  let x = BFraction(1000, 7)
  
  // To String
  let s1 = x.asString() // s1 = "1000 / 7"
  
  // To decimal String
  let s1 = x.asDecimalString(precision: 8, exponential: false) // s1 = "142.85714"
  let s2 = x.asDecimalString(precision: 8, exponential: true) // s2 = "1.4285714E+2"
  
  // To Double
  let d = x.asDouble() // d = 142.8571428571429

Operations

• Arithmetic
  • addition
  • subtraction
  • multiplication
  • division
  • modulo an integer
  • exponentiation
• Rounding to an integer
  • round - to nearest integer
  • truncate - towards 0
  • ceil - towards +infinity
  • floor - towards -infinity
• Comparison - the six standard operations == != < <= > >=

Bernoulli Numbers

let bn = BFraction.bernoulli(n)

computes the n'th (n >= 0) Bernoulli number, which is a rational number.
For example

print(BFraction.bernoulli(60))
print(BFraction.bernoulli(60).asDecimalString(precision: 20, exponential: true))

would print

-1215233140483755572040304994079820246041491 / 56786730
-2.1399949257225333665E+34

The static function

let x = BFraction.bernoulliSequence(n)

computes the n even numbered Bernoulli numbers B(0), B(2) ... B(2 * n - 2).

Chinese Remainder Theorem

let moduli = [3, 5, 7]
let residues = [2, 2, 6]
let crt = CRT(moduli)!
print("CRT value:", crt.compute(residues))

would print

CRT value: 62

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
• [HACKER] - Henry S. Warren, Jr.: Hacker's Delight. Second Edition, Addison-Wesley
• [HANDBOOK] - Menezes, Oorschot, Vanstone: Handbook of Applied Cryptography. CRC Press 1996
• [JEBELEAN] - Tudor Jebelean: An Algorithm for Exact Division. Journal of Symbolic Computation, volume 15, 1993
• [KNUTH] - Donald E. Knuth: Seminumerical Algorithms, Third Edition
• [KOC] - Cetin Kaya Koc: A New Algorithm for Inversion mod p^k

Algorithms

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
• Exact Division - Jebelean's exact division algorithm

Greatest Common Divisor and Extended Greatest Common Divisor

Modular Exponentiation

Inverse Modulus

Square Root

Square Root Modulo a Prime Number

Prime Number Test

Prime Number Generation

Factorial

Fibonacci

Jacobi and Kronecker symbols

Bernoulli Numbers

Chinese Remainder Theorem