Dodawanie dowolnych liczb rzeczywistych w systemach pozycyjnych

Jednak się da! Jednak znalazłem algorytm na dodawanie dwóch dowolnych liczb z przedziału [0,1], bo oczywiście to jest najbardziej problematyczna kwestia. Zanim przedstawię algorytm w postaci ogólnej wykonamy pewien oczywisty przykład. Wykonamy dodawanie 0,(9)+0,(9), którego skądinąd wynikiem jest 2.

Mamy

\displaystyle 0,(9)+0,(9)=\sum_{n=1}^\infty \frac{18}{10^n}=\sum_{n=1}^\infty \frac{10}{10^n}+\sum_{n=1}^\infty \frac{8}{10^n}=\sum_{n=1}^\infty \frac{1}{10^{n-1}}+\sum_{n=1}^\infty \frac{8}{10^n}=1+\sum_{n=1}^\infty \frac{1}{10^n}+\sum_{n=1}^\infty \frac{8}{10^n}=1,(9)=2

Rozważmy nieco bardziej pracochłonny przykład

\displaystyle 0,(789)+0,(212)=\frac{7+2}{10}+\frac{8+1}{10^2}+\frac{9+2}{10^3}+\frac{7+2}{10^4}+\frac{8+1}{10^5} \dots =

\displaystyle \frac{9}{10}+\frac{9}{10^2}+\frac{11}{10^3}+\frac{9}{10^4}+\frac{9}{10^5}+\frac{11}{10^6}+ \dots=

Dzielimy jedenastki z resztą przez dziesięć, przy okazji skracając wydzieloną dziesiątkę

\displaystyle \frac{9}{10}+\left(\frac{9}{10^2}+\frac{1}{10^2}\right)+\frac{1}{10^3}+\frac{9}{10^4}+\left(\frac{9}{10^5}+\frac{1}{10^5}\right)+\frac{1}{10^6}+ \dots=

\displaystyle \frac{9}{10}+\frac{10}{10^2}+\frac{1}{10^3}+\frac{9}{10^4}+\frac{10}{10^5}+\frac{1}{10^6}+ \dots=

\displaystyle \left(\frac{9}{10}+\frac{1}{10}\right)+\frac{0}{10^2}+\frac{1}{10^3}+\left(\frac{9}{10^4}+\frac{1}{10^4}\right)+\frac{0}{10^5}+\frac{1}{10^6}+\left(\frac{9}{10^7}+\frac{1}{10^7}\right)+ \dots=

\displaystyle \frac{10}{10}+\frac{0}{10^2}+\frac{1}{10^3}+\frac{10}{10^4}+\frac{0}{10^5}+\frac{1}{10^6}+\frac{10}{10^7}+ \dots=

\displaystyle \frac{1}{10^0}+\frac{0}{10^1}+\frac{0}{10^2}+\frac{2}{10^3}+\frac{0}{10^4}+\frac{0}{10^5}+\frac{2}{10^6}+\frac{0}{10^7}+ \dots=1,(002)

W powyższych przykładach wystarczyło zastosowanie skończonej liczby „globalnych” przeniesień, a co jeśli w wyniku sumy otrzymamy szereg typu

\displaystyle \frac{18}{10^1} +\frac{9}{10^2}+\frac{18}{10^3}+\frac{9}{10^4}+\frac{9}{10^5}+\frac{18}{10^6}+\frac{9}{10^7}+\frac{9}{10^8}+\frac{9}{10^9}+\frac{18}{10^{10}}+\dots

gdzie liczba dziewiątek przed każdą kolejną 18 rośnie? Wtedy nie wystarczy wydzielić skończoną ilość razy wszystkich 10 z osiemnastek, bo w wyniku tego następuje przeniesienie i powstają kolejne dziesiątki i one nigdy się też w ten sposób nie skończą z powodu rosnącej liczby dziewiątek. W ten sposób, więc nie określimy szeregu sumy, ale możemy postąpić inaczej. Zobaczymy wkrótce w jak.

