Можете ли вы использовать Пи как генератор случайных чисел?

30

Я недавно видел этот вопрос в математике. Это заставило меня задуматься. Может ли Пи использоваться как генератор грубых случайных чисел? Я имею в виду, что результаты хорошо известны (как долго вычислялось число пи сейчас?), Но пи кажется довольно случайным, если брать по одной цифре за раз.

Имеет ли это какой-либо смысл вообще?

Earlz
источник
Где будут использоваться эти случайные числа?
NullUserException
2
Теоретически это может быть, но, вероятно, будет менее оптимальным, чем существующие методы. Просто инстинкты на это, но кажется, что случайный пул таким образом больше с меньшими накладными расходами.
Рог
@NullUserException Не уверен ... Мне просто интересно, можно ли их использовать ВСЕ. Я предполагаю, что это определенно не было бы для криптографии, хотя '
Earlz
3
@FrustratedWithFormsDesigner - часть пакета ent. Он использует случайные числа, чтобы вычислить площадь круга, вписанного в квадрат, и из этого можно вычислить число пи. Используя биты пи в качестве случайных чисел, есть некоторая элегантность, чтобы использовать эти данные для вычисления пи.
1
@FrustratedWithFormsDesigner ent - это набор кода для анализа псевдослучайности группы байтов. Одним из тестов является метод Монте-Карло для вычисления числа Пи и сравнения случайного расчета с фактическим значением, чтобы увидеть, насколько оно случайное.

Ответы:

50

Копирование с http://www.befria.nu/elias/pi/binpi.html, чтобы получить двоичное значение числа pi (чтобы было проще преобразовать в байты, чем пытаться использовать десятичные цифры), а затем запустить его через ent Я получаю следующее для анализа случайного распределения байтов:

Энтропия = 7,954093 бит на байт.

Оптимальное сжатие уменьшит размер этого файла размером 4096 байт на 0 процентов.

Распределение хи-квадрат для 4096 выборок составляет 253,00, и случайным образом будет превышать это значение в 52,36 процента раз.

Среднее арифметическое значение байтов данных составляет 126,6736 (127,5 = случайное число).

Значение Монте-Карло для Pi составляет 3,120234604 (ошибка 0,68 процента).

Коэффициент последовательной корреляции составляет 0,028195 (полностью некоррелированный = 0,0).

Так что да, использование pi для случайных данных даст вам довольно случайные данные ... понимая, что это хорошо известные случайные данные.


Из комментария выше ...

В зависимости от того, что вы делаете, но я думаю, вы можете использовать десятичные дроби квадратного корня любого простого числа в качестве генератора случайных чисел. Они должны по крайней мере иметь равномерно распределенные цифры. - Паксин

Итак, я вычислил квадратный корень из 2 в двоичном коде, чтобы устранить тот же набор проблем. Используя итерацию Вольфрама, я написал простой Perl-скрипт

#!/usr/bin/perl
use strict;
use Math::BigInt;

my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;

while(1) {
    my $unew;
    my $vnew;

    if($u->bcmp($v) != 1) { # $u <= $v
        $unew = $u->bmul(4);
        $vnew = $v->bmul(2);
    } else {
        $unew = ($u->bsub($v)->bsub(1))->bmul(4);
        $vnew = ($v->badd(2))->bmul(2);
    }   

    $v = $vnew;
    $u = $unew;

    #print $i,"  ",$v,"\n";
    if($i++ > 10000) { last; }
}

open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);

Выполнение этого для первых 10 соответствовало A095804, таким образом, я был уверен, что у меня была последовательность. Значение v n, как при записи в двоичном виде с двоичной точкой, помещенной после первой цифры, дает приблизительное значение квадратного корня из 2.

Использование ent против этих двоичных данных дает:

Entropy = 7.840501 bits per byte.

Optimum compression would reduce the size
of this 1251 byte file by 1 percent.

Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.

Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).

источник
Именно тот ответ, который я искал. Я понятия не имею, как рассчитать все эти вещи
Earlz
Даже если распределение чисел является довольно случайным, не нужно ли вам найти способ случайного выбора его части?
Blumer
1
@ Блюмер нет. Случайность измеряется по последовательности чисел. Последовательность цифр пи называется случайной. См. En.wikipedia.org/wiki/Statistical_randomness
Саймон Бергот
11
Совершенно верно. И поскольку это общеизвестные случайные данные, никогда не смей использовать их в криптографических целях.
Сокол
3
+1 за «общеизвестные случайные данные». Если вам нужны случайные данные, о которых кто-то не может догадаться, пи не для вас, если по какой-то причине вам нужна просто группа случайных чисел, все работает отлично.
Jmoreno
5

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

