Schemat Hornera

Ale jak to działa?

Jak juz wiemy, schemat Hornera stosuje sie do obliczenia wartości wielomianu. Czym więc jest wielomian?

Schemat blokowy dla Hornera

Wielomian

Wiedząc czym jest wielomian wyznaczmy jego wartość.

To wyrażenie algebraiczne złożone ze zmiennych (np. litery ,,x'') i stałych (czyli cyfr) połączonych działaniami dodawania, odejmowania, mnożenia i podnoszenia do potęgi o stałym wykładniku naturalnym.

Przykład wielomianu

3x^4+5x^3+2x^2+9x+5

W(x)=3x^4+5x^3+2x^2+9x+5

Weźmy pod uwagę pierwsze 4 elementy wielomianu.

Możemy wyłączyć wspólny czynnik (x) przed nawias

(3x^3+5x^2+2x+9)x+5

Teraz "wyciągamy" przed nawias x z pierwszych trzech elementów w nawiasie:

((3x^2+5x+2)x+9)x+5)

Jeszcze raz postepujemy tak samo wyciągając x z dwóch pierwszych elementów w wewnętrznym nawiasie:

Ostatecznie otrzymujemy:

(((3x+5)x+2)x+9)x+5

Czym jest schemat Hornera?

Schemat Hornera

Schemat Hornera jest to sposób obliczenia wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń.

Schemat Hornera a systemy liczbowe

Schemat Hornera nie jest typowym, normalnym algorytmem. Jest to jedynie efektywniejszy sposób liczenia wartości wielomianów. Ponieważ mnożenie zajmuje procesorowi bardzo dużo czasu, więc wszelkie ograniczenie tego działania w jakimkolwiek algorytmie zwiększa jego szybkość w znacznym stopniu.To wlasnie ma na celu schemat Hornera.

Możliwe jest wykorzystanie algorytmu Hornera do zamiany liczby z postaci w systemie pozycyjnym o dowolnej podstawie na jej wartość w systemie dziesiętnym.

Więc co czyni ten schemat niezwykłym?

Mamy dany wielomian zapisany schematem Hornera

((((an*x+an-1)*x+an-2)*x+….+a2)*x+a1)*x+a0

Przyjrzyjmy się ilości mnożeń i dodawań w klasycznym i hornerowym sposobie.

x jest wtedy podstawą systemu np. jeśli jest to system dwójkowy wtedy x=2 natomiast an to cyfra na pierwszej pozycji.

Nazwa pochdzi od wynalazcy schematu- Williama George Hornera.

Schemat klasyczny

A jak sie przedstawia Schemat Hornera?

Przykład

Zajmijmy sie naszym wielomianem

3x^4+5x^3+2x^2+9x+5

(((3*x+5)*x+2)*x+9)*x+5

Chcąc zamienić liczbę 1011 zapisaną w systemie dwójkowym na system dziesiątkowy należy postąpić następująco.

3*x*x*x*x+5*x*x*x+2*x*x+9*x+5,

czyli 4 mnożenia i 4 dodawania!

czyli 10 mnożeń i 4 dodawania!

Różnica już przy niewielkim stopniu wielomianu jest widoczna.

Ilość mnożeń w postaci ogólnej to n*(1+n)/2

Ilość mnożeń to zaledwie n !

Gdzie n-stopień wielomianu

1011=1*2^3+0*2^2+1*2^1+1*2^0=

=(((1*2+0)*2+1)*2+1=11(10)

Przykład dla wielomianów wyższego stopnia n=100

Analogicznie wykonujemy dla innych systemów

• Schematem klasycznym: n*(1+n)/2=100*(1+100)/2=5050 mnożeń
• Schematem Hornera: 100 mnożeń

Horner jako sposób na dzielenie wielomianów.

Schemat Hornera może nam również posłużyć do dzielenia wialomianów.Oto przykład.