Arytmetyka binarna

Wstęp

Wszystkie urządzenia elektroniczne (w tym mikroprocesory) wykorzystują do obliczeń system binarny. System binarny jest pozycyjnym systemem liczbowym tzn.,że wartość danej cyfry zależy od jej położenia. W zapisie liczb w systemie dwójkowym używamy dwóch cyfr 0 i 1. Podstawą tego systemu liczbowego jest liczba 2 (stąd jego nazwa: dwójkowy). Oznacza to, że kolejne liczby licząc od prawej strony będą przyjmowały wartość 2⁰, 2¹, 2²... itd.

(ABCD)₂ = (D*2⁰ + C*2¹ + B*2² + A*2³)₁₀

Zamiana liczb dziesiętnych na system binarny

Zamianę tę przeprowadzamy dzieląc z resztą liczbę dziesiętną przez 2, pamiętając o późniejszym "wyrzuceniu" zbędnych zer z lewej strony np.: (0010110)₂ = (0010110)₂ = (10110)₂

(583)₁₀ = (1001000111)₂

Zamiana liczb binarnych na system dziesiętny

Dokonujemy jej według wzoru ze wstępu.

1*2⁵ + 1*2⁴ + 1*2³ + 1*2² + 0*2¹ + 0*2⁰ = 1*32 + 1*16 + 1*8 + 1*4 + 0*2 + 0*1 = 32 + 16 + 8 + 4 = 60

(111100)₂ = (60)₁₀

Dodawanie liczb binarnych

Liczby binarne dodajemy do siebie analogicznie, jak liczby dziesiętne, pamiętając o tym, że: 0+0=0, 0+1=1, 1+0=1, 1+1=0 i 1 przeniesienia, 1+1+1=1 i 1 przeniesienia.

(220)₁₀ + (122)₁₀ = (342)₁₀
(11011100)₂ + (1111010)₂ = (101010110)₂

Odejmowanie liczb binarnych

O ile dodawanie jest proste, to z odejmowaniem jest juz trudniej. Najlepszą metodą jest zamienić odjemnik na liczbę w ujemnym systemie binarnym i skorzystać z zasad:

Mnożenie liczb binarnych.

Mnożenie nie jest zbyt skomplikowane. Polega ono na systematycznym przesuwaniu czynnika 1 w zależności od stanu bitów czynnika 2. Jeżeli w czynniku 2 jest "1" to przepisujemy cały czynnik 1, natomiast jak jest "0" to przepisujemy tyle zer ile jest bitów czynnika 1. Następnie przesuwamy się o 1 pozycję w lewo i powtarzamy operację. I tak aż do końca czynnika 2.

Pomnożymy liczbę (101)₂ przez (110)₂ czyli (5*6)₁₀ :

(1110)₂ = (30)₁₀.

Pomnożymy liczbę (11011)₂ przez (10110)₂ czyli (27*22)₁₀ :

(1001010010)₂ = (594)₁₀.

Dzielenie liczb binarnych

Dzielenie binarne jest najbardziej skomplikowaną operacją arytmetyczną z dotychczas opisywanych. Wymyślono wiele algorytmów efektywnego dzielenia, ale dla naszych potrzeb wystarczy znany wam algorytm szkolny, który polega na cyklicznym odejmowaniu odpowiednio przesuniętego dzielnika od dzielnej. W systemie dwójkowym jest to szczególnie proste, ponieważ dzielnika nie musimy mnożyć. Oto odpowiedni przykład:

Podzielimy liczbę (1110)₂ przez (11)₂ czyli (14:3)₁₀ :

1. Przesuwamy w lewo dzielnik, aż zrówna się jego najstarszy, niezerowy bit z najstarszym, niezerowym bitem dzielnej. Nad dzielną rysujemy kreseczkę:





2. Jeśli dzielnik da się odjąć od dzielnej bez niedomiaru, to nad kreską w kolumnie najmłodszego bitu dzielnika wpisujemy 1 i wykonujemy odejmowanie:






