Re: Improving gmp

[Torbjorn Granlund]

"coen dunnink" <address@hidden> writes:

 I want to make an improvement for multiplications with to integers of
  the same length. Split them up and then multiply again. Like Say 2
  numbers x and y of each 100 bits. Then:
  x * y = (2^50 * x1 + x2)  * (2^50 * y1 + y2)
        = (2^100 * x1 * y1) + (2^50 * x1 * y2) + (2^50 * x2 *y1) + ( x2 * y2)

I cannot see how that could lead to an improvement.  As a matter
of fact, I cannot see how to define x(k) and y(k) to make your
formula correct, but if that is infact possible, I cannot see how
it could be an improvement to trade an 100-bit multiplication for
three 50-bit multiplications.

For the algorithms implemented in GMP today, please check the gmp
documentation that come with the releases.  You could also check
the online documentation:
http://swox.com/gmp/manual/Multiplication-Algorithms.html

-- 
Torbjörn