Dodawanie pisemne. Ułamki okresowe.

Samo zagadnienie dodawania pisemnego w systemach pozycyjnych o dowolnej podstawie jest sprawą dosyć banalną, o ile chodzi o sumowanie liczb całkowitych bądź ułamków o skończonych rozwinięciach. Okazuje się, że sumowanie ułamków okresowych jest mniej więcej zgodne z dodawaniem (pisemnym). Natomiast dodanie dwóch ułamków, z których przynajmniej jeden posiada rozwinięcie nieokresowe i nieskończone, przypuszczalnie nie będzie dało się ujarzmić żadną ładną regułką (w ogólnej sytuacji), a na pewno nie dodawaniem pisemnym, gdyż mogłoby wystąpić nieskończenie wiele przeniesień. Oczywiście taka suma będzie pewną liczbą, która posiada swoje rozwinięcie, ale wyznaczone będzie ono przez algorytm szacowania, który nie ma wiele wspólnego z sumowaniem poszczególnych cyfr.

Przykład 1.

Wątpię, aby docelowy czytelnik tego bloga nie spotkał się nigdy z dodawaniem pisemnym w systemie innym niż dziesiętny, ale na wszelki wypadek przyjrzyjmy się krótkiemu przykładowi sumowania w systemie siódemkowym.

\begin{array}{lllll}    &&_1&_1& \\    &6&1&5&5 \\    +&3&3&1&5 \\ \hline    1&2&5&0&3    \end{array}

Czyli gdy suma liczb przekroczy najwyższą cyfrę w systemie – w tym przypadku 6 – to wydzielamy z niej podstawę systemu – w tym przypadku 7 –  i to co zostanie zapisujemy pod spodem jako cyfrę sumy, a wydzieloną podstawę przenosimy dalej. Przyjrzyjmy się jak to wygląda od strony rachunków w ogólnej sytuacji, zanim zdefiniujemy algorytm.

Powiedzmy, że mamy dane dwie liczby a_N\dots a_1a_0 i b_N\dots b_1b_0, jak zwykle w systemie pozycyjnym o podstawie L>1. Przy czym N jest długością dłuższej z liczb, o ile nie są równej długości. Chcemy wyznaczyć reprezentację liczby a_N\dots a_1a_0+ b_N\dots b_1b_0. Przez c_n będziemy oznaczać uzyskane cyfry tejże sumy, a pomocniczo będziemy jeszcze budować ciąg s_n, odpowiadający sumie cyfr i przeniesienia. Rozpiszmy więc naszą liczbę.

a_N\dots a_1a_0+ b_N\dots b_1b_0=(a_NL^N+\dots + a_1L +a_0) +(b_NL^N+\dots + b_1L +b_0)=(a_N+b_N)L^N+\dots + (a_1+b_1)L +a_0 + b_0

Oznaczamy s_0=a_0+b_0 i dzielimy z resztą przez L. Dostajemy

s_0=d_L(s_0)L+c_0

Wstawiając

(a_N+b_N)L^N+\dots + (a_1+b_1)L +d_L(s_0)L+c_0=

(a_N+b_N)L^N+\dots + (a_1+b_1+d_L(s_0))L +c_0

Widać więc, że reszta c_0 jest zerową cyfrą sumy, natomiast d_L(s_0) wartością ewentualnego przeniesienia. Oznaczamy pomocniczo s_1=a_1+b_1+d_L(s_0) i ponownie dzielimy z resztą. Dostajemy s_1=d_L(s_1)L+c_1. Mamy więc

