algorithm - Secuencia de Bruijn-como para `2 ^ n-1`: ¿cómo está construido?

bit-manipulation discrete-mathematics

Question

Estoy buscando en la entrada Buscar la base de registro 2 de un entero de N bits en operaciones O (lg (N)) con multiplicación y búsqueda de hacks de Bit Twiddling .

Puedo ver fácilmente cómo funciona el segundo algoritmo en esa entrada

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

que calcula n = log2 v donde se sabe que v es una potencia de 2. En este caso, 0x077CB531 es una secuencia de De Bruijn ordinaria, y el resto es obvio.

Sin embargo, el primer algoritmo en esa entrada.

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;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

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

Me parece un poco más complicado. Comenzamos por ajustar v al valor 2^n - 1 mayor más cercano. Este valor de 2^n - 1 se multiplica por 0x07C4ACDD , que en este caso actúa de la misma manera que lo hizo la secuencia DeBruijn en el algoritmo anterior.

Mi pregunta es: ¿cómo construimos esta secuencia mágica 0x07C4ACDD ? Por ejemplo, ¿cómo construimos una secuencia que se puede usar para generar índices únicos cuando se multiplica por un valor de 2^n - 1 ? Para 2^n multiplicador es solo una secuencia de De Bruijn ordinaria, como podemos ver arriba, así que está claro de dónde proviene 0x077CB531 . ¿Pero qué hay de 2^n - 1 multiplicador 0x07C4ACDD ? Siento que me estoy perdiendo algo obvio aquí.

PD: Para aclarar mi pregunta: no estoy buscando realmente un algoritmo para generar estas secuencias. Estoy más interesado en alguna propiedad más o menos trivial (si existe) que haga que 0x07C4ACDD funcione como queremos que funcione. Para 0x077CB531 la propiedad que lo hace funcionar es bastante obvia: contiene todas las combinaciones de 5 bits "almacenadas" en la secuencia con pasos de 1 bit (que es básicamente lo que es la secuencia De Bruijn).

El 0x07C4ACDD , por otro lado, no es una secuencia de De Bruijn por sí misma. Entonces, ¿a qué propiedad apuntaban cuando construyeron 0x07C4ACDD (además del no constructivo "debería hacer funcionar el algoritmo anterior")? Alguien hizo el algoritmo anterior de alguna manera. Entonces, probablemente sabían que el enfoque es viable y que existe la secuencia apropiada. ¿Cómo sabían eso?

Por ejemplo, si tuviera que construir el algoritmo para una v arbitraria, lo haría

v |= v >> 1;
v |= v >> 2;
...

primero. Luego solo haría ++v para convertir v en una potencia de 2 (supongamos que no se desborda). Luego aplico el primer algoritmo. Y, finalmente, haría --r para obtener la respuesta final. Sin embargo, estas personas lograron optimizarlo: eliminaron los pasos ++v y los pasos --r simplemente cambiando el multiplicador y reorganizando la tabla. ¿Cómo sabían que era posible? ¿Cuál es la matemática detrás de esta optimización?

Answer 1

Desde: http://www.stmintz.com/ccc/index.php?id=306404

130329821
0x07C4ACDD
00000111110001001010110011011101B

bit 31 - bit 27   00000  0
bit 30 - bit 26   00001  1
bit 29 - bit 25   00011  3
bit 28 - bit 24   00111  7
bit 27 - bit 23   01111 15
bit 26 - bit 22   11111 31
bit 25 - bit 21   11110 30
bit 24 - bit 20   11100 28
bit 23 - bit 19   11000 24
bit 22 - bit 18   10001 17
bit 21 - bit 17   00010  2
bit 20 - bit 16   00100  4
bit 19 - bit 15   01001  9
bit 18 - bit 14   10010 18
bit 17 - bit 13   00101  5
bit 16 - bit 12   01010 10
bit 15 - bit 11   10101 21
bit 14 - bit 10   01011 11
bit 13 - bit  9   10110 22
bit 12 - bit  8   01100 12
bit 11 - bit  7   11001 25
bit 10 - bit  6   10011 19
bit  9 - bit  5   00110  6
bit  8 - bit  4   01101 13
bit  7 - bit  3   11011 27
bit  6 - bit  2   10111 23
bit  5 - bit  1   01110 14
bit  4 - bit  0   11101 29
bit  3 - bit 31   11010 26 
bit  2 - bit 30   10100 20
bit  1 - bit 29   01000  8
bit  0 - bit 28   10000 16

