- #1
- 2,844
- 0
'Schoolbook' multiplication takes [itex]O(n^2)[/itex] operations. Karatsuba multiplication takes [itex]O(n^{\lg 3})\approx O(n^{1.59})[/itex] operations. The best method I know of (which is only practical for very large numbers) is [itex]O(n \log n \log\log n)[/itex].
Is there a known nontrivial lower bound on the complexity of multiplication? I read a paper that discussed the time-(silicon) area tradeoff on multiplication, but I wasn't able to get a useful bound from that (caring only about the time and not knowing how to 'remove' the area):
The Area-Time Complexity of Binary Multiplication
Can anyone help me out here?
Is there a known nontrivial lower bound on the complexity of multiplication? I read a paper that discussed the time-(silicon) area tradeoff on multiplication, but I wasn't able to get a useful bound from that (caring only about the time and not knowing how to 'remove' the area):
The Area-Time Complexity of Binary Multiplication
Can anyone help me out here?