Schemat Hornera — wielomiany bez wysiłku

🎯 Po co Ci to?

Policz wartość $w(x) = 2x^3 + 3x^2 - 5x + 7$ dla $x = 4$. Sposób szkolny: potęgi ($4^2$, $4^3$), mnożenia przez współczynniki, suma — kilkanaście operacji, a przy wielomianie stopnia 20 kilkaset. Tymczasem od trzystu lat znany jest zapis, który liczy to samo najmniejszą możliwą liczbą mnożeń — i który, jak za chwilę odkryjesz, znasz już z tej książki, tylko pod innym przebraniem. Grafika, dźwięk, kompresja, kody korekcyjne — wielomiany liczy się tam miliardy razy na sekundę, więc każda zaoszczędzona operacja jest na wagę złota.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • przekształcić wielomian do postaci Hornera i policzyć jego wartość na kartce oraz w kodzie;
  • policzyć, ile operacji oszczędza Horner względem liczenia wprost;
  • wskazać, gdzie Horner ukrywa się w konwersji systemów pozycyjnych.

📘 Wyjaśnienie

Przekształcenie. Wyciągaj $x$ przed nawias, piętro po piętrze:

$$2x^3 + 3x^2 - 5x + 7 = (2x^2 + 3x - 5)x + 7 = ((2x + 3)x - 5)x + 7$$

Postać końcowa — „cebula" z nawiasów — to schemat Hornera. Policz od środka dla $x = 4$: $2 \cdot 4 + 3 = 11$; $11 \cdot 4 - 5 = 39$; $39 \cdot 4 + 7 = 163$. Trzy mnożenia, trzy dodawania — koniec. Liczenie wprost potrzebowało pięciu mnożeń (dwa na potęgi, trzy na współczynniki); dla stopnia $n$ Horner robi $n$ mnożeń wobec około $2n$ wprost — i udowodniono, że mniej się nie da. Rzadki luksus: algorytm z certyfikatem optymalności.

W kodzie schemat jest jedną pętlą po współczynnikach (od najwyższej potęgi):

def horner(wsp, x):            # wsp = [2, 3, -5, 7] dla 2x³+3x²-5x+7
    w = 0
    for c in wsp:
        w = w * x + c          # jedno mnożenie, jedno dodawanie na współczynnik
    return w

Prześledź: $w$ = 0 → $0 \cdot 4 + 2 = 2$ → $2 \cdot 4 + 3 = 11$ → $11 \cdot 4 - 5 = 39$ → $39 \cdot 4 + 7 = 163$. Ten sam taniec, co na kartce (startowe $0 \cdot x + c_0$ po prostu wnosi pierwszy współczynnik). Wzorzec w = w * x + c zapamiętaj wzrokowo — rozpoznawanie go w cudzym kodzie to standard maturalny.

💭 Pomyśl: Policz Hornerem wartość „wielomianu" o współczynnikach $[1, 0, 1, 1, 0, 1]$ dla $x = 2$. Wynik skądś znasz…

Sprawdź odpowiedź

0→1→2→5→11→22→45. A teraz spójrz: współczynniki $101101$ to bity, $x = 2$ to podstawa — policzyłeś wartość $101101_2 = 45$, dokładnie tę, którą w jednostce 2.1 składałeś z potęg dwójki! Zamiana systemu na dziesiętny to wartość wielomianu o współczynnikach-cyfrach w punkcie-podstawie. Horner liczy ją bez żadnego potęgowania — i tak właśnie robi to procesor. Dwa pozornie odległe tematy okazały się jednym; takie sklejenia to najlepsze, co algorytmika ma do zaoferowania.

🐞 Znajdź błąd

Uczeń liczy Hornerem $x^3 + 5x + 2$ dla $x = 3$: bierze współczynniki [1, 5, 2] i dostaje $w = 0 \to 1 \to 8 \to 26$. Nauczyciel kręci głową. Co poszło nie tak?

Sprawdź odpowiedź

