ilyanik Dec 17 2015 at 12:13

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

4 min

10K

Sport programming*Programming*Algorithms*Mathematics*

+15

Comments 38

Mrrl Dec 17 2015 at 14:59

Предсказываю, что для 131 бита потребуется перебор 5^20 чисел (примерно 10^14).

ilyanik Dec 17 2015 at 15:12

Почему 5²⁰? Только первая цифра десятичного палиндрома нечетная, на остальные ограничений нет.

Mrrl Dec 17 2015 at 15:58

Я рассмотрел слегка другой алгоритм — рекурсивный.
Когда мы выбрали K старших десятичных цифр палиндрома, мы почти всегда знаем K+1 его старших бит (обычно, почти 3*K, но для наших целей это неважно). Следовательно, знаем K+1 младший бит, а поскольку K младших цифр нам известно, то K+1-я цифра может принимать 5 разных значений — быть либо чётной, либо нечётной (в зависимости от ситуации). Так что число кандидатов увеличилось в 5 раз.
В редких случаях, когда старшие K+1 бит неизвестны, нам придётся поставлять все 10 кандидатов на K+1-ю цифру, но половина из них сразу отсеется.
Какой-то из пунктов 2 или 3 в Ваших рассуждениях вызывает сомнения — в нём (не знаю пока, в каком) должно быть (BASE0/BASE1)^(W/4) вариантов (или (BASE1/BASE0)^(W/4) — из текста непонятно, кто из них 2, а кто 10).

Mrrl Dec 17 2015 at 16:04

За 20 минут алгоритм нашёл числа до 10^25 (т.е. 80 первых членов последовательности). На поиск чисел до 10^40 ушло бы около 5 лет.

ilyanik Dec 17 2015 at 16:16

Я брал BASE₀ > BASE₁, но не думаю, что это принципиально.

80 первых членов я нахожу за 3.5 секунды.

ilyanik Dec 17 2015 at 16:49

Это не строгое доказательство, а попытка объяснить реальные результаты :)

Например, для ширины в 24 десятичных знака, и следовательно 900000 элементов А, проверено 3958921 палиндромов, в среднем по 4.4 различных b на каждый a.

Mrrl Dec 17 2015 at 17:35

проверено 3958921 палиндромов

Действительно палиндромов? Или значений X? Палиндромов должно быть в 64 раза больше — ведь все числа из множества B в двоичной записи заканчиваются на 6 нулей. Или я чего-то совсем не понял.
Какая там получается ширина края в двоичной записи — 19 или 20?

ilyanik Dec 17 2015 at 17:59

Ширина края — 19. Т.е. 1000000 палиндромов-серединок распределяются по 2^19 корзин (в среднем по 1.9 в каждой корзине).
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.

Mrrl Dec 17 2015 at 18:59

К сожалению, заполнено только 2^13 корзин, по 122 в каждой…

ilyanik Dec 17 2015 at 19:04

Эээ..., а почему 2^13 корзин? :)

Это же мой алгоритм, у меня 2^19? Откуда вы вообще взяли число 13?

Mrrl Dec 17 2015 at 19:32

Но вы же кладёте в них числа из множества B, которые в десятичной системе оканчиваются на 6 нулей, не так ли?

ilyanik Dec 17 2015 at 20:16

А, из-за того, что 10 делится на 2?

Да, распределение по корзинам получается очень неравномерное. Но из-за равномерного выбора каждой из 2^19 корзин, в среднем выходит 1.9: на каждую корзину с ~122 элементами 63 пустых.

ilyanik Dec 17 2015 at 18:05

Например, первого палиндрома края я проверяю 5 корзин:

100000_000000000000_000001 = 1010100101101000000_1011000111111000010100101011110110100000000000000000000001
100001_000000000000_100001 = 1010100101101000100_0010101000100101111111111010011101111001011000011010100001

ilyanik Dec 17 2015 at 17:58

Mrrl Dec 17 2015 at 21:10

Ну что же. В их последовательности пропущено 31-значное число :) Сможете найти?

Mrrl Dec 17 2015 at 23:45

Ещё они пропустили, по меньшей мере, два 39-значных числа (оба начинаются на 12...)…

Mrrl Dec 17 2015 at 23:58

Пропущенное 40-значное число: 1017421766189445102992015449816671247101
То есть, их последнее число — не 122-е, а 126-е.

Mrrl Dec 18 2015 at 00:08

Ну, и ещё одно 40-значное число: 7114907950920173924554293710290597094117. На всё ушло 49 минут на одном ядре.

ilyanik Dec 18 2015 at 18:37

Круто! А как же 5 лет?

Mrrl Dec 18 2015 at 20:45

Чуток соптимизировал.
Вот ещё:

128 14327425216354951264146215945361252472341
129 31636759764024794204540249742046795763613
130 38090421176450233778487733205467112409083
131 56545858306667087923432978076660385854565
132 98801466348600079992129997000684366410889
133 128795669673344381770077183443376966597821
134 139035351443367699760067996763344153530931
135 170341815153453197154451791354351518143071
136 309612431907274418544445814472709134216903
137 595943598626320807905509708023626895349595
138 905357630732463833436634338364237036753509
139 1816060344791285708869688075821974430606181
140 3381578420704603001613161003064070248751833
141 7342779513978827245484845427288793159772437
142 9101547767757547725021205277457577677451019

44-значных программа не нашла.
Думаю, на этом остановлюсь (до очередного прогрессивного способа) — на следующий разряд ушли бы сутки счёта.

ilyanik Dec 18 2015 at 21:57

Мне кажется, вам надо принять эстафету «Вперед, на поиски палиндромов» :)

Потому что ваш алгоритм уже быстрее O(N^1/4)

Mrrl Dec 18 2015 at 22:09

