0

我正在计算 a^b mod m 其中 a & b 是浮点数，m 是非负整数。简单的解决方案是进行 b 乘法，这需要 O(n) 时间，但是我的数字 a 和 b 可能较大（小数点前约 10 位），我想有效地做到这一点。当 a,b 和 m 是整数时，我们可以通过以下方式在 log(n) 时间内快速计算 modpow：Exponentiation_by_squaring。

我如何将这种方法（或另一种方法）用于浮点数？我正在使用 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
4

1 回答 1

1

我认为一般来说没有一种简单的方法可以做到这一点，如果a并且b可以是 10 位数字（假设在小数点之前）。问题是对于 floatx和y，您不一定拥有该属性

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

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

于 2016-06-15T04:24:42.640 回答