Informatique -- Tronc Commun
TD 2 -- Récursivité 2: l'algorithme de Karatsuba

Benjamin Werner, Eric Schost

15 novembre 1999








1  Principe

L'algorithme de Karastuba est une méthode récursive pour effectuer la multiplication de deux polynomes. Aujourd'hui on travaillera sur des polynomes à coefficients flottants et à une variable.

Un polynome à une variable est représenté par un tableau, qui donne le coefficient en fonction du degré.

On a deux polynomes P et Q et l'on cherche à calculer P.Q. Soit n le degré de P et Q (ou le maximun des deux degrés); on peut alors écrire:
P = P1+Xn/2P2
Q = Q1+Xn/2Q2
où P1,P2,Q1 et Q2 sont tous de degré n/2.

Le calcul naïf revient à prendre:
Rº P1.Q1+Xn/2(P1.Q2+P2.Q1)+Xn.P2.Q2
ce qui donne un temps de calcul en O(n2). On a, en effet, alors besoin de calculer le produit de 4 paires de polynomes de degré n/2.

L'astuce de Karatsuba consiste à remarquer qu'il suffit de calculer:
E1 º P1.Q1
E2 º P2.Q2
E3 º (P1+P2).(Q1+Q2)

On remarque en effet que
E3-E1-E2=P1.Q2+P2.Q1
, et donc:
P.Q=E1+Xn/2(E3-E1-E2)+XnE2
On n'a donc besoin ici de calculer le produit que 3 paires de polynomes.



2  Etapes

  1. Ecrivez une fonction qui affiche un tableau sous forme de polynome.
  2. Ecrivez une fonction qui lise au clavier un polynome de degré donné. Vous pouvez pour cela utiliser la fonction suivante qui lit un flottant au clavier: 
    import java.io.*;
import java.lang.*;
import java.util.*;

    static int lire (String s)  {
        int n; 
        BufferedReader in = 
            new BufferedReader(new InputStreamReader(System.in));
        System.out.print (s);
        try {
            n = Integer.parseInt (in.readLine());
        }
        catch (IOException e) {
            n = 0;
        }
        return n;
    }
  3. Ecrivez la fonction naïve de produit de deux polynomes, et essayez-la sur deux polynomes lus au clavier.

  4. Ecrivez la fonction de produit de deux polynomes utilisant l'algorithme de Karastsuba, et utilisez-la à la place de la précédante. Essayez-la.

    Attention: comme la fonction est récursive, vous avez interêt à ce que la fonction prenne en argument non seulement les deux tableaux, mais également les bornes des portions de ces tableaux qu'il s'agit effectivement de multiplier.

  5. Calculez le nombre de multiplication faites par l'algorithme de Karatsuba.

  6. Si vous avez fini, vous pouvez, par exemple, ecrire la fonction qui effectue la division euclidienne de deux polynomes.
Une solution ce trouvera ici.
This document was translated from LATEX by HEVEA.