До 40-значных включительно — O(N^7/34), потом — O(N^0.35).
Но алгоритм отличается от вашего только шириной краёв в десятичной записи: я беру не 1/4, а 5/17 от длины числа (пока хватает памяти на серединки). Тогда в непустые корзины действительно попадает по одному числу. Ну, и края фильтруются по младшим битам.

ilyanik Dec 18 2015 at 23:09

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

Mrrl Dec 18 2015 at 23:45

Память тратится только на середину. 10^8 чисел удержать можно (если хранить их как 128-битные). Края строятся динамически, их запоминать не нужно.

ilyanik Feb 17 2016 at 11:35

Мне кажется, что я придумал модификацию вашего алгоритма, позволяющую при том же количестве оперативной памяти увеличить количество десятичных разрядов N, для которых вычислительная мощность все еще равна O(N^7/34) в 10/7 раз.

Дело в том, что выбор верхних десятичных разрядов краёв влияет на четность всех цифр палиндрома, включая цифры серединок. А это значит, что можно разделить полный обход каждой конкретной ширины N на 2^X подзадач. Каждая подзадача включает в себя прегенерацию 10^Y*5^X серединок (X нижних разрядов фиксированной четности) и обход только тех краёв, для которых Х нижних разрядов серединок имеют нужную четность.

Благодаря свойствам алгоритма обхода краёв, ненужные ветки будут отсекаться относительно рано, поэтому суммарное время обхода всех краёв по всем подзадачам будет лишь незначительно больше, чем в случае, когда у нас есть достаточно оперативной памяти для всех 10^{Y + X} серединок сразу.

ilyanik Dec 19 2015 at 11:31

Но краев-то 5*10^13 (для ширины 44). Только на их генерацию должно было уйти много часов, даже при скорости генерации 10^9 в секунду.

Mrrl Dec 19 2015 at 14:05

С учётом предварительной фильтрации — всего лишь 5^14. Ушло 3-4 часа.
Если бы я не поленился и написал 192-битные числа, получилось бы ещё быстрее.

ilyanik Dec 19 2015 at 14:20

Так вы профильтровали 5*10^13 краев, или сразу сгенерировали 5^14?

Mrrl Dec 19 2015 at 15:55

Можно сказать, что сразу — фильтрация шла для каждой очередной цифры.

ilyanik Dec 20 2015 at 11:32

Здорово!

Но, если я не ошибаюсь, ваше ускорение не применимо в случае взаимно простых оснований.

ilyanik Dec 21 2015 at 17:40

А вы как-то оптимизировали/сортировали структуру, содержащую серединки?

Я только что посмотрел — на «случайный» доступ к этой огромной структуре тратится 70-80% всего времени, в разы больше чем на всю математику.

Mrrl Dec 21 2015 at 18:10

У меня основное время уходит на разворот длинных чисел в двоичной записи.
Структура, содержащая серединки, устроена просто:
struct{
UInt128 val;
int next;
}
где next — индекс в массиве следующего элемента в списке. next=0 — ячейка пуста, next=-1 — этот элемент последний. Первые 2^X элементов — корзины (начала списков), дальше — свободные места для продолжения списков. Когда массив оказался длиннее 2ГБ, пришлось переделать его на массив массивов.
Если захочу считать дальше, переделаю его на файл и буду хранить серединки, упорядоченные начиная с младшего бита. Понятие корзины при этом исчезнет, всё будет делаться сопоставлениями двух отсортированных списков. Но это потом.

ilyanik Jan 1 2016 at 11:34

А вы использовали этот прием:
graphics.stanford.edu/~seander/bithacks.html#ReverseParallel
?

Mrrl Jan 1 2016 at 12:49

Нет, я даже инверсией по табличке не пользовался. Поскольку длина в двоичной записи не кратна 8, пришлось бы совмещать её со сдвигом длинного числа. Но было лень :(

ilyanik Dec 30 2015 at 11:20

143 557019370941199612258585852216991149073910755
144 706400325289926993853434358399629982523004607
145 903240486809073407096959690704370908684042309
146 5318935032766104711807997081174016672305398135
147 9335388324586156026843333486206516854238835339

45 и 46-значные: 5:30 и 4:45 часа соответственно.

Огромное спасибо за вашу прекрасную оптимизацию и конкуренцию!

ilyanik Dec 30 2015 at 14:09

Я обновил список на сайте «Энциклопедии целочисленных последовательностей». Сейчас он доступен здесь, но после утверждения правки он скорее всего заменит предыдущий список.

Также, я указал ваше имя (Andrey Astrelin) — без вашей идеи я бы дошел лишь до 10^41.

ilyanik Jan 6 2016 at 10:43

47-значные, 9:45 часов:

148 12328899531897059171731113717195079813599882321
149 16422159001061376847917371974867316010095122461
150 36755925874534219715185758151791243547852955763
151 56243939994005432191600400619123450049993934265
152 72224512737657344148643434684144375673721542227
153 72830033748815722240681118604222751884733003827
154 74953152103456169263148284136296165430125135947
155 78737696079148631316169196161313684197069673787

И это уже с первой робкой попыткой prefetch, даже с которой на хаотическое обращение к памяти уходит 75-80% времени.

ilyanik Feb 3 2016 at 11:27

48-значные, 0:32 часа:

156 102735644379963218861031130168812369973446537201
157 502186653128032879493361163394978230821356681205
158 597817365870480462496846648694264084078563718795

49-значные, 2:41 часа:

159 1873893355166996611906735376091166996615533983781
160 7109242970502610649115178715119460162050792429017
161 9142687306518774468290258520928644778156037862419

50-значных, 2:30 часа: нет

Основные «ускорители»: 10⁹ серединок, 8 потоков.

Show the best of all time