Szybkie obliczanie log2 dla 64-bitowych liczb całkowitych

Jeśli używasz GCC, tabela wyszukiwania jest niepotrzebna w tym przypadku.

GCC dostarcza wbudowaną funkcję do określania ilości zer wiodących:

Wbudowana funkcja: int __builtin_clz (unsigned int x)
Zwraca liczbę pierwszych 0-bitów w x, zaczynając od najbardziej znaczącej pozycji bitowej. Jeśli x jest równe 0, wynik jest niezdefiniowany.

Więc można zdefiniować:

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

I będzie działać dla każdego unsigned long long int. Wynik jest zaokrąglony na ziemię.

Dla x86 i AMD64 GCC skompiluje go do bsr Instrukcja, więc rozwiązanie jest bardzo szybkie(dużo szybsze niż tabele wyszukiwania).

Przykład roboczy :

#include <stdio.h>

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

int main(void) {
    unsigned long long input;
    while (scanf("%llu", &input) == 1) {
        printf("log(%llu) = %u\n", input, LOG2(input));
    }
    return 0;
}

Próbowałem przekonwertować znaleźć bazę logów 2 N-bitowej liczby całkowitej w operacjach o(lg (N)) z mnożeniem i wyszukiwaniem na 64-bitową przez brutalne wymuszenie magicznej liczby. Nie trzeba dodawać, że trochę to trwało.

Potem znalazłem odpowiedź Desmonda i postanowiłem spróbować jego magicznej liczby jako punktu wyjścia. Ponieważ mam procesor 6 rdzeniowy, uruchomiłem go równolegle, zaczynając od 0x07edd5e59a4e28c2 / 6 wielokrotności. Byłem zaskoczony, że znalazł coś natychmiast. 0x07edd5e59a4e28c2 / 2 zadziałało.

Oto kod dla 0x07EDD5E59A4E28C2, który zapisuje przesunięcie i odjęcie:

int LogBase2(uint64_t n)
{
    static const int table[64] = {
        0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
        51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
        57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
        45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n |= n >> 32;

    return table[(n * 0x03f6eaf2cd271461) >> 58];
}

Base-2 Integer Logarytm

Oto, co robię dla 64-bitowych niepodpisanych liczb całkowitych. To oblicza podłogę logarytmu Bazy - 2, który jest odpowiednikiem indeksu najbardziej znaczącego bitu. Metoda ta jest smokingly fast dla dużych liczb, ponieważ używa rozwiniętej pętli, która wykonuje się zawsze w log₂64 = 6 krokach.

Zasadniczo odejmuje stopniowo mniejsze kwadraty w sekwencji { 0 ≤ K ≤ 5: 2^(2^k) } = { 232, 21⁶, 2⁸, 2⁴, 22, 21 } = { 4294967296, 65536, 256, 16, 4, 2, 1 } i sumuje wykładniki k odejmowanych wartości.

int uint64_log2(uint64_t n)
{
  #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }

  int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;

  #undef S
}

Zauważ, że zwraca -1, jeśli podano nieprawidłowe dane wejściowe 0 (które jest sprawdzane przez początkowy -(n == 0)). Jeśli nigdy nie spodziewasz się wywołać go za pomocą n == 0, możesz zastąpić int i = 0; inicjalizatorem i dodać assert(n != 0); przy wejściu do funkcji.

Base-10 Integer Logarytm

Baza-10 logarytmów całkowitych może być obliczona analogicznie - przy czym największy kwadrat do badania jest 101⁶ bo log₁₀2⁶⁴ ≅ 19.2659... (Uwaga: nie jest to najszybszy sposób na uzyskanie logarytmu liczby całkowitej bazy-10, ponieważ wykorzystuje on dzielenie liczby całkowitej, które jest z natury wolne. Szybszą implementacją byłoby użycie akumulatora o wartościach, które rosną wykładniczo, i porównanie z akumulatorem, w efekcie robi coś w rodzaju wyszukiwania binarnego.)

int uint64_log10(uint64_t n)
{
  #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }

  int i = -(n == 0);
  S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
  return i;

  #undef S
}

Oto dość kompaktowe i szybkie rozszerzenie, bez użycia dodatkowych tymczasowych:

r = 0;

/* If its wider than 32 bits, then we already know that log >= 32.
So store it in R.  */
if (v >> 32)
  {
    r = 32;
    v >>= 32;
  }

/* Now do the exact same thing as the 32 bit algorithm,
except we ADD to R this time.  */
if (tt = v >> 16)
  {
    r += (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
  }
else
  {
    r += (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
  }

Tutaj jest jeden zbudowany z łańcucha if s, ponownie przy użyciu żadnych dodatkowych tymczasowych. Może nie jest najszybszy.

  if (tt = v >> 48)
    {
      r = (t = tt >> 8) ? 56 + LogTable256[t] : 48 + LogTable256[tt];
    }
  else if (tt = v >> 32)
    {
      r = (t = tt >> 8) ? 40 + LogTable256[t] : 32 + LogTable256[tt];
    }
  else if (tt = v >> 16)
    {
      r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
    }
  else 
    {
      r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
    }

Algorytm zasadniczo dowiaduje się, który bajt zawiera najbardziej znaczący 1 bit, a następnie wyszukuje ten bajt w wyszukiwarce, aby znaleźć dziennik bajtu, a następnie dodaje go do pozycji bajtu.

Oto nieco uproszczona wersja 32-bitowego algorytmu:

if (tt = v >> 16)
{
    if (t = tt >> 8)
    {
        r = 24 + LogTable256[t];
    }
    else
    {
        r = 16 + LogTable256[tt];
    }
}
else 
{
    if (t = v >> 8)
    {
        r = 8 + LogTable256[t];
    }
    else
    {
        r = LogTable256[v];
    }
}

Jest to równoważny 64-bitowy algorytm:

if (ttt = v >> 32)
{
    if (tt = ttt >> 16)
    {
        if (t = tt >> 8)
        {
            r = 56 + LogTable256[t];
        }
        else
        {
            r = 48 + LogTable256[tt];
        }
    }
    else 
    {
        if (t = ttt >> 8)
        {
            r = 40 + LogTable256[t];
        }
        else
        {
            r = 32 + LogTable256[ttt];
        }
    }
}
else
{
    if (tt = v >> 16)
    {
        if (t = tt >> 8)
        {
            r = 24 + LogTable256[t];
        }
        else
        {
            r = 16 + LogTable256[tt];
        }
    }
    else 
    {
        if (t = v >> 8)
        {
            r = 8 + LogTable256[t];
        }
        else
        {
            r = LogTable256[v];
        }
    }
}

Wymyśliłem algorytm dla dowolnego rozmiaru, który moim zdaniem jest ładniejszy od oryginału.

unsigned int v = 42;
unsigned int r = 0;
unsigned int b;
for (b = sizeof(v) << 2; b; b = b >> 1)
{
    if (v >> b)
    {
        v = v >> b;
        r += b;
    }
}

Uwaga: b = sizeof(v) << 2 ustawia b na połowę liczby bitów w v. użyłem tu przesunięcia zamiast mnożenia (tylko dlatego, że miałem na to ochotę).

Możesz dodać tabelę wyszukiwania do tego algorytmu, aby ją przyspieszyć, ale jest to bardziej dowód koncepcji.