B00007 快速模幂运算的两个C语言程序

2019-04-13 14:49发布

站内文章 / 模拟电子
17018 0 1328
代码来自维基百科的Modular arithmetic。 这两段代码都不是大整数计算的程序，是2进制64整数的计算程序，数据不能大于2进制63位。两段代码分别如下：
 uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) { uint64_t d = 0, mp2 = m >> 1; int i; if (a >= m) a %= m; if (b >= m) b %= m; for (i = 0; i < 64; ++i) { d = (d > mp2) ? (d << 1) - m : d << 1; if (a & 0x8000000000000000ULL) d += b; if (d > m) d -= m; a <<= 1; } return d; } uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) { long double x; uint64_t c; int64_t r; if (a >= m) a %= m; if (b >= m) b %= m; x = a; c = x * b / m; r = (int64_t)(a * b - c * m) % (int64_t)m; return r < 0 ? r + m : r; }

热门文章