c++ - C++ - fmod 返回错误的答案

Question

首先，我正在为学校做这个项目，我们不允许使用外部库，因此我不能使用像 GMP 这样的东西。问题是，我有一个需要一些“艰难”计算的函数。IE，

m^e mod n

这是我的代码

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int e = 17, n = 3233, m = 65;
    long double p, mod;

    p = pow(m, e); // Gives 6.59974e+30 which is correct

    mod = fmodl(p, n);

    cout<<mod; // Gives 887, When the correct answer is 2790

    return 0;
}

如您所见，fmod (fmodl) 函数没有返回正确的值，是否有解决方法？再次，不使用任何外部库。

Answer 1

您可以编写自己的模幂函数。

int modpow(int a,int b,int mod)
{
    int product,pseq;
    product=1;
    pseq=a%mod;
    while(b>0)
    {
        if(b&1)
            product=(product*pseq)%mod;
        pseq=(pseq*pseq)%mod;
        b>>=1
    }
    return product;
}

请参阅http://en.wikipedia.org/wiki/Modular_exponentiation以获得解释

Answer 2

使用这种简单的方法，您的代码正在尽其所能。x86 机器上的Along double只有 80 位长，其中有很多位专用于指数和符号。

65 ¹⁷的确切值约为 103 位长。因此，您遇到了截断错误。要进行这种大的乘法和模数运算，您需要更加了解如何进行幂运算和模数运算。