algorithm - 进行非常大的计算

Question

我想计算值

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，因为我不能简单地除以阶乘项和幂项，因为它们会溢出长整数。

我的方法
在模数的帮助下做。取一个大于 10 的质数，比如 101

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

请注意，反模很容易计算，2^r%101 也可以计算。

问题:
不能保证X 始终是整数，它也可以是 float 。当 X 是整数时，我的方法可以正常工作吗？ X为 float 时如何处理

Answer 1

如果近似结果没问题，并且您可以访问具有 base-2 指数(exp2 in C)、自然对数 Gamma (lgamma in C)的数学库，和自然对数(log in C)，那么你可以做

exp2(lgamma(n+1)/log(2) - r).