News for hackers. Stuff that matters.
Re:Even faster integer multiplication by throwaway283719 on Tuesday July 15, 2014 @08:36AM (#8036028)
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.

There are no comments on this comment yet.