Algorytm Hornera (prostszy dowód)

Być może poprzedni dowód nie jest najefektywniejszy. Po krótkim przeszukaniu internetu natrafiłem na pewien dokument pdf, gdzie zastosowano prostszą metodę dowodzenia istnienia przedstawień liczb naturalnych w systemach pozycyjnych, która może nie dowodzi jako tako algorytmu Hornera, ale do niego nawiązuje. W tym wpisie postaram się sporządzić alternatywny dowód algorytmu, bazując na metodzie ze wspomnianego dokumentu. Być może okaże się prostsza. Mniej więcej widzę jak dowód powinien przebiegać, ale jeszcze nie próbowałem go spisać.

Zaczniemy w momencie, gdy już mamy zdefiniowane ciągi \{d_n\}_{n=0}^\infty oraz \{c_n\}_{n=0}^\infty i dowiedzione własności ciągu \{d_n\}_{n=0}^\infty.

Na mocy dowiedzionych własności wiemy, że zawsze istnieje N=\min\{n: \forall m>n: c_m=0 \}. Wtedy liczbę N nazywamy długością liczby reprezentowanej przez przedstawienie \{c_n\}_{n=0}^\infty.

Będziemy chcieli wykazać jak poprzednio, że

\displaystyle k=\sum_{n=0}^Nc_n L^n.

Różnica będzie taka, że poprowadzimy indukcję ze względu na k.

Dla k=0 łatwo widać, że d_n=0, a więc także c_n=0.

Załóżmy więc, że dla każdej liczby m<k schemat Hornera działa i będziemy chcieli dowieść, że działa również dla k. Mamy, że k=d_1L+c_0 i wtedy (zakładając, że k>0) zachodzi k>d_1. Stąd korzystając z założenia indukcyjnego

\displaystyle d_1=\sum_{n=0}^{N'} c_n' L^n,

gdzie c_n' są cyframi liczby d_1 dobranymi wg algorytmu, N' jej długością.

Podstawiając za d_1 dostajemy

\displaystyle k=(\sum_{n=0}^{N'} c_n' L^n)L+c_0.

Widać więc, że potrzeba, aby cyfry d_1 były takimi samymi jak k, ale przesuniętymi, a ściślej biorąc aby c_{n+1}=c_n', ale to jest oczywiste. Oznaczmy przez \{d_n'\}_{n=0}^\infty ciąg wyników dzielenia liczby d_1. Zauważmy, że z definicji d_0'=d_1, a więc cały proces dzielenia zaczynamy od d_1, ale jest on tak samo zdefiniowany jak dla k, więc przez prostą indukcję otrzymamy, że d_{n+1}=d_n'. Stąd oczywiście mamy także żądaną zależność dla cyfr, gdyż

c_{n+1}=r_L(d_{n+1})=r_L(d_n')=c_n'.

Wynika z tego też, że o ile N>0, to liczba d_1 jest krótsza o jedną cyfrę od k, tj. N-1=N', a w każdym przypadku możemy powiedzieć, że nie jest od niej dłuższa i tylko z tego faktu skorzystamy.

Zatem w rzeczywistości

\displaystyle k=\left(\sum_{n=0}^{N'} c_n' L^n\right)L+c_0=\left(\sum_{n=0}^{N} c_{n+1} L^n\right)L+c_0=\sum_{n=0}^{N} c_{n+1} L^{n+1}+c_0

i przez przesunięcie wskaźnika sumowania, przyjmując i=n+1, dostajemy

\displaystyle k=\sum_{i=1}^{N+1} c_iL^i + c_0=\sum_{i=0}^{N} c_iL^i

co kończy dowód.

To podejście jest zauważalnie prostsze. Cóż, w poprzednim przypadku przynajmniej wymyśliłem coś sam, za to teraz nauczyłem się to robić lepiej od kogoś.

Uwzględniając wiadomości z wpisu o istnieniu rozwinięć liczb z przedziału [0,1] mamy że każdą liczbę rzeczywistą przedstawimy przy pomocy dwóch ciągów: skończonego i w najgorszym wypadku nieskończonego. Wystarczy daną liczbę x przedstawić jako sumę części całkowitej i ułamkowej

x=[x]+\{x\}

a następnie odpowiednio dane części wyrazić w systemie liczbowym

[x]=c_N\dots c_1c_0 oraz  \{x\}=0,d_1d_2d_3\dots

Dzięki temu możemy zapisać, że

x=c_N\dots c_1c_0+ 0,d_1d_2d_3\dots =c_N\dots c_1c_0,d_1d_2d_3\dots

Reklamy

Jedna uwaga do wpisu “Algorytm Hornera (prostszy dowód)

  1. Pingback: Algorytm Hornera kodowania liczb (z dowodem) | roznematematyka

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s