Fast Multiplication
Learn about the efficiency and effectiveness of the fast multiplication algorithm.
We'll cover the following...
The divide-and-conquer algorithm
Two ancient algorithms for multiplying two -digit numbers in time are: the grade-school lattice algorithm and the Egyptian peasant algorithm. Maybe, we can get a more efficient algorithm by splitting the digit arrays in half and exploiting the following identity:
This recurrence immediately suggests the following divide-and-conquer algorithm to multiply two -digit numbers, and . Each of the four subproducts and is computed recursively, but the multiplications in the last line aren’t recursive because we can multiply by a power of ten by shifting the digits to the left and filling in the correct number of zeros, all in time.
Algorithm
...