4 ms·

When I read "integer multiplication", I think of "123 * 456". Is that what is actually being said here? If so, why would you do anything but "123 * 456" to ar

by tobz 12y ago

When I read "integer multiplication", I think of "123 * 456". Is that what is actually being said here? If so, why would you do anything but "123 * 456" to arrive at the actual answer? I'm sure there's a reason, but reading your explanation sounds like the solution to something much harder than just multiplying two whole numbers.

dalke 12y ago
There are many ways to multiply. Some are faster than others. The typical grade school multiplication takes O(n * n) time. Other algorithms are asymptotically better than quadratic, and become more efficient when one has 1,000s of digits. Large numbers like these can occur in computer algebra problems, of which cryptography is a member. For more details, see http://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs http://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_m...
oakwhiz 12y ago
Using these types of multiplication algorithms can actually compute the result in fewer steps versus a naive algorithm when dealing with very large integers, such as integers used in cryptography.
- tobz 12y ago
  Makes sense. :)
- zxcdw 12y ago
  To add, there might be applications in for example bignum or other arbitrary precision math libraries/implementations.
jekub 12y ago
It is very easy to perform "123 * 456" but when each numbers have millions of digits it is a lot more complex. The naive algorithm require N^2 operation to multiply two numbers with N digits. This algorithm reduce this complexity. The most simple "fast" algorithm is the karatsuba multiplication. If you want to do "12 * 34" using the classical algorithm you will compute "12 * 3" and add "12 * 4 * 10". This need 4 single digit multiplications. (the * 10 is a simple shift) Karatsuba algorithm say that you can do "13100 + (1-2)(3-4)10 + 2*4" and get the same result. This imply only 3 single digit multiplications. (again the multiplications by power of 10 are simple shifts) Here the saving is small but if both of your numbers are N digits, you need 3 multiplication of N/2 digits that can be done recursively with the same algorithm for a final complexity around N^1.585 instead of N^2. Instead of splitting each number in two, you can split them in more pieces and reduce further the complexity. For big but not so big numbers you use the Karatsuba algorithm or the various Toom-Cook splitting, but with very big number you switch to the Schönhage-Strassen algorithm who use the FFT. All these algorithms works by transforming the numbers in polynoms, compute their convolution and convert back to integer. The Fürer algorithm is most efficient algorithm known for now but only theoretically, for pratical numbers we stick with Schönhage-Strassen. This paper introduce a new proof of the complexity of the Fürer algorithm as well as a few tricks to slightly improve it.
throwaway283719 12y ago
Well, sure, but the question is how you do "123 * 456". In binary you have the multiplication 111001000 x 1111011 and the traditional grade-school algorithm looks something like this 111001000 1110010000 00000000000 111001000000 1110010000000 11100100000000 111001000000000 --------------- 1101101100011000 122222221 so the answer is 1101101100011000, or 56088 in decimal. This method takes O(n^2) bitwise multiplications, where n is the number of bits in the larger of the two integers. Clearly if you're multiplying very large integers (say you're doing cryptography - the kind of computation that computers do millions of times every day) then there's clearly an interest in having faster algorithms for multiplication.
0x0 12y ago
Some CPUs do not have a built-in mul operator, only add and sub.
- cyorir 12y ago
  As I recall that includes the Z80 instruction set. I remember this because I wanted to program my Ti-83 with assembly rather than the included basic interpreter, and was surprised to learn that the CPU in my graphing calculator could only add, subtract, and move data around.
phkahler 12y ago
>> When I read "integer multiplication", I think of "123 * 456". Is that what is actually being said here? If so, why would you do anything but "123 * 456" to arrive at the actual answer? The paper is talking about methods to multiply integers of significant length. Think 2048bit RSA keys, or multi-million-bit numbers used in GIMPS. Of course you just use a single machine instruction for small numbers. But the hardware designers actually care about such algorithms too because it affects the number of gates and propagation delay. That said, this paper will likely only be relevant to large integer software implementations.
pfh 12y ago
Multiplication is like convolution, so FFT-like algorithms can speed it up, if that helps at all. >>> numpy.convolve([1,1,1],[1,1,1]) array([1, 2, 3, 2, 1]) >>> 111 * 111 12321

