如何修复模幂运算的实现？

Question

所以我一直在尝试实现高效的模幂运算。这是我试过的：

def mypow(x, y, z):
    return x**(y % log(z, x))

然而，结果有点奇怪，我的测试用例：

z = 100
x = 2
for y in range(100):
    print(mypow(x, y, z), pow(x, y, mod=z))

结果：

1.0 1
2.0 2
4.0 4
8.0 8
16.0 16
32.0 32
64.0 64
1.2799999999999996 28
2.559999999999999 56
5.119999999999998 12
10.239999999999997 24
20.479999999999993 48
40.95999999999999 96
81.91999999999997 92
1.6383999999999987 84

这个程序明显有问题，但是正确的解好像就在几位数之后。例如，虽然 1.2799999999999996 != 28, 27.9999... ~= 28.

我试过几个不同的x、y、z，似乎是一个相当一致的模式。虽然对该程序存在缺陷感到失望。这种模式非常有趣，我想知道这里可能是什么原因。

Answer 1

题目中的公式，

x ** (y % log(z, x))

可以重写

x ** (y - k*log(z, x))

其中 k 是 y 除以 log(z, x)) 的整数结果。

这可以进一步重写为

(x**y) / (x**(k*log(z, x)) = (x**y) / (x**ln(z, x))**k

简直就是

x**y / z**k

之所以出现这种模式是因为z = 100：x**y % 100是x**y的最后两位组成的数，而这最后两位也出现在除法的末尾x**y 乘以 100**k，这是 10 的幂。

（例如，123456 % 100 = 56，和 123456 / 100**2 = 12.3456）

因此，如果 z 不是 10 的幂，则根本没有可观察的模式。

如何修复模幂运算的实现？

How can I fix my implementation of modulo exponentiation?

python

math

floating-point

logarithm

modulo