3. Dzielnik przesuwamy o jeden bit w prawo i próbujemy tego samego z otrzymaną różnicą. Jeśli odejmowanie jest możliwe, to nad kreską w następnej kolumnie dopisujemy 1, odejmujemy dzielnik od różnicy, przesuwamy go o 1 bit w prawo i kontynuujemy. Jeśli odejmowanie nie jest możliwe, to dopisujemy nad kreską 0, przesuwamy dzielnik o 1 bit w prawo i kontynuujemy.





4. Operacje te wykonujemy dotąd, aż dzielnik osiągnie swoją pierwotną wartość. Pozostała dzielna jest resztą z dzielenia.

W naszym przykładzie otrzymaliśmy wynik (100)₂ i resztę (10)₂ czyli (4 i 2)₁₀. Jest to wynik poprawny, gdyż 3 mieści się w 14 cztery razy i pozostaje reszta 2.

Dla wprawki podzielmy liczbę (110101101)₂ przez (111)₂ czyli (429:7)₁₀ :

(110101101)₂ : (111)₂ = (111101)₂i reszta (10)₂ czyli (429 : 7 = 61 i reszta 2)

Materiał z http://mikroklocki.elektroda.net/index.php?action=lekcja&id=1

Algorytmy arytmetyczne - wstęp

1. REPREZENTACJA LICZB W SYSTEMACH POZYCYJNYCH.

Dowolną liczbę możemy utożsamiać z jej reprezentacją w pewnym systemie pozycyjnym. Zwyczajowo używamy systemu dziesiętnego, który ze względu na swoją popularność wydaje się najbardziej oczywistą z podstaw matematyki. Przyjrzyjmy się reprezentacji liczby 15208 w systemie dziesiętnym. Jest to oczywiście następująca suma:

15208 = 1*10⁴ + 5*10³ + 2*10² + 0*10¹ + 8*10⁰

Zatem jest to wartość pewnego wielomianu w punkcie x=10, współczynnikami tego wielomianu są zaś kolejne cyfry zapisu liczby w systemie dziesiętnym. W ogólności dowolną liczbę L możemy jednoznacznie wyrazić za pomocą podobnej sumy:

L= an*xⁿ + an-1*x^n-1 +…+ a2*x² + a1*x¹ + a0*x⁰

Gdzie x jest podstawą danego systemu, pozycyjnego, zaś współczynniki an, an-1,..., a2, a1, a0, to kolejne cyfry rozwinięcia danej liczby w systemie o podstawie x. Oczywiście każdy ze współczynników spełnia nierówność x > a 3 0.
Bardzo interesującym ze względu na zastosowanie w programowaniu jest tzw. system binarny, czyli system o podstawie równej 2. Każda liczba całkowita ma jednoznaczną reprezentację w tym systemie (wynika to z powyższych wniosków). Przyjrzyjmy się zatem reprezentacji liczby 15208 = 11101101101000b. A zatem wnioskujemy że:

15208=1*2¹³ +1*2¹² +1*2¹¹ +0*2¹⁰ +1*2⁹ +1*2⁸ +0*2⁷ +1*2⁶ +1*2⁵ +0*2⁴ +1*2³ +0*2² +0*2¹ + 0*2⁰

