On 8 Jul 99, at 23:33, Lucas Wiman wrote:
That is going to be a *lot* slower than FFT convolution, for numbers the size
of the Mersenne numbers we're testing! FFT is O(n*log(n)) where n is the
number of limbs in the numbers being multiplied. Head's method is O(n^2),
with O being slightly
At 06:51 PM 7/9/99 +0100, Brian J. Beesley wrote:
For reasonably small multi-precision numbers, Head's method is
actually very good, if you're working on a true RISC processor with
no integer multiply instruction.
I started using Head's algorithm in 1981 on my Apple II. It was better
than
All,
In the book _Primes and Programming_ Head's method of multiplying
two numbers mod n is mentioned. Is this actually more effiecient
than simply multiplying the two numbers and taking the modulus?
If so, is it implemented in the various mersenne factoring programs
in use?
Thankyou,
Lucas
At 06:19 AM 7/8/99 -0400, you wrote:
All,
In the book _Primes and Programming_ Head's method of multiplying
two numbers mod n is mentioned. Is this actually more effiecient
than simply multiplying the two numbers and taking the modulus?
Yes, because it keeps the numbers smaller. It was
On Thu, 08 Jul 1999, Brian J. Beesley wrote:
On 8 Jul 99, at 6:19, Lucas Wiman wrote:
In the book _Primes and Programming_ Head's method of multiplying
two numbers mod n is mentioned. Is this actually more effiecient
than simply multiplying the two numbers and taking the modulus?
At 08:11 PM 7/8/99 -0400, Pierre Abbat wrote:
That is going to be a *lot* slower than FFT convolution, for numbers the size
of the Mersenne numbers we're testing!
Head's algorithm is for getting x*y mod n when 0=x,yn; and n is such that
nM but n^2M, where M is the largest integer you can store
Hi folks
In the book _Primes and Programming_ Head's method of multiplying
two numbers mod n is mentioned. Is this actually more effiecient
than simply multiplying the two numbers and taking the modulus?
Look at it this way. Head's method is essentially binary long
multiplication,
Limbs? It is good to know that the world has many different literal meanings
in many languages for "bits" - variety is good for us all. (The French word
for "buffer" is also, I seem to remember, rather amusing).
"Limb" is the term used in gmp for a digit in a large base (such as 2147483648)
Pierre Abbat writes:
In the book _Primes and Programming_ Head's method of multiplying
two numbers mod n is mentioned. Is this actually more efficient
than simply multiplying the two numbers and taking the modulus?
Look at it this way. Head's method is essentially binary long
