Usando a sequência de Bruijn para encontrar o de um número inteiro

11

Sean Anderson publicou pequenos truques de contenção contendo o algoritmo de Eric Cole para encontrar o de um número inteiro de bits nas operações com multiplicação e pesquisa.N v O ( lg ( N ) )log2vNvO(lg(N))

O algoritmo baseia-se em um número "mágico" da sequência De Bruijn. Alguém pode explicar propriedades matemáticas fundamentais da sequência usada aqui?

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];
Yury Bayda
fonte
2
A idéia vem deste artigo: supertech.csail.mit.edu/papers/debruijn.pdf . Uma sequência de Brujn de tamanho é uma maneira de representar todas as seqüências de bits de tamanho forma muito concisa: cada sequência possível aparece exatamente uma vez como uma subsequência contígua. Portanto, se você alterar a sequência de Bruijn em bits e ler os últimos bits, você terá um identificador exclusivo para . k n 2 k2kkn2knkn
Sasho Nikolov 25/10
1
A propósito, isso só calcula ; e, como está escrito, funciona apenas para números inteiros de 32 bits. log2v
Sasho Nikolov
1
@ Sasho Transformar em uma resposta?
Yuval Filmus
@SashoNikolov Obrigado, adicionou uma função de teto à pergunta #
Yury Bayda

Respostas:

9

Primeiro, observe que esse algoritmo calcula apenas e, conforme o código é escrito, funciona apenas para que se encaixa em uma palavra de bits.v 32log2vv32

A sequência de turnos e -s que aparece primeiro tem a função de propagar o 1 bit principal de até o bit menos significativo. Numericamente, isso fornece .2 log 2 v - 1v2log2v1

A parte interessante é o truque de Bruijn, que vem deste artigo de Leiserson, Prokop e Randall (aparentemente os professores do MIT passam algum tempo fazendo pequenos hacks :)). O que você precisa saber sobre as sequências de De Bruijn é que elas representam todas as sequências possíveis de um determinado comprimento de uma maneira o mais compactada possível. Precisamente, uma sequência de Brujn sobre o alfabeto é uma cadeia binária de comprimento modo que cada cadeia binária de comprimento apareça exatamente uma vez como uma substring contígua (é permitido o agrupamento). A razão pela qual isso é útil é que, se você tiver um número cuja representação de bits seja uma sequência de Bruijn (preenchida coms 2 k k X k k 2 i X i i < k{0,1}s2kkXkzeros), então os bits superiores de identificam exclusivamente (contanto que ).k2iXii<k

Sasho Nikolov
fonte
3
Observe que você pode usar qualquer sequência de Bruijn dessa maneira para calcular dado . No entanto, você não pode usar uma sequência arbitrária de Bruijn para calcular dado . Aqui 0x07C4ACDD = 00000111110001001010110011011101 parece ser uma sequência de Bruijn com algumas propriedades adicionais, graças às quais o adicional não arruina essa abordagem. 2 i i 2 i - 1 - 1i2ii2i11
Jukka Suomela 27/10/2013
Obrigado @JukkaSuomela, fiquei um pouco confuso com isso. Eu acho que você sempre pode adicionar 1 para . v
Sasho Nikolov
5

Alguns comentários (não é realmente uma resposta). Vamos classificar números inteiros de 32 bits seguinte maneira:c

  • Tipo X: (como uma sequência binária) é a sequência De Bruijn (para todas as rotações, os bits [27,31] são distintos). Um exemplo:c

    11111011100110101100010100100000
    
  • Tipo Y: os bits [27,31] de são distintos para . É isso que Leiserson et al. usos. Exemplos:i = 0 , 1 , . . . , 312ici=0,1,...,31

    00000100011001010011101011011111
    00001111101110011010110001010010
    
  • Tipo Z: os bits [27,31] de são distintos para . É disso que precisamos na pergunta original. Exemplos:i = 0 , 1 , . . . , 31(2i+11)ci=0,1,...,31

    00000111110001001010110011011101  (07C4ACDD)
    10000111110001001010110011011101
    01111000001110110101001100100011
    11111000001110110101001100100011
    

