Почему происходит зацикливание?

[Arigato]

Необходимо оценить, за сколько шагов программы возможно подобрать 10 -значное число методом тыка (рандомом).

Для начала реализовал код для 9-значного числа:

const
  A1 = 12345;
  A2 = 6789;

var R1, R2: LongWord;
    c: Int64;

begin
  Randomize;
  c := 0;
  repeat
    R1 := Random (100000);
    R2 := Random (10000);
    Inc (c);
  until (R1 = A1) and (R2 = A2);
  WriteLn (R1, R2, ' - ', c);
  ReadLn;
end.

Число 123456789, так как оно большое, я разбил его на две половинки (это никак не должно сказаться на качестве работы алгоритма). Оцениваем число итераций цикла. Запустил, получил следующее: "123456789 - 1478009974", программа задумалась секунд на 10. В принципе все верно, получили то самое число чистым рандомом, количество итераций лежит в пределах ожидаемых значение (500 000 000 - 2 000 000 000).

Теперь переходим к 10-значному числу, код меняется не сильно:

const
  A1 = 12345;
  A2 = 67890;

var R1, R2: LongWord;
    c: Int64;

begin
  Randomize;
  c := 0;
  repeat
    R1 := Random (100000);
    R2 := Random (100000);
    Inc (c);
  until (R1 = A1) and (R2 = A2);
  WriteLn (R1, R2, ' - ', c);
  ReadLn;
end.

Теоретически ожидаешь, что программа должна работать примерно в 10 раз дольше. Но она зацикливается навечно (во всяком случае, я за вечер не дождался ответа). Хочется понять хитрость, в чем же дело? Очевидно, что дело не в Теории вероятности, ведь добавив еще одну цифру мы должны увеличить количество итераций на порядок, то есть в пределах 5 000 000 000 - 20 000 000 000.

Так в чем же причина зацикливания?

[Человек_Борща]

Так в чем же причина зацикливания?

Я бы применил теорию вероятности.... нежели практику.

Ответ лежит в недрах Random'а:
Randomize генерирует не случайное число на основе процессорного такта gettickcount либо на основе QueryPerformanceCounter в RandSeed.

Сам же Random имеет вид:

var
  Temp: Longint;
begin
  Temp := RandSeed * $08088405 + 1;
  RandSeed := Temp;
  Result := (UInt64(Cardinal(ARange)) * UInt64(Cardinal(Temp))) shr 32;

Из этого делаем вывод, что чем больше Random'ов мы вызываем тем больше RandSeed, а чем больше RandSeed тем мизернее шанс вляпаться хотя бы в предыдущее число, не говоря уже а каких-то мелких статических числах.

В вашем случае это технически и через 24 часа не возможно будет.

К слову, в Math есть более интересные варианты Random'a. Например RandomRange.


Ещё бы попробовал в каждой итерации сбор статистики максимального приближения к желаемому результату(в %) в течении X времени.

[Arigato]

Я тоже примерно так думал, что дело в реализации генератора псевдослучайных чисел. Но ведь что интересно, R1 := Random (100000) есть и в первом варианте, он ведь прокатывает. Причем не важно, какое именно число мы хотим подобрать. Была идея, что комбинация 1234567890 вообще никогда не выпадает, но и любая другая комбинация из 10 цифр (2 по 5) не выпадает, а комбинации из 9 цифр (5 и 4) выпадают. Загадка!

[Человек_Борща]

Постоянные вещи так или иначе соприкасаются.
Не думаю что это загадочно. Перегрузите стандартный рандом своим, и делайте сдвиг вправо на случайное кол-во бит, а константу $08088405 так же сделайте случайной.

Это наверняка уменьшит шанс выпадения

а комбинации из 9 цифр (5 и 4) выпадают.

[Arigato]

Надо так полагать, что особенность реализации функции Random не позволяет выпасть 2 раза подряд заданной комбинации из 5 цифр. Некоторые комбинации все же выпадают, например:

A1 = 12345;
A2 = 87142;

И много других (их легко найти). Но, получается, что не все сочетания A1 и A2 могут совпасть, если они по 5 знаков, то есть такие значения, которые никогда не выпадают одно за другим.

[Человек_Борща]

Я предположил, что это связано с константой и постоянным сдвигом на 32 бита.
Попробуйте написать свой аналог Random'а.

[s-andriano]

Сообщение от Arigato

Теоретически ожидаешь, что программа должна работать примерно в 10 раз дольше. Но она зацикливается навечно

Теоретически, если бы Вы использовали ДСЧ, так и было бы. Воэможно, если бы Вы использовали два независимых ДПСЧ, то можно было бы ожидать, что время окажется конечным, но при этом ни о каких соотношениях типа "в 10 раз дольше" речь уже не идет.
А в случае одного ДПСЧ почему Вы считаете, что последовательное выпадения двух фиксированных чисел в принципе возможно?

[Arigato]

Сообщение от s-andriano

А в случае одного ДПСЧ почему Вы считаете, что последовательное выпадения двух фиксированных чисел в принципе возможно?

Уже определил, что невозможно. Большинство комбинаций из двух чисел по 5 цифр не выпадут, некоторые выпадают. Комбинации из числа 5 цифр и числа 4 цифры у меня всегда выпадали (не факт, что нет такой, которая никогда не выпадет).

[s-andriano]

ДПСЧ имитирует лишь некоторые (наиболее востребованные на практике) свойства ДСЧ. В остальном - ведет себя принципиально иначе.
В Вашем случае - как раз этот второй случай.
По сути в ДПСЧ есть период. Причем за каждым определенным числом следует вполне определенное (единственное!) другое. Отсутствие однозначности (за одним и тем же числом могут следовать разные) происходит лишь потому, что мы берем не сами случайные числа, а частное или остаток от деления.