[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Improving gmp
From: |
Torbjorn Granlund |
Subject: |
Re: Improving gmp |
Date: |
11 Mar 2002 12:45:07 +0100 |
User-agent: |
Gnus/5.0807 (Gnus v5.8.7) Emacs/20.7 |
"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
- Improving gmp, coen dunnink, 2002/03/11
- Re: Improving gmp,
Torbjorn Granlund <=