pascals triangle in c with gmp

Question

I have problems that I have tried doing this with gmp.

/*
  This code is just to see exactly how much faster C is than python
  at doing numerically stuff. It should calculate the nth row of 
  pascals triangle.
  The way you use it is by calling the executable with the row
  you wish to compute as the only argument. For example if you 
  are on an *nix system:
  ./pascal 6 

  Or in a windows command prompt:
  pascal.exe 6
*/

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <gmp.h>

/*
  I decided to use a struct here because I thought it was ugly
  to have to pass around the length of my arrays in function 
  calls.
*/

typedef struct{
  int length; //length of the array
  int numbits; //number of bits allocated per val in vals
  mpz_t* vals; //pointer to start of array
} CoolArray;

//initArray allocates memory for the CoolArray.
void initArray(CoolArray* array, int length, int numbits); 

//destroyArray frees allocated memory in the struct.
void destroyArray(CoolArray* array);

//printArray prints the contents of the array.
void printArray(CoolArray* array);

//pascal computes the nth row of pascal's 
//triangle, with n being array->length,
//and stores the values in the array.
void pascal(CoolArray* array);

//setArray takes two CoolArrays of the same length
//and sets the values in the first to the values
//in the second.
void setArray(CoolArray* array1, CoolArray* array2);

int main(int argc, char** argv){
  int length = atoi(argv[1]);
  CoolArray array1;
  initArray(&array1, length, 800); //giving every int 800 bits of memory
  printf("Calculating the %dth row of pascals triangle...\n", length);
  pascal(&array1);
  printArray(&array1);
  destroyArray(&array1);
  return 0;
}

void initArray(CoolArray* array, int length, int numbits){
  assert(length>=1); //don't make arrays with a length <=0!!!
  array->length = length;
  array->vals = (mpz_t*) calloc(length, sizeof(mpz_t)); //first I allocate memory for vals...
  mpz_array_init(array->vals, length, numbits); //then I allocate memory for each val in vals
  return;
}

void destroyArray(CoolArray* array){
  int i=0;
  for(; i < array->length; ++i){ //first I go through the array and 
    mpz_clear(array->vals[i]); //clear the memory used for each val
  }
  free(array->vals); //then use free on the entire array
  return;
}

void pascal(CoolArray* array){
  assert(array->length >= 1);//making sure the length wasn't fiddled with...

  if(array->length == 1){
    mpz_set_ui(array->vals[0], (unsigned long int)1);
    return;
  }
  int row;
  int index;
  mpz_set_ui(array->vals[0], (unsigned long int)1); //if we aren't looking for the first row
  mpz_set_ui(array->vals[1], (unsigned long int)1);//then i'll start with the second row
  CoolArray current;
  initArray(&current, array->length, array->numbits); //current is a helper array
  for(row = 2; row < array->length; ++row){
    mpz_set_ui(current.vals[0], (unsigned long int)1); //set the first val to 1
    for(index = 1; index < row; ++index){
      mpz_add(current.vals[index], //set the value of this...
          array->vals[index],  //to this...
          array->vals[index-1]); //plus this.
    }
    mpz_set_ui(current.vals[row], (unsigned long int)1); //make the last number 1
    //printArray(&current);
    setArray(array, &current); //put every value in current into array
  }
  destroyArray(&current); //get rid of current
  return;
}

void setArray(CoolArray* array1, CoolArray* array2){
  assert(array1->length==array2->length);//making sure they are the same length
  int i=0;
  for(; i < array2->length; ++i){
    mpz_set(array1->vals[i], array2->vals[i]); //array1 is the array whose values are being set
  }
  return;
}

void printArray(CoolArray* array){
  int i=0;
  printf("[");
  for(; i < array->length; ++i){
    mpz_out_str(stdout, 10, array->vals[i]);
    if(i < (array->length - 1)) printf(", ");
    else printf("]\n");
  }
  return;
}

I am getting correct output, sorta. The values the print are correct, but I'm also getting a bunch of lines like this in the terminal along with the expected output:

gmpascal(80974) malloc: *** error for object 0x1008001a0: Non-aligned pointer being freed (2)
*** set a breakpoint in malloc_error_break to debug

Am I freeing the memory incorrectly in my function destroyArray? If so, what can I do to fix it, because as far as I know (from checking the gmp manual) is am doing this correctly. Or is it a problem with my gmp install?

EDIT: Okay, I thought I found the main problem when I realized I was passing a pointer to each element of my mpz_t array to mpz_clear, when I should have just been passing the mpz_t itself. I still get the above output when I run the program. But I still have this compiler warning:

gmpascal.c: In function ‘initArray’:
gmpascal.c:62: warning: passing argument 1 of ‘__gmpz_array_init’ from incompatible pointer type

Is this:

mpz_t array[length]; //length is an int
mpz_array_init(array, length, numbits); //and so is numbits

different from this:

mpz_t* array;
array = (mpz_t*) calloc(length, sizeof(mpz_t));
mpz_array_init(array, length, numbits);

?

The first is the example straight from the manual, and the second is how I wrote it in my code. I think that might be the problem, but I don't know why the two would be different.

Answer 1

sizeof(mpz_t) is of type size_t. On many moderns systems, size_t is not defined as int. You should declare the struct field as size_t numbits.