Do trzech razy sztuka.

Będziemy teraz chcieli wykonać dodawanie w ogólnej sytuacji

\displaystyle 0,a_1a_2a_3 + 0,b_1b_2b_3 = \sum_{n=1}^\infty \frac{a_n+b_n}{L^n}

Podzielmy z resztą przez L sumę cyfr a_n+b_n=d_nL+r_n. Mamy wtedy

\displaystyle \sum_{n=1}^\infty \frac{a_n+b_n}{L^n}=\sum_{n=1}^\infty \frac{d_nL+r_n}{L^n}=\sum_{n=1}^\infty \frac{d_n}{L^{n-1}}+\sum_{n=1}^\infty \frac{r_n}{L^n}=d_1 +\sum_{n=1}^\infty \frac{d_{n+1}+r_n}{L^n}.

Oznaczmy x_n=d_{n+1}+r_n począwszy od n=1. Z faktu, że 0 \leq a_n+b_n \leq L+L-2 wnioskujemy, że 0 \leq x_n \leq L. Zredukowaliśmy więc nieco naszą sumę. Gdyby przypadkiem to wystarczyło, to znaczy gdyby wszystkie x_n<L, to mamy już rozwinięcie sumy i możemy przerwać algorytm. W przeciwnym wypadku wykonamy kolejną redukcję. Analogicznie dzielimy z resztą x_n=d'_nL+r'_n.  Mamy więc

\displaystyle d_1 +\sum_{n=1}^\infty \frac{d_{n+1}+r_n}{L^n}=d_1+\sum_{n=1}^\infty \frac{x_n}{L^n}=d_1+d'_1 +\sum_{n=1}^\infty \frac{d'_{n+1}+r'_n}{L^n}.

Oznaczmy y_n=d'_{n+1}+r'_n. Jeśli wszystkie y_n<L, to możemy przerwać algorytm. W przeciwnym wypadku wykonamy kolejną i ostatnią redukcję, ale najpierw zauważmy, że y_n=L jest równoważne, że d'_{n+1}=1 i r'_n=L-1. Z pierwszej równości otrzymujemy, że x_{n+1}=L, a więc r'_{n+1}= 0, a to oznacza to, że y_{n+1}=d_{n+2}\leq 1. Z faktu r'_n=L-1 dostajemy natomiast, że y_{n-1}=0+ r'_{n-1}\leq L-1. Ciąg y_n jest więc takiej postaci, że przed L występują cyfry, bezpośrednio po nim cyfra 0 lub 1 a potem do następnego L znowu dowolne cyfry. W praktyce wystarczy poprzestać na dwóch redukcjach albo nawet na jednej, ale już dla świętego spokoju wykonamy trzecią. W tym momencie mamy

\displaystyle d_1+d'_1 +\sum_{n=1}^\infty \frac{d'_{n+1}+r'_n}{L^n}=d_1+d'_1 +\sum_{n=1}^\infty \frac{y_n}{L^n}.

Dzielmy z resztą y_n=d"_nL+r''_n, oznaczamy z_n=d''_{n+1} +r''_n i podobnie jak wcześniej dostajemy

\displaystyle d_1+d'_1 +\sum_{n=1}^\infty \frac{y_n}{L^n}=d_1+d'_1+d''_ 1+\sum_{n=1}^\infty \frac{z_n}{L^n}.

Wyjaśnimy teraz dlaczego ciąg z_n jest bardziej zredukowany. Ponownie mamy, że z_n=L wtedy i tylko wtedy, gdy d''_{n+1}=1 i r''_n=L-1. Równość d''_{n+1}=1 oznacza, że y_{n+1}=L, więc po pierwsze r''_{n+1}=0 a po drugie z wcześniejszych rozważań y_{n+2}\leq 1, a stąd d''_{n+2}=0, zatem z_{n+1}=0. Oczywiście oszacowanie z_{n-1}\leq L-1 zachodzi z tego samego powodu, co w wypadku ciągu y_n. Po trzeciej redukcji otrzymaliśmy ciąg, który, jeśli przyjmuje L, jest takiej postaci, że przed pierwszym wystąpieniem L mamy cyfry, potem 0, być może cyfry, lub od razu kolejne L itd. Gdyby ciąg już nie przyjmował L, to możemy zakończyć algorytm. W przeciwnym wypadku przechodzimy do następnego etapu.

