We wish to find the time complexity of certain arithmetic. For example, how much work does it take to find the nth digit of √2?
Applying Newton’s method to f(x) = x2 – a, which has a zero at √a, and carefully selecting initial value around this zero yields:
xi+1 = (xi + a/xi)/2.
Set a = 2, and we gain a series that converges to √2. The convergence is quadratic, i.e., each step doubles the precision/number of correct digits. However, to calculate each step, it would require a method for high-precision division due to the term a/xi. To perform division, we start with multiplication.
Assume there are two large n-bits integers in base r, the direct multiplication is of Θ(n2) complexity. We can break each of them in half, namely, x to x1, x0, and y to y1, y0, where x1, y1 represent the first half of x, y, and x0, y0 represent the second half of x, y, respectively. We have the relation:
x = x1*rn/2 + x0, y = y1*rn/2 + y0.
Now we can represent the product of x and y in the following fashion:
z = x*y = x1*y1*rn + (x0*y1 + x1*y0)*rn/2 + x0*y0.
This way of multiplication still has Θ(n2) complexity. Karatsuba introduced a better method. If we let:
z0 = x0*y0,
z2 = x1*y1,
z1 = (x0 + x1)*(y0 + y1) – z0 – z2 = x0*y1 + x1*y0,
then z = z2*rn + z1*rn/2 + z0.
Only 3 multiplies instead of 4 are needed in this calculation. If we apply this recursively in the multiplication of x*y, we obtain a complexity of Θ(nlog 3) ≈ Θ(n1.585), which is better than direct multiplication. Toom-Cook (or Toom-3) method works with breaking integers to three parts, and only 5 multiplies are needed in each calculation; this method reduces the complexity to Θ(nlog 5/log 3) ≈ Θ(n1.465). There are some more methods such as Schönhage-Strassen with Θ(n log n log log n) complexity, which is included in gmpy package.
Back to division. We want a high-precision representation of 1/b in base r. We can assign a large number R = rk, then floor(R/b) is such representation. We apply Newton’s method to f(x) = 1/x – b/R, which has a zero at x= R/b, and end up with the following series that converges to R/b:
xi+1 = 2xi – b*xi2/R.
This series also has quadratic convergence. Note that the asymptotic complexity of this calculation is contributed by the xi2 term, i.e., multiplication. To reach precision n, one might think that the complexity is log n times the complexity of multiplication given that we will have log n multiplications in the log n iterations. However, with a closer observation, the complexity of division is equal to the complexity of multiplication.
Assume the complexity of multiplication is Θ(nα), where α > 1. The number of operations in division are:
1α + 2α + 4α +…+ (n/4)α + (n/2)α + nα < 2*nα.
Hence the complexity of division is Θ(nα), same as that of multiplication. Similarly, square root operation has the same complexity as division and multiplication.
