Content deleted Content added
No edit summary |
m de-orphan peasant multiplication |
||
Line 2:
A major advantage of [[number system|positional number system]]s over other systems of writing down numbers is that they facilitate the usual grade-school method of '''long multiplication''': multiply the first number with every digit of the second number and then add up all the properly shifted results. In order to perform this algorithm, one needs to know the products of all possible digits, which is why [[multiplication table]]s have to be memorized. Humans use this algorithm in base 10, while computers employ the same algorithm in base 2. The algorithm is a lot simpler in base 2, since the multiplication table has only 4 entries. Rather than first computing the products, and then adding them all together in a second phase, computers add the products to the result as soon as they are computed. Modern chips implement this algorithm for 32-[[bit]] or 64-[[bit]] numbers in [[hardware]] or in [[microcode]]. To multiply two numbers with ''n'' digits using this method, one needs about ''n''<sup>2</sup> operations. More formally: the time complexity of multiplying two ''n''-digit numbers using long multiplication is [[Big O|Θ]](''n''<sup>2</sup>).
An old method for multiplication, that doesn't require multiplication tables, is the [[Peasant multiplication]] algorithm; this is actually a method of multiplication using base 2.
For systems that need to multiply huge numbers in the range of several thousand digits, such as [[computer algebra system]]s and [[bignum]] libraries, this algorithm is too slow.
| |||