Me parece que 0x07C4ACDD es una secuencia de Bruijn de 5 bits.

Answer 2

Se basa en el documento Uso de secuencias de Bruijn para indexar un 1 en una palabra de computadora . Voy a adivinar que hicieron una búsqueda de una función hash perfecta para asignar 2^n-1 a [0..31] . Describen un método para buscar el conteo de ceros de enteros con hasta dos bits establecidos, lo que implica construir incrementalmente el multiplicador.

Answer 3

Una secuencia De Bruijn de orden n sobre k símbolos (y de k ^ n longitud) tiene la propiedad de que cada palabra de longitud n posible aparece como caracteres consecutivos, algunos de ellos con envoltura cíclica. Por ejemplo, en el caso de k = 2, n = 2, las palabras posibles son 00, 01, 10, 11 y una secuencia De Bruijn es 0011. 00, 01, 11 aparece en ella, 10 con el ajuste. Esta propiedad, naturalmente, significa que el desplazamiento a la izquierda de una secuencia De Bruijn (multiplicar con la potencia de dos) y tomar sus n bits superiores da como resultado un número único para cada potencia de dos multiplicadores. Entonces solo necesitas una tabla de búsqueda para determinar cuál es. Funciona según un principio similar a los números que son uno menos que el poder de dos, pero el número mágico en este caso no es una secuencia de De Bruijn, sino un análogo. La propiedad de definición simplemente cambia a "cada palabra de longitud n posible aparece como la suma de las primeras m subsecuencias de longitud n, mod 2 ^ n". Esta propiedad es todo lo que se necesita para que funcione el algoritmo. Simplemente utilizaron esta clase diferente de números mágicos para acelerar el algoritmo. Yo también lo hice.

Un posible método de construcción de los números de De Bruijn es la generación de una ruta hamiltoniana del gráfico de De Bruijn; Wikipedia proporciona un ejemplo de dicho gráfico. En este caso, los nodos son 2 ^ 5 = enteros de 32 bits, los bordes dirigidos son transiciones entre ellos, donde una transición es un desplazamiento a la izquierda y un binario u operación de acuerdo con la etiqueta del borde, 0 o 1. Es posible que Ser un análogo directo a los números mágicos del tipo 2 ^ n-1, podría valer la pena explorarlo, pero esta no es una forma en que las personas suelen construir tales algoritmos.

En la práctica, puedes intentar construirlo de manera diferente, especialmente si quieres que se comporte de una manera un poco diferente. Por ejemplo, la implementación del número inicial / final de algoritmos de ceros en la página de hacks de trucos de bits solo puede devolver valores en [0..31]. Necesita verificación adicional para el caso de 0, que tiene 32 ceros. Esta comprobación requiere una bifurcación y puede ser demasiado lenta en algunas CPU.

De la forma en que lo hice, utilicé una tabla de búsqueda de 64 elementos en lugar de 32, generé números mágicos aleatorios, y para cada uno de ellos construí una tabla de búsqueda con el poder de dos entradas, verifiqué su exactitud (inyectividad) y luego la verifiqué. todos los números de 32 bits Continué hasta que encontré un número mágico correcto. Los números resultantes no cumplen con una propiedad de "aparece cada palabra de longitud n posible", ya que solo aparecen 33 números, que son únicos para las 33 entradas posibles.

La búsqueda de fuerza bruta exhaustiva suena lenta, especialmente si los buenos números mágicos son raros, pero si primero probamos la potencia conocida de dos valores como entradas, la tabla se llena rápidamente, el rechazo es rápido y la tasa de rechazo es muy alta. Solo necesitamos limpiar la mesa después de cada número mágico. En esencia, exploté un algoritmo de alto índice de rechazo para construir números mágicos.

Los algoritmos resultantes son

int32 Integer::numberOfLeadingZeros (int32 x)
{
    static int32 v[64] = {
        32, -1, 1, 19, -1, -1, -1, 27, -1, 24, 3, -1, 29, -1, 9, -1,
        12, 7, -1, 20, -1, -1, 4, 30, 10, -1, 21, -1, 5, 31, -1, -1,
        -1, -1, 0, 18, 17, 16, -1, -1, 15, -1, -1, -1, 26, -1, 14, -1,
        23, -1, 2, -1, -1, 28, 25, -1, -1, 13, 8, -1, -1, 11, 22, 6};
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x *= 0x749c0b5d;
    return v[cast<uint32>(x) >> 26];
}

