New answers tagged multiplication
0
votes
Linear time approximate multiplication
Upon further thought I realized the best there might be is a linear time algorithm to compute $ab+\ $ like $Θ(\sqrt{ab})$ (perhaps add a log factor) and then notice you can compute $ab$ to good ...
- 103
3
votes
Accepted
Linear time approximate multiplication
If you just want a $\Theta(ab)$ precision then we can just consider the binary representation of $a, b$, and we can easily get two "ceiling" power of 2:
$$
a' = \min \{ 2^w | 2^w \ge a\} \\
...
- 68
Top 50 recent answers are included