Извлечение случайных «битов» из базы K из предварительно заполненного случайного буфера

Question

Скажем, мне нужно N криптографически безопасных псевдослучайных чисел в диапазоне [0, K). Наиболее очевидным способом достижения этого было бы N вызовов arc4random_uniform(3), и это именно то, что я делаю.

Однако профилировщик говорит мне, что многочисленные вызовы arc4random_uniform(3) занимают 2/3 всего времени выполнения, и мне действительно нужно ускорить мой код. Вот почему я планирую заранее сгенерировать несколько случайных байтов (возможно, с arc4random_buf(3)) и затем постепенно извлекать их из него.

Для K = 2 я могу просто замаскировать желаемый бит, но когда K не является степенью 2, все становится волосатым. Конечно, я могу использовать кучу %= и /=, но тогда у меня будет смещение по модулю. Другая проблема заключается в том, что когда N становится слишком большим, я больше не могу интерпретировать весь буфер как целое число и выполнять над ним арифметические операции.

Если это уместно, K будет меньше 20, тогда как N может быть действительно большим, например, миллионы.

Answer 1

Вы можете использовать оператор модуля и деление, вам просто нужно сделать немного дополнительной предварительной обработки. Создайте массив значений как обычно. Возьмите P как наибольшую степень K, меньшую или равную 2^32 (где ^ означает возведение в степень), и итерируйте по вашему массиву, убедившись, что все случайные значения строго меньше P. Любые, которые не являются, замените новым случайным числом, которое меньше P. Это удалит смещение.

Теперь для обработки больших N вам понадобится две петли. Первый цикл перебирает элементы массива, второй извлекает несколько случайных чисел из каждого элемента. Если P = k ^ e, то вы можете извлечь e случайные числа из [0, k) из каждого элемента в массиве. Каждый раз, когда вы извлекаете случайное число из элемента, делайте поэтапное деление на k для этого элемента.

Конечно, это не обязательно должны быть настоящие циклы. Вы можете хранить две переменные (индекс массива, индекс подэлемента) и извлекать их из элемента array_index при вызове функции. Если sub_element_index == e, сбросьте его на ноль и увеличьте array_index. Извлеките случайное число из этого элемента массива и вместо него верните его.