Making pascal's triangle with mpz_t's

Question

Hey, I'm trying to convert a function I wrote to generate an array of longs that respresents Pascal's triangles into a function that returns an array of mpz_t's. However with the following code:

mpz_t* make_triangle(int rows, int* count) {
//compute triangle size using 1 + 2 + 3 + ... n = n(n + 1) / 2
*count = (rows * (rows + 1)) / 2;
mpz_t* triangle = malloc((*count) * sizeof(mpz_t));

//fill in first two rows
mpz_t one;
mpz_init(one);
mpz_set_si(one, 1);
triangle[0] = one; triangle[1] = one; triangle[2] = one;

int nums_to_fill = 1;
int position = 3;
int last_row_pos;
int r, i;
for(r = 3; r <= rows; r++) {
    //left most side
    triangle[position] = one;
    position++;

    //inner numbers
    mpz_t new_num;
    mpz_init(new_num);
    last_row_pos = ((r - 1) * (r - 2)) / 2;
    for(i = 0; i < nums_to_fill; i++) {
        mpz_add(new_num, triangle[last_row_pos + i], triangle[last_row_pos + i + 1]);
        triangle[position] = new_num;
        mpz_clear(new_num);
        position++;
    }
    nums_to_fill++;

    //right most side
    triangle[position] = one;
    position++;
}

return triangle;
}

I'm getting errors saying: incompatible types in assignment for all lines where a position in the triangle is being set (i.e.: triangle[position] = one;).

Does anyone know what I might be doing wrong?

Answer 1

mpz_t is define as an array of length 1 of struct __mpz_struct, which prevents assignment. This is done because normal C assignment is a shallow copy and the various gmp numeric types store pointers to arrays of "limbs" that need to be deep copied. You need to use mpz_set or mpz_init_set (or even mpz_init_set_si) to assign MP integers, making sure you initialize the destination before using the former.

Also, you should call mpz_clear at most once for every mpz_init (they're like malloc and free in this regard, and for the same reasons). By calling mpz_init(new_nom) in the outer loop mpz_clear(new_num) in the inner loop, you're introducing a bug which will be evident when you examine the results of make_triangle. However, you don't even need new_num; initialize the next element of triangle and use it as the destination of mpz_add.

    mpz_init(triangle[position]);
    mpz_add(triangle[position++], triangle[last_row_pos + i], triangle[last_row_pos + i + 1]);

Small numeric optimization: you can update last_row_pos using an addition and subtraction rather than two subtractions, a multiplication and division. See if you can figure out how.