Jak dochodzi do podziału w naszych komputerach?

Jak dochodzi do podziału w komputerach cyfrowych? Jaki jest dla niego algorytm?

Szukałem intensywnie w Google, ale nie uzyskałem zadowalających wyników. Podaj bardzo wyraźny algorytm / schemat blokowy dla algorytmu podziału z przykładową ilustracją.

Algorytmy podziału w projektach cyfrowych można podzielić na dwie główne kategorie. Wolny podział i szybki podział.

Sugeruję przeczytanie o tym, jak działają binarne dodawanie i odejmowanie, jeśli nie znasz jeszcze tych pojęć.

Slow Division

Najprostsze powolne metody działają w następujący sposób: Odejmij mianownik od licznika. Zrób to rekurencyjnie z wynikiem każdego odejmowania, aż reszta będzie mniejsza niż mianownik. Ilość iteracji jest ilorazem całkowitym, a pozostała ilość to reszta.

Przykład:

7/3:

1. $$7-3=4$$
2. $$4-3=1$$
3. $$1 < 3$$

Tak więc odpowiedź to 2, a reszta to 1. Aby uczynić tę odpowiedź nieco bardziej trafną, oto trochę tła. Odejmowanie binarne poprzez dodanie ujemnego jest wykonywane np .: 7 - 3 = 7 + (-3). Dokonuje się tego za pomocą uzupełnienia dwóch. Każda liczba binarna jest dodawana przy użyciu serii pełnych sumatorów:

Gdzie każdy 1-bitowy pełny sumator jest implementowany w następujący sposób:

Szybki podział

Chociaż wolniejsza metoda podziału jest łatwa do zrozumienia, wymaga powtarzalnych iteracji. Istnieją różne „szybkie” algorytmy, ale wszystkie polegają na oszacowaniu.

Rozważ metodę Goldschmidta:

Wykorzystam następujące:

Ta metoda działa w następujący sposób:

1. Pomnóż N i D przez ułamek F w taki sposób, aby D zbliżył się do 1.
2. Gdy D zbliża się do 1, N zbliża się do Q

Ta metoda wykorzystuje binarne mnożenie poprzez iteracyjne dodawanie, które jest również stosowane w nowoczesnych procesorach AMD.

Sprzęt do dzielenia zmiennoprzecinkowego jest częścią jednostki logicznej, która również wykonuje mnożenie; dostępny jest moduł sprzętowy multiplikatora. Liczby zmiennoprzecinkowe, powiedzmy A i B, są podzielone (tworząc A / B) przez

1. rozkładanie liczb zmiennoprzecinkowych na wykładniki (+1 lub -1), mantysa („a” i „b” oraz (binarna liczba całkowita) wykładniki
2. znakiem wyniku jest (+1) iff oba znaki są takie same, w przeciwnym razie (-1)
3. wykładniki są odejmowane (wykładnik B odejmuje się od wykładnika A), aby utworzyć wykładnik wyniku

4. mantysy (cyfry binarne liczb) to stała liczba binarna między 1/2 a 1; oznacza to, że pierwsza cyfra po punkcie binarnym to „1”, a następnie zera i jedynki… w pierwszym kroku tabela przeglądowa znajduje odwrotność z dokładnością do sześciu bitów (są tylko 32 możliwości, to mały stolik)

5. aby rozpocząć obliczanie a / b, wykonaj dwie mnożenia

   $${a \over b} = {{a * reciprocal(b)}\over b * reciprocal(b)}$$ i zauważ, że sześciobitowa dokładność oznacza, że ​​mianownik wyniku jest bardzo bliski 1 (do pięciu lub więcej miejsc binarnych).

6. Zauważmy teraz, że w przypadku bardzo bliskich jednemu mianownikowi „d” widzimy to określenie $$d == 1 +\epsilon$$ $$d * (2-d) = ( 1+ \epsilon) \times (1-\epsilon) = 1 - \epsilon ^2$$ Oznacza to, że nasze pięciobitowe dokładne „jeden” w mianowniku stanie się dziesięciobitowe po kolejnej parze mnożenia, dwadzieścia bitów po dwóch i czterdzieści bitów po trzech. Wykonaj tyle iteracji mnożenia licznika i mianownika przez (2 - mianownik), ile wymaga dokładność wyniku.
7. Licznik, teraz, gdy mianownik ma dokładnie „1”, jest mantysą wyniku i można go łączyć z wcześniej obliczonym znakiem i wykładnikiem.
8. Liczba zmiennoprzecinkowa IEEE dopuszcza pewne wyjątki (liczby zdenormalizowane, NAN; te muszą być obsługiwane przez inne operacje logiczne.

Co ciekawe, stary błąd podziału Pentium (bardzo godny uwagi w 1994 r.) Został spowodowany błędem drukowania, który spowodował błędne wartości tabeli wzajemnej dla kroku (4). Wczesny artykuł, „A Division Method using Parallel Multplier”, Domenico Ferrari, IEEE Trans. Elektron. Comput. EC-16 / 224-228 (1967), opisuje metodę, podobnie jak „IBM System / 360 Model 91: Jednostka wykonująca zmiennoprzecinkowe” IBM J. Res. Dev. 11 : 34-53 (1967).

Istnieją bardzo różne metody podziału, w zależności od obsługiwanych liczb. W przypadku liczb całkowitych metoda shift-and-odtract podana przez innych będzie działać poprawnie. Jednak w przypadku liczb zmiennoprzecinkowych może być szybsze obliczenie odwrotności mianownika, a następnie pomnożenie tej liczby przez licznik.

Obliczenie wzajemności mianownika nie jest takie złe; odbywa się to poprzez udoskonalanie kolejnych przybliżeń. Niech g zgadnie dla 1 / d. Aby uzyskać lepsze przypuszczenie, użyj g '= g (2-gd). Zbiega się to kwadratowo, więc podwajasz cyfry precyzji przy każdej poprawce.

Przykład: obliczyć odwrotność 3,5.

Początkowa wartość wynosi 0,3. Obliczasz 0,3 * 3,5 = 1,15. Twoje skorygowane domysły wynoszą 0,3 * (2 - 1,15) = 0,285. Już całkiem blisko! Powtórz proces, a otrzymasz 0.2857125, a trzecia próba otrzyma 0.2857142857.

Istnieje kilka skrótów. W zmiennoprzecinkowym możesz wyodrębnić potęgi dziesięciu lub potęgi dwóch, w zależności od podstawy liczbowej twojej maszyny. Aby uzyskać szybkość kosztem większego wykorzystania pamięci, można użyć wstępnie obliczonej tabeli dla liczb w zakresie od 1 do b (gdzie b jest bazą liczbową), aby uzyskać domysł, który jest natychmiast bliski wymaganej wzajemności i zapisz jeden lub dwa etapy udoskonalania.

Należy pamiętać, że podobnie jak w przypadku mnożenia i zawstydzenia Kołmogorowa w 1960 r. Przez jego studenta Anatolija Karatuby, nigdy nie wiadomo, kiedy można znaleźć szybszą lub lepszą metodę. Nigdy nie rezygnuj z ciekawości.

Komputery nie wykonują iteracyjnego dodawania do mnożenia liczb - byłoby to naprawdę wolne. Zamiast tego istnieją algorytmy szybkiego mnożenia. Sprawdź: http://en.wikipedia.org/wiki/Karatsuba_algorithm