Последовательность Де Брейна порядка n по k символам (и длиной k ^ n) обладает свойством, заключающимся в том, что каждое возможное слово длины n появляется в нем как последовательные символы, некоторые из них с циклическим переносом. Например, в случае k = 2, n = 2, возможными словами являются 00, 01, 10, 11, а последовательность Де Брейна - 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();
}
}