Как реализовать случайные числа в большом диапазоне на js?
Необходимо реализовать случайные числа в большом диапащоне. Порядка 80 символов в числе. Стандартные решения типа Math.rand не дают нужной энтропии.
Необходим именно алгоритм, потому что даже библиотеки из npm не дают нужного результата в работе как с bigint.
Созрел небольшой алгоритм:
Получить число как строку и разбить его на отдельные числа.
В рамках каждого числа получить случайное от 0 до текущего числа.
Сложить как строку и получить случайный срез от 1 до кол-ва символов в исходном числе.
Вариант не плохой, но он неравномерно будет считать. Вариантов случайных чисел в числе длинной 10 символов куда меньше, чем в числе длинной 80 символов. Но по сути они будут одинаково идти при вероятности случайного выбора. Т.е. у числа 100 будет такая же вероятность появится как и у числа 100000000,
Это происходит из-за среза. По идеи нужен некий множитель вероятности, который будет определять насколько большое число и давай в его диапазоне больше вероятностей выбора.
Как можно написать алгоритм, который будет вычислять максимально верно?
Для правильного вопроса надо знать половину ответа
function rand80() {
let result = ''+Math.floor(Math.random()*10000000000);
for (let i = 0; i < 7; i++) {
result += ('0000000000'+Math.floor(Math.random()*10000000000)).substr(-10);
}
return result;
}
console.log(rand80());
Rsa97, данный пример не дает равномерного распределения во всем диапазоне значений. Как впрочем и мой. Но мой чуть ровнее будет.
Внутри каждого токена (группы из 10 цифр) Ваш вариант будет иметь экспоненциальный закон распределения, а в сумме совсем не понятно какой, но точно не равномерный.
PPS: только сейчас сообразил что jslby имено об этом и говорил, задавая вопрос.
Роман, В моём варианте результат составляется как строка, у каждой группы, кроме первой, добавляются лидирующие нули до 10 знаков (для первой они не обязательны).
Для простоты возьмём число, состоящее из девяти цифр, каждая тройка которых генерируется независимо. Сгенерируем первую тройку, от 000 до 999. Получим значения от 0 до 999 миллионов, распределённые равномерно. Следующая тройка цифр даст следующие три цифры, количество тысяч, также распределённое равномерно внутри выбранного миллиона. И последняя тройка даёт количество единиц, опять же равномерно распределённое внутри выбранной тысячи. Таким образом, получим девятизначное число с равномерным распределением.
Rsa97, логика вполне понятная, свой вариант тоже делал опираясь на нее. Но она ошибочная. Именно из-за нулей. Нельзя воспринимать токен с добавленными нулями распределенным равномерно именно по причине того, что в результат он включается вместе с этими нулями. Сейчас доберусь до компа и накидаю небольшой тестик, показывающий неравномерность распределения.
Rsa97, а пока вот вам простая выкладка:
1. При генерации 10 значного токена число генерируется в интервале от 0 до 999999999 с равномерным законом распределения, при этом если длинна числа меньше 10 символов то оно до 10 символов лидирующими нулями.
2. так как добавленные нули каждого токена включаются в результирующее 80-и значное число то рассмотрим вероятность появления нуля в каждой их 10 позиций токена:
- в 10-й позиции токена вероятность появления нуля будет 0.1
- в 9-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет однозначным, тоесть 0.1 + 10/10000000000 = 0.1000000001
- в 8-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 2 или менее значным, тоесть 0.1 + 0.0000000001 + 100/10000000000 = 0.1000000011
- в 7-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 3 или менее значным, тоесть 0.1 + 0.0000000011 + 1000/10000000000 = 0.1000000111
- в 6-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 4 или менее значным, тоесть 0.1 + 0.0000000111 + 10000/10000000000 = 0.1000001111
- в 5-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 5 или менее значным, тоесть 0.1 + 0.0000001111 + 100000/10000000000 = 0.1000011111
- в 4-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 6 или менее значным, тоесть 0.1 + 0.0000011111 + 1000000/10000000000 = 0.1000111111
- в 3-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 7 или менее значным, тоесть 0.1 + 0.0000111111 + 10000000/10000000000 = 0.1001111111
- во 2-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 8 или менее значным, тоесть 0.1 + 0.0001111111 + 100000000/10000000000 = 0.1011111111
- во 1-й позиции токена вероятность появления нуля будет 0.1 + вероятность того, что сгенерированное число будет 9 или менее значным, тоесть 0.1 + 0.0011111111 + 1000000000/10000000000 = 0.1111111111
Что позволяет однозначно утверждать, что закон распределения в токене не является равномерным, а следовательно закон распределения числа составленного из таких токенов также не является равномерным
Роман, Вы неправильно считаете. Разрядность не генерируется, она получается из сгенерированных цифр. Если в первой позиции сгенерировался не ноль, то число автоматически будет 10-разрядным.
Rsa97, я говорю о генерации таких комбинаций как
0xxxxxxxxxx
00xxxxxxxxx
000xxxxxxxx
0000xxxxxxx
00000xxxxxx
000000xxxxx
0000000xxxx
00000000xxx
000000000xx
0000000000x
где нолями отмечены 0 попавшие в число из строки '0000000000'+Math.floor....
Роман, Да, и что.
Возьмем, для простоты, числа от 0 до 99. Дополнив лидирующим нулём до двух знаков получим записи от 00 до 99.
Посмотрим, сколько раз встречается каждая цифра в каждом разряде.
Разряд десятков:
0 - (00-09) - 10 раз
1 - (10-19) - 10 раз
...
9 - (90-99) - 10 раз
Разряд единиц:
0 - (00, 10, 20, 30, 40, 50, 60, 70, 80, 90) - 10 раз
1 - (01, 11, 21, 31, 41, 51, 61, 71, 81, 91) - 10 раз
...
9 - (09, 19, 29, 39, 49, 59, 69, 79, 89, 99) - 10 раз
Таким образом во всех разрядах цифры распределены равномерно.
Rsa97, хотя постойте:)
Ваш пример всего лишь показывает что случайные числа покрывают весь диапазон от 0 до 99. Но это не доказывает что они попадают в выборку с одинаковой частотой?
Rsa97, написал простую программку для подсчета числа повторений
// упростим алгоритм, теперь в нем будет 1 токен по 10 цифр
function rand() {
return ('00000000000'+Math.floor(Math.random()*10000000000)).substr(-10);
}
// число экспериментов
var count = 10000000;
// вычисляем частоту повторения чисел в первой позиции
var summ = [0,0,0,0,0,0,0,0,0,0];
for(i=0;i<count; i++){
let test = rand();
let num = parseInt(test[0]);
summ[num]++;
}
console.log("частота повторения:\n");
summ.forEach((n,i)=>{
console.log(i," - ",n);
});
отклонения в пределах десятитысячных долей (куда делись мои полтора процента?)))
2^256 это примерно 78 десятичных знаков
Берёте криптоалгоритм на 256 бит: можно AES, а можно и SHA256 (вам же не расшифровывать). Берёте инициализирующее значение - считаете значение - вот вам 256 почти случайных бит. Прибавляете к инициализирующему значению какое-либо другое - получаете следующее, и тд
