Arithmetic on bigInts
L. Allison, FIT, Monash University, Australia 3800.
16 August 2021
An 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 time-complexity O(d2) (d~log N), div having a constant several times bigger (but this version is operating bit-wise not digit-wise like '×'). Note that N.toString() does a special 'divide by 10' repeatedly (log10(N) times) and takes maybe O(d2)-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 Subtraction
Addition and subtraction of d-digit integers take O(d)time.
1 2 3 x 4 5 6 ----------. 4 9 2 | 4 6 1 5 | 5 7 3 8 | 6 --------- 5 6 0 8 8Figure 2: Long-Multiplication.
For d-digit integers, long-multiplication takes O(d2)-time.
3.2. Karatsuba ×
Multiply two d-digit integers by multiplying three half-length, (d/2)-digit, integers [Kar62].
The algorithm has O(dlog2(3)) time complexity for d-digit multiplication, log2(3)≈1.58, so it beats long-multiplication 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. Toom-Cook × (Toom3)
Multiply two d-digit integers by multiplying five (d/3)-digit integers, version after M. Bodrato [Bod07].
The algorithm has O(dlog3(5)) time complexity (log3(5)≈1.465). This beats Karatsuba asymptotically but the more extensive house-keeping makes for a larger constant of proportionality.
3.4. Faster Multiplication
The Schonhage-Strassen 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 Long-Multiplication.
Long multiplication is closely related to vector convolution, M conv N, where we pair-wise 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(d2), but there is a faster method.
The Schonhage-Strassen 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
To 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.
Long-division has O(d2) time complexity.
e.g., 3219876 ÷ 394 8172 rem 108 .------- 394 |3219876 x8 = 3152 ---- 678 x1 = 394 --- 2847 x7 = 2758 ---- 896 x2 = 788 --- 108Figure 3: Long-Division
Long-division can be carried out in any base. If the base of the stored integers is a power of two (2k) the algorithm can still act in terms of binary (21) and this is the simplest version to implement because the only possible digit-multipliers are zero and one, however the time-complexity does decrease as the base increases because there are fewer digits.
4.2. Recursive Division
There 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.
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated).
Created with "vi (Linux)", charset=iso-8859-1, fetched Wednesday, 18-May-2022 10:48:27 UTC.
Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.