Wednesday, December 01, 2021

A Faster Way To Multiply

Any math teacher's curiosity would be piqued when seeing the title This Guy Found A Faster Way To Multiply.

It has a subtitle: Because the method you learned in middle school is ridiculously slow.

That was the first red flag:  if you didn't learn to multiply until middle school, oh my.  But I read on.

The article never discusses this new method, so I question if it's more efficient than the standard algorithm for multiplications of the size most humans have to do--say, from 1-digit times 1 digit numbers to 3-digit times 3-digit numbers.  Here's as close as we get to when this new algorithm is not as "ridiculously slow" as the standard algorithm:

The Schönhage-Strassen method is very fast, Harvey says. If a computer were to use the squared method taught in school on a problem where two numbers had a billion digits each, it would take months. A computer using the Schönhage-Strassen method could do so in 30 seconds.

But if the numbers keep rising into the trillions and beyond, the algorithm developed by Harvey and collaborator Joris van der Hoeven at École Polytechnique in France could find solutions faster than the 1971 Schönhage-Strassen algorithm.

Essentially, the "standard algorithm" works just fine for the size numbers that the vast majority of the people on the planet might need to multiply by hand; most of us aren't multiplying two billion-digit numbers.

Lastly, I watched the video at the link--does it show a faster way to multiply up to 3-digit numbers?  Or is this method better only for huge numbers most of us will never work with?  Turns out it's the latter, and even worse, we don't even know when it's more efficient:

The question is, how big does n (the number of digits in the numbers being multiplied) have to be for this algorithm to actually be faster than the previous algorithms?  The answer is, we don't know.  It could be billions of digits, it could be trillions, it could be much bigger than that.  We really have no idea at this point.

Bottom line?  The article was clickbait, the title and subtitle were misleading/wrong, and besides letting us know that a new algorithm is possible, the article never explicitly states that that such an algorithm has been created--only that it's possible.

The article originally appeared in Popular Mechanics.  They should probably stick to what they know best, because they're way out of their league here.

No comments: