Вперед, на поиски палиндромов 3

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

«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, умноженных на 10³ и множества десятичных палиндромов шириной 4, умноженных на 10².

А если неформально, то множество А — это все возможные «края», а множество 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 = 10².

Теперь возьмём каждый 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 двоичным палиндромом.

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

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

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

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

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

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

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

2¹³¹ / 2⁶⁰ = 2⁷¹

2^{71 * 1/4} < 2¹⁸ = 262144

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

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

Автор: ilyanik

Источник