New Way to Multiply Large Numbers

Thanks, that's fascinating. Never thought there was an easier way to multiply!

https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/

Interesting that the article fails to demonstrate how the process actually works.

It looks like multiplying units x units and tens x tens is the same for both methods. Calculating the cross products (tens x units) is what is different.

Traditional Method: (10a+b)(10c+d)=100ac+10ad+10bc+bd.

The cross product terms are 10(ad+bc).

Karatsuba Method:

Cross product terms are 10((a+b)(c+d)-ac-bd)=

10(ac+ad+bc+bd-ac-bd)=10(ad+bc)

But this isn't algorithm the article eventually asserts is the most efficient. I expect that is because although it takes fewer single digit calculations that one not as easy to explain in the number of words allowed.

Still interesting. I think this may be part of the basis (and confusion) of how math is taught now. There are multiple paths to the correct answer and which one is taken is not as rigidly held as the only best one.

You're right, the method described, Karatsuba, is not the most efficient, and it took a little head scratching to figure out what they were doing. It would be interesting to see if the other methods also optimize the cross products.

It looks like the efficiency is best if both numbers have the same number of digits and the length is 2^N, as is the case with the Fast Fourier Transform (FFT).

Lots of times a particular problem can be solved more easily by a variety of tricks. There are books that describe math shortcuts. For example, in this case, 25 x 63, 25 is 1/4 of 100 and 63 is 4 x 15 with 3 left over, so the product is 1500+75.

I wonder if this will have an effect on encryption security?

It seems to me that with computers the process requires many fewer steps. Each decimal number is converted to binary, then the numbers are ‘multiplied’ using the add+shift method.

There are much better ways than what has been offered here. Quickest is a calculator. After all, we have all been trained be lazy and to embrace Ai, so why not make it work.

https://www.youtube.com/watch?v=ounv5h5wjDw

A real cool calculator in this link.

https://www.youtube.com/watch?v=e4PTvXtz4GM

Different but not better. It's like the new math they teach in elementary school now. Is this it? It's the only method my kids were taught before being handed a calculator. It's probably to discourage them from ever using a pencil and paper to multiply or divide. Try 81 x 72. Which is easier, carrying over or adding sideways in your head.