Wykonaj podział całkowity za pomocą mnożenia

Question

Patrząc na zestaw x86 produkowany przez kompilator, zauważyłem, że (bez podpisu) podziały liczby całkowitej są czasem implementowane jako multiplikacje całkowite. Te optymalizacji wydaje podążał za kształtem

value/n => (value * ((0xFFFFFFFF/n) + 1))/0x100000000 

Na przykład, poprzez wykonywanie podziału 9:

12345678/9 = (12345678 * 0x1C71C71D)/0x100000000 

dzielenia przez 3 użyłby mnożenie 0x55555555 + 1, i tak dalej.

wykorzystując fakt, że dyspozycja mul przechowuje dużą część wyniku w rejestrze edx końcowy wynik podziału można uzyskać za pomocą jednego mnożenia z magicznej wartości. (Chociaż ta optymalizacja jest czasami używana w połączeniu z przesunięciem bitowym na końcu.)

Chciałbym dowiedzieć się, jak to działa. Kiedy to podejście jest prawidłowe? Dlaczego 1 należy dodać do naszej "magicznej liczby"?

Answer 1

Ta metoda nazywa się "Podział przez rozmnażanie niezmienne".

Stałe, które widzisz, są w przybliżeniu przybliżeniami odwrotności.

Więc zamiast computing:

N/D = Q 

zrobić coś takiego zamiast:

N * (1/D) = Q 

gdzie 1/D Jest to odwrotność które można precomputed.

Zasadniczo odwrotność jest nieprecyzyjna, chyba że D jest potęgą dwójki. Więc wystąpi jakiś błąd zaokrąglania. +1, który widzisz, jest poprawny w przypadku błędu zaokrąglania.

---

Najbardziej znanym przykładem jest przez podział 3:

N/3 = (N * 0xaaaaaaab) >> 33 

przypadku 0xaaaaaaab = 2^33/3 + 1.

To podejście zostanie uogólnione na inne dzielniki.