Content deleted Content added
removing section on asymmetric formula (appears to be cruft), restructured to look more like a theoretical algorithm analysis |
→Recursive application: absurd to convert to dec |
||
Line 80:
If ''n'' is four or more, the three multiplications in Karatsuba's basic step involve operands with fewer than ''n'' digits. Therefore, those products can be computed by [[recursion|recursive]] calls of the Karatsuba algorithm. The recursion can be applied until the numbers are so small that they can (or must) be computed directly.
In a computer with a full 32-bit by 32-bit [[Binary multiplier|multiplier]], for example, one could choose ''B'' = 2<sup>31</sup>
===[[Time complexity]] analysis===
| |||