Hacker News Reader

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.

View on HN

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.

My algorithm is O(n+n+..n) which is O(n), since there we also ignore addition fortunately :D

It 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).

Reply on news.ycombinator.com