Read the Beforeitsnews.com story here. Advertise at Before It's News here.
Profile image
By Political Calculations (Reporter)
Contributor profile | More stories
Story Views
Now:
Last hour:
Last 24 hours:
Total:

A Faster Way to Multiply Really Big Numbers

% of readers think this story is Fact. Add your two cents.


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!

Properties of Numbers Being Multiplied
Input Data Values
Number of Digits
Number of Operations Needed to Multiply Two Numbers
Calculated Results Values
Traditional Multiplication Method
Theoretical “Most Efficient” Method
Percentage Reduction

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!


Source: https://politicalcalculations.blogspot.com/2019/04/a-faster-way-to-multiply-really-big.html


Before It’s News® is a community of individuals who report on what’s going on around them, from all around the world.

Anyone can join.
Anyone can contribute.
Anyone can become informed about their world.

"United We Stand" Click Here To Create Your Personal Citizen Journalist Account Today, Be Sure To Invite Your Friends.

Please Help Support BeforeitsNews by trying our Natural Health Products below!


Order by Phone at 888-809-8385 or online at https://mitocopper.com M - F 9am to 5pm EST

Order by Phone at 866-388-7003 or online at https://www.herbanomic.com M - F 9am to 5pm EST

Order by Phone at 866-388-7003 or online at https://www.herbanomics.com M - F 9am to 5pm EST


Humic & Fulvic Trace Minerals Complex - Nature's most important supplement! Vivid Dreams again!

HNEX HydroNano EXtracellular Water - Improve immune system health and reduce inflammation.

Ultimate Clinical Potency Curcumin - Natural pain relief, reduce inflammation and so much more.

MitoCopper - Bioavailable Copper destroys pathogens and gives you more energy. (See Blood Video)

Oxy Powder - Natural Colon Cleanser!  Cleans out toxic buildup with oxygen!

Nascent Iodine - Promotes detoxification, mental focus and thyroid health.

Smart Meter Cover -  Reduces Smart Meter radiation by 96%! (See Video).

Report abuse

    Comments

    Your Comments
    Question   Razz  Sad   Evil  Exclaim  Smile  Redface  Biggrin  Surprised  Eek   Confused   Cool  LOL   Mad   Twisted  Rolleyes   Wink  Idea  Arrow  Neutral  Cry   Mr. Green

    MOST RECENT
    Load more ...

    SignUp

    Login

    Newsletter

    Email this story
    Email this story

    If you really want to ban this commenter, please write down the reason:

    If you really want to disable all recommended stories, click on OK button. After that, you will be redirect to your options page.