How does Schönehage-Straussen multiplication work and why is it so much faster for computers to perform than traditional multiplication?
In: Mathematics
So first you need to remember that multiplication really means adding multiple times. So normally to multiply 12×31 you’d need to go:
12+12=24
24+12=36
36+12=48
and so on.. 31 times in a row
And that would be very long. So we all learned in school how to do it faster. That faster method is basically to multiply units and decades separately and sum the results.
That’s in fact an algorithm that allows faster multiplication based on how we break down numbers to write them down.
Well, the Schonhage strassen is another algorithm, that uses another way to break numbers down to multiply them. And it happens that while the decomposition is a bit more complex, the multiplication is faster so for very large numbers, it’s worth it.
Latest Answers