- #1
n+1
- 13
- 0
Multiplying big numbers is a very common application of the FFT, and as such, there are many papers on the subject available online.
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)).
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)).