Как я могу получить диапазон, используемый при генерации случайного числа?

Question

Я генерирую случайные числа, используя начальное число в Java. Зная конечный результат 235 и начальный номер 532, как я могу получить номер intBound в Java? * 1001 например *

int randomNumber
int seed=532;
int intBound=800;
Random rand = Random(seed); 
randomNumber=rand.nextInt(intBound);

System.out.println("The generated Random number using the above seed and int bound is:- "+randomNumber);
//Results is: The generated Random number using the above seed and int bound is: 235

Упрощенная математическая версия вопроса: зная только два значения математической формулы, как вы производите третье значение? например, 1 + 2 = 3, что также означает, что если мы знаем только 2 значения и используемую формулу, мы можем легко получить третье значение, зная формулу, используемую при получении результата.

Answer 1

Вот экспериментальный метод нахождения скрытой границы. Получить копию случайного объекта и записать выходы из него. Создайте n экземпляров Random, где n - это макс. Int. Для каждого из этих Random экземпляров используйте свой индекс в качестве параметра для nextInt. Храните только экземпляры Random, которые придерживаются исходной последовательности. Продолжайте устранять кандидатов, пока не останется только один.

Рассмотрим следующую таблицу. Вверху мы называем столбцы с итерацией, в которой выбирается случайное значение. На стороне у нас есть последовательности с тем же начальным числом, к которым применены различные связанные значения. Значения в средних ячейках указывают случайное значение, полученное для данного случайного экземпляра и итерации.

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

public static void main(String [] args) throws Exception {
    final Scanner scanner = new Scanner(System.in);

    System.out.print("Please enter the seed number: ");
    final long seed = scanner.nextLong();
    System.out.print("Please enter the hidden bound: ");
    final int bound = scanner.nextInt();

    final long start = System.nanoTime();

    final IntSupplier original = rand(seed, bound);
    final int firstRandom = original.getAsInt();

    Map<Integer, IntSupplier> candidates = new HashMap<>();
    for (int i = 1; i < Integer.MAX_VALUE; i++) {
        final IntSupplier candidate = rand(seed, i);
        if (firstRandom == candidate.getAsInt()) {
            candidates.put(i, candidate);
        }
    }

    int iterations = 1;
    while (candidates.size() > 1) {
        iterations += 1;
        final int current = original.getAsInt();

        Map<Integer, IntSupplier> survivors = new HashMap<>();
        for (Map.Entry<Integer, IntSupplier> entry : candidates.entrySet()) {
            if (entry.getValue().getAsInt() == current) {
                survivors.put(entry.getKey(), entry.getValue());
            }
        }
        candidates = survivors;
    }

    if (candidates.size() == 1) {
        System.out.println("Upper bound is " + candidates.keySet().iterator().next());
    } else {
        System.out.println("No upper bound found");
    }
    System.out.println("Completed in " + iterations +  " iterations");

    final long end = System.nanoTime();
    System.out.println("Completed in " + (end - start) / Math.pow(10,9) + "seconds");
}

static IntSupplier rand(long seed, int bound) {
    final Random rand = new Random(seed);
    return () -> rand.nextInt(bound);
}

Это приводит к выводу:

Please enter the seed number: 532
Please enter the hidden bound: 800
Upper bound is 800
Completed in 4 iterations
Completed in 46.778499624 seconds

Answer 2

Это невозможно. Многие верхние границы могут давать одинаковый результат. Например, быстрый тест на Ideone показывает 9 возможных границ под 1000000, которые дали бы результат 235 с начальным значением 532 (а 800 не является одним из них): 237, 369, 711, 3239, 9717, 29151, 50549, 151647 и 454941.

import java.util.*;

class Test
{
    public static void main (String[] args) throws java.lang.Exception
    {
        List<Integer> bounds = new ArrayList<Integer>();
        for (int i = 1; i < 1000000; i++) {
            Random rng = new Random(532);
            if (rng.nextInt(i) == 235) {
                bounds.add(i);
            }
        }
        System.out.println(bounds);
    }
}

---

Лучшее, что вы можете сделать, это определить возможные границы. Реализация nextInt(int) - это , требуется , чтобы быть эквивалентным

 public int nextInt(int bound) {
   if (bound <= 0)
     throw new IllegalArgumentException("bound must be positive");

   if ((bound & -bound) == bound)  // i.e., bound is a power of 2
     return (int)((bound * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % bound;
   } while (bits - val + (bound-1) < 0);
   return val;
 }

Способы, с помощью которых этот алгоритм дает конкретный вывод, можно разделить на три возможности:

• bound является степенью двойки
• bound не является степенью двойки, и цикл завершается на первой итерации
• bound не является степенью двойки, и цикл продолжается после первой итерации

Кейсы с степенью двойки bound очень просты - просто попробуйте все кавычки bound с степенью двойки, которые подходят к int. Их всего 31. Вы можете оптимизировать это, но в этом нет особого смысла.

Случаи первой итерации без степеней двух можно обработать, вычислив значение, которое было бы next(31) (что можно сделать, заполнив экземпляр Random и вызвав next(31)), и увидев какие значения bound дадут правильное значение val и прекратят работу.

Чтобы получить правильное значение val, bound должен быть в bits - val больше, чем val. (Иногда bits - val будет 0, и любое целое число больше, чем val пройдет.) Чтобы завершить задание, bits - val + (bound-1) не должно переполняться. Таким образом, возможные границы, которые попадают в этот случай, представляют собой факторы bits - val в пределах определенного диапазона, которые не являются степенями двух.

Что касается финального случая, мне не хочется проходить через него, так что это будет «оставлено в качестве упражнения для читателя». (Это самый сложный случай с такими трудностями, как выяснение того, какие значения bound вызовут переполнение, если вы не знаете val, и это займет больше времени, чем у меня.)