PHP - Улучшение генерации последовательности случайных чисел

Question

Я предполагаю, что здесь приходит мой первый вопрос о SO.

В настоящее время я работаю над веб-сайтом, и мне нужно сгенерировать 6 номеров от 1 до 29 (по одному на каждый максимум) для лотереи. Поскольку они могут быть в любом порядке, я просто сортирую их потом.

Если я не ошибаюсь, это должно означать, что есть возможные возможные комбинации: (29*28*27*26*25*24)/6! = 475020.

Я пробовал разные способы генерации последовательностей, используя mt_rand или random_int (от random_compat), но когда я тестирую его с чем-то вроде итераций 10k, я всегда получаю около 100 дубликатов, хотя они похожи на 465k комбинаций доступный.

Вот примеры кода я пытался:

// Using an array and mt_rand (or random_int, giving same results) 
// Also tried shuffling the array instead of simply reindexing it, not better 

$values = range(1, 29); 

while(count($values) > 6) { 
    unset($values[mt_rand(0, count($values) - 1)]); 
    $values = array_values($values); 
} 



// Creating the array from random numbers (same results using random_int) 

$values = array(); 
while (count($values) < 6) { 
    $r = mt_rand(1, 29); 
    if (in_array($r, $values)) { 
     continue; 
    } else { 
     $values[] = $r; 
    } 
} 

Так хорошо ... Мои вопросы:

• Есть ли способ улучшить то, что я сейчас делаю?
• Это так, как должно быть, и я должен иметь дело с этим?
• Я просто делаю это неправильно?

Спасибо!

Lyn.

PS: Просмотрено много вопросов, но не нашлось ничего, что могло бы заполнить мои потребности, извините, если я не выглядел достаточно хорошо!

Просто, чтобы сделать несколько вещей ясно: Использование random_int (что делает использование/DEV/urandom или openssl_random_pseudo_bytes) не улучшает ничего, что я думал, что будет. И я не хочу использовать внешний API (например, random.org), если это возможно.

Answer 1

Использование random_int (что делает использование/DEV/urandom или openssl_random_pseudo_bytes) не улучшает ничего, что я думал, что будет.

Несомненно, это не то, что вы можете идентифицировать визуально. mt_rand() и rand() позволяют только около 2 возможных семян и 2 возможные выходы и, самое главное, имеют детерминированных последовательностей: if you know a few outputs, you can predict the rest until it's reseeded.

В CSPRNG вашей операционной системы нет таких ограничений. Знание нескольких выходов random_int() (которые в PHP ограничены 2 Возможные значения для 32-разрядных систем, 2 на 64-разрядных системах) не даст вам никакой информации о будущих выходах.

В настоящее время я работаю над веб-сайтом, и мне нужно сгенерировать 6 номеров от 1 до 29 (по одному на каждый максимум) для лотереи. Поскольку они могут быть в любом порядке, я просто сортирую их потом.

Хорошо, это опрятная идея. Вы определенно хотите CSPRNG здесь.

Когда я тестирую его с чем-то вроде итераций 10 тыс., Я всегда получаю около 100 дубликатов, хотя они похожи на 465 тыс. Комбинаций, которые все еще доступны.

Как уже указывалось, это birthday problem/paradox в игре.

Если вам нужно решение, попробовать что-то вроде этого:

function random_unique_select($num, array $possible_values) 
{ 
    $sizeof = count($possible_values); 
    if ($num > $sizeof) { 
     throw new InvalidArgumentException('$num is too large'); 
    } 
    $selected = []; 
    for ($i = 0; $i < $num; ++$i) { 
     // Grab a random int [0, ... N - 1] 
     $r = random_int(0, $sizeof - 1); 
     // Copy the selected value into $selected 
     $selected[] = $possible_values[$r]; 
     // Delete it from the range of possible values 
     unset($possible_values[$r]); 
     // N has grown smaller by 1 
     --$sizeof; 
     // Reset keys; we want this to be zero-indexed. 
     $possible_values = array_values($possible_values); 
    } 
    return $selected; 
} 

$lottery = random_unique_select(6, range(1,29)); 

Demos:

• http://3v4l.org/Hb97A (однопроходный; использует openssl_random_pseudo_bytes())
• http://3v4l.org/E7cb5 (100000 итераций -> очень маленькие номера дубликатов)

Answer 2

Чтобы улучшить «случайность», вы можете попробовать криптографические библиотеки, например. phpseclib.

В их математической библиотеке есть функция random() here.

EDIT: Номера, генерируемые компьютерами, не могут быть random. Лучшие псевдослучайные результаты, которые вы можете получить с помощью криптографических библиотек, самым простым, наиболее случайным решением является решение @Matthias Leuffen.

Answer 3

rand() и mt_rand() полагаются на чистую математику для получения псевдослучайных чисел.

Чтобы получить реальные случайные числа можно использовать WebService из http://www.random.org

Answer 4

Вы могли бы, при условии, что правильные расширения установлены, чтобы использовать openssl_random_pseudo_bytes().

Пример:

function strong_random() { 
    return hexdec(bin2hex(openssl_random_pseudo_bytes(20))); 
} 

Примечание: в связи с осуществлением openssl_random_pseudo_bytes(), эта функция будет очень медленно.

Быстро и грязно, конечно, можно было бы использовать добавление параметра максимальной длины.

Answer 5

Подробнее о Birthday Paradox.

Согласно моим расчетам (bc calculator), вероятность получения дублированной комбинации с 6 из 29 предметов составляет 50% или лучше с 812 числом последовательностей.

define p(n, k) { return (n-k)/n; } 
n=475020 
m=1; for (k=0; k<811; k++) m *= p(n, k); m 
.500649663424 
m=1; for (k=0; k<812; k++) m *= p(n, k); m 
.499794905988