Эффективный способ выбрать индекс массива, используя, скажем, 64-битное случайное число?

Скажем, у меня есть uint64_t rand = <какое-то случайное число>, и массив символов [20] = .... Моя цель - выбрать элемент в множество исходя из содержания ранд.

1. Один медленный способ - использовать остаток: size_t i = ранд% 20 затем выберите элемент массив [я].
2. Другой способ, который Наверное быстрее, есть i = ранд/UINT64_MAX * 20. Или, чтобы избежать плавающих операций, его обратная часть 20/(UINT64_MAX/ранд).
3. Третий способ - использовать случайные биты для перехода к индексу, подобно дереву (но пропускает каждое 5-е число):

size_t total_bytes = 20;
маска size_t = 1;
размер_т я = 0;
в то время как (всего_байтов) {
  если (ранд и маска) i += total_bytes / 2; // переход вправо
  иначе я += 0; // левая ветвь
  маска <<= 1;
  всего_байт /= 2;
}

Есть ли более быстрый способ на обычном оборудовании? Например. ноутбуки/настольные ПК?

Причина, по которой меня это волнует: я реализую функцию вывода жесткого ключа памяти, и в какой-то момент мне нужно выбрать элемент массива на основе содержимого вычисленного зашифрованного текста. Случайное число составляет 64 бита.

Целевой язык — C.

ранд % 20 генерирует результат в $\{0,1,\ldots,18,19\}$ это Около униформа (при условии ранд является): $\Pr(19)/\Pr(0)=1-1/922337203685477581$. Часто это терпимая предвзятость.

На «ноутбуке/настольном ПК» с современным 64-битным процессором ранд % 20 является достаточно быстрым и обладает важными достоинствами, заключающимися в том, что он правильный, простой и легко адаптируемый. Однако, по крайней мере, часто (см. комментарий) можно быстрее использовать

(ранд-((ранд-(ранд>>2))>>1))>>59

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

Для интуиции того, как работает эта формула: для любого $x\in\mathbb R$ он держит $(x-(x-x\,2^{-2})\,2^{-1})\,2^{-59}=20\,x\,2^{-64}$, таким образом, мы по существу оцениваем, что выражения (uint64_t)пол(ранд*(20/(UINT64_MAX+1.))) или же (uint64_t)((ранд*(uint128_t)20)>>64) попытаться оценить. Обратите внимание, что для некоторых значений, включая Ранд = 0xCCCCCCCCCCCCCCCC более поздняя формула не совсем совпадает с формулой, которую я предлагаю; однако распределение, достигаемое обоими, является оптимально однородным.

Метод не ограничивается постоянным $м=20$ для размера массива. Он обобщается на любой постоянный $м$ с умеренным весом Хэмминга. Вычисление подходящего количества сдвигов из констант нетривиально. я имею в виду это чудесный ответ (примечание: последний счетчик смен, указанный там, должен быть увеличен на 32 в данном случае) для чего-то, что работает, но не всегда оптимально. У меня нет другой ссылки на метод, который я (повторно?) изобрел для ARM Cortex-M0, где он оказался полезным. На самом деле я только эмпирически нашел формулы для нескольких констант, соответствующих моим потребностям, и Андерс Касеорг берет на себя всю ответственность за то, как систематически генерировать формулы.

Если мы хотим потерять немного единообразия и уверенности в том, что код работает с постоянным временем, мы можем использовать

((ранд>>3)*5)>>59

что проще, скорее всего, быстрее и легче адаптировать к другим константам $м$ скорее, чем $20$: мы пишем $м$ как $г\,2^я$ с $я$ целое число и $г$ желательно нечетное, затем найдите целое число $j$ с $2^{j-1}\le r<2^j$. Мы используем ((ранд>>j)*r)>>(64+i-j). Проблема в том, что нижняя $j$ кусочки ранд не используются, а единообразие результата соответственно снижается (за исключением случаев, когда $м$ является степенью двойки).

Когда $м$ является $2^j$ для некоторого целого числа $j$, мы можем использовать ранд>>(64-j) или же ранд&(м-1). Последнее замечено в тот другой ответ. Эти методы не теряют единообразия, если все биты ранд единообразны и независимы.

Если $м$ изменяется во время выполнения с $м<2^j$ для некоторой известной постоянной $j$, мы можем использовать

((ранд>>j)*m)>>(64-j)

Однако $j$ младшие биты ранд теряются, и это снижает единообразие результата (за исключением случаев, когда $м$ является степенью двойки).

Не по теме:

• (uint64_t)(пол(ранд*(20/(UINT64_MAX+1.)))) было бы хорошо, если бы не было ошибки округления, но, поскольку они существуют, трудно сказать, может ли это дать 20 для некоторого ввода; также на многих компиляторах он не является оптимально однородным.
• (uint64_t)((ранд*(uint128_t)20)>>64) математически верен и очень близок к тому, что мы оцениваем, но uint128_t является необязательным и все еще незначительно поддерживаемым компонентом C.
• Вопросы ранд/UINT64_MAX * 20 выходы в $\{0,20\}$ таким образом непригоден. Проблемы заключаются в округлении деления до целого числа и (независимо) в том, что ранд возможно UINT64_MAX.
• Вопросы 20/(UINT64_MAX/ранд) выходы в $\{0,1,2,3,4,5,6,10,20\}$ и может вызвать деление на ноль, поэтому не годится. Проблемы заключаются в округлении деления до целого числа и (независимо) в том, что ранд возможно 0.
• Фрагмент кода вопроса 3 всегда имеет я% 5 != 4 на выходе, таким образом непригоден. Проблема в том, что вывод я построен как 10+5+2+1 с некоторыми удаленными терминами.

Обычно нужно стремиться сделать размер массива степенью 2. Тогда индекс можно вычислить с помощью побитового И:

массив символов [0x40];
uint64_t ранд;
...
char c = массив [rand & 0x3f];