Optimiser la conversion entre la liste des coefficients entier et sa longue représentation entier

Que diriez-vous de mettre en œuvre directement des polynômes entier de précision arbitraire en tant que liste de tableaux numpus?

Permettez-moi d'expliquer: dites que votre polynôme est _{p a p x ^{p . Si le gros entier A P peut être représenté sous la forme d'un p = σ k a p, k 2 64 K alors le tableau K TH NUMPY contiendra le 64 bits Int A P, K à la position p.}}

Vous pouvez choisir des matrices denses ou rares en fonction de la structure de votre problème.

La mise en œuvre des opérations d'addition et scalaires ne consiste à viller à vectoriser la mise en œuvre de Bignum des mêmes opérations.

Multiplication pourrait être traité comme suit: ab = σ _{p, k, p ', k' a p, k b p ', k' < / sub> 2 ^{64 (k + k ') x p + p' . Donc, une implémentation naïve avec des érayes denses pourrait conduire à un journal 64 (n) 2 appels vers numpy.convole ou scipy.fftconvolve < / code>.}}

L'opération MODULO doit être facile à appliquer car il s'agit d'une fonction linéaire du terme main gauche et du terme à droite contient de petits coefficients.

edit Voici quelques explications supplémentaires

au lieu de représenter le polynôme sous forme de liste de nombres de précision arbitraires (représentés eux-mêmes comme des listes de "chiffres" 64 bits), transpose la représentation de sorte que:

• Votre polynôme est représenté comme une liste de tableaux
• La matrice K TH contient le K TH "chiffre" de chaque coefficient

  Si que seuls quelques-uns de vos coefficients sont très volumineux, les matrices auront la plupart du temps 0 à celles-ci afin que cela puisse valoir la peine d'utiliser des tableaux de rattrapage.

  Appelez A _{P, K LE K ^{TH DIGIT du p TH coefficient.}}

  Notez l'analogie avec de grandes représentations entier: où un grand nombre d'entiers serait représenté comme

  x = σ _{k x k 2 ^{64 k}}

  Votre polynôme A est représenté de la même manière que

  a = σ _{k a k 2 ^{64 k A k = σ k a p, k x p}}

  Pour implémenter l'addition, vous prétendez simplement que votre liste de tableaux est une liste de chiffres simples et de mettre en œuvre l'addition comme d'habitude pour les grands entiers (observez-vous pour remplacer si alors conditionnels par Numpy.Lowle ).

  Pour implémenter la multiplication, vous trouverez que vous devez créer un journal 64 (n) 2 multiplications polynomiales.

  Pour mettre en œuvre l'opération MODULO sur les coefficients, c'est à nouveau un cas simple de traduction de l'opération de modulo sur un grand nombre d'entiers.

  Pour prendre le modulo par un polynôme avec de petits coefficients, utilisez la linéarité de cette opération:

  un mod (x ^{r - 1) = (σ _{k a k 2 64 k ) mod (X r - 1)}}

  = σ _{k 2 ^{64 k (A k mod (x r - 1))}}