Генерация случайного числа в заданном диапазоне из случайных байтов

Question

Есть похожие вопросы, но большинство из них слишком специфичные для языка. Я ищу общее решение. Учитывая некоторый способ получить k случайных байтов и число n, мне нужно получить случайное число в диапазоне 1...n (включительно).

Что я придумала до сих пор:

1. Чтобы определить количество байтов, необходимых для представления n, вычислите

f(n):=ceiling(ln(n)/8ln(2))=ceiling(0.180337*ln(n))

2. Получить случайное число в диапазоне в диапазоне 1...2^8f(n) для 0-индексированных байтов b[i]:

r:=0 for i=0 to k-1: r = r + b[i] * 2^(8*i) end for

3. Чтобы масштабировать до 1...n без смещения:

   R(n,r) := ceiling(n * (r / 256^f(n)))

Но я не уверен, что это не создает смещения или какой-то тонкой одноразовой ошибки. Не могли бы вы проверить, звучит ли это и / или внести предложения по улучшению? Это правильный способ сделать это?

В ответах, пожалуйста, предположите, что нет доступных модульных битовых операций, но вы можете принять произвольную арифметику точности. (Я программирую на схеме.)

Изменить: Определенно что-то не так с моим подходом, потому что в моих тестах бросок костей дал несколько случаев 0! Но где ошибка?

Answer 1

Это похоже на то, что вы сделали бы, если бы вы хотели сгенерировать число от 1 до n из случайного числа с плавающей запятой от 0 до 1 включительно. Если r это случайное число с плавающей точкой:

result = (r * n) + 1

Если у вас есть произвольная точность арифметики, вы можете вычислить r путем деления вашего k-байтового целого числа на максимальное значение, выражаемое в k байты + 1.

Так что если у вас есть 4 байта 87 6F BD 4A, а также n = 200:

((0x876FBd4A/0x100000000) * 200) + 1