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
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 sli
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
>>
> 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)
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
> > mult
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,yM, where M is the largest integer you can store in a format
native to the com
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?
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?
Look at it this way. Head's method is essentially bin
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 ori
At 06:19 AM 7/8/99 -0400, 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?
No it is actually much less efficient, but you are mi
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 Wim
11 matches
Mail list logo