Changing from BigInteger to GMP

[SamstaUK]

I have this code which previously used the BigInteger library, however now I have GMP installed and I want to use that instead.

I have read the manual but I cannot figure out how to use GMP in this function without getting errors.

Here is the function:

int lucas(long p){ //p is a number in the range of 2 up to 50,000,000, possibly bigger
	int s = 4; //previously assigned as a big integer
	int z; //used in the for loop below
	int M = 2; //previously assigned as a big integer
	for(z = 1; z < p; z++){ //this accomplishes the same as 2 to the power of p, and is stored in M
		M *= 2;
	}
	M--; 
	int i; //used for the loop below
	for(i = 3; i <= p; i++){
		s = ((s * s) - 2) % M; //this where the bulk of the work happens
	}
		if(s == 0){ 
			return(2); //if s is 0, 2^p - 1 is prime
		}
		else
		{
			return(1); //if anything else it isn't
		}
}

I can initialize variables using the gmp library, but when I'm trying to use the mpz_pow_ui() function I get errors because it wants me to use long integers, which are too small for the numbers I want to work with.

How can I re-write this function to use GMP?

Thank You

[Paul McKenzie]

I have read the manual but I cannot figure out how to use GMP in this function without getting errors.

How about forgetting ths particular function and writing very simple programs to get familiar with how the GMP library works?

That is how any programmer goes about using a new library, function, etc. They write simple programs to see how things work first, way before they attempt to use that new library/function/class/etc.. in their larger application.

mpz_pow_ui() function I get errors because it wants me to use long integers,

I have never used GMP, but the type is an MP_INT as far as I see with just using google and doing a web search. MP_INT is a struct of two integer types. So it is not a long.

Regards,

Paul McKenzie

[SamstaUK]

I was wondering if I should post my solution or is it unlikely someone will have the same problem as me?

[laserlight]

I can initialize variables using the gmp library, but when I'm trying to use the mpz_pow_ui() function I get errors because it wants me to use long integers, which are too small for the numbers I want to work with.

I notice that you have a comment that states that "p is a number in the range of 2 up to 50,000,000, possibly bigger". The upper bound of unsigned long is guaranteed to be at least 4 billion, so are you sure that p will really have a value outside of the range of unsigned long?

I was wondering if I should post my solution or is it unlikely someone will have the same problem as me?

No harm posting

[SamstaUK]

I notice that you have a comment that states that "p is a number in the range of 2 up to 50,000,000, possibly bigger". The upper bound of unsigned long is guaranteed to be at least 4 billion, so are you sure that p will really have a value outside of the range of unsigned long?

It wont have values that high unless I'm checking the highest prime numbers which have been discovered, it's nice to be prepared though

Here is the function using GMP, I would estimate it's 100x faster than BigInteger, possibly even faster!

int lucas(long p) {
    mpz_t s;
    mpz_init(s);
    mpz_set_ui(s, 4);
    mpz_t M;
    mpz_init(M);
    mpz_set_ui(M, 2);
    mpz_pow_ui(M, M, p);
    mpz_sub_ui(M, M, 1);
    int i;

    for(i = 3; i <= p; i++) {
        mpz_mul(s, s, s);
        mpz_sub_ui(s, s, 2);
        mpz_mod(s, s, M);
    }

    if(mpz_cmp_ui(s, 0) == 0) {
        return(2);
    }
    else
    {
        return(1);
    }
}

If I could find a way to parallelise those lines in bold, I would be able to find primes a lot faster. The highest prime I have found so far is (2^23209)-1 which took me all day yesterday, running 8 separate instances of the program.

Any ideas on how I would do that? I can't see any immediately obvious way.