Taking Modulo von Double NUmber

Question

Ich habe zwei Nummer a und b .Ich muss berechnen (a^b)%1000000007 .Wie kann ich für Gleitkommazahlen berechnen. Ex:

a= 7.654 and b=10000 

Hier ist mein Code wird % Arbeit:

public static double super_pow(double A , long B){ 

      double o=1; 

      while(B>0){ 

       if((B&1)!=0) o*=A; 

       A*=A; 
       B/=2; 
       o%=mod; 
       A%=mod; 
      } 

      return (o)%mod; 
    } 

Answer 1

Ist % Modulo?

Das hängt von der Sprache ab, die Sie verwenden. Aber im Allgemeinen Fließkommawerte weiß nicht Modulo-Operation. Sie können es selbst berechnen. Nehmen wir an, positive Gleitkommazahlen a=7.654 und b=10000.0 so

d = a/b = 0.0007654        // division 
r = d-floor(d) = (0.0007654-0.0) = 0.0007654  // remainder 
r = r*b = (0.0007654*10000.0) = 7.654    // rescale back 

• floor(x) Runden bis auf nächste weniger oder gleich Anzahl an x
• d hält das schwebende Divisionsergebnis
• r den Rest hält (Modulo)

Ein anderes Beispiel a=123.456 und b=65

d = a/b = 1.8993230769230769230769230769231 
r = (d-floor(d))*b = 58.456 

Dies kann für ganzzahlige und Dezimalwerte a,b verwendet werden, aber die Gleitkommaeinheit führt Runden und kann die Genauigkeit nach wenigen Stellen lose passen ... Wenn ich richtig 64-Bit-double Variablen sind in der Regel verwendbar erinnern maximal bis zu 18 Ziffern.

[Edit1] hmm reeditiert Sie die Frage ganz anderes Problem

So suchen Sie nach modpow. Sie können für Java-Implementierung von modpow googlen. Zum Beispiel hier

• Modular arithmetics and NTT (finite field DFT) optimizations

Sie können Mine Implementierung in C++ auf 32-Bit-Integer-Arithmetik aber mit statischen Modul prim mit spezifischen Eigenschaften finden. Dennoch, wenn Sie alle

if (DWORD(d)>=DWORD(p)) d-=p; 

zu d=d%p; ändern würde es für jeden Modulo arbeiten. Sie werden modpow,modmul,modadd,modsub benötigen.

Answer 2

Ja, in Java können Sie den Operator% für Fließkommatypen verwenden.

Sie Probleme mit dem Exponenten haben aber: Sie sind nicht % können die Zwischenergebnisse zu reduzieren, weil Modulo Gleitkomma-Multiplikation nicht verteilen über: (a*b)%c ist nicht (a%c)*(b%c). Wenn Sie versuchen, 7.654^10000 direkt zu berechnen, erhalten Sie infinity; es überschreitet den Maximalwert für double. Selbst wenn dies nicht der Fall wäre, könnten Sie den niedrigsten Ziffern des Ergebnisses nicht vertrauen, da sie reines Rauschen sind, das durch Rundungs- und Darstellungsfehler erzeugt wird.

Sie könnten eine Bibliothek verwenden, die exakte Arithmetik wie java.math.BigDecimal implementiert, aber das kostet viel Zeit und Arbeitsspeicher. Wenn Sie denken, dass Sie diese Berechnung als Teil eines größeren Problems durchführen müssen, sollten Sie wahrscheinlich einen Schritt zurückgehen und einen anderen Weg finden.

Edit: Hier ist das Ergebnis mit BigDecimal:

BigDecimal[] divmod = new BigDecimal("7.654").pow(10000) 
          .divideAndRemainder(new BigDecimal("1000000007")) 

return divmod[1].doubleValue() // I get 9.01287592373194E8 

Answer 3

in Java Sie die Modulo-Operation für Schwimmer/Doppel verwenden können (How do I use modulus for float/double?)

Wenn Sie berechnen müssen (a^b)% 1000000007 Sie können double für a und b (biggest integer that can be stored in a double) verwenden, dies macht die Potenzierung einfacher, verwenden Sie die pow() Verfahren (http://www.tutorialspoint.com/java/number_pow.htm)

import static java.lang.Math.pow; 

    public static double super_pow(double A , double B){ //returns long and B is also double 

     double pow; 
     double mod = 1000000007.0; 

     pow = Math.pow(A,B); 
     mod = pow % 1000000007; 
     return mod; 
} 

Alternativ können Sie typisieren (Genauigkeitsverlust möglich!) das Ergebnis a^b-long und dann

double pow = Math.pow(A,B); 
long mod = (long) pow%1000000007L; // the 'L' is important see https://stackoverflow.com/questions/5737616/what-is-the-modulo-operator-for-longs-in-java 
return mod; //return a long not double in function 

What is the modulo operator for longs in Java?