PackageDescription: SYSEXT-LargeIntegerArithmetic


SYSEXT - Large Integer Arithmetic

Last published: April 28, 2019 by 'nice'

Defines 0 Classes
Extends 5 Classes


This package is dedicated to accelerating the arithmetic operations on large integers

Notably, it provides algorithms for fast multiplications and divisions

#fastMultiply: will perform multiplication using Karatsuba or 3-way Toom-Cook if the LargeInteger is large enough
#squared will use an asymetrical Karatsuba or asymetrical 4-way Toom-Cook
#quoRem: will return an Array with quotient and remainder of integer division, using divide and conquer algorithm if it's worth
#sqrtRem will return an Array with sqrtFloor and remainder, and also use divide and conquer.

Example of timings: (MBP 2015 core i5 2.7GHz, VW8.3 64bits)

| x |
x := 10000 factorial - 5000 factorial + 1000 factorial - 500 factorial + 100 factorial - 50 factorial + 10 factorial - 5 factorial + 1.
[x * x] timeToRun. 15.739 milliseconds
[x squaredKaratsuba] timeToRun. 3.511 milliseconds
[x squaredToom4] timeToRun. 3.033 milliseconds

| x |
x := 10000 factorial - 5000 factorial + 1000 factorial - 500 factorial + 100 factorial - 50 factorial + 10 factorial - 5 factorial + 1.
[x sqrtFloorNewtonRaphson] timeToRun. 127.169 milliseconds
[x sqrtRem first] timeToRun. 2.938 milliseconds

| x y |
x := 10000 factorial - 5000 factorial + 1000 factorial - 500 factorial + 100 factorial - 50 factorial + 10 factorial - 5 factorial + 1.
y := 11000 factorial - 6000 factorial + 1100 factorial - 600 factorial + 110 factorial - 60 factorial + 11 factorial - 6 factorial + 1.
[x * y] timeToRun. 16.213 milliseconds
[x karatsubaTimes: y] timeToRun. 4.769 milliseconds
[x toom3Times: y] timeToRun. 4.493 milliseconds

| x y |
x := 10000 factorial - 5000 factorial + 1000 factorial - 500 factorial + 100 factorial - 50 factorial + 10 factorial - 5 factorial + 1.
y := 15000 factorial - 6000 factorial + 1500 factorial - 600 factorial + 150 factorial - 60 factorial + 15 factorial - 6 factorial + 1.
[y quo: x] timeToRun. 18.116 milliseconds
[(y quoRem: x) first] timeToRun. 6.416 milliseconds