De Bruijn-подобная последовательность для `2 ^ n-1`: как она построена?

Ответ 1

Последовательность порядка n De Bruijn порядка над k символами (и длины k ^ n) обладает тем свойством, что каждое возможное слово n-length появляется в виде последовательных символов в нем, некоторые из них с циклической упаковкой. Например, в случае k = 2, n = 2, возможными словами являются 00, 01, 10, 11, и последовательность De Bruijn равна 0011. 00, 01, 11 появляется в нем, 10 с упаковкой. Это свойство, естественно, означает, что левое смещение последовательности Де Брейна (умножение на мощность двух) и принятие его верхних n бит приводит к уникальному числу для каждой мощности двух множителей. Тогда вам нужна только таблица поиска, чтобы определить, какой из них она есть. Он работает по аналогичному принципу с числами, которые меньше мощности двух, но магическое число в этом случае не является последовательностью Де Бройна, а аналогом. Определяющее свойство просто меняется на "все возможные n-длинные слова", как сумма первых m подпоследовательностей длины n, mod 2 ^ n ". Это свойство - все, что необходимо для работы алгоритма. Они просто использовали этот класс волшебных чисел для ускорения алгоритма. Я тоже сделал.

Одним из возможных способов построения чисел Де Бройна является генерация гамильтонова траектории графа Де Бройна, Википедия дает пример такого графика. В этом случае узлы представляют собой 2 ^ 5 = 32-битные целые числа, направленные ребра - это переходы между ними, где переход - сдвиг влево и двоичный или операция в соответствии с меткой края 0 или 1. Там может быть быть прямым аналогом магических чисел типа 2 ^ n-1, это может стоить изучить, но это не так, как обычно люди создают такие алгоритмы.

На практике вы можете попытаться построить его по-другому, особенно если вы хотите, чтобы он вел себя несколько иначе. Например, реализация ведущего/конечного числа алгоритмов нулевого уровня на странице бит-скринштейнов может возвращать значения только в [0..31]. Он нуждается в дополнительной проверке для случая 0, который имеет 32 нуля. Эта проверка требует разветвления и может быть слишком медленной на некоторых процессорах.

Как я это сделал, я использовал таблицу поиска из 64 элементов вместо 32, генерировал случайные магические числа, и для каждого из них я построил таблицу поиска с мощностью двух входов, проверил ее правильность (инъективность), затем проверил его для всех 32-битных чисел. Я продолжал, пока не столкнулся с правильным магическим числом. Результирующие числа не удовлетворяют свойству "появляется все возможные n-длинные слова", поскольку появляются только 33 числа, которые являются уникальными для всех 33 возможных входных данных.

Исчерпывающий поиск грубой силы звучит медленно, особенно если хорошие магические числа встречаются редко, но если мы сначала проверим известную мощность двух значений в качестве входных данных, таблица будет заполнена быстро, отклонение будет быстрым, а скорость отклонения будет очень высокой. Нам нужно только очистить таблицу после каждого магического номера. По сути, я использовал алгоритм высокой скорости отклонения для построения магических чисел.

Результирующие алгоритмы

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];
}

Что касается вашего вопроса о том, как они знают, они, вероятно, этого не сделали. Они экспериментировали, пытались изменить вещи, как и я. В конце концов, это не большой объем воображения, что 2 ^ n-1 входы могут работать вместо 2 ^ n входов с различным магическим числом и таблицей поиска.

Здесь я сделал упрощенную версию кода генератора магических чисел. Он проверяет все возможные магические числа за 5 минут, если мы проверяем только мощность двух входов, нахождение 1024 магических чисел. Проверка на другие входы бессмысленна, так как в любом случае они уменьшены до формы 2 ^ n-1. Не создает таблицу, но она тривиальна, если вы знаете магическое число.

#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();
    }
}

Ответ 2

Он основан на документе Использование последовательностей Bruijn для индексации 1 в компьютерном Word. Я собираюсь предположить, что они выполнили поиск идеальной хеш-функции для отображения 2^n-1 в [0..31]. Они описывают метод поиска нулей целых чисел с набором до двух бит, который включает в себя постепенное наращивание множителя.

Ответ 3

От: 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

Мне кажется, что 0x07C4ACDD является 5-разрядной последовательностью Брейна.