高速浮動小数点修飾子

Question

&bが浮動小数点の数値であり、mが負でない整数である場合、a^b mod mを計算しようとしています。簡単な解決策はO（n）時間かかるb乗算を行うことですが、私の数字は&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 

、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 

を持っていないということです。