Integers

Implements integer values of arbitrary magnitude. Includes all standard arithmetic and logic operations. The Integer type is compliant to the BinaryInteger and SignedInteger Swift protocols. A preliminary version of rational numbers is also included with basic arithmetic operations. Ported to Swift from an original Oberon-2 library by Michael Griebling, 18 July 2015.

This module is a reformulation of (parts of) Python's longobject.c in Swift. Optimizations like Karatsuba multiplication have been omitted.

Added algorithms are from Knuth: The Art Of Computer Programming, Vol 2, section 4.3.1 and Applied Cryptography by Bruce Schneier.

Features

1. Arbitrary-precision integers implemented entirely with Swift supporting the Codable, Sendable, Hashable, SignedInteger and BinaryInteger protocols.
2. Includes all basic mathematical functions plus prime factoring, factorial, greatest common denominator, powers, square root, and radix conversions to/from strings.
3. Supports StaticBigInt initialization allowing large number literals.

Timing

Some typical performance tests were run on a 3.6 GHz 10-Core Intel Core i9 Mac. As a comparison, the same benchmarks were also run using the BigInt package by Matthias Zenger. In both cases source code is 100% Swift.

The Integer package optimizes the integer power function using 5-ary exponentiation for large exponents. Number squaring functions have been optimized to be about twice as fast as just multiplying two numbers. String to integer conversions for power-of-two bases are about twice as fast as other conversions.

Results	String to Integer (100 digits, base 10)	Factorial(999)
Integer	192 μS	19 mS
BigInt	461 μS	167 mS

Examples

Check standard Int conversion to Integer:

Int.max = 9223372036854775807
Int.min = -9223372036854775808

1000! = 40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696
9404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779
5059509952761208749754624970436014182780946464962910563938874378864873371191810458257836478499770124766
3288983595573543251318532395846307555740911426241747434934755342864657661166779739666882029120737914385
3719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036
9768013573042161687476096758713483120254785893207671691324484262361314125087802080002616831510273418279
7770478463586817016436502415369139828126481021309276124489635992870511496497541990934222156683257208082
1333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442
4879849599533191017233555566021394503997362807501378376153071277619268490343526252000158885351473316117
0210396817592151090778801939317811419454525722386554146106289218796022383897147608850627686296714667469
7562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414
2820121873617459926429565817466283029555702990243241531816172104658320367869061172601587835207515162842
2554026517048330422614397428693306169089796848259012545832716822645806652676995865268227280707578139185
8178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558
6003014356945272242063446317974605946825731037900840244324384656572450144028218852524709351906209290231
3649327349756551395872055965422874977401141334696271542284586237738753823048386568897646192738381490014
0767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171
2298459016419210688843871218556461249607987229085192968193723886426148396573822911231250241866493531439
7013742853192664987533721894069428143411852015801412334482801505139969429015348307764456909907315243327
8288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825
0879689281627538488633969099598262809561214509948717012445164612603790293091208890869420285106401821543
9945715680594187274899809425474217358240106367740459574178516082923013535808184009699637252423056085590
3700624271243416909004153690105933983835777939410970027753472000....000

Testing Integer sequence...

1
2
3
4

Integer(1.23456789e+18) = 1234567890000000000

Debug description of Integer(69)! ->

Dump =  size=11, digits=0 0 208483648 1760158 815281888 388340220 147380948 549955052 405677315 320051255 84005611 , base=1073741824

Encoding/decoding test:

Encoded 1000 = Decoded 1000

Modulo Tests:

9 % 4 = 1
-9 % 4 = -1
9 % -4 = 1
-9 % -4 = -1

Rational Tests:

a = 1/6; b = 2/3
a+b = 5/6
a-b = -1/2
a*b = 1/9
a/b = 1/4
b**10 = 1024/59049