COMPSCI320 Chap.7 Fast Multiplication and the Fast Fourier Transform
Fast Multiplication and the Fast Fourier Transform
Grade-school multiplication of n-digit numbers costs quadratic time, and this chapter shows how divide and conquer beats it.
Karatsuba replaces four half-size products with three, Strassen replaces eight block products with seven, and the fast Fourier transform evaluates a polynomial at roots of unity by splitting it into even and odd parts, giving n log n polynomial multiplication.
Every number in the worked example is shown, from the half-size products to the recombined answer, and the even and odd split is evaluated at all four fourth roots of unity.
The analysis questions compare the recurrences of the slow and fast schemes, which is where the exponents come from.
The chapter also connects the arithmetic to the course's recurring theme: a design is judged by the Theta class of its running time.
Karatsuba, Strassen and the fast Fourier transform all keep the work outside the recursive calls linear or quadratic and save by making fewer calls, so the Master theorem from Chapter 6 explains each improvement in one line.
What this chapter covers
- 01
Why the four-product split gains nothing
- 02
The Karatsuba identity
- 03
Strassen's seven block products
- 04
Polynomial multiplication in value form
- 05
Even and odd splitting at roots of unity
- 06
Convolution and its applications
Worked example · free
Multiply with one level of Karatsuba
- 1Split into a = 24, b = 68 and c = 13, d = 57.
- 1Compute ac = 312, bd = 3,876 and (a + b)(c + d) = 92 × 70 = 6,440.
- 1The middle coefficient is 6,440 − 312 − 3,876 = 2,252.
- 1Recombine 312 × 10,000 + 2,252 × 100 + 3,876 = 3,349,076.
Key terms
- Karatsuba Multiplication
- A divide and conquer method that multiplies two numbers with three half-size products instead of four.
- Root of Unity
- A complex number whose n-th power equals one, used as an evaluation point by the fast Fourier transform.
- Fast Fourier Transform
- A divide and conquer algorithm that evaluates a polynomial at all n-th roots of unity in n log n time.
- Convolution Theorem
- The rule that the transform of a convolution equals the pointwise product of the transforms.
- Strassen Multiplication
- A method that multiplies two matrices using seven products of half-size blocks instead of eight.
Fast Multiplication and the Fast Fourier Transform FAQ
Why does saving one multiplication change the exponent?
The number of recursive calls sets the number of leaves in the recursion tree. Four half-size calls give four to the power log n leaves, which is n squared. Three calls give three to the power log n, which is n to about 1.585. The extra additions cost only linear time per level and cannot outweigh the smaller leaf count.
How does the fast Fourier transform halve the work?
A polynomial splits into its even and odd powers, A(x) = E(x squared) + x times O(x squared). Squaring the n-th roots of unity gives only the n/2-th roots, so E and O need evaluating at half as many points. That gives the recurrence T(n) = 2T(n/2) + O(n) and a total of n log n.
Where do convolutions appear in the course?
Multiplying polynomials is a convolution of their coefficient lists, and the sixth tutorial applies the same idea to forces between charged particles. Each force is a sum over all other particles, which looks quadratic, but written as a convolution it can be computed through the convolution theorem with the fast Fourier transform in n log n time.
Why does Strassen's method need care with signs?
Strassen forms seven products from sums and differences of the matrix blocks and then combines them with further additions and subtractions. Many of the intermediate values are negative even when every input entry is positive. The practice slides warn about negative entries because most hand-calculation errors come from a sign in the combining step.
Exam move
Carry out one full Karatsuba level on two new four-digit numbers and verify the product directly. Write the Strassen and Karatsuba recurrences side by side with their solutions. Then evaluate a cubic at the four fourth roots of unity using the even and odd split and check one value by direct substitution.
Also compare the three fast methods in a single table of recurrences and solutions, because exam questions often ask why one saved product changes the exponent.
Finish each Karatsuba practice by multiplying the original numbers the slow way to confirm the final product, and finish each evaluation question by substituting one root directly into the polynomial; both checks take a minute and catch the sign and carry slips that cost most marks in this topic.
Working through Fast Multiplication and the Fast Fourier Transform in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Fast Multiplication and the Fast Fourier Transform question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