Co oczywiście, jak łatwo sprawdzić, jest prawdą. System binarny jest bardzo korzystny w informatyce, ze względu na fakt iż występują w nim tylko dwie cyfry 0 i 1 (zwane częściej bitami). Z tego względu możliwe jest wykonywanie operacji logicznych na liczbach, a poprzez operacje logiczne, także możliwe jest proste zaimplementowanie operacji arytmetycznych. Wszystko to dzieje się bez udziału programisty wewnątrz procesora, dobry programista powinien być jednak obeznany z tym systemem, i umieć wykonywać podstawowe operacje na liczbach w nim reprezentowanych. W systemach pozycyjnych o podstawach większych od zera (takie o podstawach np. -2 też istnieją, jednak to już bardziej skomplikowana sprawa), prawdziwe pozostają prawie wszystkie algorytmy obliczeniowe jakie poznajemy w szkole. I tak, możliwe jest dodawanie, odejmowanie i mnożenie wykonywane w sposób absolutnie identyczny jak w systemie dziesiętnym. Z dzieleniem sprawa jest odrobinę bardziej subtelna. Aby jednak zapoznać się z algorytmami arytmetycznymi, najpierw warto zacząć od operacji logicznych, możliwych do wykonania na liczbach w takich językach programowania jak Pascal. Operacje te okażą się później bardzo ważne.

2. REPREZENTACJA LICZB W KOMPUTERZE

W komputerach zazwyczaj liczby są reprezentowane binarnie w strukturach o ściśle określonej ilości bitów. I tak struktura 8 bitowa zwana jest bajtem, 16 bitowa słowem, 32 bitowa podwójnym słowem itd.

BAJT

0

0

0

0

0

0

0

0

SLOWO

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

Bajt mając 8 bitów może pomieścić liczbę z zakresu 0-255, słowo 0-65535 itd. Wykonując wszelkie operacje na komputerze w istocie wykonujemy je na bajtach lub słowach. Podstawowe operacje takie jak dodawanie, mnożenie, dzielenie itp., procesor wykonuje na tych strukturach automatycznie, dlatego możemy to wykorzystać.
Bity znajdujące się od strony lewej mają znaczący wpływ na wartość bajtu lub słowa, dlatego nazywamy je bardziej znaczącymi bitami. Odpowiednio te z prawej strony nazywamy mniej znaczącymi bitami. Słowo jak łatwo zauważyć składa się z dwóch bajtów. O tym od lewej mówimy że jest to bardziej znaczący bajt słowa, o tym od prawej odpowiednio, mniej znaczący bajt słowa.

3. PRZEGLĄD NAJWAŻNIEJSZYCH OPERACJI LOGICZNYCH

Do dyspozycji programisty w praktycznie każdym kompilowanym języku programowania jest kilka podstawowych operacji logicznych jakie może on wykonywać na bitach. Są to odpowiednio AND, OR, NOT, SHL, SHR.

a) AND
Inaczej koniunkcja lub iloczyn logiczny. Jest to operacja dwuargumentowa operująca na bitach. Bit wyniku jest ustawiany na 1 jeśli odpowiadające mu bity argumentów były równe 1, w innym wypadku ustawiane jest zero.

p AND q	1	0
1	1	0
0	0	0

Przykład 1. Wykonajmy operacje AND na następujących liczbach:

	0	1	1	0	1	0	1	1	0	1
AND	1	1	0	0	1	1	0	1	0	0
	0	1	0	0	1	0	0	1	0	0

Ćwiczenie : wykonaj operacje AND dla poniższego przykładu:

1	1	0	1	1	0	1	1	0	0
1	0	0	1	1	0	0	0	1	1

Przykład 2. Załóżmy, że mamy liczbę B=00001111b=15. Będziemy się przyglądać wynikom operacji AND na kilku przykładowych liczbach.

16=00010000b 00010000 AND 00001111 = 00000000 = 0 = 16 mod 16
10=00001010b 00001010 AND 00001111 = 00001010 = 10 = 10 mod 16
17=00010001b 00010001 AND 00001111 = 00000001 = 1 = 17 mod 16
20=00010100b 00010100 AND 00001111 = 00000100 = 4 = 20 mod 16

Wniosek? Gdy chcemy obliczyć resztę z dzielenia liczby A przez dowolną potęgę dwójki B, wystarczy zbadać wynik operacji A AND (B-1). Operacja taka wykona się znacznie szybciej niż modulo.

