Taking Modulo of Double NUmber

问题:

I have given two number a and b.I have to Calculate (a^b)%1000000007.How Can i calculate for floating point numbers. Ex:

a= 7.654 and b=10000

Here is my Code will % work :

 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;
    }

回答1:

In java you can use the modulo operation for floats/doubles (How do I use modulus for float/double?)

If you have to calculate (a^b)%1000000007 you can use double for a and b (biggest integer that can be stored in a double), this makes exponentiation easier, use the pow() method (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;
}

Alternatively you can typecast (loss of precision possible !) the result of a^b to long and then use

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?

回答2:

Yes, in Java you can use the % operator on floating point types.

You will have problems with the exponent though: You can't use % to reduce the intermediate results because modulo does not distribute over floating point multiplication: (a*b)%c is not (a%c)*(b%c). If you try to compute 7.654^10000 directly you will get infinity; it exceeds the maximum value for double. Even if it didn't you couldn't trust the lowest digits of the result because they are pure noise created by rounding and representation error.

You could use a library that implements exact arithmetic, such as java.math.BigDecimal, but that will cost a lot in terms of execution time and memory. If you think you need to do this calculation as a part of a bigger problem, probably you should take a step back and find another way.

Edit: Here's the result with BigDecimal:

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

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

回答3:

Is % Modulo?

That depends on language you are using. But In general floating point values does not know modulo operation. You can compute it on your own. Let assume positive floating numbers a=7.654 and 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) rounds down to nearest less or equal number to x
• d holds the floating division result
• r holds the remainder (modulo)

Another example a=123.456 and b=65

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

This can be used for integer and decimal values of a,b but beware the floating point unit performs rounding and can loose precision after few digits... If I remember correctly 64 bit double variables are usually usable maximally up to 18 digits.

[Edit1] hmm you reedited the question to completely different problem

So you are searching for modpow. You can google for java implementation of modpow. For example here

• Modular arithmetics and NTT (finite field DFT) optimizations

You can find mine implementation in C++ on 32 bit integer arithmetics but with static modulo prime with specific properties. Still if you change all the

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

to d=d%p; it would work for any modulo. you will need modpow,modmul,modadd,modsub.