Algorytm szybkiego podziału liczb binarnych

Question

Obecnie buduję 16-bitową jednostkę ALU przy użyciu Logisim (tj. Tylko bramki logiczne) i utknąłem w procesie podziału. Obecnie tylko przy użyciu prostego standardu „pętli algorytmu podziału” (jak pokazano poniżej):

1. odczyt wartości wejściowych;
2. Porównaj wartości wejściowe. Poczekaj na zakończenie procesu porównywania;
3. Jeśli A < B przejdź do kroku 10. Jeśli A ≥ B, przejdź do następnego kroku;
4. Odejmij B od A;
5. Poczekaj, aż proces odejmowania zakończy się;
6. Dodaj do policzenia;
7. Poczekaj, aż proces liczenia się zakończy;
8. Zapis wartości z procesu odejmowania do wejścia;
9. Przejdź do kroku 1;
10. Odpowiedź jest liczba pozostała

To jednak trwa bardzo długo dla procesów z dużymi odpowiedzi (powtarzając cykl 300 Tick 65,000 razy nie jest zabawa). Zastanawiam się tylko, czy istnieją podobne algorytmy, które są szybsze (używają wyłącznie dodawania i/lub odejmowania i/lub mnożenia i dowolnej logiki boolowskiej), które mogłyby być zaimplementowane za pomocą bramek logicznych. Każda pomoc lub pomysły będą mile widziane! Fraser

Answer 1

Użyj long-division. W binarnym nie ma mnożenia, ponieważ iloraz w każdej pozycji bitu może wynosić tylko 1 lub 0. Można więc go wprowadzić jako warunkowe odejmowanie (odjąć, jeśli wynik nieujemny) i przesunąć.

To tylko zwykły zarys, oczywiście.

Answer 2

Typowym podejściem dla dywizji 32/16: 16 + 16 byłoby przechowywanie dywidendy w parze 16-bitowych rejestrów (które zostaną zaktualizowane podczas działania) i dywizorze we własnym rejestrze (który nie " t). Szesnaście razy odjąć górne 17 bitów dywidendy od dzielnika; jeśli wynik pożyczki, odrzuć wynik i przesuń dzielnik w lewo o jedno miejsce, umieszczając 0 w lsb. Jeśli nie uzyskasz wyniku, zapisz wynik w dzielniku, przesuwając go w lewo, ale umieść 1 w lsb. Po szesnastu takich krokach dolne 16 bitów rejestru dywidendy utrzyma iloraz, a górne 16 bitów zatrzyma resztę. Zauważ, że ta operacja będzie działać tylko wtedy, gdy iloraz jest reprezentowany w 16 bitach. Zauważ także, że na procesorze, który implementuje podział 32/16: 16 + 16 w ten sposób, można wygodnie podzielić dowolnie duże liczby przez 16-bitową ilość, ponieważ górne 16 bitów dywidendy dla każdego kroku powinno być resztą z poprzedni krok.