2

我有问题，我试过用 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;
}

我得到了正确的输出，排序。打印的值是正确的，但我在终端中也得到了一堆这样的行以及预期的输出：

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

我是否在我的函数中错误地释放了内存destroyArray？如果是这样，我该怎么做才能解决它，因为据我所知（通过检查 gmp 手册）正在正确地执行此操作。还是我的 gmp 安装有问题？

编辑：好的，当我意识到我将指向我的 mpz_t 数组的每个元素的指针传递给 mpz_clear 时，我 认为我发现了主要问题，而我应该只是传递 mpz_t 本身。当我运行程序时，我仍然得到上述输出。但我仍然有这个编译器警告：

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

这是：

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

与此不同：

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

?

第一个是直接来自手册的示例，第二个是我在代码中的编写方式。我认为这可能是问题所在，但我不知道为什么两者会有所不同。

4

2 回答 2

0

sizeof(mpz_t)是类型size_t。在许多现代系统上，size_t不定义为int. 您应该将结构字段声明为size_t numbits.

于 2012-10-25T12:46:20.950 回答
0

我最近回到了这个问题，我找到了一个效果很好的解决方案。我认为我的原始代码的问题之一是mpz_clear当文档说不使用mpz_clearwith时我正在使用mpz_array_init。无论如何，该mpz_array_init功能现在已被弃用，我的工作代码不使用它。

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

#define BASE 10


void usage(){
  puts("triangle N");
  puts("  Prints N rows of Pascal's triangle.");
}


mpz_t *new_row(size_t row_length){
  mpz_t *row = malloc(sizeof *row * row_length);
  size_t i;
  for(i = 0; i < row_length; i += 1)
    mpz_init(row[i]);
  return row;
}


void free_row(mpz_t *row, size_t row_length){
  size_t i;
  for(i = 0; i < row_length; i += 1)
    mpz_clear(row[i]);
  free(row);
}


void print_row(mpz_t *row, size_t length){
  // Prints an array of mpz_t.

  // Find the size in digits of the biggest number first, then allocate that much memory + 2 to hold the encoded ints.
  size_t max_encode_len = mpz_sizeinbase(row[0], BASE);
  size_t i;
  for(i = 0; i < length; i += 1){
    size_t encode_len = mpz_sizeinbase(row[i], BASE);
    if(encode_len > max_encode_len)
      max_encode_len = encode_len;
  }

  //mpz_get_str overwrites our allocated space every time and adds a null terminator.
  char *encoded_int = malloc(sizeof *encoded_int * max_encode_len + 2);
  for(i = 0; i < (length - 1); i += 1){
    mpz_get_str(encoded_int, BASE, row[i]);
    printf("%s ", encoded_int);
  }
  mpz_get_str(encoded_int, BASE, row[length - 1]);
  printf("%s\n", encoded_int);
  free(encoded_int);
}


int main(int argc, char **argv){
  if(argc != 2){
    puts("Incorrect number of arguments.");
    usage();
    return 1;
  }

  int n = atoi(argv[1]);
  if(n < 1){
    puts("Input needs to be an int greater than 0.");
    usage();
    return 1;
  }

  mpz_t *row_a = new_row(n);
  mpz_t *row_b = new_row(n);
  mpz_t *row_temp;

  // Every row starts with 1.
  mpz_set_ui(row_a[0], 1UL);
  mpz_set_ui(row_b[0], 1UL);

  size_t i;
  for(i = 1; i < n; i += 1){
    print_row(row_a, i);
    size_t j;
    for(j = 1; j < (i + 1); j += 1)
      mpz_add(row_b[j], row_a[j - 1], row_a[j]);
    row_temp = row_a;
    row_a = row_b;
    row_b = row_temp;
  }
  print_row(row_a, n);

  free_row(row_a, n);
  free_row(row_b, n);
  return 0;
}
于 2019-09-18T07:39:21.513 回答