Integer dzielenie przez 7

Question

Źródło moja odpowiedź w:

Is this expression correct in C preprocessor

jestem trochę z mojego forte tutaj, a ja staram się zrozumieć, jak to szczególne prace optymalizacyjne.

Jak wspomniano w odpowiedzi, gcc będzie optymalizować podział całkowitą od 7 do:

mov edx, -1840700269 
mov eax, edi 
imul edx 
lea eax, [rdx+rdi] 
sar eax, 2 
sar edi, 31 
sub eax, edi 

co przekłada się z powrotem do C jak:

int32_t divideBySeven(int32_t num) { 
    int32_t temp = ((int64_t)num * -015555555555) >> 32; 
    temp = (temp + num) >> 2; 
    return (temp - (num >> 31)); 
} 

Rzućmy okiem na pierwszej części:

int32_t temp = ((int64_t)num * -015555555555) >> 32; 

Dlaczego ten numer?

Weźmy 2^64 i podzielmy przez 7 i zobaczmy, co wyskoczy.

2^64/7 = 2635249153387078802.28571428571428571429 

To wygląda jak bałagan, a jeśli skonwertujemy go na ósemkowy?

0222222222222222222222.22222222222222222222222 

To bardzo ładny wzór powtarzalny, na pewno nie może to być zbieg okoliczności. Mam na myśli to, że pamiętamy, że 7 to 0b111 i wiemy, że kiedy dzielimy przez 99, mamy tendencję do powtarzania wzorców w bazie 10. To ma sens, że otrzymamy powtarzający się wzór w bazie 8, gdy podzielimy się przez 7.

Więc gdzie jest nasz numer?

(int32_t)-1840700269 jest taka sama jak (uint_32t)2454267027

* 7 = 17179869189

Wreszcie 17179869184 jest 2^34

Czyli 17179869189 jest najbliżej wielokrotnością 7 2^34. Lub umieścić to w inny sposób 2454267027 jest największą liczbą, która zmieści się w uint32_t która po pomnożeniu przez 7 jest bardzo blisko do potęgi 2

Co to jest liczba w systemie ósemkowym?

0222222222223 

Dlaczego jest to ważne? Cóż, chcemy podzielić przez 7. Ta liczba to 2^34/7 ... w przybliżeniu. Jeśli pomnożymy przez to, a następnie przejdziemy 34 razy, powinniśmy uzyskać liczbę bardzo bliską dokładnej liczbie.

Dwie ostatnie linie wyglądają tak, jakby zostały zaprojektowane w celu łatania błędów związanych z aproksymacją.

Być może ktoś, kto ma nieco więcej wiedzy i/lub doświadczenia w tej dziedzinie, może w tym pomóc.

>>> magic = 2454267027 
>>> def div7(a): 
... if (int(magic * a >> 34) != a // 7): 
...  return 0 
... return 1 
... 
>>> for a in xrange(2**31, 2**32): 
... if (not div7(a)): 
...  print "%s fails" % a 
... 

Awarie rozpocząć na 3435973841, która jest na tyle zabawnie 0b11001100110011001100110011010001

Klasyfikowanie dlaczego zbliżanie nie jest trochę poza mną i dlaczego łatki naprawić go jest tak dobrze.Czy ktoś wie, jak działa magia ponad to, co tu umieściłem?

Answer 1

Pierwsza część algorytmu jest pomnożona przez przybliżenie do odwrotności 7. W tym przypadku przybliżamy obliczanie odwrotności przez mnożenie całkowite i prawą zmianę bitową.

Po pierwsze, widzimy wartość -1840700269 (ósemkowa -015555555555) jako 32-bitową liczbę całkowitą. Jeśli czytasz to jako niepodpisaną 32-bitową liczbę całkowitą, ma ona wartość 2454267027 (ósemkowa 22222222223). Okazuje się, że 2454267027/2^34 jest bardzo zbliżoną liczbą całkowitą zbliżoną do 1/7.

Dlaczego wybieramy ten numer i tę szczególną moc 2? Im większe są używane liczby całkowite, tym przybliżenie jest zbliżone. W tym przypadku, 2454267027 wydaje się być największą liczbą całkowitą (spełniającą powyższą właściwość), za pomocą której można pomnożyć podpisany 32-bitowy int bez przepełnienia 64-bitowego int.

Następnie, jeśli natychmiast przesuniemy w prawo o >> 34 i zapiszemy wynik w 32-bitowej int, stracimy dokładność dwóch bitów najniższego rzędu. Te bity są niezbędne do określenia właściwej podłogi dla podziału na liczby całkowite.

Nie jestem pewien, czy druga linia została poprawnie przetłumaczona z kodu x86. W tym momencie temp jest w przybliżeniu num * 4/7, więc num * 4/7 + num do tego i bit-przesuniecia da ci około num * 1/7 + num * 1/4, całkiem duży błąd.

Na przykład jako dane wejściowe 57, gdzie 57 // 7 = 8. I zweryfikowane niżej w kodzie, a także:

• 57 * 2454267027 = 139893220539
• 139893220539 >> 32 = 32 (ok 57 * 4/7 = 32.5714... w tym momencie)
• 32 + 57 = 89
• 89 >> 2 = 22
(hę ?? Nigdzie blisko 8 w tym momencie).

W każdym razie dla ostatniej linii jest to korekta, którą wprowadzamy po obliczeniu tak podzielonego podziału na liczby całkowite ze znakiem. Cytuję z sekcji z zachwytu Hackera na podpisanym podziału:

Kod najbardziej naturalnie oblicza wynik dzielenia piętro, więc musimy korekta aby obliczyć konwencjonalna obcięty w kierunku 0 wyniku. Można to zrobić za pomocą trzech instrukcji obliczeniowych dodając do dywidendy, jeśli dywidenda jest ujemna.

W tym przypadku (odnosząc się do innego wątku) wydaje robisz podpisaną zmianę, więc będzie odjąć -1 w przypadku liczby ujemnej; podając wynik +1.

To nie wszystko, co możesz zrobić; tutaj jest jeszcze bardziej szalony blog post about how to divide by 7 with just a single multiplication.