b) OR
Inaczej alternatywa lub suma logiczna. Jest to operacja dwuargumentowa, bit wyniku jest ustawiany na 1 gdy co najmniej jeden z odpowiadających mu bitów argumentów jest równy 1.

p OR q	1	0
1	1	1
0	1	0

Przykład 1. Wykonajmy operacje OR na następujących liczbach:

	0	1	1	0	1	0	1	1	0	1
OR	1	1	0	0	1	1	0	1	0	0
	1	1	1	0	1	1	1	1	0	1

Ćwiczenie : wykonaj operacje OR dla poniższego przykładu:

1	1	0	1	1	0	1	1	0	0
1	0	0	1	1	0	0	0	1	1

c) NOT
Zaprzeczenie lub negacja. Jest to operacja jednoargumentowa i polega na zamianie jedynek na zera i zer na jedynki.

	1	0
NOT	0	1

d) SHL
Skrót od angielskiego SHIFT LEFT, czyli przesuń w lewo. Jest to operacja dwuargumentowa, wszystkie bity pierwszego argumentu przesuwane są w lewo o tyle miejsc ile wynosi wartość drugiego argumentu. W miejsce przesuniętych bitów od prawej strony wstawiane są zera.

Przykład 1.
A = 25 = 00011001b. A SHL 1 = 00110010b = 50
B = 11 = 00001011b. B SHL 2 = 00101100b = 44
C = 1 = 00000001b. C SHL 4 = 00010000b = 16

Wniosek? Operacja A SHL B odpowiada dokładnie mnożeniu A * 2^B . Gdy potrzebujemy zatem cos przemnożyć przez 2,4,8... to zdecydowanie szybciej i bardziej optymalnie będzie wykonać SHL o 1,2,3... Operacja SHL wykona się znacznie szybciej niż mnożenie.

e) SHR
Skrót od angielskiego SHIFT RIGHT, czyli przesuń w prawo. Operacja odpowiadająca SHL tyle, że przesuwająca w prawo a nie w lewo. Łatwo się domyślić, że wykonanie operacji A SHR B odpowiada dokładnie operacji A div 2^B , tyle że wykona się znacznie szybciej.

Ćwiczenia.
Wylicz następujące wartości, następnie sprawdź czy wykonałeś dobrze, pisząc stosowny programik sprawdzający:

225 SHL 2 = ?
47 SHR 1 = ?
97 OR (15 SHL 1) = ?
(315 AND 255) SHL (12 OR 13) = ?
512 OR (256 AND 16) = ?
17 AND ((1024 SHR 6) - 1) = ?

4. BINARNE ALGORYTMY ARYTMETYCZNE

Dodawanie)
Dodawanie binarne polega w istocie dokładnie na tym samym na czym polega dodawanie w słupkach liczb dziesiętnych. Zatem pojedynczym kroku dodajemy do siebie odpowiednie bity argumentów, następnie ustawiamy odpowiednio bit wyniku, zapisujemy ewentualne przeniesienie i przenosimy się do następnego bitu.

1	1					1		<- przeniesienie
0	1	1	0	1	1	0	1	A
0	1	1	0	0	0	0	1	B
1	1	0	0	1	1	1	0	A+B

Widać zatem, że binarne dodawanie nie wymaga szczególnej filozofii. Proponuję na rozgrzewkę wykonać ćwiczenie:

								<- przeniesienie
0	1	1	1	0	1	1	1	A
0	0	0	1	0	0	1	1	B
								A+B

Odejmowanie)
Nie wymaga chyba specjalnego komentarza, wykonuje się tak samo jak dodawanie, tyle że zamiast przeniesienia mamy pożyczkę, którą odejmujemy od następnych bitów. Warto może tylko zaznaczyć następujący przykład:
00000000b - 00000001b = 11111111b = 255 .
Jest to tak zwane dopełnienie liczby. W obrębie bajtu wszystkie operacje wykonywane są modulo 256, zatem
11111111b + 00000001b = 255 + 1 = 256 mod 256 = 0.
Trzeba jednak uważać, gdyż na przykład w słowie operacje są wykonywane modulo 65536. Aby więc pozwalać sobie na takie sztuczki musimy być pewni na jakim typie operujemy.