Zgubiony zerowy współczynnik przy $x^2$! Wielomian $x^3 + 0x^2 + 5x + 2$ ma współczynniki [1, 0, 5, 2]: $0 \to 1 \to 3 \to 14 \to 44$. (Kontrola wprost: $27 + 15 + 2 = 44$ ✓.) Horner czyta pozycjami — jak system dziesiętny, w którym 105 to co innego niż 15. Brakująca potęga = współczynnik 0, zawsze.

🛠️ Teraz Ty

Bez komputera: policz Hornerem $3x^4 - 2x^3 + x - 8$ dla $x = 2$ (uwaga na zero!) oraz zamień $2743_8$ na system dziesiętny wzorcem w = w * 8 + cyfra. Z komputerem: napisz horner i sprawdź oba rachunki; potem policz tym samym kodem wartość $173_{16}$ (współczynniki [1, 7, 3], $x = 16$).

📐 Definicje tej lekcji

  • Schemat Hornera — zapis $(((c_0 x + c_1)x + c_2)x + \dots)$; wartość wielomianu w $n$ mnożeniach (minimum możliwe); w kodzie pętla w = w * x + c.

📌 Najważniejsze w pigułce

  • Horner = wyciąganie $x$ przed nawias do końca; $n$ mnożeń zamiast ~$2n$, bez żadnego potęgowania.
  • Zerowe współczynniki muszą być na liście — Horner czyta pozycyjnie.
  • Zamiana systemu liczbowego na dziesiętny to Horner z podstawą w roli $x$ — jeden wzorzec, dwa rozdziały książki.

🎒 Zadania

  1. Policz Hornerem $w(x) = x^4 - 3x^3 + 2x - 1$ dla $x = 3$ i dla $x = -1$, notując ciąg wartości $w$.
Wskazówka i odpowiedź

Współczynniki [1, -3, 0, 2, -1]. Dla $x=3$: 0→1→0→0→2→5. Dla $x=-1$: 0→1→−4→4→−2→1. Kontrola dla $x=3$ wprost: $81 - 81 + 6 - 1 = 5$ ✓. Ujemne $x$ niczego nie zmienia w schemacie — to tylko liczba.

  1. Ile mnożeń wykonuje Horner, a ile liczenie wprost (każda potęga osobno przez powtarzane mnożenie) dla wielomianu stopnia 10? A stopnia 100?
Wskazówka i odpowiedź

Horner: 10 i 100 (jedno na współczynnik poza pierwszym… ściśle: tyle, ile stopień). Wprost: potęgi $x^2 \dots x^{10}$ to $1+2+\dots+9 = 45$ mnożeń plus 10 przez współczynniki — 55; dla stopnia 100: $4950 + 100 = 5050$ (znajoma liczba? Gauss z 1.5 puszcza oko). Horner wygrywa ~$n/2$-krotnie; sprytniejsze potęgowanie zmniejszyłoby przewagę, ale nie zlikwidowało — a o sprytnym potęgowaniu opowiada następna jednostka.

  1. Napisz funkcję na_dziesietny(cyfry, podstawa) używającą wzorca Hornera i przetestuj na $1101_2$, $777_8$, $\text{FF}_{16}$ (cyfry podaj listami liczb). Dlaczego ta funkcja NIE potrzebuje żadnej tablicy potęg podstawy?
Wskazówka i odpowiedź

w = 0; for c in cyfry: w = w * podstawa + c. Wyniki: 13, 511, 255. Potęgi budują się same: każde przejście pętli „awansuje" dotychczasową wartość o jedną pozycję (mnożenie przez podstawę) — dokładnie tak, jak dopisanie cyfry z prawej robi z 45 liczbę 45x. Tablica potęg to rozwiązanie człowieka, który jeszcze nie zna Hornera.

🔍 Sprawdź, czy umiesz

  • Przekształcić wielomian do postaci Hornera i policzyć wartość na kartce.
  • Rozpoznać wzorzec w = w * x + c w cudzym kodzie i powiedzieć, co liczy.
  • Wyjaśnić, czemu konwersja systemów to szczególny przypadek Hornera.

Ucz się tej jednostki z asystentem