Как я могу выбрать случайное значение между 0 и bigint?

Question

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

---

Недостатки моего нынешнего подхода

Теперь для обычных целых чисел я бы обычно писал что-то вроде int rand 500; и покончим с этим.

Но для больших целых это выглядит rand не предназначен для этого.

Используя следующий код, я запустил симуляцию 2 миллионов вызовов rand $bigint:

$ perl -Mbigint -E 'say int rand 1230138339199329632554990773929330319360000000 for 1 .. 2e6' > rand.txt

Распределение результирующего набора далеко не желательно:

• 0 (56 отсчетов)
• величина 1e+040 (112 отсчетов)
• величина 1e+041 (1411 отсчетов)
• величина 1e+042 (14496 отсчетов)
• величина 1e+043 (146324 отсчетов)
• величина 1e+044 (1463824 отсчетов)
• величина 1e+045 (отсчет 373777)

Таким образом, процесс никогда не мог выбрать номер, как 999, или же 5e+020что делает этот подход неподходящим для того, что я хочу сделать.

Похоже, это как-то связано с произвольной точностью rand, который никогда не выходит за пределы 15 цифр в ходе моего тестирования:

$ perl -E 'printf "%.66g", rand'
0.307037353515625

---

Как я могу преодолеть это ограничение?

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

В любом случае, я надеюсь, что кто-то уже шел по этому пути раньше и знает, как исправить ситуацию.

Answer 1

(Конвертировано из моего комментария)

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

ПСЕВДОКОД

• Вычислите биты, необходимые для представления вашего числа: n_needed_bits
• Проверьте размер битов, возвращаемых вашим PRNG: n_bits_prng
• Рассчитайте количество необходимых образцов: needed_prng_samples = ceil(n_needed_bits / n_bits_prng)
• Пока правда:
  • Образец needed_prng_samples (вызовы в PRNG) раз и объединить все полученные биты
  • Проверьте, находится ли полученное число в вашем диапазоне
  • Да?: номер возврата (закончено)
  • Нет?: ничего не делать (цикл продолжается; повторная выборка всех компонентов снова!)

замечания

• Это форма приемочной выборки / отбраковочной выборки
• Подход представляет собой алгоритм типа Лас-Вегаса: время выполнения не ограничено теоретически
  • Количество необходимых циклов в среднем: n_possible-sample-numbers-of-full-concatenation / n_possible-sample-numbers-within-range
• Полная повторная выборка (если результат находится за пределами диапазона) в соответствии с методом отклонения дает доступ к более формальному анализу несмещенности / однородности и является очень важным аспектом для этого подхода
• Конечно, классические предположения относительно PRNG-выхода необходимы для этой работы.
  • Если PRNG, например, имеет некоторую неоднородность в отношении младших / старших битов (как часто упоминается), это будет иметь эффект от вывода выше

Answer 2

Я смотрел на эту проблему с неправильной точки зрения

Контейнеры не одного размера. Каждая корзина в 10 раз больше предыдущей. Чтобы представить это в перспективе, есть 10 000 возможных целых чисел 1e+44 за каждое целое число с величиной 1e+40,

Вероятность нахождения любого числа по величине 1e+20 для большого в 1e+45 меньше чем 0.00000 00000 00000 00000 001 %,

Забудьте иголки в стогах сена, это больше похоже на нахождение иголки в квазаре!

Answer 3

Подход может состоять в том, чтобы разрезать строковое представление числа на куски, логическое ($low) инициализированное значение false, в то время как первые случайные ничьи равны верхней границе.

РЕДАКТИРОВАТЬ: добавил некоторые пояснения после комментария

# first argument (in) upper bound
# second argument (in/out) is lower (false while random returns upper bound, after it remains true)
sub randhlp {
    my($upp)=@_;
    my $l=length $upp;
    # random number less than
    # - upper bound if islower is false
    # - 9..99 otherwise
    my $x=int rand ($_[1] ? 10**$l : $upp+1);
    if ($x<$upp) {
        $_[1]=1;
    }
    # left padding with 0
    return sprintf("%0*d",$l,$x);
}

# returns a random number less than argument (numeric string)
sub randistr {
    my($n)=@_;
    $n=~/^\d+$/ or die "invalid input not numeric";
    $n ne "0" or die "invalid input 0";
    my($low,$x);
    do {
        undef $x;
        # split string by chunks of 6 characters
        # except last chunk which has 1 to 6 characters
        while ($n=~/.{1,6}/g) {
            # concatenate random results
            $x.=randhlp($&,$low)
        }
    } while ($x eq $n);
    $x=~s/^0+//;
    return $x;
}

Тест

for ($i=0;$i<2e6;++$i) {
    $H{length(randistr("1230138339199329632554990773929330319360000000"))}+=1;
}

print "$_ $H{$_}\n" for sort keys %H;

Возвращает

39 4
40 61
41 153
42 1376
43 14592
44 146109
45 1463301
46 374404