mercredi 15 juin 2016

Fast floating point modpow

I am looking to compute a^b mod m where a & b are floating point numbers and m is an non-negative integer. The trivial solution is to do b multiplications which takes O(n) time, however my numbers a & b can be largish (~10 digits before the decimal point) and I would like to do this efficiently. When a,b and m are integers we can compute the modpow quickly in log(n) time via: Exponentiation_by_squaring.

How would I use this method (or another) for floating point numbers? I am using Python to do this computation and the pow function only allows integers. Here is my attempt at doing exponentiation by squaring with Decimal numbers, but the answer is not coming out right:

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

When a,b,m are all integers this is what the method looks like:

# 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

Aucun commentaire:

Enregistrer un commentaire