by tobz 12y ago

dalke 12y ago

There are many ways to multiply. Some are faster than others. The typical grade school multiplication takes O(n * n) time. Other algorithms are asymptotically better than quadratic, and become more efficient when one has 1,000s of digits. Large numbers like these can occur in computer algebra problems, of which cryptography is a member. For more details, see http://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs http://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_m...

oakwhiz 12y ago

Using these types of multiplication algorithms can actually compute the result in fewer steps versus a naive algorithm when dealing with very large integers, such as integers used in cryptography.

tobz 12y ago
Makes sense. :)
zxcdw 12y ago
To add, there might be applications in for example bignum or other arbitrary precision math libraries/implementations.

jekub 12y ago

It is very easy to perform "123 * 456" but when each numbers have millions of digits it is a lot more complex. The naive algorithm require N^2 operation to multiply two numbers with N digits. This algorithm reduce this complexity. The most simple "fast" algorithm is the karatsuba multiplication. If you want to do "12 * 34" using the classical algorithm you will compute "12 * 3" and add "12 * 4 * 10". This need 4 single digit multiplications. (the * 10 is a simple shift) Karatsuba algorithm say that you can do "13100 + (1-2)(3-4)10 + 2*4" and get the same result. This imply only 3 single digit multiplications. (again the multiplications by power of 10 are simple shifts) Here the saving is small but if both of your numbers are N digits, you need 3 multiplication of N/2 digits that can be done recursively with the same algorithm for a final complexity around N^1.585 instead of N^2. Instead of splitting each number in two, you can split them in more pieces and reduce further the complexity. For big but not so big numbers you use the Karatsuba algorithm or the various Toom-Cook splitting, but with very big number you switch to the Schönhage-Strassen algorithm who use the FFT. All these algorithms works by transforming the numbers in polynoms, compute their convolution and convert back to integer. The Fürer algorithm is most efficient algorithm known for now but only theoretically, for pratical numbers we stick with Schönhage-Strassen. This paper introduce a new proof of the complexity of the Fürer algorithm as well as a few tricks to slightly improve it.

throwaway283719 12y ago

Well, sure, but the question is how you do "123 * 456". In binary you have the multiplication 111001000 x 1111011 and the traditional grade-school algorithm looks something like this 111001000 1110010000 00000000000 111001000000 1110010000000 11100100000000 111001000000000 --------------- 1101101100011000 122222221 so the answer is 1101101100011000, or 56088 in decimal. This method takes O(n^2) bitwise multiplications, where n is the number of bits in the larger of the two integers. Clearly if you're multiplying very large integers (say you're doing cryptography - the kind of computation that computers do millions of times every day) then there's clearly an interest in having faster algorithms for multiplication.

0x0 12y ago

Some CPUs do not have a built-in mul operator, only add and sub.

cyorir 12y ago
As I recall that includes the Z80 instruction set. I remember this because I wanted to program my Ti-83 with assembly rather than the included basic interpreter, and was surprised to learn that the CPU in my graphing calculator could only add, subtract, and move data around.

phkahler 12y ago

>> When I read "integer multiplication", I think of "123 * 456". Is that what is actually being said here? If so, why would you do anything but "123 * 456" to arrive at the actual answer? The paper is talking about methods to multiply integers of significant length. Think 2048bit RSA keys, or multi-million-bit numbers used in GIMPS. Of course you just use a single machine instruction for small numbers. But the hardware designers actually care about such algorithms too because it affects the number of gates and propagation delay. That said, this paper will likely only be relevant to large integer software implementations.

pfh 12y ago

Multiplication is like convolution, so FFT-like algorithms can speed it up, if that helps at all. >>> numpy.convolve([1,1,1],[1,1,1]) array([1, 2, 3, 2, 1]) >>> 111 * 111 12321