Mnożenie)
Również mnożenie wykonuje się w sposób podobny jak w szkole, wykorzystujemy w tym algorytmie tylko dodawanie:

				1	1	1	0	1
		*		0	1	0	1	0
				0	0	0	0	0
			1	1	1	0	1
		0	0	0	0	0
+	1	1	1	0	1
0	0	0	0	0
1	0	0	1	0	0	0	1	0

Dzielenie)
Jak już wspomniałem z dzieleniem sprawa jest odrobinkę bardziej subtelna. W algorytmie którego uczymy się ze szkoły wykorzystujemy już dzielenie mniejszych liczby (w pojedynczych krokach). Jak na razie binarnie nie umiemy podzielić żadnej liczby (chyba że przez potęgę 2 za pomocą SHR). Umiemy jedynie dodawać, odejmować, mnożyć i przesuwać.

Na początku można od razu wpaść na prosty algorytm z dodawaniem. Mianowicie wystarczy dodawać dzielnik do dodatkowej zmiennej (zainicjowanej na zero), do czasu gdy dzielna będzie od niej mniejsza. Wtedy ilość wykonanych dodawań (minus jeden) będzie wynikiem operacji div, a dzielna minus to co pozostanie w dodatkowej zmiennej (minus dzielnik) będzie wynikiem operacji mod.

Czy ten algorytm jest wydajny? Już pierwszy rzut oka przekonuje nas, że nie. Na przykład 3 000 000 000 : 3 wymagało by miliarda dodawań, a to nawet na najszybszych komputerach działało by długo. Złożoność czasowa tego algorytmu jest liniowa ze względu na wartość liczby, a więc wykładnicza ze względu na długość zapisu liczby. Zatem czas działania naszego naiwnego algorytmu rośnie zastraszająco szybko gdy na przykład zachce nam się dzielić liczby 512 bitowe...

Jak zatem go zoptymalizować? Istotnie łatwo jest ten algorytm przerobić tak aby działał w czasie liniowym ze względu na długość reprezentacji liczby (czyli w czasie ln(x)). Wymaga to jednak wprowadzenia kilku oznaczeń:

D(x) - długość reprezentacji binarnej liczby, np. D(000100101b) = 6

x_i - i-ty bit liczby. Np. jeśli b=00101101b to b₂ = 1, b₄ = 0.

Dzielenie binarne ( wejście : x,y wyjście d - wynik dzielenia m - wynik modulo )

p:=0;
d:=0;
y:= y shl (D(x)-D(y)) {przesuwamy tak aby y miał tę samą długość rozwinięcia co x}

for i:=(D(x)-D(y)) downto 0 do

     p:=p+y
     if x<=p then di:=1; else p:=p-y;
     y:=y shr 1;

m:=x-p;

Jak działa ten algorytm? W zasadzie dokładnie tak jak naiwny. Tyle, że w jednym kroku nie dodajemy pojedynczego dzielnika, a od razu dzielnik wymnożony przez pewną potęgę 2. Gdy okaże się, że nasza zmienna pomocnicza przekroczyła dzielą to operacje cofamy. W innym wypadku ustawiamy stosowny bit wyniku dzielenia. Następnie przesuwamy dzielnik w prawo o jeden (innym słowy dzielimy przez 2), i wykonujemy stosowną operacją jeszcze raz. Pętla for wykonuje się tyle razy o ile różnią się długością reprezentacji liczby x i y. Zatem w ostatnim wykonaniu for dzielnik osiąga swoją początkową wartość i sam koniec przebiega dokładnie tak samo jak w algorytmie naiwnym.

