5 ms·
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.
by moi2388 2mo ago
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.
- entrope 2mo agoThe 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.
- moi2388 2mo agoMy algorithm is O(n+n+..n) which is O(n), since there we also ignore addition fortunately :D
- AlotOfReading 2mo agoIt would only be O(n) if the number of additions was constant. Here it varies with the size of the multiplier, giving us O(n*m).