We have recently breaking news from the world of maths, where David Harvey and Joris van der Hoeven have posted a new paper describing a computational method they developed that may have reached the theoretical speed limit for performing the multiplication of very large numbers.
In the following video, Harvey describes what that speed limit is, or rather, the minimum number of calculations required to reach the correct product for two large numbers that are being multiplied:
If the method is proven, it represents a large step forward in speeding the solution of large number multiplication by reducing the number of required calculations. We built the following tool to get a sense of how much smaller the theoretical limit of N log (N) [N multiplied by the natural logarithm of N] is when compared to the N² operations required by the traditional method of multiplying two numbers with the same number of digits. If you're reading this article on a site that republishes our RSS news feed, click here to access a working version of this tool!
For the default example, where we're multiplying two numbers with 10,000 digits each, you can see why this development is exciting because it would be possible to reduce the number of individual operations needed to arrive at the product from 100,000,000 to 92,104, a computational efficiency gain of nearly 99.91%.
Which is to say that you can not only get to the answer much more quickly, you would also greatly reduce the amount of energy that computers consume in reaching the product of the two very large numbers being multiplied.
Writing at The Conversation, Harvey describes what he and van der Hoeven have achieved, where the secret to reaching the theoretical peak efficiency for multiplying very large integers is to use multidimensional Fast Fourier Transforms (FFTs):
A few weeks ago, Joris van der Hoeven and I posted a research paper describing a new multiplication algorithm that finally reaches the N log (N) holy grail, thus settling the “easy” part of the Schönhage–Strassen conjecture.
The paper has not yet been peer-reviewed, so some caution is warranted. It is standard practice in mathematics to disseminate research results before they have undergone peer review.
Instead of using one-dimensional FFTs — the staple of all work on this problem since 1971 — our algorithm relies on multidimensional FFTs. These gadgets are nothing new: the widely-used JPEG image format depends on 2-dimensional FFTs, and 3-dimensional FFTs have many applications in physics and engineering.
In our paper, we use FFTs with 1,729 dimensions. This is tricky to visualise, but mathematically no more troublesome than the 2-dimensional case.
If you want to find out more about FFTs, Better Explained has one of the gentler introductions to the math of Fast Fourier Transforms.
Meanwhile, Harvey recognizes the current generation of van der Hoeven's and his algorithm is limited in how it can be used effectively:
The new algorithm is not really practical in its current form, because the proof given in our paper only works for ludicrously large numbers. Even if each digit was written on a hydrogen atom, there would not be nearly enough room available in the observable universe to write them down.
On the other hand, we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits. If so, it may well become an indispensable tool in the computational mathematician’s arsenal.
So it's not quite yet the perfect way to multiply, but it initially appears to be much closer than what anyone else has achieved, and with a little more work, could very well become the "perfect way to multiply" very big numbers!
Welcome to the blogosphere's toolchest! Here, unlike other blogs dedicated to analyzing current events, we create easy-to-use, simple tools to do the math related to them so you can get in on the action too! If you would like to learn more about these tools, or if you would like to contribute ideas to develop for this blog, please e-mail us at:
ironman at politicalcalculations
Thanks in advance!
Closing values for previous trading day.
This site is primarily powered by:
CSS Validation
RSS Site Feed
JavaScript
The tools on this site are built using JavaScript. If you would like to learn more, one of the best free resources on the web is available at W3Schools.com.
Other Cool Resources
Blog Roll