Zauważmy, iż w rzeczywistości algorytm ten jest liniowy ze względu na D(x)-D(y), zatem najbardziej pesymistycznym jego czasem działania jest D(x)-1. W istocie oznacza to czas rzędu O( ln(x) ). Jest to zatem algorytm bardzo szybki, nieporównywalnie szybszy od naiwnego.

Jak widać w systemie binarnym da się zdziałać wiele. W budowaniu arytmetyki nie musimy się jednak ograniczać do operacji binarnych. Procesor w końcu wykonuje standardowe operacje na bajtach i słowach, można to zatem wykorzystać.

5. ARYTMETYKA W PRAKTYCE

Jak zatem zabrać się do napisania procedur arytmetycznych? Po pierwsze trzeba zadbać o kilka podstawowych procedur to jest: konwersję z systemu dziesiętnego na nasz wewnętrzny system i z powrotem. Aby mieć to, musimy mieć dzielenie przez 10, modulo 10, dodawanie i odejmowanie cyferki. Musimy mieć relację porównania pomiędzy dwoma zmiennymi naszego typu. Każda zmienna powinna być zerowana przed użyciem.

Najlepiej jest zdefiniować swój typ arytmetyczny jako tablicę bajtów. Można traktować to jako system o podstawie 256 (pojedynczy bajt to cyfra), w istocie jest to jednak system binarny, a nasza tablica odpowiada BARDZO długiemu słowu.

type liczba = array[0..31] of byte;

Proponuje indeksować tablice od 0, później okaże się to całkiem wygodne. Najbliżej 0 będą najmniej znaczące bity naszej liczby, odpowiednio najdalej najbardziej znaczące bity. Ponieważ operujemy na bajtach a operacje arytmetyczne mamy wykonywane przez procesor na bajtach i słowach, wykorzystamy to więc w naszych algorytmach.

1) Zerowanie tablicy. Będziemy tę operację wykonywać często, można więc zadbać aby była zaimplementowana szybko. Proponuje napisać ją w asemblerze, mniej zaawansowani zadowolą się zwykłym forem w pascalu, który nie powinien im sprawić żadnej trudności.

2) Dodawanie Liczba + cyfra. Algorytm jest bardzo prosty:

Procedure incL(var L : Liczba; c : byte);
Var w : word;
    I : byte;
Begin
   W:=c;
   I:=0;
    Repeat
      W:=W+L[i];       {W jest słowem zatem mieści wynik dodawania jak i ewentualne przepełnienie }
      L[i]:=W and 255;     { L[i] zostaje przypisana wartość mniej znaczącego bajtu w }
      W:=W shr 8;     { ewentualne przepełnienie zostanie dodane w następnym cyklu pętli }
      I:=I+1;       { zwiększamy aktualny indeks }
    Until W=0;
End;

3) Mnożenie liczba * cyfra. Algorytm odpowiada zwykłemu algorytmowi mnożenia, mnożnikiem jest jednak pojedyncza cyfra systemu, co można wykorzystać. W efekcie całe mnożenie wykonuje się w obrębie jednej zmiennej typu liczba i za pomocą jednego słowa. Nietrudno sprawdzić że algorytm tej jest poprawny.

Procedure mulL(var L : liczba; c : byte);
Var W : Word;
     I : Byte;
Begin
   W:=0;
   For i:=0 to 31 do
   Begin
      W:=W+L[i]*c;       {mnożymy cyfry i dodajemy ewentualne przeniesienie z poprzedniej operacji }
      L[i]:=W and 255;      { przypisujemy wartość iloczynu }
      W:=W shr 8;       { przesuwamy zmienną pomocniczą zawierającą ewentualne przeniesienie }
   End;
End;

4) Dzielenie liczba : cyfra. Ten przypadek dzielenia jest bardzo wygodny z punktu widzenia algorytmiki, i zakładając że mamy zdefiniowane operacje dzielenia i modulo na bajtach i słowach, jest bardzo prosty w implementacji.