int32 Integer::numberOfTrailingZeros (int32 x)
{
    static int32 v[64] = {
        32, -1, 2, -1, 3, -1, -1, -1, -1, 4, -1, 17, 13, -1, -1, 7,
        0, -1, -1, 5, -1, -1, 27, 18, 29, 14, 24, -1, -1, 20, 8, -1,
        31, 1, -1, -1, -1, 16, 12, 6, -1, -1, -1, 26, 28, 23, 19, -1,
        30, -1, 15, 11, -1, 25, 22, -1, -1, 10, -1, 21, 9, -1, -1, -1};
    x &= -x;
    x *= 0x4279976b;
    return v[cast<uint32>(x) >> 26];
}

En cuanto a su pregunta de cómo lo sabían, probablemente no lo sabían. Ellos experimentaron, trataron de cambiar las cosas, igual que yo. Después de todo, no es una gran cantidad de imaginación que 2 ^ n-1 entradas puedan funcionar en lugar de 2 ^ n entradas con diferente número mágico y tabla de búsqueda.

Aquí, hice una versión simplificada de mi código generador de número mágico. Verifica todos los números mágicos posibles en 5 minutos si verificamos solo la potencia de dos entradas, encontrando 1024 números mágicos. La comprobación contra otras entradas no tiene sentido, ya que de todos modos se reducen a 2 ^ n-1. No construye la tabla, pero es trivial una vez que conoces el número mágico.

#include <Frigo/all>
#include <Frigo/all.cpp>

using namespace Frigo::Lang;
using namespace std;

class MagicNumberGenerator
{

    public:

        static const int32 log2n = 5;
        static const int32 n = 1 << log2n;
        static const bool tryZero = false;

        MagicNumberGenerator () {}

        void tryAllMagic ()
        {
            for( int32 magic = 0; magic < Integer::MAX_VALUE; magic++ ){
                tryMagic(magic);
            }
            tryMagic(Integer::MAX_VALUE);
            for( int32 magic = Integer::MIN_VALUE; magic < 0; magic++ ){
                tryMagic(magic);
            }
        }

        bool tryMagic (int32 magic)
        {
            //  clear table
            for( int32 i = 0; i < n; i++ ){
                table[i] = -1;
            }
            //  try for zero
            if( tryZero and not tryInput(magic, 0) ){
                return false;
            }
            //  try for all power of two inputs, filling table quickly in the process
            for( int32 i = 0; i < 32; i++ ){
                if( not tryInput(magic, 1 << i) ){
                    return false;
                }
            }
            //  here we would test all possible 32-bit inputs except zero, but it is pointless due to the reduction to 2^n-1 form
            //  we found a magic number
            cout << "Magic number found: 0x" << Integer::toHexString(magic) << endl;
            return true;
        }

        bool tryInput (int32 magic, int32 x)
        {
            //  calculate good answer
            int32 leadingZeros = goodNumberOfLeadingZeros(x);
            //  calculate scrambled but hopefully injective answer
            x |= x >> 1;
            x |= x >> 2;
            x |= x >> 4;
            x |= x >> 8;
            x |= x >> 16;
            x *= magic;
            x = Integer::unsignedRightShift(x, 32 - log2n);
            //  reject if answer is not injective
            if( table[x] != -1 ){
                return table[x] == leadingZeros;
            }
            //  store result for further injectivity checks
            table[x] = leadingZeros;
            return true;
        }

        static int32 goodNumberOfLeadingZeros (int32 x)
        {
            int32 r = 32;
            if( cast<uint32>(x) & 0xffff0000 ){
                x >>= 16;
                r -= 16;
            }
            if( x & 0xff00 ){
                x >>= 8;
                r -= 8;
            }
            if( x & 0xf0 ){
                x >>= 4;
                r -= 4;
            }
            if( x & 0xc ){
                x >>= 2;
                r -= 2;
            }
            if( x & 0x2 ){
                x >>= 1;
                r--;
            }
            if( x & 0x1 ){
                r--;
            }
            return r;
        }

        int32 table[n];

};

int32 main (int32 argc, char* argv[])
{
    if(argc||argv){}
    measure{
        MagicNumberGenerator gen;
        gen.tryAllMagic();
    }
}