Давайте предположим, что у меня есть N-битный поток сгенерированных битов. (В моем случае 64 килобит.)
Какова вероятность нахождения последовательности из X «всех истинных» битов, содержащихся в потоке из N битов. Где X = (от 2 до 16) и N = (от 16 до 1000000), а X
Например: если N = 16 и X = 5, какова вероятность нахождения 11111 в пределах 16 -битное число.
Как этот псевдокод:
int N = 1<<16; // (64KB)
int X = 5;
int Count = 0;
for (int i = 0; i < N; i++) {
int ThisCount = ContiguousBitsDiscovered(i, X);
Count += ThisCount;
}
return Count;
То есть, если мы выполнили целое число в al oop от 0 до 64K-1 ... сколько раз в этих числах появилось бы 11111.
Дополнительное правило: 1111110000000000 не считается, потому что в нем 6 истинных значений подряд, а не 5. Итак:
1111110000000000 = 0x // because its 6 contiguous true bits, not 5.
1111100000000000 = 1x
0111110000000000 = 1x
0011111000000000 = 1x
1111101111100000 = 2x
Я пытаюсь выполнить некоторую работу, включающую физическую генерацию случайных чисел и обнаружение «насколько случайны» числа. Вот для чего это.
...
Это было бы легко решить, если бы N было меньше 32 или около того, я мог бы просто "запустить al oop" от 0 до 4 ГБ. , затем посчитайте, сколько смежных битов было обнаружено после завершения l oop. Тогда я мог бы сохранить число и использовать его позже.
Учитывая, что значение X варьируется от 2 до 16, мне буквально нужно было бы хранить только 15 чисел, каждое из которых меньше 32 бит! (если N = 32)!
НО в моем случае N = 65,536. Поэтому мне нужно запустить al oop, для 2 ^ 65 536 итераций. В принципе невозможно:)
Нет способа "экспериментально рассчитать значения для данного X, если N = 65 536". В общем, мне нужна математика.