Вопросы Теги

Узел: генерирует 6 цифр случайного числа, используя crypto.randomBytes

Попробуйте с очень простым регулярным выражением. 

^([-0][0-1][0-9][0-9][0-9])$|^([-0]20[0-4][0-9])$|^([-0]205[0-5])$

Визуальное представление

enter image description here [/g0]

Это очень просто понять.

  • группа 1 [-0][0-1][0-9][0-9][0-9] будет охватывать [-1999, 1999] значения
  • группа 2 [-0]20[0-4][0-9] будет охватывать [-2000, -2049] и [2000,2049] значения
  • группа 3 [-0]205[0-5] будут отображаться [-2050, -2055] и [2050, 2055] значения

String.format("%05d", number) делают очень хорошо

Пример кода: (Читайте встроенные комментарии для большей ясности.) 

int[] numbers = new int[] { -10002, -3000, -2056, -2055, -2000, -1999, -20, 
                            -1,  0, 1, 260, 1999, 2000, 2046, 2055, 2056, 2955, 
                             3000, 10002, 123456 };

//valid range -2055 to 2055 inclusive

Pattern p = Pattern.compile("^([-0][0-1][0-9][0-9][0-9])$|^([-0]20[0-4][0-9])$|^([-0]205[0-5])$");

for (int number : numbers) {
    String string = String.format("%05d", number);
    Matcher m = p.matcher(string);

    if (m.find()) {
        System.out.println(number + " is in range.");
    } else {
        System.out.println(number + " is not in range.");
    }
}

output: 

-10002 is not in range.
-3000 is not in range.
-2056 is not in range.
-2055 is in range.
-2000 is in range.
-1999 is in range.
-20 is in range.
-1 is in range.
0 is in range.
1 is in range.
260 is in range.
1999 is in range.
2000 is in range.
2046 is in range.
2055 is in range.
2056 is not in range.
2955 is not in range.
3000 is not in range.
10002 is not in range.
123456 is not in range.
2
задан wdetac 13 July 2018 в 12:40
поделиться

3 ответа

Существует несколько способов извлечения случайных чисел в диапазоне от случайных бит. Некоторые общие из них описаны в Специальная публикация NIST 800-90A, версия 1: Рекомендация для генерации случайных чисел с использованием детерминированных генераторов случайных битов

Хотя этот стандарт относится к детерминированным случайным битовым генерациям, существует полезное приложение под названием A.5 Преобразование случайных битов в случайное число, которое описывает три полезных метода.

Описанные методы:

  • A.5.1 Метод простой отбрасывания
  • A.5.2 Метод комплексного удаления
  • A.5.3 Простой модульный метод

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

Ваш алгоритм явно является версией метода Simple Discard, поэтому он прекрасен.

Конечно, вы должны использовать общий метод , который эффективен при любом значении N. В этом случае метод комплексного отказа или простой модульный метод следует рассматривать по методу «Simple Discard». Существуют и другие, более сложные алгоритмы, которые еще более эффективны, но в целом вы можете использовать любой из этих двух.

Обратите внимание, что часто бывает полезно сначала проверить, является ли N мощность из двух при генерации случайных значений в диапазоне [0, N). Если N является степенью двух, тогда нет необходимости использовать какие-либо из этих, возможно, дорогостоящих вычислений; просто используйте нужные вам биты из генератора случайных бит или байтов.

Я надеюсь добавить еще один, более эффективный метод, основанный на выборке отбраковки в будущем.

3
ответ дан Maarten Bodewes 17 August 2018 в 12:51
поделиться
  • 1
    Обратите внимание, что вам никогда не придется использовать hexadecimals в расчетах. Гексадецималы - это просто читаемые человеком представления бит и байтов. Все вычисления предпочтительно должны выполняться самими битами и байтами. – Maarten Bodewes 14 July 2018 в 12:29
  • 2
    Спасибо за отличную статью. В моем случае для метода комплексного отбрасывания 999999^1/(2^20-1) ~ 0.95, 999999^2/(2^40-1) ~ 0.91 ... так что наилучшим случаем остается t = 1`. Если я использую простой модульный метод, мне нужно будет использовать 70 бит для одного случайного числа !? Звучит намного менее эффективно! Можете ли вы еще больше объяснить поразрядный расчет? – wdetac 16 July 2018 в 04:20
  • 3
    Я знаю некоторый побитовый оператор, такой как shifts и логический and or, но как они связаны с алгоритмом? – wdetac 16 July 2018 в 04:25
  • 4
    В вашем случае вам повезло, и простой метод отбрасывания работает хорошо. Для других чисел может потребоваться регенерация для до 50% случаев, в частности от 0 до 2 ^ Х, где первый бит всегда должен быть 0. Этого особо неприятного можно избежать, просто взяв X - 1 бит. – Maarten Bodewes 16 July 2018 в 09:45

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

Поэтому вместо сравнения строк я бы использовал следующую целую операцию. 

if (random_bytes < 16700000) {
    return random_bytes = random_bytes - 100000 * Math.floor(random_bytes/100000);
}

около 99,54% шанса получить ответ от первых 3 байтов, в отличие от около 76% шансов на ваш подход.

2
ответ дан btilly 17 August 2018 в 12:51
поделиться
  • 1
    извините, не могу понять, можете ли вы объяснить больше? – wdetac 13 July 2018 в 16:45
  • 2
    @wdetac Упс, я ошибся. Согласно github.com/nodejs/node-v0.x-archive/issues/6372 он может блокировать, но он использует / dev / urandom под капотом, который блокируется только при запуске системы, а не / dev / random, где вы можете использовать энтропию быстрее, чем вы ее генерируете. Поэтому использование менее случайных байтов не является проблемой. Но если вы используете сильный криптографический источник на высокой скорости, вы хотите использовать каждую унцию случайности, которую вы можете. Так что сделайте догадки таким образом, когда вы сможете, если сможете. – btilly 13 July 2018 в 17:07
  • 3
    @MaartenBodewes Нет, на самом деле это отбраковка с низким коэффициентом отклонения. Следовательно, условие if. Нет предубеждений. – btilly 14 July 2018 в 15:51
  • 4
    Вы правы; представляет собой комплексный метод отбрасывания. Отсутствие петли омрачило мой разум. – Maarten Bodewes 14 July 2018 в 15:54

Это правильный алгоритм ( https://en.wikipedia.org/wiki/Rejection_sampling ), хотя вы можете рассмотреть возможность использования побитовых операций вместо преобразования в hex. Он может работать вечно, если генератор случайных чисел работает неправильно - вы можете попробовать попробовать фиксированное количество раз, а затем выбросить исключение, а не цикл навсегда.

3
ответ дан David Eisenstat 17 August 2018 в 12:51
поделиться
Другие вопросы по тегам:

Похожие вопросы: