Pow() function with parameters 13 and 30 failing

Question

I have just a little question: Why do I get the result of 25 if I calculat 13^30 mod 31 in java? The result should be 1. Thx for the answer in advance. p.s. I wrote the code on https://www.compilejava.net/

import java.lang.Math; 
public class HelloWorld
{
  public static void main(String[] args)
  {
    System.out.println(calculateModulo());

  }

  public static String calculateModulo(){

    String res = new String();

    for (int i = 1; i < 31; i++){   
      for (int j = 1; j < 31; j++){

          double var = Math.pow((double)i, (double)j);


         if (j == 30) {
            System.out.println("adding: "+i);
            res = res + "  " + i;
          } 
          if (var % 31 == 1) {
            System.out.println("The number " + i +" to the power of "+j +" modulo 31 results in "+var % 31);
            break;
          }

        }
    }
    System.out.println(Math.pow(13,30)+"         "+(Math.pow(13,30)%31)); // why is the output of this "2.619995643649945E33         25.0"
    return res;
  }
}

The number is too big to be stored exactly internally. So what you get is a rounded result here. You may try your luck with the `BigInteger` class or devise a more intelligent way to calculate the modulus of that number. — Sirko, Nov 29 '17 at 17:25
Perhaps look at @Jon Skeet post https://stackoverflow.com/questions/11317875/finding-really-big-power-of-a-number . If all else fails creating a simple function like pow that works with large numbers the way you want might be an idea. — SimperT, Nov 29 '17 at 17:47

score 1 · Answer 1 · answered Nov 29 '17 at 17:37

You are storing the results of these operations in doubles. Note that double is just 64 bytes long. It is not possible to store the result of 13³⁰ accurately in 64 bytes. And no, the compiler won't be able to calculate this with tricks either. See Is floating point math broken?

Try using BigInteger:

BigInteger a = new BigInteger("13");
BigInteger b = a.pow(30);
BigInteger c = b.mod(new BigInteger("31"));
System.out.println(c);

score 1 · Answer 2 · answered Nov 29 '17 at 17:40

The number you get after 13^30 is too big to hold in int or double so you have to use BigInteger for this. If you really want to calculate this than you can do something like this:

BigInteger bf = new BigInteger("13");
BigInteger bf1 = new BigInteger("30");
BigInteger bf2 = new BigInteger("31");
BigInteger p =bf.pow(30);
System.out.println(p.mod(bf2));

Pow() function with parameters 13 and 30 failing

2 Answers2