Swiftpack.co - Package - leif-ibsen/BigInt

## 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 and remainder
• 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 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.

## Usage

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

## 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 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 a MacBook Pro 2018, 2,2 GHz 6-Core Intel Core i7. 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).

Based on these measurements it seems that Java BigInteger is roughly 2-5 times faster than Swift BigInt.

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()89 uSec59 uSec
As magnitude bytesc2000.asMagnitudeBytes()0.42 uSec0.45 uSec
Bitwise anda1000 & b10000.48 uSec0.065 uSec
Bitwise ora1000 | b10000.46 uSec0.066 uSec
Bitwise xora1000 ^ b10000.47 uSec0.088 uSec
Bitwise not~c20000.22 uSec0.14 uSec
Test bitc2000.testBit(701)0.0010 uSec0.0040 uSec
Flip bitc2000.flipBit(701)0.0055 uSec0.12 uSec
Set bitc2000.setBit(701)0.0046 uSec0.099 uSec
Clear bitc2000.clearBit(701)0.0043 uSec0.092 uSec
Subtractiona1000 - b10000.26 uSec0.077 uSec
Multiplicationa1000 * b10000.64 uSec0.37 uSec
Divisionc2000 / a10008.1 uSec2.7 uSec
Modulusc2000.mod(a1000)8.1 uSec2.7 uSec
Inverse modulusc2000.modInverse(p1000)1.8 mSec0.25 mSec
Modular exponentiationa1000.expMod(b1000, c2000)5.9 mSec2.0 mSec
Equalc2000 + 1 == c20000.0016 uSec0.027 uSec
Less thanb1000 + 1 < b10000.020 uSec0.016 uSec
Shift 1 leftc2000 <<= 10.22 uSec0.076 uSec
Shift 1 rightc2000 >>= 10.22 uSec0.082 uSec
Shift 100 leftc2000 <<= 1000.42 uSec0.063 uSec
Shift 100 rightc2000 >>= 1000.26 uSec0.067 uSec
Is probably primep1000.isProbablyPrime()11 mSec10 mSec
Make probable 1000 bit primeBInt.probablePrime(1000)100 mSec42 mSec
Greatest common divisora1000.gcd(b1000)0.26 mSec0.066 mSec
Make random numberc2000.randomLessThan()9.4 uSec0.97 uSec
Square root modulob1000.sqrtMod(p1000)4.5 mSecn.a.

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.

• [CRANDALL] - Crandall and Pomerance: Prime Numbers - A Computational Perspective. Second Edition, Springer 2005
• [HANDBOOK] - Menezes, Oorschot, Vanstone: Handbook of Applied Cryptography. CRC Press 1996
• [KNUTH] - Donald E. Knuth: Seminumerical Algorithms. Addison-Wesley 1971
• [WARREN] - Henry S. Warren, Jr: Hacker's Delight. Second Edition, Addison-Wesley 2013

## Acknowledgement

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

Total: 0

## Release 1.2.1 - 2020-09-15 08:40:39

1. Fixed a bug in Karatsuba multiplication that produced wrong results in rare cases

2. Fixed a bug in the init?(_ x: String, radix: Int = 10) initializer, so that a leading '+' sign is allowed and empty strings are not allowed, that is

• BInt("") returns nil instead of 0

• BInt("+1") return 1 instead of nil

## 1.2.0 - 2020-09-02 09:14:17

Changes in release 1.2.0:

1. Improved expMod implementation
2. Changed abs to a computed property instead og a function, syntax x.abs instead of x.abs()
3. Fixed a bug in a modInverse testcase

Minor cleanup

## Bugfix in the square function - 2020-02-24 08:50:58

Fixed a bug in the square function

## 1.1.0 - 2019-12-08 11:22:02

Fixed a bug in the sqrtMod function

## 1.0.1 - 2019-11-27 21:01:45

Small performance improvements, and a bit operation bug fix

Initial release