测试Miller Rabin时的Stackoverflow异常

Question

全,

我已经实现了一个产生2个随机素数的代码，这两个数字的乘法应该通过Miller Rabin素数检验。但是，我的代码一直在循环，试图找到一个通过Miller rabin测试并以堆栈溢出异常结束的数字。以下是代码：

private void populateRandomPrimes()
{
    onePrimeValue = RandomPrime.getValue();

    do
    {
        secondPrimeValue= RandomPrime.getValue();
    }while(onePrimeValue == secondPrimeValue);

    BigInteger calcNum = new BigInteger(Integer.toString(onePrimeValue*secondPrimeValue));

    try
    {
        **if (calcNum.isProbablePrime(20))**
            populateMultiplicativeForPlayer();
        else
            populateRandomPrimes();
    }
    catch (Exception io)
    {
        io.printStackTrace();
    }
}

在上述守则中：

1> RandomPrime类返回一个随机素数数

2> onePrimeValue和secondPrimeValue都应该是不同的

3>由于代码行：if (calcNum.isProbablePrime(20))从不返回true，所以在得到Stackoverflow异常之前，我将调用相同的

有人能建议我如何处理这个问题吗？

Answer 1

请看我对你问题的评论..。

private void populateRandomPrimes()
{
    while (true){
      onePrimeValue = RandomPrime.getValue();

      do
      {
          secondPrimeValue= RandomPrime.getValue();
      }while(onePrimeValue == secondPrimeValue);

      BigInteger calcNum = new BigInteger(Integer.toString(onePrimeValue*secondPrimeValue));

      try
      {
          if (calcNum.isProbablePrime(20)){
              populateMultiplicativeForPlayer();
              return;
          }
      }
      catch (Exception io)
      {
          io.printStackTrace();
      }
    }
}

Answer 2

将calcNum计算移到do-while循环中，并添加一个额外的条件：

private void populateRandomPrimes()
{
    onePrimeValue = RandomPrime.getValue();
    BigInteger calcNum = null;
    do {
        secondPrimeValue= RandomPrime.getValue();
        calcNum = new BigInteger(Integer.toString(onePrimeValue*secondPrimeValue));
    } while(onePrimeValue.equals(secondPrimeValue) && !(calcNum.isProbablePrime(20));

    //if you get here, calcNum isProbPrime, so no need to check again
    try {
        populateMultiplicativeForPlayer();
    } catch (Exception ex) {
        ex.printStackTrace();
    }
}

您遇到这个问题是因为您没有确定的递归的大小写。另外，除非您知道自己在做什么，否则不要在对象上使用==。您的并发条件应该使用.equals()比较onePrimeValue和secondPimeValue。

这种方法的最坏情况是，您的程序将被卡在无限回路中，因为do-while循环的退出条件永远无法满足。为了弥补这一点，您可以向循环中添加第三个条件，以确保它在一定次数的迭代之后终止。

Answer 3

private BigInteger generateAppropriateNumber() {
    BigInteger result;
    boolean isOk = false;
    while (isOk == false) {
        onePrimeValue = RandomPrime.getValue();
        do {
            secondPrimeValue= RandomPrime.getValue();
        } while(onePrimeValue.equals(secondPrimeValue));
        BigInteger result = 
              new BigInteger(Integer.toString(onePrimeValue * secondPrimeValue));
        if (result.isProbablePrime(20)) {
            isOk = true;
        }            
    }
    return result;
}

private void populateRandomPrimes() {
    populateMultiplicativeForPlayer(generateAppropriateNumber());
}

也就是说。

1. 使用循环而不是递归来避免堆栈增加。
2. 不要使用全局变量。这是非常糟糕的风格。