Użycie sekwencji de Bruijn do znalezienia liczby całkowitej

11

Sean Anderson opublikował nieco hacków zawierających algorytm Erica Cole'a, aby znaleźć liczby całkowitej bit w operacjach z mnożeniem i wyszukiwaniem. $\lceil\log_2 v \rceil$ $N$ $v$ $O(\lg(N))$

Algorytm opiera się na „magicznej” liczbie z sekwencji De Bruijn. Czy ktoś może wyjaśnić podstawowe właściwości matematyczne zastosowanej tu sekwencji?

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

nt.number-theory comp-number-theory

— Yury Bayda
źródło

2

Pomysł pochodzi z tego artykułu supertech.csail.mit.edu/papers/debruijn.pdf . Sekwencja de Brujna o rozmiarze jest sposobem bardzo zwięzłego przedstawienia wszystkich ciągów bitów o rozmiarze : każdy możliwy ciąg pojawia się dokładnie raz jako ciągła podsekwencja. Więc jeśli przesuniesz sekwencję de Bruijna o bitów i odczytasz ostatnie bitów, otrzymasz unikalny identyfikator dla .

2^{k}

$2^k$

k

$k$

n \leq 2^{k}

$n \leq 2^k$

k

$k$

n

$n$

— Sasho Nikolov

1

Przy okazji oblicza to tylko ; i jak napisano, działa tylko dla 32-bitowych liczb całkowitych.

⌈ \log_{2} v ⌉

$\lceil \log_2 v \rceil$

— Sasho Nikolov

1

@Sasho Zamienisz się w odpowiedź?

— Yuval Filmus,

@SashoNikolov Dzięki, dodano funkcję sufitu do pytania

— Yury Bayda

9

Po pierwsze, ten algorytm oblicza tylko , a ponieważ kod jest zapisywany, działa tylko dla które mieszczą się w bitowym słowie. $\lceil \log_2 v \rceil$ $v$ $32$

Sekwencja przesunięć i-or, która pojawia się jako pierwsza, ma funkcję propagacji wiodącego 1-bitu aż do najmniej znaczącego bitu. Liczbowo daje to . $v$ $2^{\lceil \log_2 v \rceil} - 1$

Interesującą częścią jest trik de Bruijn, który pochodzi z tego artykułu Leisersona, Prokopa i Randalla (najwyraźniej profesorowie MIT spędzają czas robiąc trochę hacków :)). To, co musisz wiedzieć o sekwencjach de Bruijna, to to, że reprezentują one wszystkie możliwe sekwencje o danej długości w sposób możliwie skompresowany. Dokładniej, de sekwencja Brujn na alfabet jest binarny ciąg długości tak, że każdy odcinek ciąg binarny pojawia się tylko raz w ciągłą fragmentu (technologia zawijania jest dostępna). Powodem tego jest to, że jeśli masz liczbę której bitową reprezentacją jest sekwencja de Bruijna (wypełniona $\{0, 1\}$ $s$ $2^k$ $k$ $X$ $k$ zera), a następnie górne bitów jednoznacznie identyfikuje (o ile ). $k$ $2^iX$ $i$ $i <k$

— Sasho Nikolov
źródło

3

Należy pamiętać, że można użyć dowolnej sekwencji de Bruijn w ten sposób do obliczenia

podane

. Jednak nie można używać arbitralnej sekwencji de Bruijn do obliczenia

podane

. Tutaj 0x07C4ACDD = 00000111110001001010110011011101 wydaje się być de sekwencja Bruijn z dodatkowymi właściwościami, dzięki czemu dodatkowa

nie niszczy tego podejścia.

i

$i$

2^{i}

$2^i$

i

$i$

2^{i} - 1

$2^i - 1$

- 1

$-1$

— Jukka Suomela

Dzięki @JukkaSuomela, byłem trochę zdezorientowany. Myślę jednak, że zawsze możesz po prostu dodać 1 do

.

v

$v$

— Sasho Nikolov

5

Kilka komentarzy (nie do końca odpowiedź). Sklasyfikujmy 32-bitowe liczby całkowite w następujący sposób: $c$

Typ X: (jako ciąg binarny) jest sekwencją De Bruijna (dla wszystkich obrotów bity [27, 31] są różne). Przykład: $c$
```
11111011100110101100010100100000
```
Typu Y: Bity [27,31] z są różne dla . To właśnie Leiserson i in. wykorzystuje. Przykłady: $2^i \cdot c$ $i = 0, 1, ..., 31$
```
00000100011001010011101011011111
00001111101110011010110001010010
```
Typ: z bitów [27,31] z są różne dla . Właśnie tego potrzebujemy w pierwotnym pytaniu. Przykłady: $(2^{i+1} - 1) \cdot c$ $i = 0, 1, ..., 31$
```
00000111110001001010110011011101  (07C4ACDD)
10000111110001001010110011011101
01111000001110110101001100100011
11111000001110110101001100100011
```

