W dniu 2014-07-30 16:41, bartekltg pisze:
> Wtedy to dowolny (w granicach rozsądku) wielomian policzę sobie
> w czasie log_2 (n) ;-)

Policzmy:
mamy wielomian 10-tego stopnia: a_0+a_{1}x+a_{2}x^2+...a_{10}x^{10}
Schemat Hornera
((((((((((a_{10}*x)+a_9)x+a_8)x+a_7)x+a_6)x+a_5)x+a_
4)x+a_3)x+a_2)x+a_1)+a_0

Rozkład wygodny do obliczeń równoległych:
a_0+a_{1}x+x^2*(a_{2}+a_{3}x)+
x^4*(a_{4}+a_{5}x+x^2*(a_{6}+a_{7}x) )+
x^8*(a_{8}+a_{9}x+a_{10}x^2)

1. krok - mnożenie przez x
o blizenie x^2:= x*x
a_{1}x
a_{3}x
a_{5}x
a_{7}x
a_{9}x
2. krok, ale krótki, tylko dodawanie
f0 := a_0+a_{1}x
f1 := a_{2}+a_{3}x
f2 := a_{4}+a_{5}x
f3 := a_{6}+a_{7}x
f4 := a_{8}+a_{9}x
otrzymujemy:
f0+x^2*(f1)+
x^4*(f2+x^2*(f3) )+
x^8*(f4+a_{10}x^2)

3. krok mnożenie przez x^2
obliczenie x^4 := x^2*x^2
g0 := x^2*(f1)
g1 := x^2*(f3)
g2 := a_{10}x^2
otrzymujemy
f0+g0+
x^4*(f2+g1 )+
x^8*(f4+g2)

4. krok, ale krótki, tylko dodawanie
h0 := f0+g0
h1 := f2+g1
h2 := f4+g2
otrzymujemy
h0 + x^4*h1 + x^8*h2
5. krok mnożenie przez x^4
obliczenie x^8 := x^4*x^4
x^4*h1
6. dodawanie
h0 + x^4*h1
7. mnożenie x^8*h2
8. dodawanie
(h0 + x^4*h1) + x^8*h2

8 kroków w tym 4 mnożenia

Chociaż z drugiej strony mnożeni i dodawanie obecnie to tyle samo za to
dzielenie dużo więcej
dodawanie, mnożenie na int32 czy też float tylko 1 takt, dzielenie
stałoprzecinkowe 7-8 a zmiennoprzecinkowe 13 taktów.