0

a & b が浮動小数点数で、m が非負の整数である a^b mod m を計算しようとしています。簡単な解決策は、O(n) 時間かかる b 乗算を行うことですが、私の数値 a と b は大きくなる可能性があり (小数点の前に ~ 10 桁)、これを効率的に行いたいと考えています。a、b、および m が整数の場合、 Exponentiation_by_squaringを介して log(n) 時間で modpow をすばやく計算できます。

この方法 (または別の方法) を浮動小数点数に使用するにはどうすればよいですか? この計算を行うために Python を使用していますが、pow 関数では整数のみを使用できます。これは、10 進数で 2 乗して累乗を試みたのですが、答えが正しくありません。

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 に答える