Kilka obserwacji opartych na szybkich eksperymentach (mam nadzieję, że udało mi się to dobrze):

Istnieje 65536 liczb całkowitych typu X.
Istnieje 4096 liczb całkowitych typu X + Y. Są to dokładnie te liczby całkowite typu X, które zaczynają się od sekwencji „0000 ...”
- intuicja: z wiodącymi zerami obrót = przesunięcie?
Istnieje 256 liczb całkowitych typu X + Y + Z. Są to dokładnie te liczby całkowite typu X, które zaczynają się od sekwencji „0000011111 ...”
- intuicja: ??
Wszystkie liczby całkowite typu Y są również typu X.
Istnieją jednak 768 liczb całkowitych typu Z, które nie są ani typu X, ani typu Y. Zaczynają się one od „1000011111 ...”, „0111100000 ...” lub „1111100000 ...”

— Jukka Suomela
źródło

1

Jest to jedyna odpowiedź na pytanie, dlaczego mnożenie De Bruijn przez 2 ^ n-1 działa, w przeciwieństwie do 2 ^ n, co jest po prostu zmianą. Bardzo bym chciał, gdyby ktoś mógł rozwinąć „intuicję” z punktu 3 powyżej. Jak wymyślił to Eric Cole? Wersja próbna i błąd? Lub jakieś zrozumienie tego, co faktycznie dzieje się z bitami, gdy pomnożymy przez 2 ^ n-1?

— FarmerBob,

1

Skąd ta stała?

Cytując: „W dniu 10 grudnia 2009 r. Mark Dickinson ogolił kilka operacji, wymagając zaokrąglenia v do jednej mniejszej niż następna potęga 2 zamiast potęgi 2”. [graphics.stanford.edu/~seander/bithacks.html]

Ta szczególna stała jest sekwencją De Bruijna z alfabetem binarnym, ale z dodatkową właściwością. Nazwie to „Właściwością Marc Dickinson”, ponieważ oryginalny algorytm mógłby zostać zaimplementowany bez tych specjalnych sekwencji DB. Dołączając 2 dodatkowe operacje, moglibyśmy użyć dowolnej zwykłej sekwencji DB. Operacja: v ^ = (v >> 1); // clr wszystkie bity oprócz MSB ustawionego po kaskadowym lub przesunięciu.

Wyniki (bruteforce)

Seq.Type | Nie. Liczby całkowite | Nie. DBSeq. z | bez rotacji | z Dickinson Property
B (2, 3) | 256 | 16 | 2 | 1
B (2, 4) | 64Ki | 256 | 16 | 4
B (2, 5) | 04Gi | 64Ki | 02Ki | 256
B (2, 6) | 16Ei | 04Gi | 64Mi | ??

Specjalna właściwość

${0x7C4ACDD}$ $*$ $2^k$ ${1}$ $\pmod {2^{32}}$ $32\ge k\ge1$ $2^k$ ${1}$

Leksykograficznie najmniejsze binarne sekwencje de Bruijna z Dickinson Property

[B (2,3): 0x1D] [B (2,4): 0x0F2D] [B (2,5): 0x7C4ACDD] [B (2,6): Wyszukiwanie wciąż]

Jeśli liczyłeś na elegancki wzór matematyczny do ich opisania lub twierdzenia, aby je wytworzyć lub coś podobnego, myślę, że wymagałoby to głębokiego wglądu w teorię liczb i ewentualnie inne dziedziny, które są poza moim zakresem umiejętności. Jeśli chcę zgadywać, to założę się, że mogą być wytwarzane przez automaty komórkowe. To nie jest odpowiedź dlaczego? na rygorystycznej podstawie, ale próba intuicyjnego zrozumienia, dlaczego to działa i dlaczego działa poprawnie, abyś mógł z niego korzystać z pewnością.

PS Nie omawiałem konstrukcji LUT, którą łatwo wywnioskować, jeśli zrozumiesz zasady działania algorytmów.

— FranG
źródło

W końcu znaleziono: B (2,6) 0x3f08a4c6acb9dbd - 64-bitowa sekwencja de bruijn z „właściwością dickinsona”. Znalazłem co najmniej 122 000 takich sekwencji.

— FranG