Исключение Stackoverflow при тестировании Миллера Рабина - PullRequest
Новая
       0

Исключение Stackoverflow при тестировании Миллера Рабина

0 голосов
/ 05 декабря 2010

All

Я реализовал код, который генерирует 2 случайных простых числа, и умножение этих 2 чисел должно пройти тест на примитивность Миллера Рабина. Тем не менее, мой код все время зацикливается, пытаясь найти число, которое проходит тест Рабина Миллера и заканчивается исключением Stackoverflow. Вот код: 

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 исключение

Может кто-нибудь подсказать мне, как обойти эту проблему?

Ответы [ 3 ]

1 голос
/ 05 декабря 2010

Переместите вычисление 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 никогда не выполняется. Чтобы исправить это, вы можете добавить третье условие в цикл, чтобы убедиться, что оно завершается после фиксированного числа итераций.

1 голос
/ 05 декабря 2010 
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. Не используйте глобальные переменные. Это действительно плохой стиль.
1 голос
/ 05 декабря 2010

Пожалуйста, смотрите мой комментарий под вашим вопросом ... 

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