C++: Bibliothek zum Interpolieren von Polynomen und Finden von Polynomwurzeln

Ich fand die NTL-Interpolation nützlich, also unten ist die NTL-Interpolation mit geringfügigen Änderungen. Jetzt funktioniert es mit GMP mpz_t Typ Big Integer. Es wurde viele Male getestet und funktioniert gut (soweit ich es beobachtet habe).

Bemerkung: N ist Module. Die folgende Funktion ermöglicht die Interpolation eines Polynoms $f$ bei gegebenen $(a,b)$-Paaren (dh $(a_0,b_0),...,(a_n,b_n)$ ), wobei $f(a_i)= b_i$. Die Funktion gibt Koeffizienten des Polynoms $f$ zurück. Hier ist die Größe $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 scheint eine kostenlose C++-Bibliothek mit mehreren Genauigkeiten bereitzustellen, die das zu tun scheint, was Sie benötigen. Sie müssen jedoch für die Multithread-Unterstützung bezahlen.