(a_N+b_N)L^N+\dots + (a_2+b_2)L^2+((d_L(s_1)L+c_1)L +c_0

i dalej

(a_N+b_N)L^N+\dots + (a_2+b_2+d_L(s_1))L^2+c_1L +c_0

Następnym krokiem będzie wydzielenie z resztą s_2=a_2+b_2+d_L(s_1), ale nie będziemy go już wykonywać.

Algorytm dodawania pisemnego.

Definiujemy zatem pomocniczo ciąg tymczasowych sum

\left\{ \begin{array}{l}s_0=a_0+b_0 \\    s_{n+1}=a_{n+1}+b_{n+1}+d_L(s_n) \end{array} \right.

i ciąg cyfr wzorem

c_n=r_L(s_n).

Na pierwszy rzut oka widać, że jest to ciąg cyfr, gdyż jest ciągiem reszt. Natomiast zostaje nam do wykazania, że jest to reprezentacja pewnej liczby całkowitej, tzn. od pewnego momentu cały czas przyjmuje zera, a co więcej, że jest reprezentacją a_N\dots a_1a_0+ b_N\dots b_1b_0. Dodatkowo uzasadnimy, że przeniesienie, to jest d_L(s_n) wynosi co najwyżej 1 (nieujemność sobie darujemy) i że nasza reprezentacja jest długości co najwyżej N+1.

Fakt 1.

W każdym kroku przeniesienie wynosi co najwyżej 1, tj. dla każdego naturalnego n zachodzi d_L(s_n) \leq 1.

Dowód.

Indukcja ze względu n. Dla n=0. Mamy s_0=a_0+b_0=L-1+L-1=L+L-2, zatem d_L(s_0) \leq 1. Teraz jeśli założymy, że d_L(s_n)\leq1, to rozpisując z definicji i szacując z założenia

s_{n+1}=a_{n+1} +b_{n+1}+d_L(s_n) \leq L+L-2 + 1 \leq L+L-1

zatem nadal d_L(s_{n+1}) \leq 1

Wniosek.

Ciąg \{s_n\}_{n=0}^\infty jest stale równy zero począwszy od N+2 elementu.

Dowód.

Ponieważ liczby a_N\dots a_1a_0, b_N\dots b_1b_0 mają długość co najwyżej N, więc dla każdego n>N

a_n=0  i b_n=0

Zatem uwzględniając jeszcze Fakt 1 mamy

s_{N+1}=a_N+b_N + d_L(s_N) \leq 1

a stąd d_L(s_{N+1})=0, gdyż L \geq 2

i co za tym idzie

s_{N+2}=a_{N+2}+a_{N+2}+d_L(s_{N+1})=0

Teraz jeśli s_n=0 dla n>N+1, to d_L(s_n)=0 i

s_{n+1}=a_{n+1}+b_{n+1}+d_L(s_n)=0

Fakt 2.

Ciąg \{c_n\}_{n=0}^\infty jest przedstawieniem liczby całkowitej o długości co najwyżej N+1, gdzie c_{N+1}\leq 1, a dokładniej to, N+1-sza cyfra jest równa wartości ostatniego przeniesienia c_{N+1}=d_L(s_N).

Dowód.

Na podstawie wniosku dla każdego n>N+1 zachodzi s_n=0, zatem także c_n=r_L(s_n)=0. Dodatkowo z definicji oraz Faktu 1 s_{N+1}=d_L(s_N) \leq 1, więc także c_{N+1}=r_L(d_L(s_N))=d_L(s_N)\leq 1.

Fakt 3.

c_{N+1}c_N\dots c_1 c_0= a_N\dots a_1a_0+ b_N\dots b_1b_0

Dowód.

Indukcyjnie ze względu na N. Dla N=0 mamy

a_0+b_0=s_0=d_L(s_0)L+c_0=r_L(a_1+b_1+d_L(s_0))L+c_0

gdyż a_1+b_1=0 i przeniesienie d_L(s_0)\leq 1.

Z definicji s_1=a_1+b_1+d_L(s_0) oraz c_1=r_L(s_1). Zatem

a_0+b_0=r_L(s_1)L+c_0=c_1L+c_0=c_1c_0.

Załóżmy teraz, że dodawanie pisemne działa dla wszystkich par liczb x_{N_1}\dots x_1x_0, y_{N_2}\dots y_1y_0, dla których \max\{N_1,N_2\} \leq N i rozważmy sumę

a_{N+1}\dots a_1a_0+ b_{N+1}\dots b_1b_0

dowolnych dwóch liczb, których długość nie przekracza N+1.

Możemy zapisać, że

a_{N+1}\dots a_1a_0+ b_{N+1}\dots b_1b_0= L^{N+1}(a_{N+1}+b_{N+1}) + (a_N\dots a_1a_0+ b_N\dots b_1b_0)

Z założenie indukcyjnego, możemy zastosować algorytm dodawania pisemnego dla sumy

a_N\dots a_1a_0+ b_N\dots b_1b_0.

Niech \{a'_n \}_{n=0}^\infty, \{b'_n \}_{n=0}^\infty będą odpowiednio rozwinięciami liczb a_N\dots a_1a_0 oraz b_N\dots b_1b_0, a \{s'_n \}_{n=0}^\infty i \{c'_n \}_{n=0}^\infty odpowiednio sumami tymczasowymi i rozwinięciem wynikającym z zastosowania dodawania pisemnego dla tych liczb.

Oczywiście mamy

a_n'=a_n i b'_n=b_n dla n\leq N oraz a'_n=0=b'_n dla n>N.

Zauważmy więc, że

s'_0=a'_0+b'_0=a_0+b_0=s_0

s'_1=a'_1+b'_1+d_L(s'_0)=a_1+b_1+d_L(s_0)=s_1

\vdots

s'_N=a'_N+b'_N+d_L(s'_{N-1})=a_N+b_N+d_L(s_{N-1})=s_N

