Search code examples
c++cloopsgmp

Issue with a while loop using GMP

I'm trying to code the extended Euclidean algorithm using the GMP library because I'm using large numbers. My algorithm is the basic one, just adapted for GMP numbers.

But I have a problem with my while loop. The code below is a minable reproducible example of my algorithm. I changed the content of the loop just for testing.

void euclid(mpz_t a, mpz_t b){


mpz_t r1, r2, u1, u2, v1, v2;

mpz_init_set_ui(u1, 1);
mpz_init_set_ui(v1, 0);
mpz_init_set_ui(u2, 0);
mpz_init_set_ui(v2, 1);

mpz_inits(r1, r2);

mpz_set(r1, a);
mpz_set(r2, b);

while(mpz_cmp_ui(r2, 0))
{
    gmp_printf("r2 : %Zd\n", r2);
    mpz_sub_ui(r2, r2, 1);

    mpz_t q;
    mpz_init(q);
}}

The loop doesn't seem to be executed.

Looking for the origin of the problem, I tried to simplify the loop and I get a problem (the loop doesn't execute anymore) whenever I add the line "mpz_init(q);". I called my function euclid with a equal to mpz_t 33 and b equal to mpz_t 5.

Solution

  • Problems like this ("I added a seemingly irrelevant variable/function call and the behaviour changed mysteriously") are almost always the result of Undefined Behaviour. In this case, the UB is in the line

    mpz_inits(r1, r2);

    which should have been

    mpz_inits(r1, r2, NULL);

    (See the docs). The list given to mpz_inits must be NULL-terminated so that the function knows when to stop; otherwise it will overwrite random memory.

    Valgrind is an invaluable tool for uncovering this kind of issue.