0
      for(i=0; i<n+1; i++)
        {
            y=y+(a[i]*(int)Math.pow(j,i));
        }
        int r=y/786433;
        s[k]=y-(r*786433);
        k++;

Now in this code the j value can be 786432. So when I try to get modulus of a number say (1+2*(786432)^2+3*(786432)^3)%786433 then I get -521562 which is not correct I was using modulus operator before too but I got the same answer even with this approach I am getting the same answer. In this approach the modulus of the number is stored in array s[k]. Can anyone help?

Vladimir Vagaytsev
  • 2,871
  • 9
  • 33
  • 36
vidhit
  • 9
  • 1
  • 7
  • 786432 cubed isn't even that big. By the way you can use modular exponentiation to avoid ever having a big number. – harold Jul 04 '16 at 13:35
  • as a sidenode, that´s the remainder operator, and not the modulo operator. The remainder can return negative values if one value is negativ, wheras the mathematical modulo operator can´t do that. If you´d like to have the mathematical modulo use `Math#floorMod` – SomeJavaGuy Jul 04 '16 at 13:37
  • @harold but it is too big to store in an `int`. – Jesper Jul 04 '16 at 13:37
  • @Jesper well fits in a `long`, so even with explicit calculation no bigints are required – harold Jul 04 '16 at 15:33

1 Answers1

2

If you use Math.pow you are using a double types. Then you convert it back to an int. Rounding can happen and also truncating if values are too big.

To solve this problem You need to use BigInteger:

Immutable arbitrary-precision integers

In particular the method mod:

Returns a BigInteger whose value is (this mod m). This method differs from remainder in that it always returns a non-negative BigInteger.

Davide Lorenzo MARINO
  • 26,420
  • 4
  • 39
  • 56
  • thanks @davideLorenzoMarino the type casting was not required.Its giving positive answer as 2 – vidhit Jul 04 '16 at 14:24