Content deleted Content added
Added brief description of the Toom-Cook method |
m disambig Haskell |
||
Line 44:
The major improvement in this algorithm arises because the number of operations required is O(log y) rather than O(y). For numbers which can be represented directly as computer words a further benefit is that multiplying by 2 is equivalent to an arithmetic shift left, while division by 2 is equivalent to an arithmetic shift right. Clearly the major benefits arise when y is very large in which case it will not be possible to represent it as a single computer word.
This may not help so much for multiplication by [[real number|real]] or [[complex number|complex]] values, but is useful for multiplication of very large integers ("[[bignum]]s") which are supported in some programming languages such as [[ Haskell programming language|Haskell]],
[[Ruby programming language|Ruby]], and
[[Common Lisp]].
| |||