Mathematicians find an amazing trick to multiply bigger numbers

0
294
Karatsuba during a lecture
Anatoly Karatsuba developed the Karatsuba algorithm which is the first known divide and conquer algorithm for multiplication. (Credits - Wikimedia Commons)

The tables which were an amazing aid, pioneered first some 4000 years ago by the Babylonians is the most handy tool when it comes to multiplications. Well, its good for multiplication of small numbers but for bigger numbers , it becomes a bit tedious without the calculators and computers since we switch to the old school math of multiplying basically two numbers together. This method , though very accurate is slow since, for every single digit in a number , there needs to be a separate multiplication operation, before we add up the products. For every single digit in each number in the problem, you need to perform a separate multiplication operation, before adding all the products up.

Long multiplication is basically an algorithm, but not an efficient one, since the process is unavoidably pain-stricken. The problem is that as the numbers get bigger, the amount of work increases, represented by n raised to the power 2.

Well, the long multiplication algorithm was one of the most advanced multiplication algorithm we ever had until the 1960s, when a Russian mathematician, named Anatoly Karatsuba found that n raised to the power 1.58 was possible.

Soon after a decade, a pair of German mathematicians generated another shockwave with the most advanced breakthrough: the Schönhage–Strassen algorithm which in words of Harvey is- “They predicted that there should exist an algorithm that multiplies n-digit numbers using essentially n * log(n) basic operations,” as he posted his research paper which is yet to be peer- reviewed. However, It is in standard practice in mathematics to disseminate the results before undergoing any sort of peer review.

Using the Schönhage-Strassen algorithm and with new theoretical proof, it would take less than 30 minutes to solve the multiplication theoretically – and might be the fastest multiplication algorithm that is mathematically possible. Although the researchers have no idea about how big a number can they use to solve any multiplication problem using this method but the one they gave on the paper equates to 10214857091104455251940635045059417341952, which is really a very big number.

Fürer from Penn State University told the Science News that around a decade ago, he himself tried to make amendments the Schönhage-Strassen algorithm but eventually discontinued since it seemed quite hopeless to him. Now , that the mathematicians can verify it, his hopelessness has diminished.

In the meantime, Harvey and Joris van der Hoeven from École Polytechnique in France, say that their algorithm needs optimisation as they feel anxious if the results go wrong!

LEAVE A REPLY

Please enter your comment!
Please enter your name here