Accueil

Lexique

Unités

ALGORITHMES

Tutoriel

Sommaire Algorithmes

Ici nous discutons de la pertinence de créer des fonctions de puissances en partant d'algorithme utilisant des puissances entières.

J'ai pensé à créer 2 algorithmes de puissanse d'entiers. Celle dite "heuristique" consistant, d'instinct, à faire N fois la multiplication d'un nombre par la variable initiale X, et celle optimisant cette tâche en se rendant compte qu'un entier reste une somme de puissance de 2. On passerait donc d'une complexité de type O(n) à une complexité de type O(Log2(N)).

On va donc écrire les 2 algorithmes et comparer la vitesse du 2ème algorithme à celle de la fonction Power basée sur l'exponentielle.

Algorithme Heuristique

function pow1( X: real; N: integer) : real;
var
    resultat:real;
begin
    resultat:=1;
    for i:=1 to N
        resultat:=resultat*X;
    pow1:=resultat;
end;

Algorithme Optimisé

Le 2ème algorithme est basé sur le fait qu'un entier est une somme de puissances de 2. On part du fait que le bit le plus faible est une puissance 1 de X, puis on compare avec les bits de N suivant le rang de bit dans lequel on est.

function pow2( X: real; N: word) : real;
var
    resultat,xpow:real;
    powbite:word;
begin
    powbite:=1;
    resultat:=1;
    xpow:=X;
    while (powbite <=N) do
    begin
        if (powbite AND N <>0) then
            resultat:=resultat*xpow;
        powbite:= powbite shl 1;
        xpow:=xpow * xpow;
    end;
    pow2:=resultat;
end;

Dès que N=8, le second algorithme devient nettement plus rapide. Car, même s'il fait 2 multiplications par cycle (au pire), on a juste 4 boucles (bits 0 à 3) avec N=8 contre 8 pour le premier algorithme. Pour N=16, on a 5 boucles (10 multiplications au pire) contre 16 pour le premier algorithme. Pour N=256, on a au pire 16 multiplications pour le 2ème algorithmes. Les opérations de décalage de bit sont négligeableq (1 à 2 cycles d'horloge processeur).

Il convient donc de comparer le 2ème algorithme avec celui donné dans la fonction power. Pour cela, on va créer un programme sur Atari ST pour faire une suite de N puissances (ça peut être la même opération) et chronométrer entre les 2 algorithmes.

On écrit ce programmme

program Maths;
const nb_boucle = 100000;

Var
    I:longint;
    X:real;

BEGIN
    writeln('Premier algorithme, tapez sur entrée');
    readln;
    for i:=1 to nb_boucle do
        X:=pow2(1.25,128);
    writeln('Fin premier algorithme, tapez sur entrée', X);
    readln;
    writeln('Deuxième algorithme, tapez sur entrée');
    readln;
    for i:=1 to nb_boucle do 
        X:=power(1.25,128);
    writeln('Fin deuxième algorithme, tapez sur entrée', X);
    readln;
END.

A à la grande surprise, la fonction power basée sur des exposants réel met 5 secondes pour 100.000 boucles contre 16 secondes avec la fonction (pow2) basée sur des entiers (Sur Atari Falcon 030 16 MHz)!
Dans les 2 cas, le résultat, le même, est 2.537941837315652x10¹²

Sommaire Algorithmes