Re: Mersenne: 128 floatingpoint operations
Could you tell me how to find this gmp library? I searched gnu.org site for it, but I couldn't find anything. The GMP homepage is at http://www.matematik.su.se/~tege/gmp/ It is linked from the Mersenne Freeware page at http://www2.netdoor.com/~acurry/mersenne/freeware.html If anyone has contributions to the Freeware page let me know, I have not gotten any updates for awhile.
Re: Mersenne: 128 floatingpoint operations
Thanks to the people who provided the references for gmp.
My own (very simple) gmp-based Lucas-Lehmer program follows below:
I wrote it mostly in order to make sure I understood what mprime was doing,
especially the Res64. As I mentionned, it is *WAY* slower than mprime,
even for primes far below 1,000,000. This is not at all surprising,
of course, given the algorithm that gmp uses for multiplication.
Even if gmp had a faster algorithm, mprime would *still* be faster
since it was optimized in machine-language.
Oh, btw, this was done in Linux. It probably works anywhere you have
gmp and a C compiler, though.
==
/*
lucaslehmer.c
Compute this program thus:
gcc lucaslehmer.c -lm -lgmp -O3 -Wall -o lucaslehmer
/
#include math.h
#include stdio.h
#include stdlib.h
#include gmp.h
unsigned long int p, i, j;
mpz_t pp, ll, aux;
int
main(int argc, char *argv[])
{
extern unsigned long int p, i, j;
extern mpz_t pp, ll, aux;
int k;
mpz_init(pp);
mpz_init(ll);
mpz_init(aux);
if ( argc == 1 )
{
fprintf(stderr,"lucaslehmer: usage: lucaslehmer p1 p2 ... pn\n");
}
else for ( k = 1 ; k argc ; k++ )
{
p = atol(argv[k]);
mpz_set_ui(ll,(long)(4));
mpz_ui_pow_ui(aux,(long)(2),p);
mpz_sub_ui(pp,aux,(long)(1));
for ( j = 1 ; j + 2 = p ; j++ )
{
mpz_powm_ui(aux,ll,(long)(2),pp);
mpz_sub_ui(ll,aux,(long)(2));
}
if ( mpz_sgn(ll) == 0 )
{
fprintf(stdout,"M%ld is a prime!\n",p);
}
else
{
mpz_fdiv_r_2exp(aux,ll,(long)(64));
fprintf(stdout,"M%ld is not a prime. Res64: ",p);
mpz_out_str(stdout,(int)(16),aux);
fprintf(stdout,"\n");
}
}
return(0);
}
Re: Mersenne: 128 floatingpoint operations
The library gmp (GNU multi-precision) uses this algorithm although it is much slower than FFT-like methods. Maybe because it only involves integers, and there is no danger at all of rounding errors. I once wrote a gmp-based program to perform LL tests: for low exponents it worked fine but for the prime 65537 it already took much longer that mprime. Could you tell me how to find this gmp library? I searched gnu.org site for it, but I couldn't find anything. __ Get Your Private, Free Email at http://www.hotmail.com
Re: Mersenne: 128 floatingpoint operations
Testing Mersenne primes involves a lot of multiplication (and division) of very large numbers, but better algorithms are used so that the multiplication time is something line O( n^2 log(n) log(log(n)) ). This is probably a typo: with FFT or similar methods multiplication time is aproximately O( n log(n) log log(n) ). BTW, there is a simple method, simple enough to be used by hand, which already reduces multiplication time to O( n^a ), where a = log 3 / log 2 = 1.584962501. In order to multiply two numbers with two digits each, say M = Ad + B and N = Cd + D, d being the base, we normally perform four multiplications: AC, AD, BC and BD in order to get the answer: MN = AC d^2 + (AD + BC) d + BD This expression however shows that AD and BC are never used alone: only the sum matters. This sum can be computed as AD + BC = (A+B)(C+D) - AC - BD; notice that AC and BD will be computed anyway so that now we perform three multiplications instead of four. We may recursively repeat this process in order to reduce the number of products from n^2 to n^a; true, there are many sums, but sums are cheap. The library gmp (GNU multi-precision) uses this algorithm although it is much slower than FFT-like methods. Maybe because it only involves integers, and there is no danger at all of rounding errors. I once wrote a gmp-based program to perform LL tests: for low exponents it worked fine but for the prime 65537 it already took much longer that mprime.
Re: Mersenne: 128 floatingpoint operations
At 11:47 AM 11/4/98 -0200, Nicolau Corcao Saldanha wrote: is something line O( n^2 log(n) log(log(n)) ). This is probably a typo: with FFT or similar methods multiplication time is aproximately O( n log(n) log log(n) ). That's right - my error. +--+ | Jud McCranie [EMAIL PROTECTED] | +--+
Mersenne: 128 floatingpoint operations
If our hardware can do 128-bit floating point operations in twice the time needed for similar 64-bit operations, then our overall time has improved by a factor of 2. Strange calculation. But I dont`t know how you came to this result. What I was always asking me is how fast fpu operation can be done. For normal integer addition, there is an algorithm in O(n) [with n as the bit lenght of number] and even one in O(log n to a base x) (i saw it in my book of digital engeniering). For integer multiplication you can prepare the n*n multiplication matrix in one step and add the numbers in 2*n*log n [O(n*log n)]. Maybe there are faster methods of doing this both. But for FPU addition you need shifts and comparing and so on. And for FPU multiplication you need truncating. Floatingpoint multiplication needs fewer steps but the first step (the pure multiplication) needs a lot of time. So it`s difficult to say what time a 128 bit FPU operation to perform, but with twice as fast ...? I will ask my assistent of system programming this question. Bojan
Re: Mersenne: 128 floatingpoint operations
At 04:01 PM 11/3/98 +0100, Bojan Antonovic wrote: If our hardware can do 128-bit floating point operations in twice the time needed for similar 64-bit operations, then our overall time has improved by a factor of 2. Strange calculation. But I dont`t know how you came to this result. Actually it is more than a factor of 2. I think this has been explained, but I'll try again. First multiply two general 5-digit numbers by hand, then multiply two 10-digit numbers. It will take you about 4 times as long to do the second multiplication because the manual method of multiplication takes O(n^2) time, where n is the number of digits. Testing Mersenne primes involves a lot of multiplication (and division) of very large numbers, but better algorithms are used so that the multiplication time is something line O( n^2 log(n) log(log(n)) ). 32-bit processors handle 32-bit arithmetic as quickly as they handle 16-bit or 8-bit arithmetic. 128-bit processors will handle 128-bit arithmetic as easily as 64-bit arithmetic. However, using 128-bit arithmetic instead of 64-bit arithmetic means that you cut the number of digits in the multiple-precision arithmetic in half. Stick in n/2 in place of n in (n^2)*log(n)*log(log(n)) and you will see that the ratio is more than 2, so using the larger number of bits will be more than twice as fast for multiplication and division. (It will be twice as fast on addition and subtraction.) +--+ | Jud McCranie [EMAIL PROTECTED] or @camcat.com | | | | Where a calculator on the ENIAC is equipped with 19,000 | | vacuum tubes and weighs 30 tons, computers in the future | | may have only 1,000 vacuum tubes and perhaps only weigh | | 1.5 tons.-- Popular Mechanics, March 1949. | +--+
