Content deleted Content added
→Optimizing space complexity: wikilink Theta |
→Usage in computers: suggest to link (via redirect) to appropriate section |
||
Line 98:
Some [[Integrated circuit|chips]] implement this algorithm for various integer and floating-point sizes in [[computer hardware]] or in [[microcode]]. In [[arbitrary-precision arithmetic]], it's common to use long multiplication with the base set to 2<sup>''w''</sup>, where ''w'' is the number of bits in a word, for multiplying relatively small numbers.
To multiply two numbers with ''n'' digits using this method, one needs about ''n''<sup>2</sup> operations. More formally: using a natural size metric of number of digits, the time complexity of multiplying two ''n''-digit numbers using long multiplication is [[
When implemented in software, long multiplication algorithms have to deal with overflow during additions, which can be expensive. For this reason, a typical approach is to represent the number in a small base ''b'' such that, for example, 8''b'' is a representable machine integer (for example Richard Brent used this approach in his Fortran package MP<ref>Richard P. Brent. A Fortran Multiple-Precision Arithmetic Package. Australian National University. March 1978.</ref>); we can then perform several additions before having to deal with overflow. When the number becomes too large, we add part of it to the result or carry and map the remaining part back to a number less than ''b''; this process is called ''normalization''.
| |||