Where does my translation of this code into processing differ from the original?

Question

I have translated the prime testing code from this paper (here is a link to just the original code) into processing. When testing it I found it works for numbers below 10,000,000 but it skips some primes above that.

Here is my translation (except the table which is identical).

boolean is_SPRP(int n, int a) {
  int d = n-1, s = 0;
  while ((d&1)==0) { s++; d>>>=1; }
  long cur = 1, pw = Integer.toUnsignedLong(d);
  while (pw!=0) {
    if ((pw&1)!=0) { cur = Long.remainderUnsigned((cur*a), n); }
    a = int(Long.remainderUnsigned((long)a*a, n));
    pw >>>= 1;
  }
  if (Long.compareUnsigned(cur, 1)==0) { return(true); }
  for (int r=0; r<s; r++) {
    if (Long.compareUnsigned(cur, n-1)==0) { return(true); }
    cur = Long.remainderUnsigned((cur*cur), n);
  }
  return(false);
}
boolean isPrime(int x) {
  if (x==2 || x==3 || x==5 || x==7) { return(true); }
  if (x%2==0 || x%3==0 || x%5==0 || x%7==0) { return(false); }
  if (x<121) { return(x>1); }
  long h = x;
  h = ((h >>> 16) ^ h) * 0x45d9f3b;
  h = ((h >>> 16) ^ h) * 0x45d9f3b;
  h = ((h >>> 16) ^ h) & 255;
  return is_SPRP(x,bases[int(h)]);
}

EDIT: I have found the issue. Processing's int(long) converts to float and then to int which causes rounding errors. Using (int)long fixes the problem. Here is a working (and slightly optimized) version of the code.

int bases[]={15591,2018,166,7429,8064,16045,10503,4399,1949,1295,2776,3620,560,3128,5212,
2657,2300,2021,4652,1471,9336,4018,2398,20462,10277,8028,2213,6219,620,3763,4852,5012,3185,
1333,6227,5298,1074,2391,5113,7061,803,1269,3875,422,751,580,4729,10239,746,2951,556,2206,
3778,481,1522,3476,481,2487,3266,5633,488,3373,6441,3344,17,15105,1490,4154,2036,1882,1813,
467,3307,14042,6371,658,1005,903,737,1887,7447,1888,2848,1784,7559,3400,951,13969,4304,177,41,
19875,3110,13221,8726,571,7043,6943,1199,352,6435,165,1169,3315,978,233,3003,2562,2994,10587,
10030,2377,1902,5354,4447,1555,263,27027,2283,305,669,1912,601,6186,429,1930,14873,1784,1661,
524,3577,236,2360,6146,2850,55637,1753,4178,8466,222,2579,2743,2031,2226,2276,374,2132,813,
23788,1610,4422,5159,1725,3597,3366,14336,579,165,1375,10018,12616,9816,1371,536,1867,10864,
857,2206,5788,434,8085,17618,727,3639,1595,4944,2129,2029,8195,8344,6232,9183,8126,1870,3296,
7455,8947,25017,541,19115,368,566,5674,411,522,1027,8215,2050,6544,10049,614,774,2333,3007,
35201,4706,1152,1785,1028,1540,3743,493,4474,2521,26845,8354,864,18915,5465,2447,42,4511,
1660,166,1249,6259,2553,304,272,7286,73,6554,899,2816,5197,13330,7054,2818,3199,811,922,350,
7514,4452,3449,2663,4708,418,1621,1171,3471,88,11345,412,1559,194};

boolean is_SPRP(int n, int a) {
  int d = (n-1)>>>1, s = 1;
  while ((d&1)==0) { s++; d>>>=1; }
  long cur = 1;
  while (d!=0) {
    if ((d&1)!=0) { cur = Long.remainderUnsigned(cur*a, n); }
    a = (int)Long.remainderUnsigned((long)a*a, n);
    d >>>= 1;
  }
  if (cur==1) { return(true); }
  for (int r=0; r<s; r++) {
    if (cur==n-1) { return(true); }
    cur = Long.remainderUnsigned((cur*cur), n);
  }
  return(false);
}

