Modpow à virgule flottante rapide

Question

Je cherche à calculer un^b mod m où & b sont nombre à virgule flottante et m est un nombre entier non négatif. La solution triviale est de faire des multiplications b qui prennent du temps O (n), cependant mes nombres a & b peuvent être plus gros (~ 10 chiffres avant la virgule décimale) et je voudrais le faire efficacement. Lorsque a, b et m sont des entiers, nous pouvons calculer rapidement le modpow en log (n) via: Exponentiation_by_squaring.

Comment utiliser cette méthode (ou une autre méthode) pour les nombres à virgule flottante? J'utilise Python pour faire ce calcul et la fonction pow permet uniquement les entiers. Voici ma tentative de faire exponentiation en élevant au carré avec des nombres décimaux, mais la réponse ne vient pas à droite:

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 

Quand a, b, m sont tous les entiers c'est ce que la méthode ressemble à:

# 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

Je ne pense pas qu'il existe un moyen facile de le faire en général, si a et b peut être de 10 chiffres (en supposant avant la virgule décimale). Le problème est que pour les flotteurs x et y, vous ne devez pas nécessairement la propriété

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

Si vous nous dites à votre contexte et pourquoi vous voulez faire cela, il pourrait y avoir d'autres approches possibles.