C++: библиотека для интерполяции полинома и поиска корней полинома

Мне нужно знать, какую библиотеку, совместимую с C++, можно использовать для интерполяции многочлена. Таким образом, по заданным $n$ парам точка-значение он может восстановить полином. Библиотека должна поддерживать большие целые числа (множественной точности), так как мой полином определен в кольце полиномов R[x], где R — 1024-битное число.

Примечание. Я использовал NTL, но, по-видимому, он не поддерживает большие целые числа.

Ответы (2)

Я нашел интерполяцию NTL полезной, поэтому ниже интерполяция NTL с небольшими изменениями. Теперь он работает с большим целым числом типа GMP mpz_t. Он был протестирован много раз и отлично работает (насколько я наблюдал).

Примечание: N — модули. Приведенная ниже функция позволяет интерполировать многочлен $f$ по парам $(a,b)$ (т.е. $(a_0,b_0),...,(a_n,b_n)$ ), где $f(a_i)= б_и$. Функция возвращает коэффициенты многочлена $f$. Здесь размер равен $n$.

#include<gmp.h>
#include <gmpxx.h>
typedef mpz_t bigint;

bigint* interpolate(int size, bigint* a, bigint* b,bigint N) 
{
long m = size;
bigint* prod;
prod=(mpz_t*)malloc(size*sizeof(mpz_t));
prod = a;
bigint t1, t2;
mpz_init(t1);
mpz_init(t2);
int k, i;

bigint* res;
res=(mpz_t*)malloc(size*sizeof(mpz_t));
bigint aa;
for (k = 0; k < m; k++) {

  mpz_init_set(aa ,a[k]);
  mpz_init_set_str(t1,"1",10);
  for (i = k-1; i >= 0; i--) {
     mpz_mul(t1, t1, aa);
     mpz_mod(t1, t1,N);
     mpz_add(t1, t1, prod[i]);
  }

  mpz_init_set_str(t2,"0",10);
  for (i = k-1; i >= 0; i--) {
     mpz_mul(t2, t2, aa);
     mpz_mod(t2, t2,N);
     mpz_add(t2, t2, res[i]);
  }

  mpz_invert(t1, t1,N);
  mpz_sub(t2, b[k], t2);
  mpz_mul(t1, t1, t2);

  for (i = 0; i < k; i++) {
     mpz_mul(t2, prod[i], t1);
     mpz_mod(t2, t2,N);

     mpz_add(res[i], res[i], t2);
     mpz_mod(res[i], res[i],N);

  }

  mpz_init_set(res[k], t1);
  mpz_mod(res[k], res[k],N);
  if (k < m-1) {
     if (k == 0)
        mpz_neg(prod[0], prod[0]);
     else {
        mpz_neg(t1, a[k]);
        mpz_add(prod[k], t1, prod[k-1]);
        for (i = k-1; i >= 1; i--) {
           mpz_mul(t2, prod[i], t1);
           mpz_mod(t2, t2,N);

           mpz_add(prod[i], t2, prod[i-1]);
        }
        mpz_mul(prod[0], prod[0], t1);
        mpz_mod(prod[0], prod[0],N);

     }
  }
}

while (m > 0 && (res[m-1]==0)) m--;
return res;
}

alglib.net , кажется, предоставляет бесплатную библиотеку множественной точности С++ и, кажется, делает то, что вам нужно, хотя вам нужно платить за поддержку многопоточности.

Могу я спросить, пользовались ли вы им? Это не кажется очень перспективным.
нет, я не слышал, но кажется, что он был портирован на несколько языков и хорошо разработан с точки зрения функций и документации. что в нем не многообещающего?
Я думаю, что он не поддерживает полиномиальное кольцо.
C++: библиотека для интерполяции полинома и поиска корней полинома
СпросиСетьПолитика конфиденциальности1y, 0v