大数字阶乘模大素数 [英] Big number factorial modulo big prime number

问题描述

我需要计算一个很大的数的阶乘（小于= 1000000），我需要的结果模1000000007。 我写了下面的，但它会产生运行时（TEST.EXE已停止工作）中的错误。它仅适用于小的数字。

 很长很长的无符号模（很长很长的无符号NR）{
    返回NR％1000000007;
}

很长很长的无符号其实（很长很长的无符号NR）{
    如果（NR）返程模（NR *事实（NR  -  1））;
    否则返回1;
}
 

更新1：

 很长很长的无符号的事实（很长很长的无符号NR）{
    长长的无符号R = NR;
    而（ -  NR）{
        R =模（R * NR）;
    }
    返回ř;
}
 

解决方案

这是因为你的实现使用递归。对于小的数字，它工作正常，但对于大量溢出堆栈。

这行

 如果（NR）返程模（NR *事实（NR  -  1））;
 

创建 NR 堆栈帧。由于堆栈空间是非常有限的，在进入大量导致栈溢出。

更改您的实现用阶乘的迭代计算，以避免崩溃。

一旦完成修复崩溃，处理数字溢出。而不是计算阶乘已经计算后的模，保持施加模数在计算的每个步骤

I need to calculate the factorial of a big number (<=1.000.000) and I need the result modulo 1000000007. I wrote the following but it generates an error when run (test.exe has stopped working). It works only for small numbers.

long long unsigned modulo(long long unsigned nr){
    return nr % 1000000007;
}

long long unsigned fact(long long unsigned nr){
    if(nr)return modulo(nr * fact(nr - 1));
    else return 1;
}

UPDATE 1:

long long unsigned fact(long long unsigned nr){
    long long unsigned r = nr;
    while(--nr){
        r = modulo(r * nr);
    }
    return r;
}

解决方案

This is because your implementation uses recursion. For small numbers it works fine, but for large numbers it overflows the stack.

This line

if(nr)return modulo(nr * fact(nr - 1));

creates nr stack frames. Since the stack space is very limited, entering a large number causes stack overflows.

Change your implementation to use iterative calculation of the factorial to avoid the crash.

Once you are done fixing the crash, deal with the numeric overflow. Rather than computing the modulo after the factorial has been calculated, keep applying modulo at each step of the calculation.

这篇关于大数字阶乘模大素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！