После того, как вроде бы неплохой результат, полученный в предыдущей части, оказался лишь «локальным максимумом», я на некоторое время забросил задачку. Напомню условие:
«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
К сожалению, я уже разучился строго доказывать вычислительную сложность алгоритмов, приведу лишь несколько соображений:
- Множества A и B содержат O(N1/4) элементов.
- Для каждого a в среднем существует не более BASE0 вариантов X.
(Мы изначально выбираем ширину интересующих нас начальных цифр в BASE1 так, чтобы получившееся из них число было не больше BASE0WA, а max(A) больше min(A) в BASE0 раз.) - Для каждого X в среднем проверяется не более, чем BASE1 различных b.
(X распределяется равномерно и почти не коррелирует с конечными цифрами a в BASE1. Значит каждая корзина с b выбирается равномерно, а всего таких корзин не более чем в BASE1 раз меньше, чем самих b.) - Проверка на палиндром все равно занимает O(log(N)).
В общем, я предполагаю, что вычислительная сложность алгоритма O(N1/4 * log(N) * BASE0 * BASE1).
Первая же реализация этого алгоритма вполне предсказуемо была на пару порядков быстрее, а потратив еще немного времени на оптимизацию я довел время вычисления до чуть более 0.01 секунды, более чем в 1000 раз быстрее предыдыщего алгоритма. Этот результат наконец-то меня удовлетворил, но вполне естественно возникло желание проверить его на числах, бо́льших, чем 260. К этому времени я уже обнаружил интересующую меня последовательность в «Энциклопедии целочисленных последовательностей». В списке двойных палиндромов было 122 члена, самый большой из которых состоял из 131 бита. Это было впечатляюще, но и косвенно указывало на то, что никто пока не придумал алгоритм логарифмической сложности.
Вызов был серьёзный — можно было не сомневаться, что люди, получившие такой результат, вложили немало сил в разработку алгоритма и к тому же наверняка были готовы потратить дни и недели машинного времени на последующий поиск. Поэтому, я решил хотя бы приблизительно оценить, время, которое необходимо моему алгоритму на повторение:
2131 / 260 = 271
271 * 1/4 < 218 = 262144
Учитывая 0.01 секунды, необходимых для предела в 260, выходило, что мой алгоритм должен был справиться с этой задачей примерно за 1 час! Я чувствовал какой-то подвох, но вызов был уже принят.
Продолжение следует.
Автор: ilyanik
