问题：

我将此代码翻译成处理与原始代码有何不同？

佟翰林

2023-03-14

我已经将本文中的主要测试代码（此处是原始代码的链接）转换为处理。在测试它时，我发现它适用于低于10，000，000的数字，但它跳过了一些高于该数字的素数。

这是我的翻译(除了表格是相同的)。

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

编辑：我发现了问题。处理的int（long）转换为浮点数，然后转换为int，这会导致舍入错误。使用（int）long修复了问题。这是代码的工作（并且稍微优化）版本。

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

此版本仅适用于有符号整数。由于某种原因简单地修改它会导致其余操作失败。

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

然而，像这样进一步修改它可以修复这个问题。

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

最终编辑：我现在看到将其转换为使用无符号整数的错误是乘法中的错误。要将int和long相乘，必须将int转换为long。转换是自动完成的，但它假设它是一个有符号的int。手动转换可防止这种情况发生。

共有1个答案

羊昊苍

2023-03-14

正如@dxiv已经指出的，尽管< code>long是64位的，但它是有符号的，因此它的最大值是9，223，372，036，854，775，807，而< code>uint64的最大值是18，446，744，073，709，551，615，因此您不会得到大值的预期结果。

您可以尝试使用BigInteger而不是< code>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()]);
}

请注意，上述内容尚未经过全面测试，因此实际上可能存在错误。希望它能说明使用BigInt足以向前发展。

值得注意的是，BigInt具有可能是有用的概率优先级（int）。

此外，您可以使用JNI包装原始代码，保持实现/数据类型不变，只需在C和Java之间进行接口/桥接。

类似资料：

Gradle:如何将一些groovy代码翻译成kotlin

下面的groovy代码在脚本构建中运行良好。格拉德尔：我不能成功地将它的语法翻译成kotlin build.gradle.kts。有人能给我正确的翻译吗？
如何将下面的代码翻译成英特尔汇编代码（x86）？[复制]

我试图翻译成x86汇编，以帮助我更好地理解在x86汇编中编码的概念，我觉得自己被困在了如何开始编写这段代码上。
使用socket.io将服务器代码翻译成ES6

我们完全是socket.io和表达的新手。我们遵循这个教程来学习socket.iohttps://www.valentinog.com/blog/socket-react/ 现在我们要翻译这行代码（旧样式）： const index = require("。/routes/index”)。系统默认值到 ES6，如下所示：从“./routes/index”导入路由器 app.use('/'，路由
短代码的WordPress SDL翻译

我有某种短代码，如。我想从中提取这个短代码，然后将这两个属性：和发送到SDL World Server进行翻译。从SDL得到响应后，我想相应地替换那个短代码。有什么建议或帮助吗？
如何使此异常处理代码符合DRY原则？

我有一个特殊的情况，我需要捕获异常并将一个对象返回给客户端来代替异常。我不能将异常处理逻辑放在更高的级别，即将 Foo 包装在 try 子句中。最好用一些样本代码来演示。异常处理逻辑模糊了方法的意图，如果我有，许多相似意图的方法，在Foo类中，我发现自己重复了大部分catch逻辑。在下面的代码中包装常见异常功能的最佳技术是什么？
将预处理的代码映射到源代码

在你的代码合并，压缩或编译后，保持客户端代码可读性和可调试性。使用Source Maps(源码映射)将源代码映射到已编译的代码。 TL;DR 使用Source Maps(源码映射)将压缩代码映射到源代码。然后，您可以在其原始源代码中读取和调试编译的代码。仅使用能够生成Source Maps(源码映射)的预处理器。验证您的web 服务器是否可以为Source Maps(源码映射)提供服务。开始

我将此代码翻译成处理与原始代码有何不同？

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档