Algorytm Hornera kodowania liczb (z dowodem)

Zajmiemy się teraz zagadnieniem bardziej podstawowym niż poprzednio, będziemy chcieli zbadać istnienie i jednoznaczność przedstawień liczb naturalnych w systemach liczbowych pozycyjnych o dowolnej podstawie L>1. Systemem jedynkowym, czyli kreskami, którymi więźniowie zwykle odznaczają przebyte w celi dni, nie będziemy się zajmować (względnie systemem, w którym mamy tylko do dyspozycji 0).

Zacznijmy od tego, że samo istnienie jak i jednoznaczność takiego przedstawienia dowolnej liczby można wykazać przy pomocy dokładnie takich samych metod jak przy liczbach z przedziału [0,1] (mam na myśli konstruowanie ciągu przybliżającego od dołu) i jest to nawet prostsze, dlatego cel postawimy sobie ambitniejszy – uzasadnienie algorytmu Hornera kodowania liczb. Da nam to jednocześnie odpowiedź na pytanie o istnienie przedstawień a także pewien sposób ich wyliczania.

Systemy liczbowe pozycyjne o podstawie L polegają na tym, że mamy do dyspozycji L cyfr od 0 do L-1 i gdy doliczymy się do L-1 to następną po niej liczbą jest 10, co rozumiemy w ten sposób, że mamy już 1 raz L oraz 0 „jedności”. Następnie korzystając z dwóch cyfr doliczymy się maksymalnie do L-1 \, L-1, co rozumiemy, że mamy L w ilości L-1 oraz L-1 itd. Ogólnie, ciąg cyfr

c_n c_{n-1}\dots c_1c_0

w systemie o podstawie L interpretujemy  jako liczbę

c_nL^n+c_{n-1}L^{n-1} + \dots +c_1L +c_0.

Zajmiemy się zagadnieniem wyznaczenia takiego ciągu cyfr dla dowolnej liczby naturalnej, tzn. jeśli k \in \mathbb{N} to dobieramy taki ciąg cyfr, żeby k=c_nL^n+c_{n-1}L^{n-1} + \dots +c_1L +c_0. Cały czas będziemy mówili o systemie przynajmniej dwójkowym (L>1) oraz cyfry będziemy rozumieć jako liczby naturalne od 0 do L-1.

Algorytm Hornera

Na rozgrzewkę wyznaczymy cyfry liczby 23 w systemie trójkowym, aby lepiej poczuć jak działa algorytm, nim przejdziemy do ogólnego zapisu. W kroku zerowym mamy 23 i teraz kolejno

  1. Dzielimy 23 z resztą przez trzy 23=3\cdot7+2.
  2. Znowu dzielimy z resztą przez trzy, ale wynik dzielenia całkowitego 7=3\cdot2+1.
  3. Postępujemy jak poprzednio 2=3 \cdot 0+2.
  4. Otrzymaliśmy poprzednio zerowy wynik dzielenia całkowitego, więc możemy przestać.

Wróćmy teraz do liczby 23 i wykorzystajmy otrzymane wyniki dzielenia z resztą

23=3\cdot7+2=3\cdot(3\cdot2+1)+2=2\cdot3^2+1\cdot 3 +2 \cdot 3^0.

Zatem 23 w systemie trójkowym przedstawia się za pomocą ciągu cyfr 212.

Przejdziemy teraz do ścisłego zapisu algorytmu. Będziemy intensywnie korzystać z twierdzenia o dzieleniu z resztą liczb naturalnych. Załóżmy, że mamy dowolną liczbę naturalną k. Zdefiniujemy rekurencyjnie ciąg wyników z dzielenia całkowitego. W kroku zerowym mamy po prostu k, więc przyjmujemy

d_0:=k

Następnie dzielimy k z resztą przez L i otrzymujemy k=d_1L+r, następnie dzielimy d_1 otrzymując d_1=d_2L+r' itd. Stąd przyjmujemy rekurencyjną zależność

d_n=d_{n+1}L+r,

gdzie r jest resztą, a d_{n+1} wynikiem dzielenia całkowitego. Ponieważ dzielenie z resztą dowolnej liczby naturalnej m jest jednoznaczne (zarówno jeśli chodzi o resztę jak i wynik dzielenia całkowitego), otrzymujemy, więc przy ustalonym L dwie funkcje – resztę r_L oraz wynik dzielenia d_L, dla których argumentem jest m i które zależą od niego w sposób następujący m=d_L(m)L+r_L(m). Zatem przy tych oznaczeniach naszą definicję zapiszemy

