二元供电给我一个错误的结果

-1

我的二进制供电功能有问题。包含结果的变量在执行乘法时溢出并给出错误结果。它发生在源值大于4,312,952,827时。那么我该如何解决这个问题呢？这是我的函数的代码。二元供电给我一个错误的结果

unsigned long long binpow(unsigned long long a, unsigned long long n, unsigned long long m) 
{ 
    unsigned long long res; 
    res=1; 
    while (n) 
    { 
     if (n & 1) 
     { 
      res=(res*a)%m; 
      n--; 
     } 
     a=(a*a)%m; 
     n >>= 1; 
    } 
    return res; 
}

来源

2016-05-31 Simon Rusinov

案例：'binpow（positive_a，0，1）'产生错误的答案'1'。可以从'unsigned long long res = 1LLU％m'开始来捕捉这种情况。 – chux

两者的残基和模量已超出一个unsigned long long的宽度（由m移位）。

你可以通过使用编译器扩展类型如unsigned __int128来解决问题，该类型生成4,312,952,827的正确结果。

unsigned __int128 binpow(unsigned __int128 a, unsigned __int128 n, unsigned __int128 m) 
{ 
    unsigned __int128 res; 
    res = 1; 
    while (n) 
     { 
      if (n & 1) 
       { 
        res = (res*a)%m; 
        n--; 
       } 
      a = (a*a) % m; 
      n >>= 1; 
     } 
    return res; 
}

另外，如果你想在一个安全的方式处理大量的工作，有喜欢gmplib

来源

2016-05-31 22:25:53

谢谢我的朋友，你的回答非常有帮助。实际上，我使用这个函数作为定义数字是否为素数的算法的一部分。所以这里的计算速度至关重要。我可以问你，图书馆会减慢计算速度吗？ –

表达a*a需要房间的两倍之多源的大小通用BIGNUM库。在你的场景4,312,952,827 > 2^32-1中，因此你不在unsigned long long的范围内。

实现模块化指数的二进制梯形图的经验法则是能够对至少是参数数据类型两倍的范围进行算术运算，因此在你的情况下它是128位的。

来源

2016-05-31 22:32:05

二元供电给我一个错误的结果

回答

相关问题