Dodawanie pisemne

Gdy po trzech redukcjach nie osiągnęliśmy zadowalającego skutku, wiemy, że ciąg z_n przyjmuje gdzieś L. Jeśli skończoną ilość razy, to możemy stosować redukcje do skutku albo wykonać coś innego. Operacja ta będzie taka sama, gdy L będzie przyjmowane nieskończoną ilość razy, dlatego opiszę tylko ten przypadek. Załóżmy, że n_1<n_2<n_3 < \dots to wszystkie liczby naturalne takie, że z_{n_i}=L, oznaczymy jeszcze dla wygody n_0=0.  Załóżmy też bez straty ogólności, że z_1<L. Możemy więc teraz zapisać, że

\displaystyle \sum_{n=1}^\infty \frac{z_n}{L^n}=\sum_{i=1}^\infty \sum_{k=n_{i-1}+1}^{n_i} \frac{z_k}{L^k}=\sum_{i=1}^\infty \sum_{j=1}^{n_i-n_{i-1}} \frac{z_{n_{i-1}+j}}{ L^{n_{i-1}+j} }=\sum_{i=1}^\infty \frac{1}{L^{n_{i-1}}}\sum_{j=1}^{n_i-n_{i-1}} \frac{z_{n_{i-1}+j}}{ L^j }

Dalej przekształcając dostajemy

\displaystyle \sum_{i=1}^\infty \frac{1}{L^{n_{i-1}}}\sum_{j=1}^{n_i-n_{i-1}} \frac{z_{n_{i-1}+j}}{ L^j }

Następnie uwzględniając własności ciągu z_n oraz stosując dodawanie pisemne otrzymujemy

\displaystyle \sum_{i=1}^\infty \frac{1}{L^{n_{i-1}}}    \left( \begin{array}{lllllll}    &0,&0&z_{n_{i-1}+2}&\dots&z_{n_{i}-1}&L-1 \\    +&0,&0&0&\dots &0&1 \\ \hline    &0,&c_{n_{i-1}+1}&c_{n_{i-1}+2} &\dots & &c_{n_i-1}    \end{array} \right)

Inaczej zapisując mamy

\displaystyle \sum_{i=1}^\infty 0,\underbrace{0 \dots 0}_{n_i-1}c_{n_{i-1}+1} c_{n_{i-1}+2} \dots c_{n_i-1} = \sum_{n=1}^\infty \frac{c_n}{L^n}

Zatem znaleźliśmy rozwinięcie początkowej sumy i wynosi ono

\displaystyle 0,a_1a_2a_3 + 0,b_1b_2b_3= c_0,c_1c_2c_3 \dots

gdzie c_0=d_1+d'_1+d''_1 wynosi 0 lub 1.

Algorytm więc pozwala sprowadzić nas do sytuacji dodawania od lewej do prawej, co jest wygodne w przypadku poruszania się od jedynki do nieskończoności, choć to dodawanie od lewej do prawej w istocie polega na podzieleniu pracy na pewne segmenty, wewnątrz których wykonujemy dodawanie pisemne od prawej do lewej. :) Algorytm ma głównie sens teoretyczny. Być może dałoby się zaproponować pewną konstrukcję liczb rzeczywistych jako ciągów cyfr. Zresztą takie pomysły miał już Karl Weierstrass. Właśnie wzmianka na ten temat w pewnych tablicach matematycznych zachęciła mnie do próby odtworzenia takiej konstrukcji. Póki co mam tylko dodawanie, ale może w takim razie mnożenie też się da w miarę sensownie zdefiniować.

Reklamy