d_0:=k

oraz

d_{n+1}:=d_L(d_n).

Możemy teraz określić ciąg cyfr \{c_n\}_{n=0}^\infty przepisem c_n:=r_L(d_n) dla każdego naturalnego n. Zatem zerowa cyfra to reszta z dzielenia k przez L, tj. c_0=r_L(d_0)=r_L(k) i następnie reszty z ciągu wyników dzielenia. Chwilowo nasz ciąg cyfr jest nieskończony, ale za moment poradzimy sobie z tym problemem. Aby to uczynić wykażemy kilka kluczowych własności ciągu \{d_n\}_{n=0}^\infty.

Własność.

Ciąg \{d_n\}_{n=0}^\infty wyznaczony dla dowolnej liczby k jest

  1. Nieujemny.
  2. Słabo malejący, tzn. \forall n \in \mathbb{N}: d_n \geq d_{n+1}
  3. Gdy dla pewnego n zachodzi d_n>0, to mamy silną nierówność, tzn. d_n > d_{n+1}.
  4. Gdy dla pewnego n zachodzi d_n=0, to mamy równość, tzn. d_n = d_{n+1}.

Dowód.

Zerowy element jest liczbą naturalną, więc jest nieujemny, a każdy następny jest wynikiem dzielenia nieujemnej liczby przez dodatnią, więc też jest nieujemny.

Teraz monotoniczność. Z twierdzenia o dzieleniu z resztą oraz z definicji

d_n=d_L(d_n)L+r_L(d_n)=d_{n+1}L+r_L(d_n)\geq d_{n+1}L

gdyż r_L(d_n)\geq 0. Mamy także

d_{n+1}L \geq d_{n+1}

dzięki nieujemności d_{n+1} oraz nierówności L>1.

A gdy dodatkowo wiemy, że d_n>0, to ponieważ L>1, mamy

d_n> \frac{d_n}{L} \geq d_{n+1}.

Zauważmy, że gdy d_n=0 to mamy 0=d_n \geq d_{n+1}\geq 0, a więc równość d_n =0=d_{n+1}.

Wniosek 1.

Ciąg \{d_n\}_{n=0}^\infty jest od pewnego momentu stale równy zero.

Dowód.

Niech d:=min\{d_n: n \in \mathbb{N} \} (taka liczba istnieje ze względu na nieujemność ciągu). Przypuśćmy, że d>0. Wtedy oczywiście d_n=d dla pewnego n i z punktu 3. powyższej Własności d=d_n>d_{n+1} – sprzeczność z minimalnością. Zatem istnieje n dla którego d_n=0, ale wtedy z z punktu 4. d_{n+1}=0 itd. (indukcja). Otrzymujemy więc, że ciąg jest od tego momentu stale równy zero.

Wniosek 2.

Dostajemy zatem, że także ciąg \{c_n\}_{n=0}^\infty jest od pewnego momentu stale równy zero, gdyż c_n=r_L(d_n) i tam gdzie d_n=0 reszta także będzie zerowa.

Zatem dla pewnego N \in \mathbb{N}

\displaystyle \sum_{n=0}^\infty c_n L^n=\sum_{n=0}^Nc_n L^n

a więc zawsze jest to jakaś liczba,  chociaż na razie nie wiemy czy tą liczbą będzie k.

Zanim jednak dowiedziemy tego faktu, wprowadzimy pomocniczo pewne pojęcie. Liczbę

(Dalsza część wpisu zawiera dowód, który udało mi się sporządzić samodzielnie, ale nie jest on najefektywniejszą metodą. Dodatkowo wykorzystuje równoważną definicję długości liczby. By zapoznać się z prostszym dowodem zapraszam do wpisu: Algorytm Hornera (prostszy dowód).)

N:=min\{ n\in \mathbb{N}: \forall m>n: d_m=0\}

