Выбор глубины при поиске отложенных палиндромов

25 ноября 2020
(обновлено 5 февраля 2022)
Время на чтение: 6 минут

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

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

Возникает вопрос: а сколько нужно сделать итераций, чтобы точно сказать, что некоторое число не является отложенным палиндромом? Ведь чем больше итераций мы будем делать для каждого проверяемого числа, тем медленнее будет поиск. А, с другой стороны, если мы выполним недостаточно операций Перевернуть-И-Сложить, мы ошибочно можем принять отложенный палиндром за число Лишрел, попросту не дождавшись его превращения в палиндром.

Ниже в таблице приведены данные для каждого диапазона о наибольшем количестве итераций, которое требуется его числам для того, чтобы стать палиндромами (* диапазоны 23-, 24-, 25- и 26-значных чисел проверены не полностью).

Номер
диапазона
Наибольший
шаг
Номер
диапазона
Наибольший
шаг
12 14186
224 15201
323 16197
421 17236
555 18232
664 19261
796 20258
896 21256
998 22252
10109 23289*
11149 24285*
12149 25293*
13188 26289*

Проанализировав эти данные, мы можем прийти к выводу, что номер диапазона и наибольший шаг внутри него находятся в линейной зависимости. И проведя расчёты (используя данные диапазонов с 1 по 23), выяснить, что коэффициент корреляции равен 98.9%, что является очень высоким показателем! Поэтому, используя линейную регрессию, можно получить следующую формулу, приблизительно описывающую зависимость наибольшего количества итераций от номера диапазона:

Наибольший шаг = Номер диапазона × 13.326 – 10.261

При этих коэффициентах стандартное отклонение равно 13.33. Говоря человеческим языком, формула выше позволяет нам рассчитать нужную глубину поиска. А отклонение означает, что в среднем полученное значение будет отклоняться на 13.33 шага от истинного.

• • •

Учитывая вероятностный характер подобных расчётов, мы, разумеется, не можем применить полученное значение глубины поиска в исходном виде. Из-за того, что формула лишь приблизительно описывает истинную закономерность, результат тоже будет не идеально точным.

Чтобы снизить вероятность выбора недостаточной глубины, мы должны добавить к полученному значению некоторое количество сигм (так называют стандартное отклонение). Так, если мы добавим 1 сигму, то получим вероятность того, что глубина окажется недостаточной, равную примерно 15.9% (это очень много), для 2 сигм значение уменьшится до 2.28%, для 3 сигм — до 0.135% (полагая, что величина имеет нормальное распределение).

Другими словами, добавляя сигмы, мы как бы берём значение с «запасом», чтобы наверняка не ошибиться. И чем больше сигм мы возьмём, тем ниже будет вероятность ошибки. Но брать слишком много сигм так же нет никакого смысла.

Для проекта MDPN это значение выбрано равным 6, что даёт вероятность ошибки немного лучше, чем 1:1,000,000,000 (1 к миллиарду). Это очень низкая вероятность пропустить отложенный палиндром. А окончательная формула для вычисления необходимой глубины поиска выглядит следующим образом:

Глубина поиска = Номер диапазона × 13.326 – 10.261 + 13.33 × 6.0

• • •

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

Это означает, что количество итераций и продолжительность поиска находятся в квадратичной зависимости. Для типичных значений длины проверяемых чисел (от 10 до 25 знаков) и глубины поиска (от 200 до 400 итераций), именно глубина поиска имеет решающее значение.

Так, при увеличении глубины поиска с 200 до 283 итераций, время поиска увеличивается примерно в 2 раза. При увеличении с 200 до 400 итераций — примерно в 4 раза! А незначительная на первый взгляд разница в 20 итераций между глубиной поиска 375 и 395 делает процесс медленнее примерно на 11%.