Делаем очень большой расчет

Я хочу вычислить значение

X =n!/2^r

where n<10^6 and r<10^6
and it's guarantee that value of X is between O to 10

Как вычислить X, так как я не могу просто разделить факториал и степень, так как они переполняют длинное целое число.

Мой подход
Делайте с помощью Modulus. Возьмем простое число больше 10, скажем, 101 

 X=  [(Factorial N%101)*inverse Modulo of(2^r)]%101;

Обратите внимание, что можно легко вычислить обратное значение по модулю, а также вычислить 2^r%101.

Проблема:
Не гарантируется, что X всегда будет целым числом, оно также может быть числом с плавающей запятой. Мой метод отлично работает, когда X является целым числом? Как поступить, когда X является числом с плавающей запятой


module algorithm numbers
person Narendra Modi    schedule 07.02.2017    source источник
comment
Как насчет чего-то вроде 3/2.0*4/2.0*5/2.0*...?   -  person barak manos    schedule 07.02.2017

Ответы (4)


arrow_upward
1
arrow_downward

Если приблизительные результаты в порядке, и у вас есть доступ к математической библиотеке с экспонентой по основанию 2 (exp2 в C), натуральной логарифмической гаммой (lgamma в C) и натуральным логарифмом (log в C), вы можете сделать

exp2(lgamma(n+1)/log(2) - r).
person David Eisenstat    schedule 07.02.2017

arrow_upward
0
arrow_downward

Найдите степень, в которой 2 появляется в n!. Это:

P = n / 2 + n / 2^2 + n / 2^3 + ...

Используйте целочисленное деление, пока не достигнете результата 0.

Если P >= r, то у вас целочисленный результат. Вы можете найти этот результат, вычислив факториал таким образом, чтобы игнорировать r степени 2. Что-то типа:

factorial = 1
for i = 2 to n:

    factor = i
    while factor % 2 == 0 and r != 0:
        factor /= 2
        r -= 1

    factorial *= factor

Если P < r, установить r = P, применить тот же алгоритм и в конце разделить результат на 2^(initial_r - P).

person IVlad    schedule 07.02.2017

arrow_upward
0
arrow_downward

За исключением очень немногих случаев (с малыми n и r) X не будет целым числом — ведь если n >= 11, то 11 делит n! но не делит никакую степень двойки, поэтому, если бы X был целым числом, оно должно было бы быть не менее 11.

Один из методов: инициализировать X единицей; затем цикл: если X > 10, делите на 2, пока не получится; если X ‹ 10 умножить на следующие множители, пока не получится; пока у вас не закончатся множители и степени двойки.

person dmuir    schedule 07.02.2017
comment
@Paul Вы можете уменьшить X до 10 или ниже, разделив на 2, как я уже сказал. Поскольку ответ os не больше 10, должно быть достаточно двойки. - person dmuir; 07.02.2017
comment
Ответ — значение с плавающей запятой ниже 10. И, как уже указывалось в моем комментарии, наивысшее n, такое, что X на каждом шаге будет сводиться к значению ниже 10, равно 4. Просто попробуйте ваш подход к 5!. - person Paul; 07.02.2017

arrow_upward
0
arrow_downward

Подход, который можно настроить для точности/производительности, будет следующим:

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

Всякий раз, когда целое число будет переполняться из-за умножения, сдвиньте его вправо на несколько позиций и вычтите это значение из r. В конце должно остаться небольшое число r и целое число v со старшими битами факториала. Это v теперь можно интерпретировать как число с фиксированной запятой с r дробными цифрами.

В зависимости от требуемой точности этот подход может работать даже с long, хотя у меня пока не было времени протестировать этот подход, если не считать небольшого эксперимента с калькулятором.

person Paul    schedule 07.02.2017