nazwiemy długością liczby k. Krótko mówiąc d_N jest najwcześniejszym elementem ciągu \{d_n\}_{n=0}^\infty, po którym już wszystkie są równe zero. Taki na pewno istnieje dzięki Wnioskowi 1. Zwróćmy uwagę, że jeśli wszystkie d_n=0, to N=0 i także d_N=0, natomiast w każdym innym przypadku d_N>0 (w definicji mamy ostrą nierówność). Pojęcie długości liczby miało odpowiadać minimalnej ilości cyfr, które wpływają na wartość, lecz po pierwsze wiadomo tylko, że od momentu, od którego zeruje się ciąg wyników z dzielenia zeruje się także ciąg cyfr, a nie jest pewne czy np. ciąg cyfr nie zaczyna się zerować wcześniej (skądinąd wiem, że tak nie jest, ale ta wiedza nie jest potrzebna), po drugie nawet gdyby \{c_n\}_{n=0}^\infty i \{d_n\}_{n=0}^\infty zerowały się od tego samego momentu, to rzeczywista ilość cyfr istotnych wynosiła by N+1, gdyż numerujemy cyfry od 0.  To tyle w kwestii uwag, które należy traktować co najwyżej jako ciekawostki. Po prostu wprowadzone pojęcie jest użyteczne przy dowodzie poprawności algorytmu. Wiedząc, że \forall n>N: d_n=0 mamy również, że \forall n>N: c_n=0. Zatem możemy powiedzieć, że:

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

Dowód faktu, że

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

będzie indukcją prowadzoną ze względu na długość liczby k, ale zanim do niego przystąpimy potrzebny będzie pewien lemat. Wręcz lemat można uznać za główne twierdzenie, z pewnością najtrudniejsze.

Zatem przy oznaczeniach jak dotychczas:

Lemat.

Niech \{d_n'\}_{n=0}^\infty będzie ciągiem wyników z dzielenia wyznaczonym dla liczby k-c_NL^N, wtedy dla dowolnego n naturalnego

  1. Gdy n \leq N, to d_n=d_n'+c_NL^{N-n}.
  2. Gdy n>N, to d_n'=0.

Teza dosyć koślawa, ale przed dowodem postaram się wyjaśnić do czego jest potrzebna. Teza daje nam efektywną zależność między ciągiem wyników dzielenia liczby k, a ciągiem wyników dzielenia liczby k z wyzerowaną „ostatnią” cyfrą. Dzięki takiej postaci twierdzenia, w ogóle da się je dowieść (a z tym było sporo kłopotów) a też łatwo z niego wynika, że k-c_NL^N ma takie same cyfry, co k, poza N-tą, która zostaje wyzerowana. Dowiedziemy lematu przez indukcję, jeszcze zanim będzie wiadomo, że
\displaystyle \sum_{n=0}^Nc_n L^n=k.

Gdybyśmy mieli już tę wiedzę, sprawa rozbijała się tylko o jednoznaczność przedstawienia, a to już było dowiedzione w jednym z wcześniejszych wpisów i wymaga tylko komentarza, lecz nie mamy takiej wiedzy i musimy się chwytać wszelkich sposobów.

Dowód. Indukcja ze względu na n.

Dla n=0 do sprawdzenia jest tylko punkt pierwszy 0\leq N. Z definicji d_0'=k-L^Nc_N=d_0-L^Nc_N, zatem teza jest spełniona.

Załóżmy, że teza spełniona jest dla n i będziemy chcieli dowieść, że

  1. Gdy n+1 \leq N, to d_{n+1}=d_{n+1}'+c_NL^{N-(n+1)}.
  2. Gdy n+1>N, to d_{n+1}'=0.

Załóżmy więc na początek, że n+1\leq N. Wtedy n < N i z założenia indukcyjnego d_n=d_n'+c_NL^{N-n}. Rozpisując z definicji n-te wyrazy ciągów mamy, że

d_n=d_L(d_n)L+r_L(d_n)=d_{n+1}L+c_n,

d_n'=d_{n+1}'L+c_n',

gdzie oczywiście c_n'=r_L(d_n') jest ciągiem cyfr liczby k-c_NL^N.

Wstawiając je do wcześniejszej równości dostajemy

d_{n+1}L+c_n=d_{n+1}'L+c_n'+c_NL^{N-n}

z czego wnioskujemy, że c_n=c_n', gdyż

