## PackageDescription: SYSEXT-LargeIntegerArithmetic

SYSEXT - Large Integer ArithmeticLast 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