Как правильно реализовать алгоритм двоичного поиска, чтобы угадать случайный BigInteger в Java? - PullRequest
Новая
       15

Как правильно реализовать алгоритм двоичного поиска, чтобы угадать случайный BigInteger в Java?

0 голосов
/ 11 января 2019

Я пишу программу, которая должна угадывать случайно сгенерированный BigInteger из другой программы. Числовой класс дает обратную связь о том, было ли мое предположение выше или ниже числа («правильный», если ответ правильный). Хотя моя программа работает нормально и правильно угадывает BigInteger, мой алгоритм двоичного поиска, который я реализовал, работает менее эффективно, чем я ожидал. Я ломал голову и не могу понять, почему количество догадок (после того, как бит найден) превышает время log (n).

Я подсчитал количество догадок, и первая часть моего кода (которая находит правильный бит большого int) работает исключительно хорошо, обычно требуется всего несколько догадок. 

public static BigInteger guesser(Number n) {
    int guesses=0;

    String feedback = n.guess(BigInteger.ONE); 
    guesses++;

    if (feedback.equals("correct")){
        return BigInteger.ONE;

    } else{
        BigInteger two = new BigInteger("2");
        BigInteger max = two;
        BigInteger min = max;
        BigInteger mid;

        if(n.guess(max).equals("correct")) {
            return max;
        }

        while (!feedback.equals("lower")) {
            min = max;
            max = max.pow(2);
            feedback=n.guess(max); 
                    guesses++;
        }

        mid = min.add(max).divide(two);
        feedback = n.guess(mid); 
            guesses++;

        while (!feedback.equals("correct")){
            if (feedback.equals("higher")){
                min=mid.add(BigInteger.ONE);
            } else if (feedback.equals("lower")){
                max=mid.subtract(BigInteger.ONE);
            } 
            mid= min.add(max).divide(two);
            feedback = n.guess(mid); 
                guesses++;
        }
        return mid;
    }

Часть кода с бинарным алгоритмом поиска набирает огромное количество догадок, и я не могу понять, почему. Для 38119-битного BigInteger программа занимает примерно вдвое больше угадываний. Я делаю что-то в корне неправильно или есть простая ошибка, которую я пропускаю? Разве число догадок не должно быть примерно равно 2log (n)?

1 Ответ

0 голосов
/ 12 января 2019

Проблема в том, что вы идете слишком высоко с экспоненциальным поиском. Когда число достаточно большое, первое найденное число намного выше, чем должно быть.

Скажем, число, которое вы хотите угадать, равно 43263289412904812894021841098214912804215324, ищите верхний диапазон, применяя pow(2) первое число, которое вы наберете, это 115792089237316195423570985008687907853269984665640564039457584007913129639936 - это намного выше, так много попыток просто вернуться обратно в непосредственной близости.

Теперь предположим, что вместо этого вы применили multiply(new BigInteger("25")) - первое число, которое вы нажали, - 43368086899420177360298112034797668457031250. Да, требуется больше попыток, чтобы добраться до этого числа, но оно того стоит, в конце концов, потому что последний pow(2) на таком огромном числе создает такой большой излишек, что трудно вернуться. Я использовал здесь небольшое число, но с большими числами оно становится все хуже и хуже.

По-моему, вы должны найти баланс между применением умножения и умножением при поиске верхней границы. Может быть, если число достаточно велико, тогда прекратите возведение в степень и начните умножение на какое-то значение и сделайте это значение выше, когда граница становится выше.

Я использовал небольшое значение в моем примере выше, но с 38119 бит BigInteger:

  • pow(2) - верхняя граница 17 догадок - все догадки 65552
  • multiply(new BigInteger("25")) - верхняя граница 8209 догадок - все догадки 46327
  • multiply(new BigInteger("100")) - верхняя граница 5738 догадок - все догадки 43854
  • multiply(new BigInteger("1000")) - верхняя граница 3826 догадок - все догадки 41946
  • multiply(new BigInteger("10000")) - верхняя граница 2870 догадок - все догадки 40994
  • multiply(new BigInteger("50000")) - верхняя граница 2443 догадок - все догадки 40562
  • multiply(new BigInteger("100000")) - верхняя граница 2296 догадок - все догадки 40416

Требуется намного больше догадок, чтобы добраться до верхней границы, но тогда мы намного ближе к конечному значению, так что оно все еще стоит. Обратите внимание, что в какой-то момент он перестает быть ценным.

...