如何在 c 中获取 (3623752876 * 3623752876) % 4294434817

Question

我实现了一个快速功率算法来执行操作 (x^y) % m。

由于m很大（4294434817），我用long long来存储结果。但是，long long在运行过程中似乎还是不够用。例如，(3623752876 * 3623752876) % 4294434817.

得到一个负数

有办法解决吗？

Answer 1

所有这三个常量都在 2³¹ 和 2³².

之间

类型unsigned long long保证能够存储至少2⁶⁴-1的值，超过乘积3623752876 * 3623752876。

所以只用unsigned long long来计算。 long long 足够宽以容纳单个常量，但不能容纳乘积。

您也可以使用 uint64_t，在 <stdint.h> 中定义。与 unsigned long long 不同，它保证正好 64 位宽。由于您实际上并不需要 64 位的精确宽度（128 位算术也可以），因此 uint_least64_t 或 uint_fast64_t 可能更合适。但是 unsigned long long 可以说更简单，在这种情况下它会正常工作。（uint64_t 不保证存在，但在任何 C99 或更高版本的实现中它几乎肯定会存在。）

对于较大的值（包括中间结果），您可能需要使用比 unsigned long long 更宽的值，这可能需要某种多精度算法。 GNU GMP 库是一种可能性。另一种是使用内置支持任意宽度整数运算的语言（例如 Python）。

Answer 2

这个答案是基于计算(x * x) % y虽然问题并不完全清楚。

使用 uint64_t 因为尽管 unsigned int 足够大以容纳操作数和结果，但它不会容纳乘积。

#include <stdio.h>
#include <stdint.h>

int main(void)
{
    unsigned x = 3623752876;
    unsigned m = 4294434817;
    uint64_t r;

    r = ((uint64_t)x * x) % m;
    printf("%u\n", (unsigned)r);
    return 0;
}

程序输出：

3896043471

Answer 3

我们可以利用模运算的力量来做这样的计算。两个数 a 和 b 的模数运算中乘法的基本属性状态：

(a*b)%m = ((a%m)*(b%m))%m

如果m适合long long int类型，那么上面的计算永远不会溢出。由于您正在尝试进行模幂运算，因此您可以阅读更多相关信息 here。

如何在 c 中获取 (3623752876 * 3623752876) % 4294434817

how to get (3623752876 * 3623752876) % 4294434817 in c

c

long-integer