Multiplication de grands entiers
- 2 entiers représentés par des suites de n chiffres
à une base B
- souvent calcul en virgule flottante donne un résultat
acceptable, mais ...
- déjà vu un algorithme en temps O(nlog3)
- mais on peut faire mieux encore
multiplication par convolution
- par exemple c3=a0b3+a1b2+a2b1+a3b0
- calcul de la convolution suivi d'une petite étape de
correction quand les éléments de
la convolution sont > =B
convolution par multiplication de polynômes
- les éléments de la convolution sont les
coefficients du produit des deux polynômes
dont les coefficients étaient les ai et les bi
- pas surprenant si on regarde le résultat de la
substitution de B (la base) pour x
multiplication de polynômes par changement de
représentation
- représenter un polynôme par ses valeurs à 2n
points
- multiplication dans cette représentation est très
facile : multiplier les valeurs
- il reste un gros problème : conversion entre les deux
représentations
- ``évaluation'' et ``interpolation''
Choix des points : la transformée de Fourier rapide
- choix astucieux : les n points sont les n racines d'unité
(n une puissance de 2)
- évaluation équivaut à multiplication par
une matrice
- interpolation est la même chose ; la matrice est celle
d'une autre racine
divisée par n
- donc, le même algorithme vaudra pour les deux
évaluation par division
- évaluation de f(x) à a équivaut à
trouver la reste quand f(x) est divisé par (x-a)
- et un regroupement astucieux de ces divisions permet
d'économiser énormément de calcul
- les calculs de f(x) mod (x-w) et f(x) mod (x+w)
partagent le calcul de
f(x) mod (x2-w2)
- et ainsi de suite
- 2 calculs de taille n suivis de 4 de taille n/2, 8 de taille
n/4, ...
- travail total de O(nlogn) au lieu de n2
Choix de la racine de 1
- Ce calcul avec des nombres réels et les résultats
intermédiaires complexes est très important
dans le domaine de calcul scientifique (traitement de signaux, ...)
- mais embêtant pour des calculs sur les entiers avec des
résultats entiers
- qui plus est, un problème de possibilité d'erreurs
introduites par les arrondis
- donc, l'idée de faire tous les calculs en
arithmétique modulo 2k/2+1 où 2k/n
est une racine convenable de 1
L'algorithme de Schönhager et Strassen
choix de la base
- Nous revenons au problème de départ de
multiplication d'entiers representés en base B
- Si les entiers sont inférieurs à 2n (n=2k),
il convient de prendre comme base,
B=22k/2
(k/2 arrondi vers le haut ; nombre de chiffres l)
- on ne garantit qu'un résultat mod 2n+1
- Le calcul de la convolution se fait en utilisant le même
algorithme récursivement si les
chiffres sont trop grand pour l'arithmétique normale
- résultats mod B2+1 corrigés par un
autre calcul simple modulo l
- temps total de calcul O(nlognloglogn)
File translated from
TEX
by
TTH,
version 3.05.
On 19 Apr 2004, 17:23.