- #1

n+1

- 13

- 0

However, these papers all use sophisticated algorithms where a simple one seems to work. My question is, what's wrong with the simple algorithm:

Multiplication of Two Big Numbers Algorithm:

Input: Two integers, a and b, stored in base B.

Step 1: Write a and b as polynomials in Z[B ], a(B) and b(B).Let m be the the larger of the two degrees.

Step 2: Rewrite a(B) and b(B) as 2m-dimensional vectors by padding with 0s. Denote these vectors by v_a and v_b.

Step 3: Use the FFT and Convolution Theorem to compute the Convolution of v_a and v_b quickly.

Step 4: Recover ab by reversing step 2 and 1.

Complexity Analysis

Let D = Max(a,b). Notice log(D) ~ m.

Step 1: 1. You're just reinterpreting what a list represents.

Step 2: m. You're at most adding 2m zeroes.

Step 3: m log(m).

Step 4: m. You're doing similar operations as in steps 1 and 2.

Conclusion: m log(m) or log(d) log(log(d)).