Создание треугольника Паскаля с помощью mpz_t - PullRequest
Новая
       18

Создание треугольника Паскаля с помощью mpz_t

0 голосов
/ 29 апреля 2010

Эй, я пытаюсь преобразовать написанную мной функцию для генерации массива длин, представляющего треугольники Паскаля, в функцию, которая возвращает массив mpz_t. Однако со следующим кодом: 

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;
}

Я получаю сообщения об ошибках: несовместимые типы в присваивании для всех линий, в которых устанавливается позиция в треугольнике (т.е. треугольник [position] = one;).

Кто-нибудь знает, что я могу делать неправильно?

1 Ответ

3 голосов
/ 30 апреля 2010

mpz_t определяется как массив длиной 1 из struct __mpz_struct, что предотвращает присвоение. Это сделано потому, что обычное присвоение C - это мелкая копия, а различные числовые типы gmp хранят указатели на массивы "limbs" , которые необходимо глубоко копировать. Вам необходимо использовать mpz_set или mpz_init_set (или даже mpz_init_set_si) для назначения целых чисел MP, убедившись, что вы инициализировали пункт назначения перед использованием первого.

Кроме того, вы должны вызывать mpz_clear самое большее один раз для каждого mpz_init (они похожи на malloc и свободны в этом отношении и по тем же причинам). Вызывая mpz_init(new_nom) во внешнем цикле mpz_clear(new_num) во внутреннем цикле, вы вводите ошибку, которая станет очевидной при рассмотрении результатов make_triangle. Тем не менее, вам даже не нужно new_num; инициализируйте следующий элемент triangle и используйте его в качестве пункта назначения mpz_add. 

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

Небольшая числовая оптимизация: вы можете обновить last_row_pos, используя сложение и вычитание, а не два вычитания, умножение и деление. Посмотри, сможешь ли ты выяснить как.

...