Addizione vs moltiplicazione sulle prestazioni dell'algoritmo

Question

Addizione vs moltiplicazione sulle prestazioni dell'algoritmo

#1 da (7 voti)

3

Sto studiando sull'ottimizzazione degli alogritmi. (Albo degli algoritmi del Prof. Skiena)

Uno degli esercizi ci chiede di ottimizzare un algoritmo:

Suppose the following algorithm is used to evaluate the polynomial
p(x) = a^(xn) + a^n−1(xn−1) + . . . + a(x) + a
p := a0;
xpower := 1;
for i := 1 to n do
xpower := x ∗ xpower;
p := p + ai ∗ xpower
end

(Qui xn, xn-1 ... sono i nomi dati a costanti distinte.)

Dopo aver dato un po 'di riflessione, l'unico modo in cui ho trovato di migliorare l'algoritmo è il seguente

p := a0;
xpower := 1;
for i := 1 to n do
  xpower := x ∗ xpower;
     for j := 1 to ai
         p := p + xpower
     next j
next i
end

Con questa soluzione ho convertito la seconda moltiplicazione in aggiunta in un ciclo for.

Le mie domande:

Trovi un altro modo per ottimizzare questo algoritmo?
L'alternativa che ho suggerito è migliore dell'originale? (Modifica: come suggerito nei commenti, questa domanda, sebbene legata al problema, merita un'altra domanda a parte. Ignora.)

language-agnostic algorithms

posta TheSilverBullet 19.02.2013 - 10:45

fonte

1 risposta

Leggi altre domande sui tag language-agnostic algorithms

Entropia nei sistemi software su larga scala [duplicato] La programmazione orientata agli oggetti dovrebbe essere la prima cosa che gli studenti apprendono? [chiuso]

score 7 · Accepted Answer

La soluzione standard è notare che si hanno molte moltiplicazioni con lo stesso numero x.

Quindi invece di

p(x) = a_n*x^n + a_n−1*x^n−1 + . . . + a_1*x + a_0

si potrebbe scrivere

p(x) = (...((a_n*x) + a_n−1)x + ... + a_1)*x + a_0

Forse più facile da leggere:

p(x) := a_3*x^3 + a_2*x^2 + a_1*x + a_0
q(x) := ((a_3*x + a_2)*x + a_1)*x + a_0
p(x) == q(x)

Chiamiamo tale valutazione metodo Horner . Si traduce in circa:

p := a_n;
for i is n-1 to 0
   p := p*x + a_i

Il metodo di Horner ha n moltiplicazioni e n aggiunte ed è ottimale.