alt Hacker NewsFor large numbers, operations like addition don’t matter? Only multiplication? And now we want to find the fewest amount of multiplications?
Okay. No problem.
(ad + bc) = d + d .. + d + c + c .. + c
There we go, zero multiplications.
For large numbers, operations like addition don’t matter? Only multiplication? And now we want to find the fewest amount of multiplications?
Okay. No problem.
(ad + bc) = d + d .. + d + c + c .. + c
There we go, zero multiplications.
The article is explicit that addition is O(n), with n digits, which is cheaper than multiplication is believed to be. Naive multiplication is O(n*n) -- considerably less than your algorithm.