s'_{N+1}=a'_{N+1}+b'_{N+1}+d_L(s'_N)

Zatem również c'_n=c_n dla n \leq N i oczywiście c'_n=0 gdy n>N+1.

Dostajemy więc, że

a_N\dots a_1a_0+ b_N\dots b_1b_0=c'_{N+1}c_N\dots c_1 c_0.

A stąd

a_{N+1}\dots a_1a_0+ b_{N+1}\dots b_1b_0= L^{N+1}(a_{N+1}+b_{N+1} +c'_{N+1}) + c_N\dots c_1 c_0

Mamy

a_{N+1}+b_{N+1} +c'_{N+1}=a_{N+1}+b_{N+1}+d_L(s_N)=s_{N+1}=d_L(s_{N+1})L+c_{N+1}

gdyż z Faktu 2 c'_{N+1}=d_L(s'_N) \leq 1 a dodatkowo s'_N=s_N.

Z Faktu 2 wiemy również, że c_{N+2}=d_L(s_{N+1}) zatem ostatecznie

\displaystyle a_{N+1}\dots a_1a_0+ b_{N+1}\dots b_1b_0= L^{N+1}(c_{N+2}L+c_{N+1}) + c_N\dots c_1 c_0=c_{N+2}\dots c_1 c_0

co kończy dowód.

Podobnie można sobie poradzić z odejmowaniem pisemnym. Rozważmy dwa przykłady.

Odejmowanie 123-89 w systemie dziesiątkowym.

Pisemnie

\begin{array}{lllll}    &&&_{+10}& \\    &&_{-1}&_{-1}&_{+10} \\    &&1&2&3 \\    -&&&8&9 \\ \hline    &&&3&4    \end{array}

W postaci jawnej

123-89=10^2 +2\cdot 10 + 3 - (8\cdot10 + 9)= 10^2 +(2-8)\cdot 10 + (3-9)

Dzielimy z resztą 3-9=-6 przez 10 i wychodzi -6=-10 +4. Zauważmy, że podzielenie z resztą sprowadza się właśnie do dodania i odjęcia dziesiątki, gdyż -10+(10+3-9)=-10 + 4. Wracamy do obliczeń wstawiając otrzymaną wartość

10^2 +(2-8)\cdot 10 + (3-9)= 10^2 +(2-8)\cdot 10 -10 +4=10^2 +(2-8-1)\cdot 10 +4

Zajmujemy się teraz 2-8-1. Widać, że z powodu pożyczonej dziesiątki pojawiła się nam teraz -1. Ponownie dzielimy z resztą, czyli -10+(10+2-8-1)=-10+3, a stąd

10^2 +(2-8-1)\cdot 10 +4=10^2 +(-10 +3)\cdot 10 +4=10^2 -1\cdot10^2 +3\cdot 10 +4=34.

Odejmowanie w systemie ósemkowym

\begin{array}{lllll}    &&_{+8}&_{+8}& \\    &_{-1}&_{-1}&_{-1}&_{+8} \\    &1&0&0&0 \\    -&&&&1 \\ \hline    &&7&7&7    \end{array}

Zatem stosujemy taki sam algorytm, ale przyjmujemy s_n=a_n-b_n i wtedy przeniesienia będą wynosiły -1 lub 0, gdyż -L+1 \leq a_n-b_n \leq L -1.  Jeśli a_N\dots a_1a_0 > b_N\dots b_1b_0, to otrzymamy poprawny wynik. Zauważmy, że nierówność ta oznacza, że istnieje 0 \leq k \leq N takie, że a_k>b_k i a_n \geq b_n dla n > k.

Zatem

L- 1\geq s_k=a_k-b_k+d_L(s_{k-1})\geq 0

a stąd d_L(s_k)=0 i

s_{k+1}=a_{k+1}-b_{k+1} \geq 0

\vdots

L- 1 \geq s_N=a_N-b_N \geq 0

więc s_{N+1}=0 i wszystkie następne też.

Dowód indukcyjny faktu, że

c_{N+1}c_N\dots c_1 c_0= a_N\dots a_1a_0 - b_N\dots b_1b_0

będzie przebiegał bardzo podobnie, dlatego go sobie podarujemy. Można też uzasadnić odejmowanie przy pomocy dodawania.

