Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 38
Предсказываю, что для 131 бита потребуется перебор 5^20 чисел (примерно 10^14).
Я рассмотрел слегка другой алгоритм — рекурсивный.
Когда мы выбрали 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).
Когда мы выбрали 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).
За 20 минут алгоритм нашёл числа до 10^25 (т.е. 80 первых членов последовательности). На поиск чисел до 10^40 ушло бы около 5 лет.
Я брал BASE0 > BASE1, но не думаю, что это принципиально.
80 первых членов я нахожу за 3.5 секунды.
80 первых членов я нахожу за 3.5 секунды.
Это не строгое доказательство, а попытка объяснить реальные результаты :)
Например, для ширины в 24 десятичных знака, и следовательно 900000 элементов А, проверено 3958921 палиндромов, в среднем по 4.4 различных b на каждый a.
Например, для ширины в 24 десятичных знака, и следовательно 900000 элементов А, проверено 3958921 палиндромов, в среднем по 4.4 различных b на каждый a.
проверено 3958921 палиндромов
Действительно палиндромов? Или значений X? Палиндромов должно быть в 64 раза больше — ведь все числа из множества B в двоичной записи заканчиваются на 6 нулей. Или я чего-то совсем не понял.
Какая там получается ширина края в двоичной записи — 19 или 20?
Ширина края — 19. Т.е. 1000000 палиндромов-серединок распределяются по 2^19 корзин (в среднем по 1.9 в каждой корзине).
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Например, первого палиндрома края я проверяю 5 корзин:
100000_000000000000_000001 = 1010100101101000000_1011000111111000010100101011110110100000000000000000000001
100001_000000000000_100001 = 1010100101101000100_0010101000100101111111111010011101111001011000011010100001
100000_000000000000_000001 = 1010100101101000000_1011000111111000010100101011110110100000000000000000000001
100001_000000000000_100001 = 1010100101101000100_0010101000100101111111111010011101111001011000011010100001
Ширина края — 19. Т.е. 1000000 палиндромов-серединок распределяются по 2^19 корзин (в среднем по 1.9 в каждой корзине).
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Ну что же. В их последовательности пропущено 31-значное число :) Сможете найти?
Ещё они пропустили, по меньшей мере, два 39-значных числа (оба начинаются на 12...)…
Пропущенное 40-значное число: 1017421766189445102992015449816671247101
То есть, их последнее число — не 122-е, а 126-е.
То есть, их последнее число — не 122-е, а 126-е.
Ну, и ещё одно 40-значное число: 7114907950920173924554293710290597094117. На всё ушло 49 минут на одном ядре.
Круто! А как же 5 лет?
Чуток соптимизировал.
Вот ещё:
44-значных программа не нашла.
Думаю, на этом остановлюсь (до очередного прогрессивного способа) — на следующий разряд ушли бы сутки счёта.
Вот ещё:
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 910154776775754772502120527745757767745101944-значных программа не нашла.
Думаю, на этом остановлюсь (до очередного прогрессивного способа) — на следующий разряд ушли бы сутки счёта.
Мне кажется, вам надо принять эстафету «Вперед, на поиски палиндромов» :)
Потому что ваш алгоритм уже быстрее O(N1/4)
Потому что ваш алгоритм уже быстрее O(N1/4)
До 40-значных включительно — O(N7/34), потом — O(N0.35).
Но алгоритм отличается от вашего только шириной краёв в десятичной записи: я беру не 1/4, а 5/17 от длины числа (пока хватает памяти на серединки). Тогда в непустые корзины действительно попадает по одному числу. Ну, и края фильтруются по младшим битам.
Но алгоритм отличается от вашего только шириной краёв в десятичной записи: я беру не 1/4, а 5/17 от длины числа (пока хватает памяти на серединки). Тогда в непустые корзины действительно попадает по одному числу. Ну, и края фильтруются по младшим битам.
Ну, с шириной краев и середины я тоже «играл», тем более, что потом всё равно кончается память. Но дальше вы по краям тоже ведь не просто проходите…
Мне кажется, что я придумал модификацию вашего алгоритма, позволяющую при том же количестве оперативной памяти увеличить количество десятичных разрядов N, для которых вычислительная мощность все еще равна O(N7/34) в 10/7 раз.
Дело в том, что выбор верхних десятичных разрядов краёв влияет на четность всех цифр палиндрома, включая цифры серединок. А это значит, что можно разделить полный обход каждой конкретной ширины N на 2X подзадач. Каждая подзадача включает в себя прегенерацию 10Y*5X серединок (X нижних разрядов фиксированной четности) и обход только тех краёв, для которых Х нижних разрядов серединок имеют нужную четность.
Благодаря свойствам алгоритма обхода краёв, ненужные ветки будут отсекаться относительно рано, поэтому суммарное время обхода всех краёв по всем подзадачам будет лишь незначительно больше, чем в случае, когда у нас есть достаточно оперативной памяти для всех 10Y + X серединок сразу.
Дело в том, что выбор верхних десятичных разрядов краёв влияет на четность всех цифр палиндрома, включая цифры серединок. А это значит, что можно разделить полный обход каждой конкретной ширины N на 2X подзадач. Каждая подзадача включает в себя прегенерацию 10Y*5X серединок (X нижних разрядов фиксированной четности) и обход только тех краёв, для которых Х нижних разрядов серединок имеют нужную четность.
Благодаря свойствам алгоритма обхода краёв, ненужные ветки будут отсекаться относительно рано, поэтому суммарное время обхода всех краёв по всем подзадачам будет лишь незначительно больше, чем в случае, когда у нас есть достаточно оперативной памяти для всех 10Y + X серединок сразу.
Но краев-то 5*10^13 (для ширины 44). Только на их генерацию должно было уйти много часов, даже при скорости генерации 10^9 в секунду.
С учётом предварительной фильтрации — всего лишь 5^14. Ушло 3-4 часа.
Если бы я не поленился и написал 192-битные числа, получилось бы ещё быстрее.
Если бы я не поленился и написал 192-битные числа, получилось бы ещё быстрее.
Так вы профильтровали 5*10^13 краев, или сразу сгенерировали 5^14?
Можно сказать, что сразу — фильтрация шла для каждой очередной цифры.
Здорово!
Но, если я не ошибаюсь, ваше ускорение не применимо в случае взаимно простых оснований.
Но, если я не ошибаюсь, ваше ускорение не применимо в случае взаимно простых оснований.
А вы как-то оптимизировали/сортировали структуру, содержащую серединки?
Я только что посмотрел — на «случайный» доступ к этой огромной структуре тратится 70-80% всего времени, в разы больше чем на всю математику.
Я только что посмотрел — на «случайный» доступ к этой огромной структуре тратится 70-80% всего времени, в разы больше чем на всю математику.
У меня основное время уходит на разворот длинных чисел в двоичной записи.
Структура, содержащая серединки, устроена просто:
struct{
UInt128 val;
int next;
}
где next — индекс в массиве следующего элемента в списке. next=0 — ячейка пуста, next=-1 — этот элемент последний. Первые 2^X элементов — корзины (начала списков), дальше — свободные места для продолжения списков. Когда массив оказался длиннее 2ГБ, пришлось переделать его на массив массивов.
Если захочу считать дальше, переделаю его на файл и буду хранить серединки, упорядоченные начиная с младшего бита. Понятие корзины при этом исчезнет, всё будет делаться сопоставлениями двух отсортированных списков. Но это потом.
Структура, содержащая серединки, устроена просто:
struct{
UInt128 val;
int next;
}
где next — индекс в массиве следующего элемента в списке. next=0 — ячейка пуста, next=-1 — этот элемент последний. Первые 2^X элементов — корзины (начала списков), дальше — свободные места для продолжения списков. Когда массив оказался длиннее 2ГБ, пришлось переделать его на массив массивов.
Если захочу считать дальше, переделаю его на файл и буду хранить серединки, упорядоченные начиная с младшего бита. Понятие корзины при этом исчезнет, всё будет делаться сопоставлениями двух отсортированных списков. Но это потом.
143 557019370941199612258585852216991149073910755
144 706400325289926993853434358399629982523004607
145 903240486809073407096959690704370908684042309
146 5318935032766104711807997081174016672305398135
147 9335388324586156026843333486206516854238835339
45 и 46-значные: 5:30 и 4:45 часа соответственно.
Огромное спасибо за вашу прекрасную оптимизацию и конкуренцию!
Я обновил список на сайте «Энциклопедии целочисленных последовательностей». Сейчас он доступен здесь, но после утверждения правки он скорее всего заменит предыдущий список.
Также, я указал ваше имя (Andrey Astrelin) — без вашей идеи я бы дошел лишь до 10^41.
Также, я указал ваше имя (Andrey Astrelin) — без вашей идеи я бы дошел лишь до 10^41.
47-значные, 9:45 часов:
И это уже с первой робкой попыткой prefetch, даже с которой на хаотическое обращение к памяти уходит 75-80% времени.
148 12328899531897059171731113717195079813599882321
149 16422159001061376847917371974867316010095122461
150 36755925874534219715185758151791243547852955763
151 56243939994005432191600400619123450049993934265
152 72224512737657344148643434684144375673721542227
153 72830033748815722240681118604222751884733003827
154 74953152103456169263148284136296165430125135947
155 78737696079148631316169196161313684197069673787
И это уже с первой робкой попыткой prefetch, даже с которой на хаотическое обращение к памяти уходит 75-80% времени.
48-значные, 0:32 часа:
49-значные, 2:41 часа:
50-значных, 2:30 часа: нет
Основные «ускорители»: 109 серединок, 8 потоков.
156 102735644379963218861031130168812369973446537201
157 502186653128032879493361163394978230821356681205
158 59781736587048046249684664869426408407856371879549-значные, 2:41 часа:
159 1873893355166996611906735376091166996615533983781
160 7109242970502610649115178715119460162050792429017
161 914268730651877446829025852092864477815603786241950-значных, 2:30 часа: нет
Основные «ускорители»: 109 серединок, 8 потоков.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вперед, на поиски палиндромов 3