| FazBrowse Wikipedia Viewer | Main Page | | |
| Viewing: https://en.wikipedia.org/wiki/Multiplication_algorithm |
| Contents |
|---|
| Usage in computers |
| Lattice multiplication |
| Russian peasant multiplication |
| Description |
| Examples |
| Schönhage–Strassen |
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much research into the topic.
The oldest and simplest method, known since antiquity as long multiplication or grade-school multiplication, consists of multiplying every digit in the first number by every digit in the second and adding the results. This has a time complexity of O(nlognloglogn). In 2007, Martin Fürer proposed an algorithm with complexity O(nlogn22log∗n) in 2018. In 2019, Harvey and van der Hoeven came up with a galactic algorithm with complexity multiply(a[1..p],b[1..q],base)// Operands containing rightmost digits at index 1 product=[1..p+q]// Allocate space for result forb_i=1toq// for all digits in b carry=0 fora_i=1top// for all digits in a product[a_i+b_i-1]+=carry+a[a_i]*b[b_i] carry=product[a_i+b_i-1]/base product[a_i+b_i-1]=product[a_i+b_i-1]modbase product[b_i+p]=carry// last digit comes from final carry returnproduct
Some chips implement long multiplication, in hardware or in microcode, for various integer and floating-point word sizes. In arbitrary-precision arithmetic, it is common to use long multiplication with the base set to 2, 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 operations. More formally, multiplying two n-digit numbers using long multiplication requires Θ(n) single-digit operations (additions and multiplications).
When implemented in software, long multiplication algorithms must deal with overflow during additions, which can be expensive. A typical solution is to represent the number in a small base, b, such that, for example, 8b is a representable machine integer. Several additions can then be performed before an overflow occurs. When the number becomes too large, we add part of it to the result, or we carry and map the remaining part back to a number that is less than b. This process is called normalization. Richard Brent used this approach in his Fortran package, MP.
Computers initially used a very similar algorithm to long multiplication in base 2, but modern processors have optimized circuitry for fast multiplications using more efficient algorithms, at the price of a more complex hardware realization. ((x << 2) + x) << 1 # Here 10*x is computed as (x*2^2 + x)*2 (x << 3) + (x << 1) # Here 10*x is computed as x*2^3 + x*2
In some cases such sequences of shifts and adds or subtracts will outperform hardware multipliers and especially dividers. A division by a number of the form 300 40 90 + 12 ———— 442
| × | 30 | 4 |
|---|---|---|
| 10 | 300 | 40 |
| 3 | 90 | 12 |
followed by addition to obtain 442, either in a single sum (see right), or through forming the row-by-row totals
This calculation approach (though not necessarily with the explicit grid arrangement) is also known as the partial products algorithm. Its essence is the calculation of the simple multiplications separately, with all addition being left to the final gathering-up stage.
The grid method can in principle be applied to factors of any size, although the number of sub-products becomes cumbersome as the number of digits increases. Nevertheless, it is seen as a usefully explicit method to introduce the idea of multiple-digit multiplications; and, in an age when most multiplication calculations are done using a calculator or a spreadsheet, it may in practice be the only multiplication algorithm that some students will ever need.
One column contains the numbers that result from repeatedly halving the multiplier while ignoring the remainder. Another column beside it contains the results of repeatedly doubling the multiplicand. The product is evaluated by crossing out each row where the first number ends in an even digit, then summing up the remaining numbers in the second column in order to obtain the product.
This example uses peasant multiplication to multiply 11 by 3 to arrive at a result of 33.
Decimal: Binary: 11 3 1011 11 5 6 101 110 2 12 10 1100 1 24 1 11000 —— —————— 33 100001Describing the steps explicitly:
The method works because multiplication is distributive, so:
Currently, the algorithm with the best computational complexity is a 2019 algorithm of David Harvey and Joris van der Hoeven, which uses the strategies of using number-theoretic transforms introduced with the Schönhage–Strassen algorithm to multiply integers using only y be represented as m less than y=y1Bm+y0,
where Bm. The product is then
z1=x1y0+x0y1,
If we express this in fewer terms, we get:
c(i,j)∈{0,1}
Another method of multiplication is called Toom–Cook or Toom-3. The Toom–Cook method splits each number to be multiplied into multiple parts. The Toom–Cook method is one of the generalizations of the Karatsuba method. A three-way Toom–Cook can do a size-3N multiplication for the cost of five size-N multiplications. This accelerates the operation by a factor of 9/5, while the Karatsuba method accelerates it by 4/3.
Although using more and more parts can reduce the time spent on recursive multiplications further, the overhead from additions and digit management also grows. For this reason, the method of Fourier transforms is typically faster for numbers with several thousand digits, and asymptotically faster for even larger numbers.
Furthermore, multiplication of two numbers could be thought of as a product of two polynomials:
Bk
in the product is O(nlogn⋅2Θ(log∗(n))) using Fourier transforms over complex numbers, where log denotes the iterated logarithm. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using modular arithmetic in 2008 achieving the same running time. In context of the above material, what these latter authors have achieved is to find N much less than 2 + 1, so that Z/NZ has a (2m)th root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.In 2014, Harvey, Joris van der Hoeven and Lecerf gave a new algorithm that achieves a running time of O(nlogn⋅22log∗n) but whose validity relies on standard conjectures about the distribution of Mersenne primes. In 2016, Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of Fermat primes that conjecturally achieves a complexity bound of O(n log n) multiplication algorithm. It was published in the Annals of Mathematics in 2021. Because Schönhage and Strassen predicted that n log(n) is the "best possible" result, Harvey said: "...(a+bi)(c+di)=(ac−bd)+(bc+ad)i.
Or
| View original on Wikipedia | Back | FazBrowse Home |