Changing from BigInteger to GMP

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:

Code:

---

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

Quote:

---

Originally Posted by SamstaUK

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.

Quote:

---

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

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

Quote:

---

Originally Posted by SamstaUK

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?

Quote:

---

Originally Posted by SamstaUK

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

---

No harm posting :)

Quote:

---

Originally Posted by laserlight

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!

Code:

---

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.