Jaka jest logika algorytmu podziału Fouriera?

Question

z Wikipedia: fourier division.

Oto zrzut ekranu tego samego: (view in full-resolution)

Jaka jest logika tego algorytmu?

Wiem, że można go używać do dzielenia bardzo dużych liczb, ale jak dokładnie to działa?

Answer 1

wydaje się to być sprytnym przekształceniem algorytmu Long Division. Sprytne części wydają się być takie, że używają tylko operacji podziału dla pierwszej "cyfry", a1, i unikają konieczności używania drugiej a (x) w ten sam sposób, stosując je w następnym kroku, odejmując ich produkt (w stosunku do ilorazu cząstkowego) z pozostałej części.

To, że można to zrobić i że zawsze działa, prawdopodobnie wynika z faktu, że "cyfry" (podstawa 100, w tym przypadku) nie są prawdziwymi cyframi i mogą prawnie przyjąć wartości większe od ich podstawy (tj. ponad 100), a nawet mniej niż zero. Pozwala to na większą elastyczność w czasie stosowania każdej "cyfry" do operacji, na przykład odroczenia stosowania dodatkowych cyfr dzielnika (a (x> 1)), dopóki nie zostanie utworzony częściowy iloraz Podział poprzedniej czynności przez a (1), co z kolei pozwala na zastosowanie ich jako odejmowania produktu, a nie operacji dzielenia.

Answer 2

To niezwykle sprytny algorytm. Nie mogę sobie wyobrazić, jak bardzo JF udało się to osiągnąć, ponieważ relacja therecurrence jest niezwykle trudna do zobaczenia, nawet jeśli wiecie, że istnieje. Moim zdaniem sformalizował metodę, której używał do zrobienia londyńskiego podziału - musiał dokonać ogromnej liczby obliczeń ręcznie w wieku przed cyfrowymi kalkulatorami, i prawdopodobnie wolał być dokładny przy użyciu suwaka, żeby mieć pewność.

Prawdą jest, że można niewyraźnie zobaczyć zarys metody na początku standardowego algorytmu długiego podziału, ale to jedyna wskazówka. Możesz wyszukiwać długo i ciężko na ten nawrót, nie widząc go. W grę wchodzi tak wiele liczb - jest to mylące spojrzenie na relacje.

Istnieje jeszcze jedna intuicja, którą można uzyskać, badając przepływ danych w standardowym algorytmie mnożenia. Jeśli wypiszesz go w sprzęcie komputerowym, zobaczysz, że kwadratowa tablica 8-bitowych jednostek multiplikatywnych pobiera dwie 32-bitowe liczby ułożone wzdłuż ich dolnej i prawej strony i przesuwa dane w górę i w lewo, wychodząc z górnej krawędzi tablica w 64-bitowej odpowiedzi. Najwyższa lewa jednostka dostarcza górne DWIE (8-bitowe) cyfry produktu, używając górnych cyfr multiplikacji i przenosząc je od reszty tablicy po prawej stronie. OK? Cóż, wyobraźmy sobie, że tablica działa w odwrotnym kierunku, przyjmując jako dane wejściowe 64-bitową dzielnik wzdłuż górnej krawędzi i 32-bitowy dzielnik, powiedzmy wzdłuż prawej krawędzi tablicy. Następnie wyprowadza 32-bitowy iloraz wzdłuż dolnej krawędzi (reszta również musi zostać wygenerowana .. zapomnij o tym dla mo). Teraz najwyższa lewa jednostka w tablicy przyjmuje W dwóch pierwszych cyfrach dywidendy od góry tablicy, górnej cyfry dzielnika z prawej strony tablicy i emituje górną cyfrę ilorazu W DÓŁ array (i out the bottom) oraz pozostałą ilość RIGHTWARDS do tablicy.

Whew! To było tylko dla pierwszej cyfry. To dopiero początek. Geniusz Fouriera polegał na tym, by zobaczyć, w jaki sposób można nakarmić resztki akumulujące, aby ograniczyć nakłady tylko do trzech (powiedzmy 8-bitowych) cyfr, a wynik na dwie (powiedzmy 8-bitowe) cyfry dla każdej jednostki w zmodyfikowanym tablica multiplikatywna działająca w rewersie (którą możemy teraz nazwać tablicą dzielenia).

Oczywiście, w ten sposób możemy wykonać podział sprzętu, bez wymaganego mikrokodu, w komputerowej jednostce ALU.

Przynajmniej, zakładam, że ta metoda jest używana tam, gdzie mikrokod został pominięty na rzecz kilku miliardów tranzystorów. Nie mam dostępu do wnętrza najnowszych procesorów, ale mają tranzystory do nagrywania.