有困难的，当n变大的计算阶乘（N）模m， [英] Having difficulty in computing factorial(n) mod m, when n gets large

问题描述

我试图计算mod一个大素数大数阶乘。

改编[] 存储阶乘各种数字的值

如果我计算事实（32570）第一，然后打印改编[1] 和常用3 [2] ，则该作品。

如果我计算事实（32571）第一，然后打印改编[1] 和常用3 [2] ，那是行不通的。

然而，仅计算事实（32571）和

我真的无法调试此code。

另外，
计算事实（32572）独立不起作用。
但是，如果我计算事实（32572）找到后事实（32571）那么这工作好。

请告诉我怎么回事？

 的#define LL无符号很长很长
＃定义ULL无符号很长很长常量LL MOD = 1000000009;LL ARR [1048580]内嵌ULL mulMod（ULL一，ULL B，ULL C）
{
    如果（A＆LT; = 1000000000ULL和放大器;和B＆LT; = 1000000000ULL）
    {
        // COUT＆所述;≤（（一％C）*（B％c））的％℃下;＆下; ENDL;
        ULL RET =（（A％C）*（B％C））％C; //还赠送分段故障
        返回RET;
    }
    ULL RET = 0ULL; A = A％C;    而（B＆GT; 0ULL）
    {
        如果（B＆安培; 1ULL）RET =（（RET％C）+（A％C））％C;
        A =（A＆LT;＆LT; 1ULL）％C;
        B＆GT;＆GT; = 1ULL;
    }
    返回RET％C;
}LL事实（LL NUM）
{
    如果（ARR [NUM] == 0）
    {
        ARR [NUM] = mulMod（NUM，其实（NUM-1），MOD）; //给分段错误
        返回ARR [NUM]
    }    返回ARR [NUM]
}
诠释的main（）
{
    改编[0] = 1;
    //不起作用
    // COUT＆LT;＆LT;事实（32571）LT;＆LT; ENDL;
    // COUT＆所述;＆下;常用3 [1];＆下;＆所述;＆下;常用3 [2]＆下;＆下; ENDL;    //作品
    // COUT＆LT;＆LT;事实（325）LT;＆LT; ENDL;
    // COUT＆所述;＆下;常用3 [1];＆下;＆所述;＆下;常用3 [2]＆下;＆下; ENDL;    //也适用
    COUT＆LT;＆LT;事实（32571）LT;＆LT; ENDL;
}
 

解决方案

我的猜测是，你正在运行出栈。每（递归）调用其实（）推几个值到程序的堆栈（返回地址，保存由ABI规定的寄存器等）。栈的大小是固定的（根据您的操作系统，你可以或多或少轻易改变它;看到的ulimit 如果你使用的是Bourne外壳一样），所以最后，当你有很深的递归这样的，有一个一根稻草压死骆驼的背，当你调用一个更多的时间，没有栈左，你的程序有某种错误信息（如分割违反退出关于的Unix 的样OSS）。

由于特里斯坦正确评价以下时，迭代算法阶乘没有这个问题。

I am trying to compute factorial of large numbers mod a large prime number.

arr[] stores the value of the factorials for various numbers

If I calculate fact(32570) first and then print arr[1] and arr[2], then that works.

If I calculate fact(32571) first and then print arr[1] and arr[2], then that does not work.

However, calculating only fact(32571) works.

I really cannot debug this code.

Also, calculating fact(32572) independently does not work. But, if I calculate fact(32572) after finding fact(32571) then that works okay.

Whats going on here?

#define LL unsigned long long
#define ull unsigned long long

const LL mod=1000000009;

LL arr[1048580];

inline ull mulMod(ull a,ull b,ull c)
{
    if(a<=1000000000ULL && b<=1000000000ULL)
    {
        //cout<<((a%c)*(b%c))%c<<endl;
        ull ret = ((a%c)*(b%c))%c;         //also giving segmentation fault
        return ret;
    }
    ull ret = 0ULL; a=a%c;

    while(b > 0ULL)
    {
        if(b&1ULL) ret = ((ret%c)+(a%c))%c;
        a = (a<<1ULL)%c;
        b>>=1ULL;
    }
    return ret%c;
}

LL fact(LL num)
{
    if(arr[num]==0)
    {
        arr[num]=mulMod(num,fact(num-1),mod);    //gives segmentation fault
        return arr[num];
    }

    return arr[num];
}


int main()
{
    arr[0]=1;
    // does not work
    //    cout<<fact(32571)<<endl;
    //    cout<<arr[1]<<" "<<arr[2]<<endl;

    //works
    //    cout<<fact(325)<<endl;
    //    cout<<arr[1]<<" "<<arr[2]<<endl;

    //also works
    cout<<fact(32571)<<endl;
}

解决方案

My guess is that you're running out of stack. Every (recursive) call to fact() pushes a few values onto the program's stack (return address, saved registers mandated by ABI, etc.). The size of the stack is fixed (depending on your OS, you can change it more or less easily; see ulimit if you're using a Bourne-like shell), so eventually, when you have deep recursion like this, there is a "straw that breaks the camel's back", and when you call one more time, there's no stack left and your program exits with an error message of some kind (e.g. "Segmentation violation" on Unix-like OSs).

As Tristan correctly comments below, an iterative factorial algorithm does not have this problem.

这篇关于有困难的，当n变大的计算阶乘（N）模m，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！