boolean isPrime(int x) {
  if (x==2 || x==3 || x==5 || x==7) { return(true); }
  if (x%2==0 || x%3==0 || x%5==0 || x%7==0) { return(false); }
  if (x<121) { return(x>1); }
  long h = x;
  h = ((h >>> 16) ^ h) * 0x45d9f3b;
  h = ((h >>> 16) ^ h) * 0x45d9f3b;
  h = ((h >>> 16) ^ h) & 255;
  return is_SPRP(x,bases[(int)h]);
}

This version only works for signed integers. Modifying it simply like this for some reason causes the remainder operations to fail.

boolean is_SPRPUnsigned(int n, int a) { //broken (i think)
  int d = (n-1)>>>1, s = 1;
  while ((d&1)==0) { s++; d>>>=1; }
  long cur = 1;
  while (d!=0) {
    if ((d&1)!=0) { cur = Long.remainderUnsigned(cur*a, n); }
    a = (int)Long.remainderUnsigned((long)a*a, n);
    d >>>= 1;
  }
  if (cur==1) { return(true); }
  for (int r=0; r<s; r++) {
    if ((int)cur==n-1) { return(true); }
    cur = Long.remainderUnsigned((cur*cur), n);
  }
  return(false);
}

boolean isPrimeUnsigned(int x) { //not broken (i think)
  if (x==2 || x==3 || x==5 || x==7) { return(true); }
  if (Integer.remainderUnsigned(x, 2)==0 || Integer.remainderUnsigned(x, 3)==0 || Integer.remainderUnsigned(x, 5)==0 || Integer.remainderUnsigned(x, 7)==0) { return(false); }
  if (Integer.compareUnsigned(x, 121)<0) { return(Integer.compareUnsigned(x, 1)>0); }
  long h = Integer.toUnsignedLong(x);
  h = ((h >>> 16) ^ h) * 0x45d9f3b;
  h = ((h >>> 16) ^ h) * 0x45d9f3b;
  h = ((h >>> 16) ^ h) & 255;
  return is_SPRPUnsigned(x,bases[(int)h]);
}

However modifying it further like this fixes that.

boolean is_SPRPUnsigned(int n, int a) {
long ln=Integer.toUnsignedLong(n);
  int d = (n-1)>>>1, s = 1;
  while ((d&1)==0) { s++; d>>>=1; }
  long cur = 1;
  int debug=0;
  while (d!=0) { println(debug); debug++;
    long la=Integer.toUnsignedLong(a);
    if ((d&1)!=0) { cur = Long.remainderUnsigned(cur*la, ln); println("do"); }
    a = (int)Long.remainderUnsigned(la*la, ln);
    d >>>= 1;
    println(cur, a, Integer.toUnsignedString(a));
  }
  if (cur==1) { return(true); }
  for (int r=0; r<s; r++) {
    if ((int)cur==n-1) { return(true); }
    cur = Long.remainderUnsigned((cur*cur), ln);
  }
  return(false);
}

FINAL EDIT: I see now that the error with converting it to use unsigned ints was the in the multiplication. To multiply the int and the long the int must be converted to a long. The conversion is done automatically, but it assumes that it is a signed int. Converting manually prevent this from happening.

Answer 1

As @dxiv already pointed out, even though long is 64 bit, it's signed, so it's max value is 9,223,372,036,854,775,807 while uint64's max value is 18,446,744,073,709,551,615, therefore you won't get your expected result for large values.

You could try using BigInteger instead of long:

import java.math.BigInteger;

