时间戳

首页 > 解决方案 > Python 的 pow() 函数和快速求幂给出了不同的答案

python - Python 的 pow() 函数和快速求幂给出了不同的答案

问题描述

对于 C 和 python 中的以下两种实现，我得到了不同的答案。在 Python 中

print(pow(15, 47413144071, 94826288143))

打印 1

但是在C

#include<stdio.h>
unsigned long Power(unsigned long A, unsigned long B, unsigned long X)
{
    unsigned long res = 1;
    while( B > 0 )
    {
        if( B & 1UL )
        {
            res = ( res * A ) % X;
        }
        A = ( A * A ) % X;
        B >>= 1UL;
    }
    return res;
}
int main()
{
    printf("%lu", Power(15, 47413144071, 94826288143));
    return 0;
}

打印：893231448 感谢任何帮助。

标签： pythoncperformancepowexponentiation

解决方案

这是一个证明，即使使用uint64_t类型，您的 C 代码也会产生溢出。

我刚刚将 C 代码转换为 Python，添加了溢出测试。第一个不能表示为 an 的值uint64_t是 2**64 或 0x10000000000000000 或 18446744073709551616。所以我在 mod 操作之前测试了所有产品：

def Power(A, B, X):
    res = 1
    step = 1
    while (B > 0):
        if B & 1:
            if (res * A) >= 0x1000000000000000:
                print("uint64_t overflow at res step", step)
            res = (res * A) % X
        if (A * A) >= 0x1000000000000000:
            print("uint64_t overflow at A step", step)
        A = (A * A) % X
        B >>= 1
        step += 1
    return res

>>> Power(15, 47413144071, 94826288143)
uint64_t overflow at A step 4
uint64_t overflow at A step 5
uint64_t overflow at A step 6
uint64_t overflow at A step 7
uint64_t overflow at A step 8
uint64_t overflow at A step 9
uint64_t overflow at res step 10
uint64_t overflow at A step 10
uint64_t overflow at A step 11
uint64_t overflow at res step 12
uint64_t overflow at A step 12
uint64_t overflow at A step 13
uint64_t overflow at res step 14
uint64_t overflow at A step 14
uint64_t overflow at A step 15
uint64_t overflow at A step 16
uint64_t overflow at res step 17
uint64_t overflow at A step 17
uint64_t overflow at res step 18
uint64_t overflow at A step 18
uint64_t overflow at A step 19
uint64_t overflow at res step 20
uint64_t overflow at A step 20
uint64_t overflow at A step 21
uint64_t overflow at A step 22
uint64_t overflow at A step 23
uint64_t overflow at A step 24
uint64_t overflow at A step 25
uint64_t overflow at res step 26
uint64_t overflow at A step 26
uint64_t overflow at A step 27
uint64_t overflow at res step 28
uint64_t overflow at A step 28
uint64_t overflow at A step 29
uint64_t overflow at A step 30
uint64_t overflow at A step 31
uint64_t overflow at A step 32
uint64_t overflow at res step 33
uint64_t overflow at A step 33
uint64_t overflow at res step 34
uint64_t overflow at A step 34
uint64_t overflow at A step 35
uint64_t overflow at res step 36
uint64_t overflow at A step 36
1

这绝对证明了算法是正确的（我们1最终得到），而且如果您尝试使用 64 位整数，您也会得到一些溢出。

长话短说，如果你需要在 C 中实现它，你需要一个具有uint128_t类型的系统，或者使用像gmplib这样的多精度库。

推荐阅读