빠른 부동 소수점 모드

Question

&b가 부동 소수점이고 m이 음수가 아닌 정수 인^b mod m을 계산하려고합니다. 사소한 해결책은 O (n) 시간이 걸리는 b 곱셈을 수행하는 것입니다. 그러나 & b는 largish (소수점 이하 10 자리) 일 수 있으므로 효율적으로 처리하고 싶습니다. a, b 및 m이 정수인 경우 log (n) 시간에 modpow를 신속하게 계산할 수 있습니다 (Exponentiation_by_squaring).

부동 소수점 숫자에이 방법 (또는 다른 방법)을 어떻게 사용합니까? 나는이 계산을하기 위해 파이썬을 사용하고 있으며, pow 함수는 정수 만 허용합니다. 여기 진수 숫자의 제곱 지수를하고 나의 시도는, 그러나 대답은 바로 나오는되지 않습니다

# 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 

: A, B, m 모든 정수 경우

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 

이 메소드는 모습입니다

Answer 1

a 및 b이 10 자리 (소수점 이하로 가정) 일 수있는 경우 일반적으로이를 쉽게 수행 할 방법이 없다고 생각합니다. 문제는 당신이 우리에게 특정 상황을 말해 당신이이 일을하려는 이유, 다른 접근 가능한있을 수 있습니다 경우 수레 x 및 y을 위해, 당신은 반드시 재산을

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

이 없다는 것입니다.