c_n=r_L(d_{n+1}L+c_n)=r_L((d_{n+1}'L+c_n'+c_NL^{N-n})=c'_n

Inaczej mówiąc, po zredukowaniu \mod L zostaną nam tylko c_n i c_n', gdyż pozostałe składniki są podzielne przez L (potęga N-n jest dodatnia). Z tego faktu upraszcza się nam równość i otrzymujemy

d_{n+1}L=d_{n+1}'L+c_NL^{N-n}.

Ponownie z założenia, że N>n, możemy podzielić obie strony przez L. Mamy ostatecznie

d_{n+1}=d_{n+1}'+c_NL^{N-(n+1)},

co należało dowieść w tym przypadku.

Załóżmy więc teraz, że n+1>N. Możemy mieć dwie sytuacje albo n=N albo n>N, lecz w każdej mamy otrzymać, że d_{n+1}'=0. Załóżmy najpierw, że n=N. Z założenia indukcyjnego d_N=d_N'+c_N, z definicji ciągu wyników dzielenia mamy d_N=d_{N+1}L+c_N oraz z definicji N wiemy, że d_{N+1}=0. Oba te fakty dają nam, że d_N=c_N, wracając zatem do rozpatrywanej równości mamy, że d_N'=0, a stąd także d_{N+1}'=0. Rozważmy na koniec przypadek gdy n>N. Jednak jest on trywialny, gdyż z założenia indukcyjnego d_n'=0, więc również d_{n+1}'=0.

Mniej więcej było to już widoczne podczas dowodu, ale aby było porządnie zapiszmy kolejny wniosek.

Wniosek 3.

Niech \{c_n'\}_{n=0}^\infty będzie ciągiem cyfr liczby k-c_NL^N, wtedy c_n'=c_n, gdy n\neq N, a c_N'=0.

Dowód.

Dla n<N z Lematu dostajemy, że c_n=r_L(d_n)=r_L(d_n'+c_NL^{N-n}), dla n=N mamy d_N=d_N'+c_N, ale wykazaliśmy przy okazji w poprzednim dowodzie, że z tej równości wynika, że d_N'=0, a więc też c_N'=0, natomiast gdy n>N, to zarówno d_n jak i d_n' się zerują, a więc także c_n i c_n'.

Twierdzenie.

Dla dowolnej liczby naturalnej k o dowolnej długości N

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

Dowód. Indukcja ze względu na N.

N=0. Mamy k=d_0=d_1L+c_0, ponieważ d_1=0, dostajemy, że k=c_0.

Załóżmy teraz, że teza zachodzi dla dowolnej liczby k o długości nie większej niż N i rozważmy dowolną liczbę m o długości N+1. Niech \{c_n\}_{n=0}^\infty będzie jej ciągiem cyfr, a \{c_n'\}_{n=0}^\infty ciągiem cyfr liczby m-c_{N+1}L^{N+1}. Wtedy na podstawie Lematu liczba m-c_NL^{N+1} jest długości co najwyżej N i z założenia indukcyjnego

\displaystyle \sum_{n=0}^Nc_n' L^n=m-c_{N+1}L^{N+1}.

Ale dzięki Wnioskowi 3 wiemy dodatkowo, że c_n'=c_n dla n<N+1, stąd otrzymujemy

\displaystyle \sum_{n=0}^Nc_n L^n=m-c_{N+1}L^{N+1},

a więc, że

\displaystyle \sum_{n=0}^{N+1}c_n L^n=m

co było do wykazania.

Pozostała nam tylko kwestia jednoznaczności takiego przedstawienia. Wystarczy jednak zauważyć, że Lemat z wpisu o jednoznaczności już nam rozstrzyga tę kwestię, jako że jedynym rozwiązaniem równania

\displaystyle \sum_{n=0}^{N}x_n L^n=0,

spośród liczb całkowitych x_n spełniających warunek -L<x_n<L jest aby dla wszystkich n\leq N było x_n=0.

Dzięki czemu wiemy, że po przyrównaniu dwóch przedstawień, będą musiały być identyczne (obejmuje to także sytuację z przedstawieniami o dwóch niekoniecznie równych długościach).

Podsumowując, każda liczba naturalna ma jednoznaczne przedstawienie w postaci ciągu cyfr o skończonej długości, a do tego wiemy jak można je wyliczyć przy pomocy wyznacza reszt z dzielenia i wyników dzielenia całkowitego.

Advertisements

Jedna uwaga do wpisu “Algorytm Hornera kodowania liczb (z dowodem)

  1. Pingback: Gra w marynarza | roznematematyka

Skomentuj

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

Logo WordPress.com

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

Zdjęcie z Twittera

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

Facebook photo

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

Google+ photo

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

Connecting to %s