Mając dodawanie (odejmowanie) pisemne liczb całkowitych możemy też dodawać (odejmować) pisemnie ułamki o skończonych rozwinięciach, gdyż

0,a_N\dots a_1a_0 + 0,b_N \dots b_1b_0=L^{-(N+1)}(a_N\dots a_1a_0 + b_N \dots b_1b_0)=

L^{-(N+1)}c_{N+1}c_N\dots c_1 c_0=c_{N+1},c_N\dots c_1 c_0

Teraz zajmiemy się działaniami na ułamkach okresowych. Najpierw pewne spostrzeżenie.

Obserwacja.

Jeśli dana jest pewna liczba x przy pomocy okresowego rozwinięcia

x=0,c_1c_2\dots c_N(c_{N+1}\dots c_{N+T})

to dla dowolnego naturalnego k>0 zachodzi

  1. x=0,c_1c_2\dots c_{N+k}(c_{k+N+1}\dots c_{k+N+T})
  2. x=0,c_1c_2\dots c_N(c_{N+1}\dots c_{N+T} c_{N+T+1}\dots c_{N+T+T} \dots c_{N+1+Tk} \dots c_{N+T+Tk})

Możemy zatem zawsze sprowadzić dwa ułamki okresowe do takiej samej postaci. Zobaczmy jak to wygląda w praktyce.

Przykład 2.

Rozważmy ułamki 0,1234(56) oraz 0,123(456). Tak będziemy manipulować okresami, aby były równej długości i zaczynały się od tego samego miejsca.

0,123(456)=0,1234(564)=0,1234(564564)

0,1234(56)=0,1234(565656)

Wniosek.

Dowolne dwa ułamki okresowe możemy sprowadzić do takiej samej postaci.

Dowód.

Rozważmy ułamki okresowe

x=0,c_1c_2\dots c_{N_1}(c_{N_1+1}\dots c_{N_1+T_1})

y=0,d_1d_2\dots d_{N_2}(d_{N_2+1}\dots d_{N_2+T_2})

Przyjmijmy, że np. N_2\geq N_1. Wtedy na podstawie Obserwacji

x=0,c_1c_2\dots c_{N_2}(c_{N_2+1}\dots c_{N_2+T_1T_2})

y=0,d_1d_2\dots d_{N_2}(d_{N_2+1}\dots d_{N_2+T_1T_2}).

Oczywiście zamiast T_1T_2 można też wziąć NWW(T_1,T_2), tak jak Przykładzie 2.

Rozważymy za moment przykład, który naprowadzi nas na zasadę dodawania ułamków okresowych, ale najpierw przypomnijmy, że  gdy mamy liczbę

x=0,c_1c_2\dots c_N (d_1d_2\dots d_T).

Wtedy

\displaystyle x=\frac{c_1c_2\dots c_Nd_1d_2 \dots d_T-c_1c_2\dots c_N}{L^N(L^T-1)}= \frac{c_1c_2\dots c_N, d_1d_2 \dots d_T-0,c_1c_2\dots c_N}{L^T-1}

(Patrz: Dzielenie pisemne. Rozwijanie liczb wymiernych na ułamki okresowe cz. II)

W szczególności

0, (d_1d_2\dots d_T)=\frac{d_1d_2\dots d_T}{L^T-1}

oraz

0,\underbrace{00\dots 0}_{\mbox{N-razy}} (d_1d_2\dots d_T)=\frac{1}{L^N}\frac{d_1d_2 \dots d_T}{L^T-1}

Dodatkowo przypomnijmy, że

L^T-1=(L-1)L^{T-1}+\dots + (L-1)L +L-1=\underbrace{ L-1 L-1 \dots L-1}_{\mbox{T-razy}}

Przykład 3.

Dodamy liczby 0,(543) i 0,(345) w systemie dziesiątkowym.

0,(543)+0,(365)=\frac{543}{999}+\frac{365}{999}=\frac{908}{999}=0,(908)

Jednocześnie

\begin{array}{lllll}    &&_1&& \\    &0,&5&4&3 \\    +&0,&3&6&5 \\ \hline    &0,&9&0&8    \end{array}

Wydawałoby się więc, że ułamki okresowe o wspólnej postaci dodaje się tak jakby nie miały okresu, a potem dopisuje się okres, ale nie zawsze jest to prawdą. Jednak prawdziwa będzie własność.

Własność.

Jeśli dane są ułamki okresowe 0,(b_1b_2\dots b_T) oraz 0,(d_1d_2\dots d_T). Wtedy jeśli

