Вперед, на поиски палиндромов 317.12.2015 13:18

После того, как вроде бы неплохой результат, полученный в предыдущей части, оказался лишь «локальным максимумом», я на некоторое время забросил задачку. Напомню условие:

«The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». Или, по-русски: «Десятичное число 585 в двоичной системе счисления выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-й подобный палиндром».


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

В конце концов, алгоритм оказался не таким уж и сложным, зато, на мой взгляд, очень красивым.
Оригинальное объяснение и реализация используют префиксное дерево, но на мой взгляд, чуть более глубокое понимание математики алгоритма позволяет обойтись более простыми и быстрыми структурами. Думаю, что лучше всего разобрать алгоритм на примере.

Мы будем искать двоичные палиндромы среди десятичных палиндромов шириной 8. Исходных палиндромов ровно 9000: от 10000001 до 99999999.

Теперь возьмём 2 множества чисел:

  • А[90] = { 10000001, 11000011, 12000021, …, 98000089, 99000099 }
  • B[100] = { 00000000, 00011000, 00022000, …, 00988900, 00999900 }


Если описывать эти множества формально, то множество А является подмножеством десятичных палиндромов шириной 8, у которых средние 4 разряда — нули, а множество B состоит из 0, множества десятичных палиндромов шириной 2, умноженных на 103 и множества десятичных палиндромов шириной 4, умноженных на 102.

А если неформально, то множество А — это все возможные «края», а множество B — все возможные «серединки» десятичных палиндромов шириной 8. Очевидно, что множество всех десятичных палиндромов шириной 8 — это множество всех попарных сумм элементов множеств A и B.

for each (a in A) {
        for each (b in B) {
                palindrome = a + b;
        }
}


Далее, для краткости я буду использовать «a» вместо «элемент множества A», и «b» вместо «элемент множества B».

Теперь переведём элементы обоих множеств в двоичную систему счисления:

A

10000001 100110001001011010000001
11000011 101001111101100011001011
12000021 101101110001101100010101
…
98000089 101110101110101110011011001
99000099 101111001101001111100100011


B

00000000 000000
00011000 10101011111000
00022000 101010111110000
…
00988900 11110001011011100100
00999900 11110100000111011100


Я выделил по 6 верхних и нижних разрядов у всех a, и 6 нижних разрядов у всех b. Ширина 6 выбрана не случайно — это максимальная степень 2, не превышающая ширину «краёв» A = 102.

Теперь возьмём каждый a, и посмотрим, что общего у всех палиндромов, образованных от него прибавлением b. А общее у них, то, что все они находятся в интервале между самим a и следующим за ним элементом A.

Например, для a = 10000001, все образованные от него десятичные палиндромы { 10000001, 10011001, 10022001, …, 10988901, 10999901 } находятся в интервале [10000001, 11000011).

Это значит, что все десятичные палиндромы, образованные от a = 10000001 могут начинаться только со следующих 6 двоичных цифр:

100110 — первые двоичные цифры a = 10000001
100111
101000
101001 — первые двоичные цифры a = 11000011


Следовательно, чтобы быть двоичными палиндромами, все эти десятичные палиндромы могут заканчиваться только на обратную перестановку начальных двоичных цифр:

100110 → 011001
100111 → 111001
101000 → 000101
101001 → 100101


А учитывая, что сам, а = 10000001 заканчивается на двоичные цифры 000001, то из всех возможных b нас интересуют только те, которые заканчиваются на двоичные цифры:

011001 — 000001 = 011000
111001 — 000001 = 111000
000101 — 000001 = 000100
100101 — 000001 = 100100


Только для таких b нужно проверять, является ли 10000001 + b двоичным палиндромом.

Используя данный подход, алгоритм для нахождения палиндромов в основаниях BASE0, BASE1 в интервале [1, N] может быть описан следующим образом:

Для каждой ширины W из [1, количество разрядов N в BASE0]
    Сгенерировать множества A и B, используя BASE0. Ширина «краёв» A WA = O (W/4), WA ≥ WB
    Перевести элементы A и B в BASE1
    Рассортировать элементы B по корзинам по последним цифрам в BASE1
    Для каждого a из множества A
        Для каждого X из множества возможных начальных цифр a + b
            Для каждого b, заканчивающегося на (X — конечные цифры a)
                Проверить, является ли a + b палиндромом в BASE1


К сожалению, я уже разучился строго доказывать вычислительную сложность алгоритмов, приведу лишь несколько соображений:

  1. Множества A и B содержат O (N1/4) элементов.
  2. Для каждого a в среднем существует не более BASE0 вариантов X.
    (Мы изначально выбираем ширину интересующих нас начальных цифр в BASE1 так, чтобы получившееся из них число было не больше BASE0WA, а max (A) больше min (A) в BASE0 раз.)
  3. Для каждого X в среднем проверяется не более, чем BASE1 различных b.
    (X распределяется равномерно и почти не коррелирует с конечными цифрами a в BASE1. Значит каждая корзина с b выбирается равномерно, а всего таких корзин не более чем в BASE1 раз меньше, чем самих b.)
  4. Проверка на палиндром все равно занимает O (log (N)).


В общем, я предполагаю, что вычислительная сложность алгоритма O (N1/4 * log (N) * BASE0 * BASE1).

Первая же реализация этого алгоритма вполне предсказуемо была на пару порядков быстрее, а потратив еще немного времени на оптимизацию я довел время вычисления до чуть более 0.01 секунды, более чем в 1000 раз быстрее предыдыщего алгоритма. Этот результат наконец-то меня удовлетворил, но вполне естественно возникло желание проверить его на числах, бо́льших, чем 260. К этому времени я уже обнаружил интересующую меня последовательность в «Энциклопедии целочисленных последовательностей». В списке двойных палиндромов было 122 члена, самый большой из которых состоял из 131 бита. Это было впечатляюще, но и косвенно указывало на то, что никто пока не придумал алгоритм логарифмической сложности.

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

2131 / 260 = 271

271 * ¼ < 218 = 262144

Учитывая 0.01 секунды, необходимых для предела в 260, выходило, что мой алгоритм должен был справиться с этой задачей примерно за 1 час! Я чувствовал какой-то подвох, но вызов был уже принят.

Продолжение следует.

© Habrahabr.ru