Как определить, сколько битов должен занимать результат факториала в виде числа?

В результате функция факториала может возвращать очень большое число.

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

Например, факториал (5) = 5 * 4 * 3 * 2 = 120.

Число 120 будет 120 = 0b1111000, где 0b указывает, что это двоичное число. По крайней мере, мне нужно 7 бит для представления результата и вероятности, которую я хотел бы уместить в 8 бит, чтобы он был байтом.


factorial
person Phil    schedule 27.11.2012    source источник

Ответы (1)


arrow_upward
4
arrow_downward

вам нужно вычислить log2(factorial(N)), округлив до следующего большего числа, чтобы получить количество битов, необходимое для представления результата. если вы не уверены, можете ли вы вычислить или представить результат факториала с вашей текущей настройкой, вы можете попытаться вычислить сумму log2(i) для всех i в диапазоне от 2 до N включительно (включая 2 и N, то есть).

в качестве примера рассчитаем количество бит для factorial(5):

log2(120) = 6.906, rounded up become 7 (bits)

иначе,

log2(2) + log2(3) + log2(4) + log2(5) = 6.906, which gives same result
person lenik    schedule 27.11.2012