Arithmetic on bigInts 

L. Allison, FIT, Monash University, Australia 3800.16 August 20211. IntroductionAn arbitrarily big integer, a bigInt, can be represented by a
sign (±) and a vector (array) of digits in some base: Timings of long division and long multiplication are reasonably consistent with quadratic timecomplexity O(d^{2}) (d~log N), div having a constant several times bigger (but this version is operating bitwise not digitwise like '×'). Note that N.toString() does a special 'divide by 10' repeatedly (log_{10}(N) times) and takes maybe O(d^{2})time overall but is very lumpy (try 64K bits or more), while N.toBinary() is very fast of course. (And the garbage collector may kick in at any time.) 2. Addition and SubtractionAddition and subtraction of ddigit integers take O(d)time. 3. Multiplication3.1. LongMultiplication1 2 3 x 4 5 6 . 4 9 2  4 6 1 5  5 7 3 8  6  5 6 0 8 8Figure 2: LongMultiplication. For ddigit integers, longmultiplication takes O(d^{2})time. 3.2. Karatsuba ×Multiply two ddigit integers by multiplying three halflength, (d/2)digit, integers [Kar62].
The algorithm has O(d^{log2(3)}) time complexity for ddigit multiplication, log_{2}(3)≈1.58, so it beats longmultiplication for big enough bigInts. 2.2.1 The polynomial view:An integer corresponds to a polynomial, the integer's digits being the coefficients of the polynomial. Multiplying two integers is mirrored by multiplying their corresponding polynomials to give the product polynomial. Recall that a polynomial of degree 'd' is defined by its values at d+1 points. In particular, a quadratic is defined by its values at three points, e.g., 0, 1 and −1, say.
3.3. ToomCook × (Toom3)Multiply two ddigit integers by multiplying five (d/3)digit integers, version after M. Bodrato [Bod07].
The algorithm has O(d^{log3(5)}) time complexity (log_{3}(5)≈1.465). This beats Karatsuba asymptotically but the more extensive housekeeping makes for a larger constant of proportionality. 3.4. Faster MultiplicationThe SchonhageStrassen algorithm [SS71], running in O(n log n log log d)time, was the asymptotically fastest multiplication algorithm for more than four decades. Harvey and van der Hoeven [HV19] finally removed the log log d term (as S and S had speculated would be possible); the improvement is of great theoretical interest but little practical use. 1 2 3 123 x 456 < 6  7 3 8  . 5  6 1 5 .  . . 4  4 9 2 . 8 v . . . 8 . . 0 . 6 5 123 x 456 = 56088Figure 4: Another Angle on LongMultiplication. Long multiplication is closely related to vector convolution, M conv N, where we pairwise multiply elements and add up diagonals and that is all, the carries are dealt with afterwards (this is linear convolution below): 1 2 3 123 conv 456 < 6  6 12 18  . 5  5 10 15 .  . . 4  4 8 12 . 18 v . . . 27 . . 28 . 13 4 4,13,28,27,18 >carries> 5, 6, 0, 8, 8, i.e., 56088Figure 5: Linear Convolution Trouble is, the obvious way to do the above still takes quadratic time, O(d^{2}), but there is a faster method. The SchonhageStrassen algorithm [SS71] relies on
the Fast Fourier Transform (FFT) algorithm [CT65] which
calculates the Discrete Fourier Transform (F) of a vector
and on the fact that 4. DivisionTo divide M≥0 by N>0, M ÷ N, find quotient Q≥0 and remainder r∈[0, N−1] such that M = Q×N + r, e.g., for 14÷4, Q=3 and r=2. 4.1. LongDivisionLongdivision has O(d^{2}) time complexity. e.g., 3219876 ÷ 394 8172 rem 108 . 394 3219876 x8 = 3152  678 x1 = 394  2847 x7 = 2758  896 x2 = 788  108Figure 3: LongDivision Longdivision can be carried out in any base. If the base of the stored integers is a power of two (2^{k}) the algorithm can still act in terms of binary (2^{1}) and this is the simplest version to implement because the only possible digitmultipliers are zero and one, however the timecomplexity does decrease as the base increases because there are fewer digits. 4.2. Recursive DivisionThere are recursive algorithms [BZ98] to divide bigInts, e.g., To divide M by N, giving a quotient, Q, and a remainder: Naturally this division algorithm avails itself of the fastest multiplication algorithm. 5. ConclusionTo make the very fastest implementation of operations on large integers it is best to use a programming language that is close to the underlying hardware and C, C++ or assembler are obvious choices. Javascript is not that kind of choice but it does run in web browsers which is convenient for interactive demonstrations of algorithms. References


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Tuesday, 23Jul2024 00:12:39 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 