相关疑难解决方法(0)

最近我在一次采访中被要求描述一种计算任意大数的阶乘的方法; 一种方法,我们获得答案的所有数字.

我搜索了不同的地方,并在几个论坛上询问.但我想知道是否有任何方法可以在不使用像GMP这样的库的情况下实现这一目标.

谢谢.

为了加快我的bignum除数,我需要加速y = x^2bigints的操作,bigints被表示为无符号DWORD的动态数组.要明确:

DWORD x[n+1] = { LSW, ......, MSW };

• 其中n + 1是使用的DWORD的数量
• 所以数量的价值 x = x[0]+x[1]<<32 + ... x[N]<<32*(n)

问题是:如何在y = x^2没有精度损失的情况下尽快计算？ - 使用C++和整数算术(32位带Carry)处理.

我目前的方法是应用乘法y = x*x并避免多次乘法.

例如:

x = x[0] + x[1]<<32 + ... x[n]<<32*(n)

为简单起见,让我重写一下:

x = x0+ x1 + x2 + ... + xn

其中index表示数组内的地址,因此:

y = x*x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)
y = x0*(x0 …

如何编写c ++程序来计算大因子.

例如,如果我想计算(100!)/(99!),我们知道答案是100,但如果我分别计算分子和分母的阶乘,那么这两个数字都是巨大的.

我有一个定点bignumber库,想要实现快速阶乘,没有精度损失.

在纸上做了一些数学技巧后,我得到了这个公式:

(4N)!=((2N)!).((2N)!).{ (2N+1).(2N+3).(2N+5)...(4N-1) }.(2^N)/(N!)

这已经非常快了,并且通过一些编程技巧,复杂性接近~ O(log(n)).

要清楚,我目前的实现是:

//---------------------------------------------------------------------------
longnum fact(const DWORD &x,longnum &h) // h return (x>>1)! to speed up computation
    {
    if (x==0) { h=1; return  1; }
    if (x==1) { h=1; return  1; }
    if (x==2) { h=1; return  2; }
    if (x==3) { h=1; return  6; }
    if (x==4) { h=2; return 24; }
    int N4,N2,N,i; longnum c,q;
    N=(x>>2);
    N2=N<<1;
    N4=N<<2;
    h=fact(N2,q);                                          // get 2N! and N!
    c=h*h; for (i=(N2+1)|1;i<=N4;i+=2) c*=i; c/=q;         // c= …