X puissance n

manianis a écrit:Donner la méthode la plus optimisée pour calculer X^n. (x est un réel non nul et n est un entier relatif quelconque).

Code:

expo := 1;
pour i de 1 à |n| répéter
      expo := expo * X;


Combien d'opérations de multiplications pour calculer X^256 ?
Avec la méthode naïve, il faut 255 multiplications.
Or en remarquant que 256 = 2^8, on peut écrire:

Code:

X^256 = 2^[2^8] = 2^(2*2*....*2) = (((((((2^2)^2)^2)^2)^2)^2)^2)^2

D'où, il suffit de faire 8 multiplications (au lieu de 255!!)

A mon avis, la question la plus judicieuse c'est à quelle base on doit écrire l'exposant "n" pour avoir le minimum de multiplications possible

manianis a écrit:Donner la méthode la plus optimisée pour calculer X^n. (x est un réel non nul et n est un entier relatif quelconque).

Vraiment bravo pour le topic. Ca me donne l'idée de poster d'autres topics du style:
Quelle est la meilleure méthode pour calculer ....?

Ca révise les notions de base de la complexité.
C'est mon tour, la prochaine fois je posterai un sujet du même genre que le tien

Code:

function puissance(x : real ; a : integer):real;
var
    i : integer;
    pu, p : real;
    neg : boolean;
begin
    pu := 1.0;
    p := x;
   
    neg := (a < 0);
   
    while (a <> 0) do
    begin
        if (a mod 2 <> 0) then pu := pu * p;
        p := p * p;
        a := a div 2;
    end;
   
    if neg then puissance := 1/pu else puissance :=pu;
end;

manianis a écrit:Merci, j'avais travaillé avec la méthode que tu avait indiqué et je cherche une plus optimisée.
Par exemple :
x^15 = x^8.x^4.x^2.x
d'ou :

Code:

function puissance(x : real ; a : integer):real;
var
    i : integer;
    pu, p : real;
    neg : boolean;
begin
    pu := 1.0;
    p := x;
   
    neg := (a < 0);
   
    while (a <> 0) do
    begin
        if (a mod 2 <> 0) then pu := pu * p;
        p := p * p;
        a := a div 2;
    end;
   
    if neg then puissance := 1/pu else puissance :=pu;
end;

manianis a écrit:Merci, j'avais travaillé avec la méthode que tu avait indiqué et je cherche une plus optimisée.
Par exemple :
x^15 = x^8.x^4.x^2.x
d'ou :

Code:

function puissance(x : real ; a : integer):real;
var
    i : integer;
    pu, p : real;
    neg : boolean;
begin
    pu := 1.0;
    p := x;
    neg := (a < 0);
    while (a <> 0) do
    begin
        if (a mod 2 <> 0) then pu := pu * p;
        p := p * p;
        a := a div 2;
    end;
    if neg then puissance := 1/pu else puissance :=pu;
end;