快速浮点调制

Question

我希望计算a^b模m，其中a&b是浮点数，m是一个非负整数。平凡的解决办法是做b乘法，这需要O(n)时间，但是我的数字a&b可以大一些(小数点前10位)，我想要有效地做到这一点。当a、b和m是整数时，我们可以通过：平方在log(n)时间内快速计算modpow。

我将如何使用这种方法(或另一种)浮点数？我使用Python进行计算，而pow函数只允许整数。下面是我试图通过与十进制数相乘来进行幂运算的尝试，但答案并不正确：

from decimal import Decimal

EPS = Decimal("0.0001")

# a, b are Decimals and m is an integer
def deci_pow(a, b, m):
  if abs(b) < EPS:
    return Decimal(1)
  tmp = deci_pow(a, b / 2, m) % m # Should this be // ?
  if abs(b % 2) < EPS:
    return (tmp * tmp) % m
  else:
    if b > 0:
      return (a * tmp * tmp) % m
    else:
      return ((tmp * tmp)/a) % m

print(deci_pow(Decimal(2.4), Decimal(3.5), 5)) # != 1.416

当a，b，m都是整数时，这个方法就是这样的：

# a, b, m are Integers
def integer_pow(a, b, m):
  if b == 0: return 1
  tmp = integer_pow(a, b // 2, m) % m
  if b % 2 == 0:
    return (tmp * tmp) % m
  else:
    if b > 0:
      return (a * tmp * tmp) % m
    else:
      return ((tmp * tmp) / a) % m

Answer 1

一般来说，如果a和b可以是10位(假设小数点之前)，我不认为有一种简单的方法可以做到这一点。问题是，对于x和y，您不一定拥有这个属性

((x % m) * (y % m)) % m == (x * y) % m

如果您告诉我们您的具体上下文以及您为什么要这样做，可能还有其他可能的方法。