Jak dochodzi do podziału w naszych komputerach?

17

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ą.

program-o-steve
źródło
1
@ program-o-steve Podział w jednostce ALU jest złożoną operacją. Nie otrzymasz „prostego” schematu blokowego.
Majenko,
5
@ Leon Heller Oh! Nie mówi tak. To jest pytanie czysto sprzętowe
program-o-steve,
2
@ Leon Heller Chyba nie jest to …, które obejmuje elektronikę, obliczenia fizyczne ...
program-o-steve
2
Podział na mikrokontrolery nie jest prosty. Istnieją szybkie i powolne sposoby. Wolne sposoby są łatwiejsze do zrozumienia, ale szybkie sposoby są stosowane w nowoczesnych procesorach, o czym konkretnie chcesz wiedzieć? Czy chcesz tylko podstawowe zrozumienie zasad lub szczegółową analizę współczesnych procesorów?
Konsalik 18.11.11
4
@LeonHeller Zwykle zgadzam się z pytaniami, które chcesz zamknąć, ale konstrukcja procesora jest w dużej mierze kwestią elektrotechniki. To pytanie może pomóc w wyjaśnieniu, czego się chce (np. O co pyta konsalik), ale to nie wyklucza tematu.
Kellenjb,

Odpowiedzi:

17

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. 73=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:

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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:

Q=Nre

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.

Konsalik
źródło
1
Niektóre schematy blokowe dla wariantów metody „powolnej” (zaimplementowanej w asemblerze na mikrach bez podziału sprzętowego, ale nadal pomocne) podano w przypisie AVR200 firmy Atmel .
Kevin Vermeer
czy możesz podać ilustrację dotyczącą metody podziału Goldschmidta? Również schemat podany tutaj jest przykładem powolny podział?
program-o-steve,
Jaka jest ta metoda, w której musimy wielokrotnie przesuwać dywidendę w lewo?
program-o-steve
@ program-o-steve Oto szybka ilustracja: znajdź 22/7 (przybliżenie pi). Najpierw pomnóż górę i dół przez 0,1, aby uzyskać: 2,2 / 0,7 Pomnóż ponownie, używając 1,3, dając: 2,86 / 0,91 Używając 1,09 daje: 3,11174 / 0,9919 1,008 daje: 3,1423393 / 0,9998352 Kontynuuj, wkrótce osiągniesz OSTATECZNĄ ODPOWIEDŹ 3.1428571 / 1.000000 ...
Alan Campbell
Jak „pomnożyć przez ułamek”? Ułamki nie są reprezentowalne w zmiennoprzecinkowym. Ułamek z definicji to licznik podzielony przez mianownik, więc pozostaje ci okrągły argument, że nadal musisz dzielić. A w jaki sposób szacuje się tę frakcję?
CogitoErgoCogitoSum
5

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

    zab=zarmidojaprodozal(b)brmidojaprodozal(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
    re==1+ϵ
    re(2)-re)=(1+ϵ)×(1-ϵ)=1-ϵ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).

Whit3rd
źródło
1

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.

richard1941
źródło
-1

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

użytkownik59608
źródło
Witamy w EE.SE. Odpowiedzi tylko z linkiem są odradzane. Proszę streścić informacje w linku.
Null
Oni robią. Mnóstwo procesorów wciąż nie ma mnożników jednocyklowych i używa mnożenia programowego.
user3528438,