PSR
источник
2

Такой генератор был бы генератором псевдослучайных чисел, т. Е. При том же начальном числе результат всегда был бы одинаковым. При этом в большинстве сред при использовании стандартного генератора случайных чисел существует та же проблема псевдослучайности.

Распределение цифр, по-видимому, очень похоже на стандартные генераторы случайных чисел so, поэтому цифры π можно использовать для обычных сценариев генерации случайных чисел.

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


Я верю, что это правда, но у меня нет никаких доказательств. Было бы интересно (и не усложнять) сделать сравнение, основанное на большом количестве чисел.

Арсений Мурзенко
источник
5
@NullUserException: Нет, некоторые генераторы случайных чисел используют источник энтропии. Это может быть сделано либо через специализированное аппаратное обеспечение (подход, выбранный random.org ), либо с использованием существующих источников энтропии (измеримые флуктуации в существующих аппаратных сенсорах, определенные типы взаимодействий с пользователем, микро-вариации в определенных типах тестов производительности и т. Д.). ).
Брайан
1
@NullUserException: существуют криптографически защищенные PRNG, которые все еще являются псевдослучайными. Кроме того, существуют реальные ГСЧ, основанные на
фактических данных
2
@MainMa Но даже тогда, случайность радиоактивного распада, атмосферный шум, полученный из пользовательского ввода и т.д. спорно. То, что мы не распознаем шаблон, не означает, что его не существует.
NullUserException
1
@NullUserException: в прошлом году Колбек / Реннер опубликовал документ, который призван доказать: «Никакое расширение квантовой теории не может улучшить предсказательную силу». Если предположить, что это действительно так, то может существовать источник энтропии, который действительно непредсказуем, а не просто невозможен для предсказания.
Брайан
1
@MainMa - вы все равно будете выполнять математические тесты на случайность. Хотя основная физика является случайной (насколько нам известно), это не означает, что измерение есть. Детекторы всех типов имеют много «интересного» поведения в реальном мире
Мартин Беккет
2

Случайность цифр числа Пи (или, в этом отношении, любой другой последовательности) может быть проверена так называемыми «тестами батареи». Одним из популярных тестов батареи является тест Diehard Battery Джорджа Марсальи . Существует также специальная публикация NIST 800-22, в которой описывается ряд таких тестов и результаты применения этих тестов к ряду физических констант, в том числе - lo and behold - pi для более миллиона битов. Результат числа pi приведен в Приложении B отчета и выглядит следующим образом:

Statistical Test                            P-value
Frequency                                   0.578211
Block Frequency (m = 128)                   0.380615
Cusum-Forward                               0.628308
Cusum-Reverse                               0.663369
Runs                                        0.419268
Long Runs of Ones                           0.024390
Rank                                        0.083553
Spectral DFT                                0.010186
Non-overlapping Templates (m = 9, B = 000000001)          0.165757
Overlapping Templates (m = 9)               0.296897
Universal                                   0.669012
Approximate Entropy (m = 10)                0.361595
Random Excursions (x = +1)                  0.844143
Random Excursions Variant (x = -1)          0.760966
Linear Complexity (M = 500)                 0.255475
Serial (m = 16, 2m∇Ψ )                      0.143005

Является ли пи хорошим генератором случайных последовательностей? Посмотрите на приведенные выше результаты (или найдите значения левой колонки, если вы не знаете, что они означают), и проверьте, удовлетворяет ли она вашим потребностям.

sm535
источник
1
Читайте мне для Diehard говорит, что ему нужно около 10-12 мегабайт двоичных данных (лучшее, что я мог найти, это 32 килобайта). Если вы запускаете его в сравнении с данными ascii, тестирование будет весьма далеко от того, что ожидает приложение.
Мой ответ был на вопрос OP и оригинальный вопрос на Math.SE - ни в одном из них не упоминалось ничего об ascii в сравнении с двоичными данными или о длине выборки. Без достаточно большого набора выборок, как можно определить статистическую случайность любой последовательности?
sm535