Procedure divL(var L : Liczba; c : byte; var M : byte);
Var W : Word;
     i : Byte;
Begin
   W:=0;
   For i:=31 downto 0 do
   Begin
     W:=(W shl 8) + L[i]       { przypisz W resztę z poprzedniego dzielenia shl 8 plus L[i] }
     L[i]:=W div c;       { wykonaj dzielenie i przypisz L[i] }
     W:=W mod c;       { w zmiennej W zapisz resztę z dzielenia }
   End;
   M:=W and 255;       { w M zwracana jest reszta z dzielenia }
End;

5) Konwersja. Nie wymaga chyba specjalnego komentarza. Mając do dyspozycji dwie powyższe procedury każdy powinien szybko poradzić sobie z problemem konwersji na system dziesiętny i z powrotem.

6) Porównywanie dwóch liczb. Najwygodniej jest zrobić to za pomocą funkcji dwuargumentowej która zwróci która z dwóch liczb jest większa, ewentualnie zero gdy będą równe.

Function CMP (var a,b : Liczba) : Byte;
{mimo że liczb a i b nie będziemy modyfikować to zastosowanie var nieco przyspieszy wykonanie funkcji }
Var I : Byte;
Begin
   I:=31;
   While (A[i]=B[i]) and (I>0) do dec(i);
   If i=0 then CMP:=0 else
   Begin
     If A[i]>B[i] Then CMP:=1 else CMP:=2;
   End;
End;

Oczywiście porównanie przebiega od bardziej do mniej znaczących bitów.

7) Dodawanie dwóch liczb. Opiera się na trywialnym algorytmie szkolnym, tyle że za jednym krokiem dodajemy cały bajt a nie pojedyncze bity.

Procedure ADD( var a,b : Liczba);
{liczby b nie będziemy modyfikować, lecz przekazanie jej przez var nieco przyspieszy procedurę }
Var W : Word;
    I : Byte;
Begin
   W:=0;
   For I:=0 to 31 do
   Begin
     W:=W+A[i]+B[i];
     A[i]:=W and 255;
     W:=W shr 8;
   End;
End;

8) Odejmowanie wykonujemy analogicznie (patrz w przykładowym unicie)

9) Mnożenie. Stosujemy standardowy algorytm z dodawaniem tylko, że za jednym krokiem algorytmu mnożymy nie przez bit a przez pojedynczy bajt (mnożenie przez bajt już opracowaliśmy)

10) Dzielenie. Stosujemy wcześniej przytoczony optymalny algorytm binarny, aby go zaimplementować musimy mieć jeszcze funkcję zwracającą stan i-tego bita i funkcję zapalającą i-ty bit, oraz funkcję zliczającą binarną długość rozwinięcia liczby (patrz w przykładowym unicie).

6. SŁOWO NA KONIEC

Opanowanie i szybkie zaimplementowanie procedur arytmetycznych może się okazać pożyteczne w bardzo wielu sytuacjach, począwszy od pisania kalkulatorów z nieograniczonym zakresem, a skończywszy na implementacji kryptosystemów. Mając zaimplementowane duże liczby możemy się pokusić o implementacje testów pierwszosci, algorytmu Euklidesa na największy wspólny dzielnik itp.

Bibliografia

"Wprowadzenie do algorytmów" - Thomas H. Cormen, Charles E.Leiserson, Ronald L.Rivest.
"Algorytmy" - Maciej M. Sysło
"Matematyka Konkretna" - Ronald L. Graham, Donald E. Knuth, Oren Patashnik
"Matematyka Dyskretna" - Kenneth A. Ross, Charles R.B. Wright
"Jezyk C++" - Bjarne Stroustrup

Część 2 pobrano z http://www-users.mat.uni.torun.pl/~philip/arytm.html

---