Algumas observações baseadas em experimentos rápidos (espero ter acertado):

  1. Existem 65536 inteiros do tipo X.

  2. Existem 4096 números inteiros do tipo X + Y. Esses são precisamente aqueles números inteiros do tipo X que começam com a sequência '0000 ...'

    • intuição: com zeros à esquerda, rotação = deslocamento?
  3. Existem 256 números inteiros do tipo X + Y + Z. Esses são precisamente aqueles números inteiros do tipo X que começam com a sequência '0000011111 ...'

    • intuição: ??
  4. Todos os números inteiros do tipo Y também são do tipo X.

  5. No entanto, também existem 768 números inteiros do tipo Z que não são do tipo X nem do tipo Y. Eles começam com '1000011111 ...', '0111100000 ...' ou '1111100000 ...'

Jukka Suomela
fonte
1
Esta é a única resposta que lida com o porquê da multiplicação de De Bruijn por 2 ^ n-1 funcionar, em oposição a 2 ^ n, que é apenas uma mudança. Eu adoraria se alguém pudesse expandir a "intuição" do nº 3 acima. Como Eric Cole surgiu com isso? Tentativa e erro? Ou alguma compreensão do que realmente acontece com os bits quando você multiplica por 2 ^ n-1?
FarmerBob
1
  • De onde vem essa constante?

Citação: "Em 10 de dezembro de 2009, Mark Dickinson cortou algumas operações exigindo que v seja arredondado para um a menos que a próxima potência de 2, em vez da potência de 2". [graphics.stanford.edu/~seander/bithacks.html]

Essa constante particular é uma sequência de De Bruijn com alfabeto binário, mas com uma propriedade extra. Vou chamá-lo de 'Propriedade de Marc Dickinson', já que o algoritmo original pode ser implementado sem essas sequências especiais de banco de dados. Ao adicionar duas operações extras, poderíamos usar qualquer sequência de banco de dados comum. Operação: v ^ = (v >> 1); // clr todos os bits, exceto o MSB definido após a cascata ou mudança.

  • Resultados (força bruta)

Seq.Type | No. Inteiros | Não. DBSeq. com | sem rotações | com Dickinson Propriedade
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 | ??

  • A propriedade especial

A operação ( ( - )) , produz 32 resultados nos quais se descartarmos todos, exceto os 5 bits do MSB, e depois empilharmos nelas, a coluna de 5 bits forma um LFSR que indexa todas as 32 permutações de uma sequência de 5 bits de 0 a 31. Outras constantes De Bruijn B (2,5) podem indexar 31 das 32 permutações de uma sequência de 5 bits, mas a operação (v * 0x07C4ACDD ) >> 27 falharia. Observe também que apenas os 5 MSBits formam esse LFSR, por exemplo. a soma de 5 LSBits é 166 em vez de 496 .. O padrão abaixo da linha diagonal é um artefato de multiplicação por ( - ) * 2 k 10x7C4ACDD 2k1(mod232)32k1insira a descrição da imagem aqui2k1

  • Sequências binárias de Bruijn lexicograficamente menores com Dickinson Property

    [B (2,3): 0x1D] [B (2,4): 0x0F2D] [B (2,5): 0x7C4ACDD] [B (2,6): Ainda pesquisando]

Se você estava esperando uma fórmula matemática elegante para descrevê-los ou um teorema para produzi-los ou algo semelhante, acho que isso exigiria uma compreensão profunda da teoria dos números e possivelmente de outros campos que estão além do meu conjunto de habilidades. Se eu quiser adivinhar, eu apostaria que eles poderiam ser produzidos por autômatos celulares. Esta não é uma resposta porque? em uma base rigorosa, mas uma tentativa de entender intuitivamente por que funciona e por que funciona corretamente, para que você possa usá-lo com confiança.

PS: Não cobri a construção LUT, que é facilmente deduzida se você entender os princípios de funcionamento dos algoritmos.

FranG
fonte
Finalmente encontrado: B (2,6) 0x3f08a4c6acb9dbd - uma sequência de 64 bits de bruijn com a 'propriedade dickinson'. Eu encontrei pelo menos 122K dessas seqüências.
Frang