int bases[]={15591,2018,166,7429,8064,16045,10503,4399,1949,1295,2776,3620,560,3128,5212,
2657,2300,2021,4652,1471,9336,4018,2398,20462,10277,8028,2213,6219,620,3763,4852,5012,3185,
1333,6227,5298,1074,2391,5113,7061,803,1269,3875,422,751,580,4729,10239,746,2951,556,2206,
3778,481,1522,3476,481,2487,3266,5633,488,3373,6441,3344,17,15105,1490,4154,2036,1882,1813,
467,3307,14042,6371,658,1005,903,737,1887,7447,1888,2848,1784,7559,3400,951,13969,4304,177,41,
19875,3110,13221,8726,571,7043,6943,1199,352,6435,165,1169,3315,978,233,3003,2562,2994,10587,
10030,2377,1902,5354,4447,1555,263,27027,2283,305,669,1912,601,6186,429,1930,14873,1784,1661,
524,3577,236,2360,6146,2850,55637,1753,4178,8466,222,2579,2743,2031,2226,2276,374,2132,813,
23788,1610,4422,5159,1725,3597,3366,14336,579,165,1375,10018,12616,9816,1371,536,1867,10864,
857,2206,5788,434,8085,17618,727,3639,1595,4944,2129,2029,8195,8344,6232,9183,8126,1870,3296,
7455,8947,25017,541,19115,368,566,5674,411,522,1027,8215,2050,6544,10049,614,774,2333,3007,
35201,4706,1152,1785,1028,1540,3743,493,4474,2521,26845,8354,864,18915,5465,2447,42,4511,
1660,166,1249,6259,2553,304,272,7286,73,6554,899,2816,5197,13330,7054,2818,3199,811,922,350,
7514,4452,3449,2663,4708,418,1621,1171,3471,88,11345,412,1559,194};  

// 0x45d9f3b as BigInt
final BigInteger HEX_45d9f3b = new BigInteger(new byte[]{(byte)0x04,(byte)0x5d,(byte)0x9f,(byte)0x3b});
final BigInteger HEX_ff = new BigInteger("255");

boolean isSPRP(int n, int a) {
    int d = n-1, s = 0;
    while ((d & 1) == 0) {  
      ++s; 
      d >>= 1;  
    }
    //uint64_t cur = 1, pw = d;
    BigInteger cur = new BigInteger("1");
    BigInteger pw  = new BigInteger(""+d);
    BigInteger abi = new BigInteger(""+a);
    BigInteger nbi = new BigInteger(""+n);
    while (pw.intValue() > 0) { 
        if (pw.and(BigInteger.ONE).intValue() > 0){
          //cur = (cur*a) % n;
          cur = cur.multiply(abi).mod(nbi);
        }
        //a = ((uint64_t)a*a) % n;
        abi = abi.multiply(abi).mod(nbi);
        //pw >>= 1;
        pw = pw.shiftRight(1);
    }   
    if (cur == BigInteger.ONE) return true;
    for (int r=0; r < s; r++) {
        //if (cur == n-1) return true;
        if(cur.equals(nbi.subtract(BigInteger.ONE))){
          return true;
        }
        //cur = (cur*cur) % n;
        cur = cur.multiply(cur).mod(nbi);
    }
    return false;
}       
    
boolean isPrime(int x) { 
    if (x==2 || x==3 || x==5 || x==7) return true;
    if (x%2==0 || x%3==0 || x%5==0 || x%7==0) return false;
    if (x<121) return (x>1);
    BigInteger h = new BigInteger(""+x);
    //h = ((h >> 16) ^ h) * 0x45d9f3b;
    h = h.shiftRight(16).xor(h).multiply(HEX_45d9f3b);
    //h = ((h >> 16) ^ h) * 0x45d9f3b;
    h = h.shiftRight(16).xor(h).multiply(HEX_45d9f3b);
    //h = ((h >> 16) ^ h) & 255;
    h = h.shiftRight(16).xor(h).and(HEX_ff);
    return isSPRP(x,bases[h.intValue()]);
}   

Note that the above isn't thoroughly tested, so it might actually be buggy. Hopefully it illustrates using BigInt enough to move forward.

It's worth noting that BigInt has isProbablePrime(int) that could be useful.

Additionally, you could wrap the original code using JNI, leaving the implementation/data types intact, simply interfacing/bridging between C++ and Java.