\displaystyle b_1b_2\dots b_T+ d_1d_2\dots d_T \leq \underbrace{L-1L-1\dots L-1,}_{\mbox{T-razy}}=L^T-1

to

0,(b_1b_2\dots b_T) + 0,(d_1d_2\dots d_T)= 0,(c_1c_2\dots c_T),

gdzie c_1c_2\dots c_T=b_1b_2\dots b_T+ d_1d_2\dots d_T.

Dowód.

Zauważmy tylko jedną rzecz, że założenie gwarantuje nam, że istotnie przedstawienie b_1b_2\dots b_T+ d_1d_2\dots d_T będzie miało zerową cyfrę c_{T+1}, gdyż nie będzie ostatniego przeniesienia.  Możemy teraz na podstawie wcześniejszych uwag wyliczyć sumę.

b=0,(b_1b_2\dots b_T) + 0,(d_1d_2\dots d_T)=\frac{b_1b_2\dots b_T}{L^T-1}+\frac{d_1d_2\dots d_T}{L^T-1}=\frac{c_1c_2\dots c_T}{L^T-1}\leq 1

a stąd

0,(b_1b_2\dots b_T) + 0,(d_1d_2\dots d_T)=0,(c_1c_2\dots c_T).

Jeśli chcemy dodać liczby postaci 0,a_1a_2\dots a_N (b_1b_2\dots b_T), 0,c_1c_2\dots c_N (d_1d_2\dots d_T) o okresach spełniających powyższe założenia, to sprowadzamy sytuację do znanej:

0,a_1a_2\dots a_N (b_1b_2\dots b_T)+0,c_1c_2\dots c_N (d_1d_2\dots d_T)=

0,a_1a_2\dots a_N+0,c_1c_2\dots c_N+ \frac{1}{L^N}(0,(b_1b_2\dots b_T) + 0,(d_1d_2\dots d_T))

Ponieważ sumowanie okresów (przy założeniu z Własności) nie daje nam przeniesienia poza nie, więc możemy zastosować dodawanie pisemne do całości ułamków.

Na koniec przyjrzymy się sytuacji, gdy nie jest spełnione założenie odnośnie okresów.

Przykład 4.

Dodajmy teraz do siebie ułamki 0,(998)+0,(002) (w systemie dziesiątkowym). Na podstawie Własności 0,(002)=0,(001)+0,(001), a więc

0,(998)+0,(002)=0,(998)+0,(001)+0,(001)=0,(999)+0,(001)=1,(001)

ale

\begin{array}{lllll}    &_1&_1&_1& \\    &0,&9&9&8 \\    +&0,&0&0&2 \\ \hline    &1,&0&0&0    \end{array}

Podwójne przeniesienie

Ogólnie w  przypadku gdy \displaystyle b_1b_2\dots b_T+ d_1d_2\dots d_T=c_{T+1}c_T\dots c_1c_0, mamy

c_{T+1}c_T\dots c_1c_0 \leq 1 \underbrace{L-1L-1\dots L-1}_{\mbox{T-1-razy}} L-2

i wtedy (gdy c_{T+1}=1)

\displaystyle 0,(b_1b_2\dots b_T)+ 0,(d_1d_2\dots d_T)=\frac{1 c_T \dots c_1c_0}{L^T-1}=\frac{L^T}{L^T-1}+\frac{c_T\dots c_1c_0}{L^T-1}=

\displaystyle \frac{L^T-1}{L^T-1}+\frac{c_T\dots c_1c_0+1}{L^T-1}=1,(c'_1c'_2 \dots c'_T)

gdzie c'_1c'_2 \dots c'_T=c_T\dots c_1c_0+1.

Można, więc powiedzieć, że gdy sumowanie liczb w okresie powoduje przeniesienie za okres, to obowiązuje zasada podwójnego przeniesienia, którą rozumiemy w ten sposób, że dodajemy pisemnie ułamki okresowe, jakby nie miały okresu a następnie do uzyskanej sumy dodajemy liczbę

0,0\dots01, gdzie 1 jest na T-tym miejscu po przecinku i dopiero wtedy dopisujemy okres.

Daje to nam możliwość w miarę sensownego i zgodnego z działaniami na liczbach wymiernych, zdefiniowania dodawania dla ciągów cyfr skończonych i okresowych, dzięki czemu można by się pokusić o jakąś alternatywną konstrukcję liczb wymiernych przy pomocy takich ciągów. Jednak jak się okaże byłaby to bardzo problematyczna sztuka dla sztuki. Będziemy jeszcze dyskutować tę ideę w następnych wpisach

Advertisements

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