希望你能帮助我;下面的代码:
#include <iostream>
#include <math.h>
using namespace std;
long int
cifra (long int b, long int e, long int n)
{
/* Calcula a tal que (b^e)=a MOD n. Algoritmo 3.1 de Allenby & Redfern,1989. */
long int a, i, q, r;
a = 1;
q = b / n;
r = b - q * n;
for (i = 1; i <= e; i++)
{
a = a * r;
q = a / n;
a = a - q * n; /* ou, de forma equivalente, a=mod(a,n) */
}
return a;
}
int
main ()
{
long int a, b, e, n;
b = 116104101;
e = 19661;
n = 383768051;
a = cifra (b, e, n);
cout << "a=" << a << endl;
return 0;
}
这应该会输出
a = 199324862
就像我使用在线C++编译器(https://www.onlinegdb.com/online_c++_compiler,它使用g ++)时一样。
但是:如果我使用MinGW64(在Windows 10上)在Code::Blocks上运行它,我会得到错误的结果:
a = 298405922
有什么想法吗?我做错什么了吗?
2条答案
按热度按时间trnvg8h31#
q * n
、a * r
、q * n
风险溢出。long
的宽度至少为32位,但全范围乘法需要2xlong
宽度的乘积。在某些平台上,它是64位的,因此在某些平台上测试值成功,在其他平台上测试值失败。或者:
1.使用更宽的类型进行中间计算。
long long
将满足OP的b = 116104101; e = 19661; n = 383768051;
测试用例,但对于b = 116104101<<32; e = 19661<<32; n = 383768051<<32;
,long long
仍然失败或
1.计算时要更加仔细。例如:Modular exponentiation without range restriction.
for (i = 1; i <= e; i++)
在e
较大的情况下 * 非常慢 *。研究Modular exponentiation。int64_t cifra(int64_t b, int64_t e, int64_t n)
在某些小的极端情况下不正确。cifra(b, 0, 1)
在应该返回0时返回1。示例修复OP的代码有限的范围。我去了 * unsigned * 类型的分析 * signed * 类型与负值是太乏味了。
可能有更多改进。
soat7uwm2#
看起来您假设
long int
是64位的(或更大)整数类型,但在特定环境中它实际上是32位类型。如果您需要特定大小的类型,则应使用int64_t
或uint64_t
等更显式的类型。此外,您可能希望使用余数运算符%
以完全避免使用q
变量。例如r = b % n
或仅b %= n
: