iLWN
Главная MDPN Рекорды

Most Delayed Palindromic Number

Дневник проекта (хронология)
Это старая страница Дневника проекта MDPN. Она больше не обновляется!
Новый блог проекта находится здесь. Новости и события проекта — здесь.

26 декабря 2020

Сегодня было завершено обновление базы данных и проверка диапазона 20-значных чисел. Всего на проверку этого диапазона потребовалось 539 дней (включая перерывы в работе программы): с 6 июля 2019 года до 26 декабря 2020 года. Суммарное процессорное время составило: 11,838,331 секунду (3,288.5 часов или 137.0 дней). Большая часть работы была проделана стареньким 4-ядерным Core i7-2600K и сравнительно небольшая — 6-ядерным Core i7-8700.

Для сравнения, около 13 лет назад Vaughn Suite потратил на сканирование всех 20-значных чисел 381 день, используя 6 ПК: Pentium 4 HT, 2 Athlon XP, Athlon 64, Athlon 64 X2, Core 2 Quad. Он проделал это в период с 6 января 2007 по 22 января 2008 года. Суммарное процессорное время составило 131,146,531 секунду (36,429.6 часов или 1,517.9 дней).

Всего в диапазоне было проверено 5,808,378,560,022 кандидата, из которых 5,459,760,062,742 оказались числами Лишрел. Полное количество чисел Лишрел составило 84,410,376,335,506,093,101 (84.4 квинтиллиона) или 93.789% всех 20-значных чисел. Таким образом лишь 6.211% чисел стали палиндромами (тогда как для диапазона 19-значных чисел это значение равно 7.819%). Количество шагов, необходимых наиболее отложенному палиндрому в диапазоне, равно 258. Минимальная глубина поиска составила 335 шагов.

Среди 20-значных чисел были найдены 6 новых наименьших отложенных палиндромов: шаги 223 и от 253 до 257.

Достижения дня: завершена проверка 20-значных чисел.


20 декабря 2020

Вчера я экспериментировал с количеством рабочих потоков программы. Так как все высокопроизводительные процессоры Intel поддерживают технологию Hyper-Threading (HT), в том числе мой старый Core i7-2600K, а также более новый Core i7-8700, мне стало интересно, каков будет эффект от использования количества потоков, большего, чем количество физических ядер. Я попробовал выполнить поиск на одном и том же интервале чисел при разном количестве потоков. В одном эксперименте это был конец 18-значного диапазона (где отсев максимально эффективен), в другом — начало того же диапазона (где отсев не работает). Результаты для 4-ядерного CPU Intel Core i7-2600K:

Количество
потоков
Время работы
(конец диапазона)
Процессорное
время
Изменение скорости поиска Время работы
(начало диапазона)
Изменение скорости поиска
3 140.8 7:45 (x3.30) 74.3
4 121.6 8:51 (x4.37) 0.0% 61.2 0.0%
5 107.8 9:42 (x5.40) +12.8% 54.1 +13.1%
6 98.3 10:42 (x6.53) +23.7% 48.4 +26.4%
7 94.1 11:33 (x7.36) +29.2% 45.6 +34.2%
8 99.0 12:46 (x7.74) +22.8% 46.1 +32.8%

Таким образом, дополнительные 3 потока позволили увеличить скорость работы в среднем на 31.7%! При 8 рабочих потоках на 4 физических ядрах скорость оказалась хуже, чем при 7 (особенно, если отсев эффективен). Это объясняется тем, что поток базы данных тоже "съедает" часть ресурсов, причём его активность значительно выше в случае эффективного отсева, так как при этом за то же самое время находится больше отложенных палиндромов и чисел Лишрел, информацию о которых нужно сохранять в БД. Также оказывает влияние работа механизма Turbo Boost: частота процессора снижалась до базовых 3.4 GHz при активных 7 и 8 потоках, тогда как при 3-6 потоках частота составляла 3.47-3.52 GHz.

В среднем, накладные расходы на организацию поиска в несколько потоков составляют около 9% (12%, если рабочих потоков только два). Однако при 7 потоках это значение упало до 5%, в при 8 — вообще ушло в отрицательную зону (время x7.74 на 8 потоков). Причина очень проста: при 7 рабочих потоках процессор часто оказывается загружен на 100%, а при 8 он загружен на 100% всегда. И так как помимо программы на нём выполняются и другие процессы, в том числе системные, потоки программы в сумме получают менее 87.5% (7/8) и 100% (8/8) процессорного времени соответственно, что и приводит к искажению множителя.

Отдельно хочу сказать об оптимизации многопоточного доступа к набору отсева. Изначально для этого использовались две атомарные переменные. Однако то же самое можно сделать и с помощью всего одной — 32-битного счётчика читателей, один бит которого отведён под флаг записи. При таком способе упрощается организация доступа для рабочих потоков (вместо 2 операций RMW и 2 чтений флага остаются только 2 RMW операции, которые теперь всегда выполняются безусловно). Но немного ухудшаются параметры спин-лока в главном потоке (ожидание доступа на запись может быть дольше). Но так как главный поток один, а рабочих много, то этот способ приводит к увеличению скорости поиска в среднем на 2.8%.

Итогом всех вышеперечисленных изменений стало значительное увеличение скорости поиска (проверки чисел). Так, на Core i7-8700 увеличение количества рабочих потоков с 6 до 11 дало в среднем +34% прироста скорости поиска, а вместе с оптимизацией доступа к набору отсева чисел Лишрел получилось +37.7%! Средняя скорость проверки (около 10% от начала диапазона 21-значных чисел) выросла с 864K/s до 1.19M/s, а пиковая скорость во второй половине этого же диапазона выросла до рекордных 18.2M/s (при наборе отсева ~23.8 Гб)!

По результатам замеров за последние 18 часов общая средняя скорость проверки 21-значных чисел составляет ~1.8% от всего диапазона в сутки (~43.6 миллиарда чисел в час). На данный момент проверено 9.957% всех 21-значных чисел.


9 декабря 2020

Не так давно я рассказывал, что в текущем формате базы данных помимо обычного сжатия используется дельта-кодирование при сохранении найденных отложенных палиндромов. Его суть в том, что для каждого найденного числа мы на самом деле записываем в файл разность между ним и предыдущим числом. Это позволяет сильно уменьшить размер БД, ведь разность близких чисел намного меньше самих этих чисел.

Вчера я немного думал о том, как ещё можно уменьшить размер базы данных и решил посмотреть, как выглядят данные файла до сжатия. И оказалось, что в числах есть закономерность! Из-за того, что сохраняются не все найденные палиндромы, а только те, для которых нужно 45 и более операций RAA для достижения ими палиндрома, их разности часто содержат много подряд идущих нолей или девяток!

Я попробовал заменить такие последовательности латинскими буквами, чтобы уменьшить длину чисел. Как и дельта-кодирование, этот способ, по сути, является энтропийным кодированием (т.е. сжатием без потерь). Но применяя эти методы перед последующим обычным сжатием данных, можно добиться как уменьшения размера сжатых данных, так и увеличения скорости сжатия! Так, в среднем, размер сжатых данных уменьшился на 4.8% (для 15-значных чисел), а размер данных до сжатия — более, чем на 20%! К 11 символам цифр и разделителя добавились ещё несколько букв. Размер несжатых данных уменьшился, они стали плотнее, а их энтропия увеличилась, что привело к тому, что сжатие стало быстрее в среднем на те же 20%. Другими словами, сплошные плюсы! И вот как красиво теперь это выглядит (пары чисел: отложенный палиндром и его шаг; где-то во второй половине 17-значных чисел):

9C 29 134N1C 29 9C 29 26O1C 29 9C 29 1O3C 2 4G 1 511A2C 37 9F 37 1016N7C 53 603F 53 347F 5 12F 3 13A7C 0 108F 0 46O3C 5 21G 3 13PC 19 9C 19 13N5C 5 17A4C 1 53OC 29 N7C 5 1A1C 25 232OC 5 17B3C 29 P7C 5 1C1C 25 315N8C 56 11N8C 5 4A5C 11 3A2C 0 104N8C 11 3C2C 0 7O5C 56 20O8C 5 27G 5 12A7C 1 54N6C 5 17A4C 1 1N6C 7 34A4C 1 27G 1 1P6C 7 8G 5 340145C 12 29D 31 58D 34 34D 0 46D 5 172D 34 97D 0 478D 24 56D 7 602D 0 306D 16 37D 9 382D 31 206D 3 157D 13 322D 3 85D 1 526D 0 12D 17 21D 5 205D 19 345D 3 359D 1 59D 6 33D 19 155D 6 19E 1 47D 34 97D 0 289D 17 15E 53 153D 14 452D 6 92D 0 185D 7 278D 29 57D 1 173D 4 58D 13 197D 12 87D 34 359D 17 397D 19 263D 5 654D 13 92D 1 133D 6 375D 25 92D 1 125D 3 81D 0 1029D 34 34D 0 46D 5 19D 34 3NE 3 94E 0 1044D 6 5022D 9 1N7D 1 OD 6 1974D 0 948D 12 3039D 34 1044D 3 914D 31 4NE 34

6 декабря 2020

Сегодня завершилось обновление базы данных для чисел 19-значного диапазона! И теперь известно, сколько всего чисел Лишрел среди 19-значных. Их ровно 8,296,298,148,670,772,741 (округляя, это будет 8.3 квинтиллиона)! Количество цифр в этом числе не должно удивлять, ведь речь, собственно, о 19-значных числах. Но было очень интересно найти именно точное их количество! На главной странице есть полная таблица с количеством чисел Лишрел для каждого проверенного диапазона.

Таким образом, 92.181% всех 19-значных чисел являются числами Лишрел, и лишь 7.819% — отложенными палиндромами. Несмотря на такое невысокое процентное соотношение, количество чисел, которые становятся палиндромами, просто огромно: 703,701,851,329,227,259 (более 703 квадриллионов)! Для того, чтобы просто сохранить их в файл понадобилось бы более 7 миллионов жестких дисков по 2 терабайта каждый!

А ещё сегодня случилась одна приятность! Парк машин, неустанно проверяющих новые числа, пополнился одним ценным экземпляром: 6-ядерным Intel Core i7-8700 в комплекте с 32 Гб оперативной памяти DDR4! При полной нагрузке на все 6 ядер он работает на частоте 4.3 ГГц! Теперь общее количество процессорных ядер, которые трудятся в проекте в режиме 24/7 достигло 13! И это не может не радовать!

На текущий момент диапазон 20-значных чисел уже полностью проверен, и 10 потоков занимаются обновлением его базы данных. До завершения остаётся ещё примерно 39.8% и около недели времени. 3 оставшихся потока по-прежнему трудятся на проверке 21-значных чисел: здесь проверено 3.717%.


4 декабря 2020, "Многопоточность"

Всю последнюю неделю я занимался многопоточным поиском. Говоря точнее, переписывал алгоритм проверки чисел так, чтобы это делалось параллельно в нескольких потоках на нескольких физических ядрах центрального процессора. Задача оказалась нетривиальной. Недостаточно просто создать несколько потоков, дать каждому по кусочку диапазона и правильно защитить примитивами синхронизации доступ к совместно используемым объектам... Самым трудным оказалось сделать так, чтобы все потоки были заняты работой и не простаивали, особенно на топовом 6-ядерном процессоре Intel Core i7 8-го поколения (ух, какой же он быстрый... по крайней мере в сравнении с моим i7-2600K).

Очень долго я не мог заставить программу эффективно загрузить более 3 ядер процессора. Главный поток, выполняющий роль диспетчера, не успевал обрабатывать готовые задания и формировать новые с достаточной скоростью. И хотя профилирование однопоточного алгоритма показывало, что 85% времени уходит на операции RAA (до отсева чисел Лишрел и после), полное вынесение этих операций в "рабочие" потоки позволило загрузить в случае более-менее эффективно работающего отсева всего 3-4 потока (примерно с 20% диапазона), и лишь 1-2 потока в его второй половине. Работа с БД (сохранение результатов) практически сразу была вынесена в отдельный поток. Но и отсев чисел Лишрел в главном потоке делался слишком медленно по сравнению с операциями RAA, которых из-за его же эффективности становилось значительно меньше.

4 дня я пробовал разные способы. А заработало решение, ошибочно забракованное вначале. Те же решения, что казались перспективными, в итоге были выброшены в мусорную корзину после их реализации и тестирования. Вернувшись к первоначальной идее делать отсев в каждом рабочем потоке, мне удалось загрузить их полностью. Главное, что меня беспокоило — это одновременный доступ потоков к набору отсева для проверки наличия в нём чисел и необходимость добавления при этом в него новых (что нельзя делать одновременно).

Решением стал lock-free алгоритм совместного доступа. Всего 2 атомарные переменные позволили сделать так, чтобы все рабочие потоки могли одновременно иметь доступ на чтение к набору отсева (т.е. проверке наличия в нём числа), а главный поток — эксклюзивный доступ на запись (т.е. добавление новых чисел в набор). Когда накапливается некоторое количество новых чисел Лишрел, главный поток дожидается, пока рабочие потоки закончат проверки, и затем начинает добавление чисел, делая это максимально быстро в один приём. В течение этой непродолжительной операции рабочие потоки не выполняют отсев, а делают обычную проверку в полную глубину, чтобы не простаивать.

Таким образом, удалось добиться одновременной полной загрузки главного и всех рабочих потоков, потеряв не так много в эффективности на синхронизации доступа к набору отсева. Несмотря на отсутствие "тяжёлых" блокировок в алгоритме, необходимость блокировать кеш-линию процессора для атомарного инкремента и декремента счётчика читателей никуда не делась, так же как никуда не исчез и спин-лок в главном потоке при ожидании доступа на запись.

Так, по сравнению с однопоточным алгоритмом, для 6-ти поточного эффективность снизилась примерно на 15%. То есть, то, что 6 "новых" потоков в сумме делают за 600 секунд (6 по 100 каждый), 1 "старый" поток делал за 522 секунды. Но зато теперь не нужно запускать на одном ПК 4 (или даже 6) копий программы, каждая из которых проверяет свой небольшой участок диапазона, а потом ещё объединять результаты их работы. Одна единственная копия новой программы, используя по максимуму ресурсы ПК (ЦП + ОЗУ), делает это примерно в 5.2 раза быстрее (на 6-ядерном процессоре).

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


18 ноября 2020

Последние два дня я потратил на то, чтобы попытаться сделать алгоритм RAA быстрее. Прошлая большая оптимизация этого алгоритма заключалась в переходе от обработки цифр числа по 4 к обработке по 8 цифр за раз, что было возможно только в 64-битных конфигурациях. На этот раз идея заключалась в том, чтобы каким-то образом задействовать SIMD-инструкции.

Вообще говоря, SIMD — это немного о другом: из-за того, что нам нужно учитывать перенос из старших разрядов, мы не можем "обрабатывать" цифры числа параллельно, поэтому особую выгоду от SIMD получить сложно. Однако, в наборе инструкций SSSE3 (доступном, начиная с Intel Core 2) есть очень полезная инструкция pshufb (интринсик _mm_shuffle_epi8), которая является более функциональным SSE-аналогом инструкции bswap, но "переставляет" 16 байт за раз. Плюс, с помощью SSE оказалось намного проще генерировать маску после сложения, что дало в результате меньше инструкций на цикл.

В итоге, переписанный на SSE алгоритм RAA стал быстрее в 2.25 раза в 32-битной конфигурации и в 1.47 раза в 64-битной. 32-битный код получил значительно больший прирост из-за того, что ранее в его цикле обрабатывалось по 4 цифры числа (32 бита регистра общего назначения), а теперь — по 16 (128 бит регистра XMM). Но так как, во-первых, цикл стал "длиннее" в тактах CPU, и во-вторых, алгоритм RAA состоит также из сложения оставшихся цифр (при длине числа, не кратной 16), проверки палиндрома, копирования временного буфера (в конце работы) и кода инициализации, скорость работы выросла менее, чем в 4 раза (то же самое справедливо и для 64-битной версии алгоритма).

Тем не менее, 47% — это весьма существенный прирост производительности! Как и ожидалось, самый значительный эффект наблюдается для длинных чисел (для них подавляющая часть времени работы приходится именно на SSE-цикл сложения). Так, время, необходимое на выполнение операций RAA над числом Лишрел 196 до достижения им длины в 1 миллион знаков, уменьшилось с 4 минут 50 секунд до 2 минут 49 секунд, т.е. в 1.72 раза для x64 (в 3.25 раза для x86)!

Делая изменения в коде алгоритма, я обнаружил, что то, что должно по моему мнению работать быстрее, на самом деле не даёт никакого эффекта или даже наоборот, уменьшает скорость работы. Мне стало интересно, почему код, показывающий лучшие результаты в тесте, проигрывает в скорости работы при реальном поиске чисел. Оказалось, что мой старый тест, в котором я просто делал 400 операций RAA над 14-значным числом Лишрел, плохо подходит, потому что совершенно не похож на то, что делает сейчас программа при поиске отложенных палиндромов. Нужно отметить, что тест был написан очень давно, для одной из первых версий программы без отсева чисел Лишрел, а с тех пор в основном алгоритме поиска было сделано много изменений.

После доработки теста всё встало на свои места. Более того, небольшие изменения в других частях алгоритма (за пределами основного цикла сложения) позволили теперь получить ещё около +7% к скорости работы. Раньше, пытаясь делать похожие изменения, из-за неудачно выбранного теста я просто не видел, как они на самом деле влияют на скорость проверки чисел.


16 ноября 2020

Диапазон 20-значных чисел проверен уже на 92.6%, но есть кое-что, что помешает мне его сейчас закончить. Дело в том, что раньше в базе данных не сохранялись сведения о полном количестве обнаруженных чисел Лишрел (сохранялось только количество проверенных первичных чисел). Из-за этого вычисление полного количества чисел Лишрел требовало очень большого объёма работы, сравнимого с самим поиском.

По этой причине с октября программа сохраняет результаты в БД нового формата, которая содержит больше полезной информации. Но теперь требуется "обновить" старую БД для уже проверенного 18- и 19-значного, а также начала 20-значного диапазонов. На это потребуется ещё примерно 3 недели. И так как обновление не может выполняться в несколько потоков, я решил заново "перепроверить" часть 19-значного и начало 20-значного диапазонов, уменьшив тем самым объём БД, который понадобится обновить. Как итог, будет сэкономлено время, а процессор будет занят полезной работой.

С середины прошлой недели диапазон 21-значных чисел проверяется на отдельной машине в 3 потока в режиме 24/7. Поэтому далее процесс поиска пойдёт намного веселее.


5 ноября 2020

Сегодня в начале девятого вечера был найден новый отложенный палиндром: 20-значное число 70,000,000,000,507,277,299, дающее палиндром за 253 шага. Это последний из 6 известных отложенных палиндромов среди 20-значных чисел. Диапазон проверен на 77.753%, до завершения остаётся около двух недель.

Почти все мои вычислительные мощности сейчас сосредоточены на диапазоне 20-значных чисел, чтобы как можно скорее завершить его проверку. И пока процесс идёт даже быстрее, чем я ожидал. Диапазон 21-значных чисел, как и раньше, проверяется в 1 поток: на данный момент проверено 2.155% чисел.

Достижения дня: найден отложенный палиндром для шага 253.


14 октября 2020

Сегодня около половины девятого вечера были найдены 2 новых отложенных палиндрома: 20-значное число 10,200,000,000,065,287,900, дающее палиндром за 257 шагов, и 20-значное число 10,200,000,000,708,183,947, дающее палиндром за 254 шага.

Продолжаю поиск в диапазоне 20-значных чисел (3 потока), на данный момент проверено 27.8% чисел. И в диапазоне 21-значных чисел (1 поток), проверено 1.958% диапазона. За последние 144 часа было проверено примерно 8.1% всех 20-значных чисел. Если скорость будет такой же для оставшейся части диапазона, то ориентировочно через 53 дня, в воскресенье 6 декабря я должен закончить 20-значные числа. Предыдущие версии программы проверили около 14.5% диапазона за 321 день, работая в 1 поток (что примерно в 10 раз медленнее в пересчёте на 1 поток, но без учёта того, что именно первые ~15% диапазона — самые "трудные").

Достижения дня: найдены отложенные палиндромы для шагов 254 и 257.


12 октября 2020

Сегодня я хочу снова вернуться к вопросу отсева чисел Лишрел. И сначала рассказажу о результатах экспериментов с длиной чисел, добавляемых в набор отсева. Вот небольшая таблица с интересными цифрами:

Диапазон Первичных
чисел Лишрел
Проверено
чисел Лишрел
Отсеяно
чисел Лишрел
Отсеяно чисел
Лишрел в %
3 3 2 1 33.33%
4 12 5 7 58.33%
5 248 74 174 70.16%
6 939 173 766 81.58%
7 14,405 1,901 12,504 86.80%
8 38,639 3,552 35,087 90.81%
9 499,014 31,714 467,300 93.64%
10 1,163,706 57,494 1,106,212 95.06%
11 13,562,892 431,925 13,130,967 96.82%
12 29,164,434 786,640 28,377,794 97.30%
13 319,286,794 5,238,388 314,048,406 98.36%
14 653,494,940 9,693,941 643,800,999 98.52%
15 6,894,142,797 59,130,369 6,835,012,428 99.14%
16 13,712,115,652 112,094,957 13,600,020,695 99.18%

Длина чисел в наборе была равна 30 знакам. Данные приведены до диапазона 16-значных чисел включительно (весь набор отсева в оперативной памяти). Так как полный набор для 17-значного диапазона содержит очень много чисел, то в оперативной памяти умещается лишь его часть, что сильно снижает эффективность отсева. И поэтому не имело смысла сравнивать её с эффективностью для полного набора.

Выбранная длина (чисел в наборе) напрямую влияет на скорость работы: чем она больше, тем больше операций RAA приходится выполнять и тем ниже скорость. Однако снижение длины также приводит к снижению эффективности отсева (т.е. в наборе обнаруживается меньше чисел). Задача эксперимента состояла в том, чтобы найти такую минимальную длину, при которой падение эффективности отсева компенсировалось бы увеличением скорости проверки чисел в наборе. Так как проверить нужно было все возможные длины, начиная от длины чисел диапазона до максимально возможной длины в 30 знаков, на это потребовалось много времени, поэтому я ограничился максимум 14-значным диапазоном. Полный лог эксперимента можно скачать здесь.

Оказалось, что при длине числа в наборе на 3 знака большей, чем длина чисел диапазона, время работы было наименьшим в большинстве случаев. Однако в других тестах, где размер набора был недостаточен, лучшее время получалось при длине чисел в наборе, большей на 4, 5 или 6 знаков, чем длина чисел диапазона. Вот пример для 13-значного диапазона (размер набора ~1.83M чисел):

Range: 13-digit, primary Lychrels found: 319,286,794
----------------------------------------------------
LEN=22, SIFTED=276,933,460 (86.74%), TIME=333.97s [SET TRUNCATED]   // +9
LEN=21, SIFTED=276,894,298 (86.72%), TIME=327.38s [SET TRUNCATED]   // +8
LEN=20, SIFTED=276,805,226 (86.69%), TIME=323.45s [SET TRUNCATED]   // +7
LEN=19, SIFTED=276,513,335 (86.60%), TIME=312.25s [SET TRUNCATED]   // +6
LEN=18, SIFTED=275,917,400 (86.42%), TIME=307.86s [SET TRUNCATED]   // +5
LEN=17, SIFTED=273,536,783 (85.67%), TIME=314.42s [SET TRUNCATED]   // +4
LEN=16, SIFTED=269,027,138 (84.26%), TIME=329.34s [SET TRUNCATED]   // +3
LEN=15, SIFTED=239,960,945 (75.16%), TIME=425.05s [SET TRUNCATED]   // +2 к длине

Общая эффективность заметно снизилась: с 97.99% (#16) отсеянных чисел до 86.42% (#18) (размер набора при этом был меньше необходимого примерно в 3 раза). А изменение длины чисел в наборе стало иметь более выраженный эффект. Таким образом, здесь повышение длины на 2 знака и вызванные этим дополнительные операции RAA компенсируются более существенным повышением "отсеиваемости" чисел Лишрел. Аналогично обстоят дела и в других (старших) диапазонах, например, в 20-значном. Даже при размере набора отсева, в десятки раз меньше необходимого, и ещё большем снижении общей эффективности отсева, закономерность, наблюдаемая при изменении длины чисел в наборе отсева, сохраняется.

Следующая большая таблица, на мой взгляд, ещё интереснее. В ней собраны данные из 12-значного диапазона по количеству отсеянных чисел Лишрел при разных размерах набора отсева, разбитые на 20 частей по 5% диапазона каждая:

Часть диапазона Последнее
проверенное
число
Всего
чисел Лишрел
Отсеяно чисел Лишрел в %
[Размер набора отсева]
MAX 114.69K 57.34K 28.67K 14.34K
0% - 5% 100,024,998,489 843,119 51.57% 23.16% 13.83% 9.00% 6.11%
5% - 10% 100,303,949,978 1,423,143 89.58% 30.00% 20.32% 8.67% 4.74%
10% - 15% 100,909,979,467 1,459,214 95.80% 44.00% 31.77% 11.48% 5.25%
15% - 20% 103,981,999,956 1,391,873 97.26% 58.36% 44.78% 26.86% 19.35%
20% - 25% 107,007,980,945 1,437,356 98.45% 58.87% 45.38% 27.86% 20.28%
25% - 30% 110,086,998,394 1,464,826 98.91% 62.00% 46.98% 28.38% 21.16%
30% - 35% 129,060,999,993 1,389,798 98.16% 75.05% 63.56% 49.83% 44.46%
35% - 40% 143,808,939,992 1,451,125 97.88% 73.82% 60.82% 44.61% 37.74%
40% - 45% 160,500,289,591 1,432,703 98.94% 75.48% 64.06% 47.97% 40.57%
45% - 50% 180,004,903,290 1,486,600 99.63% 75.84% 64.04% 51.11% 45.88%
50% - 55% 196,050,195,990 1,553,524 99.15% 78.85% 63.76% 48.40% 42.90%
55% - 60% 260,044,996,499 1,450,981 99.95% 92.58% 84.15% 74.07% 71.50%
60% - 65% 340,165,999,699 1,405,212 99.65% 93.34% 87.38% 77.95% 75.26%
65% - 70% 420,506,989,899 1,510,514 99.97% 93.32% 85.95% 77.13% 74.67%
70% - 75% 509,000,342,999 1,479,158 99.54% 93.63% 87.19% 78.14% 76.14%
75% - 80% 605,067,997,999 1,451,589 99.96% 93.39% 86.36% 77.00% 75.05%
80% - 85% 701,652,999,999 1,553,836 99.57% 93.51% 85.96% 77.59% 76.07%
85% - 90% 800,443,999,199 1,601,016 99.96% 93.30% 84.20% 77.00% 75.69%
90% - 95% 900,040,096,099 1,765,407 99.57% 94.52% 87.54% 81.04% 80.08%
95% - 100% 999,999,999,999 1,613,440 99.96% 98.04% 92.51% 86.54% 85.37%
Все числа 29,164,434 97.21% 76.74% 66.76% 54.76% 50.70%

На основании полных данных эксперимента можно сделать 2 основных вывода. Первый. В самом начале диапазона (примерно до 2% для 12-значных, до 1% для 13-значных, до 0.16% для 19-значных) преобладают отложенные палиндромы низких шагов, а чисел Лишрел сравнительно мало. В остальной части диапазона числа Лишрел распределены практически равномерно, средняя частота их встречаемости едва заметно растёт от начала диапазона к его концу.

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

Совсем иначе обстоят дела в случаях, когда размер набора недостаточен. В этих случаях наблюдается существенный рост эффективности отсева от начала диапазона (около 5% для набора, меньшего в 55 раз) к концу диапазона (85% для того же набора). Причём рост эффективности происходит скачкообразно, начиная с чисел 100,100,... (усреднённая эффективность отсева 12%), затем 101,000,... (20-30%), затем 110,000,... (40-50%), и 200,000,... (70-80%). К самому концу диапазона (от чисел 800... и 900... наблюдаются ещё 2 подъёма: до примерно 80% и 85% в среднем соответственно.

Сравнение данных между разными по размеру наборами отсева подтверждает сделанный ранее вывод о том, что чем больше размер набора, тем в целом выше эффективность отсева и скорость поиска.


10 октября 2020, "Глубина поиска"

Пришло время написать о глубине поиска. В предыдущей версии программы я использовал фиксированную глубину поиска в 650 шагов для всех диапазонов, и лишь для 21-значных чисел её значение было ниже — 565 шагов. Ещё 10 июня прошлого года я говорил о том, что, вероятно, это очень большая глубина и что нужно выполнить статистический анализ и выяснить, можно ли использовать меньшую глубину поиска, оставив при этом разумно низкой вероятность пропуска нового палиндрома. Но, скорее всего, из-за того, что в младших диапазонах поиск не был таким уж и медленным, я откладывал это раз за разом. Но сейчас, когда вопрос о скорости поиска в диапазонах 20- и 21-значных чисел встал в полный рост, я решил, наконец, это сделать.

Задача заключалась в том, чтобы найти зависимость между номером диапазона (т.е. длиной числа) и наибольшим найденным в этом диапазоне шагом. Я взял 20 пар значений (так как на данный момент уже известны наибольшие шаги палиндромов во всех диапазонах чисел от 1-значных до 20-значных). И оказалось, что значения имеют очень сильную корреляцию (99.18%). Далее я попытался применить линейную регрессию, вычислить её коэффициенты и выяснить значение стандартного отклонения. Оказалось, что при коэффициентах 14.211 и -16.968, стандартное отклонение равно 10.58. Что есть очень и очень хорошо!

Говоря человеческим языком, расчётную глубину поиска можно вычислить по формуле: D = N * 14.211 - 16.968, где D — это глубина поиска, а N — номер диапазона. Отклонение 10.58 шага означает, что в среднем значение D отклоняется на 10.58 от истинного.

Разумеется, полученное значение глубины поиска нельзя применять в исходном виде: из-за того, что формула лишь приблизительно описывает истинную закономерность, результат тоже будет не идеально точным. Чтобы снизить вероятность выбора недостаточной глубины, мы должны добавить к полученному значению некоторое количество сигм (так называют стандартное отклонение). Так, если мы добавим 1 сигму, то получим вероятность того, что глубина окажется недостаточной, равную примерно 15.9% (что чудовищно много), для 2 сигм значение уменьшится до 2.28%, для 3 сигм — до 0.135% (здесь мы полагаем, что величина имеет нормальное распределение).

Другими словами, добавляя сигмы, мы как бы берём значение с "запасом", чтобы наверняка не ошибиться. И чем больше сигм мы возьмём, тем ниже будет вероятность ошибки. Но брать слишком много сигм так же нет никакого смысла. Я выбрал значение 6 сигм, что даёт вероятность ошибки немного лучше, чем 1:1,000,000,000 (1 к миллиарду). Это очень низкая вероятность. Ниже приведена таблица с полученными значениями достаточной глубины для всех диапазонов с 1-го по 22-й с учётом шести сигм:

Диапазон Наибольший шаг Глубина поиска Диапазон Наибольший шаг Глубина поиска
1261 12149218
22475 13188232
32390 14186246
421104 15201260
555118 16197274
664132 17236289
796147 18232303
896161 19261317
998175 20258331
10109189 21345
11149203 22360

Из этой таблицы видно, что если не брать во внимание диапазоны с 1-го по 6-й, то "запас" глубины оказывается равным от x1.21 (для 19-значных чисел) до x1.79 (для 9-значных), и что полученные значения намного меньше, чем изначально выбранное мной значение 650 шагов. Результаты тестирования программы (см. таблицу в предыдущей записи от 9 октября) наглядно показывают разницу в скорости поиска с фиксированной глубиной в 650 шагов и новыми значениями глубины поиска для каждого диапазона чисел.


9 октября 2020, "Отсев чисел Лишрел"

Сегодня я хочу рассказать об отсеве чисел Лишрел... Как-то раз, одной летней ночью, где-то в конце июня, мне не спалось. Я лежал и думал о том, как именно отсеиваются числа Лишрел в программе. И вдруг неожиданно мне пришло понимание того, что всё на самом деле может быть намного проще! Сама мысль была настолько простой и очевидной, что я не мог понять, почему я не додумался до этого раньше, и вместо простого способа изобрёл велосипед. Но пользуясь моментом, расскажу сначала о том, как это раньше работало.

Сама суть "отсева" заключается в том, что начиная проверять очередное число, мы пытаемся быстро определить, не сходится ли оно за какое-то (сравнительно небольшое) количество операций RAA к какому-нибудь уже проверенному числу Лишрел (а строже говоря, к потоку какого-либо проверенного ранее базового числа Лишрел). И если да, то нам не придётся выполнять намного больше операций RAA, чтобы проверить, является ли число палиндромом. О большой эффективности такой оптимизации я писал ранее в дневнике и о сопутствующих ей проблемах (большом количестве требуемой памяти, снижении эффекта в старших диапазонах) — тоже.

В записи от 30 июня 2019 года я писал о том, что для эффективного отсева, найденное число Лишрел, перед тем, как его поместить в набор (список), нужно "провернуть" какое-то количество раз. Т.е. сначала выполнить над ним несколько (12, если точно) операций RAA и только потом добавить в набор то, что получилось. А при поиске в наборе, аналогично, над тестируемым числом нужно было выполнить 6 операций RAA, а затем 9 итераций цикла, в каждой выполняя ещё по одной операции RAA + поиск в наборе. Эта схема — 12-6-9 — была выбрана в результате долгих тестов таким образом, чтобы не потерять в эффективности отсева и при этом не слишком снизить скорость работы этого велосипеда. Сложно, не правда ли?

Причина столь странной схемы в том, что мы не можем знать, через какое количество операций RAA проверяемое число может сойтись с потоком, и поэтому проверяем несколько (9) вариантов в надежде, что какой-то сработает... Однако, на самом деле нам и не нужно этого знать! Как я уже сказал, всё намного проще. Так как наше число мы сравниваем с числом из набора, то для того, чтобы они были равны, как минимум необходимо, что были равны их длины! Другими словами, весь секрет в том, чтобы добавлять в набор числа одинаковой (заранее выбранной) длины, а при проверке числа, сначала выполнять над ним операции RAA до достижения им такой же длины и только потом проверять его наличие в наборе.

Такой способ экономит кучу времени! Мы не только не делаем "лишние" операции RAA, но ещё и экономим на проверках наличия числа в наборе! Причём второе в большой степени происходит из-за нерациональности внутреннего устройства моей хеш-таблицы: главной задачей было сэкономить память, но я сделал это в ущерб производительности проверки присутствия числа в наборе (но, пожалуй, лучше будет рассказать об этом в другой раз, когда дойдут руки до оптимизации хеш-таблицы). Если коротко, то суть проблемы в том, что числа (элементы) в односвязном списке хеш-таблицы расположены друг от друга на очень большом расстоянии в памяти и поэтому, проверяя каждый раз их все (при отсутствии числа в наборе, а чаще всего оно отсутствует), мы каждый раз имеем кеш-промахи и простои CPU в ожидании данных из медленной оперативной памяти. Теперь же (в новом способе) такая проверка делается всего 1 раз, а не 9 как раньше!

В качестве проверки моих рассуждений, я выполнил поиск чисел от самого начала до 21.409% 17-значного диапазона. И сравнил время работы новой версии программы с версией от 3 июля 2019 года (глубина поиска 650 шагов; не считая мелких оптимизаций, различие только в новом способе отсева чисел Лишрел и немного меньшем объёме используемой памяти в новой версии: 9.5 Гб против 10.6 Гб):

Диапазон Старая версия
(без отсева)
Версия от 03.07.2019
(старый способ отсева)
Новая версия
(новый способ отсева)
Новая версия
(новый способ отсева + меньшая глубина поиска)
1-значные числа 00:00:00 00:00:00 00:00:00 00:00:00
• • • • • • • • • • • • • • •
7-значные числа 00:00:00 00:00:00 00:00:00 00:00:00
8-значные числа 00:00:02 00:00:00 00:00:00 00:00:00
9-значные числа 00:00:15 00:00:02 00:00:02 00:00:01
10-значные числа 00:00:53 00:00:05 00:00:05 00:00:03
11-значные числа 00:09:03 00:00:42 00:00:33 00:00:21
12-значные числа 00:26:27 00:01:28 00:01:08 00:00:46
13-значные числа 03:37:28 00:10:11 00:07:09 00:04:49
14-значные числа 10:44:06 00:24:27 00:16:16 00:12:06
15-значные числа 90:13:06 03:21:13 01:51:19 01:27:53
16-значные числа 281:49:49 08:40:19 04:28:01 03:42:41
21.409% диапазона 17-значных чисел 617:23:55 51:44:10 20:56:30 13:01:22

Можно видеть, что до 17-значного диапазона новая версия программы с отсевом имела практически 30-кратное преимущество в скорости работы над старой версией программы без отсева чисел Лишрел. Это подтверждает мои эксперименты, в которых я выяснил, что за 2 и более шага сходятся около 97% всех тестируемых чисел Лишрел. Однако, 10.6 Гб оперативной памяти, используемых программой, хватило лишь до примерно 3.5% чисел 17-значного диапазона, после чего началось активное замещение чисел в наборе и эффективность отсева значительно снизилась, сократив итоговое преимущество новой версии до примерно 12 раз.

Также хорошо заметно, что преимущество растёт по мере движения к старшим диапазонам (от примерно x7 для всех чисел до 9-значных включительно, до примерно x36 для диапазона 16-значных чисел). Так происходит потому, что от диапазона к диапазону количество чисел Лишрел (которые мы должны протестировать и которые мы способны отсеять) непрерывно растёт: в 3-значном диапазоне у нас 1.67% чисел Лишрел относительно всех тестируемых чисел, в 4-значном — 3.51%, в 5-значном — 7.25%, потом 14.45%, 22.17%, 31.30% и так далее, до 88.03% в 17-значном диапазоне.

Эта же закономерность наблюдается между преимуществом программы со старым способом отсева и программы с новым способом. Так, до 10-значного диапазона включительно разница в скорости их работы незаметна совсем. Для диапазонов 11- и 12-значных чисел преимущество составляет примерно по 30%, для 13-значных — 44.9%, для 14-значных — 56.5%, для 15-значных — 86.0%, а для 16-значных — внушительные 103.6%! В общем итоге новый способ отсева чисел Лишрел сделал поиск быстрее в 2.47 раза! Шикарный результат!

Update: Добавил в таблицу ещё одну колонку с таким же тестом для программы с новым способом отсева и сниженной глубиной поиска. Заметно, что снижение глубины поиска даёт ускорение работы. Но из-за высокой эффективности отсева чисел Лишрел, преимущество остаётся не слишком значительным (около 20%) до конца 16-значного диапазона. А вот в диапазоне 17-значных чисел ситуация уже совершенно иная. Из-за снижения эффективности отсева влияние глубины RAA на общую скорость поиска стало значительно больше. Что в общем итоге привело к увеличению скорости работы ещё в 1.61 раза по сравнению с предыдущей версией программы.


8 октября 2020

Сегодня, после почти недели рефакторинга и доработки кода поиск был возобновлён! Теперь сразу в 4 потока: 3 потока на 20-значных числах и 1 поток на 21-значных! Также, новый более быстрый алгоритм отсева чисел Лишрел (расскажу об этом в следующий раз) и сниженная глубина поиска (вычисленная с помощью линейной регрессии, об этом тоже позже) позволили значительно ускорить поиск в обоих проверяемых диапазонах чисел в расчёте на 1 поток. Так что дальше будет веселее!

Очень много изменений было сделано в коде базы данных, а её формат обновлён до 4-й версии. Теперь в файлах БД сохраняется полное количество чисел Лишрел, так как это достаточно несложно сделать во время поиска (но значительно сложнее посчитать потом). Начиная с шага 45, сохраняются все числа без исключений, что, с одной стороны привело к сильному увеличению размера БД (речь идёт о десятках гигабайт), но с другой стороны имеет ряд положительных моментов, связанных с экспортом данных и анализом БД.

Отложенные палиндромы до шага 45, по прежнему сохраняются только для младших диапазонов: шаги с 1 по 11 сохраняются для всех диапазонов до 12-значного включительно; шаги с 12 до 33 сохраняются для всех диапазонов до 13-значного включительно; шаги с 34 до 44 сохраняются для всех диапазонов до 14-значного включительно. А начиная с 15-значного диапазона, сохраняются только отложенные палиндромы для шагов от 45 и выше (ранее всегда сохранялись только числа для шагов от 133).

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


3 октября 2020

Наступил октябрь. Уже более 4 месяцев я не занимаюсь проектом, вычисления не ведутся. 24 мая я разобрал второй ПК, полностью прекратив поиск в 20- и 21-значном диапазонах. В апреле и начале мая я занимался новым кодом базы данных, которым было бы удобно пользоваться: до этого кода для чтения/анализа БД вообще не было, а код сохранения данных был написан на скорую руку в процедурном стиле. В общем, эта часть проекта требовала серьёзного рефакторинга. Но нагрузка на основной работе заставила меня сделать перерыв. И вот только сейчас у меня снова появилось достаточно времени, чтобы вернуться к проекту.

В ближайшие дни я планирую закончить рефакторинг (т.к. в текущем состоянии код уже не работает после начатых изменений) и возобновить поиск в 20- и 21-значном диапазонах чисел.


9 апреля 2020, "Все 19-значные"

Сегодня рано утром в 5:52 была завершена проверка диапазона 19-значных чисел. Всего на проверку всех чисел диапазона потребовалось 272 дня. Первая часть диапазона до числа 1,000,032,046,929,951,459 проверялась старой версией программы в течение 30 дней и 22 часов. Вторая (значительно большая) часть диапазона была проверена новой версией с отсевом чисел Лишрел за 241 день.

Среди всех 19-значных чисел были обнаружены 2,823,374,612,612 первичных чисел Лишрел (всего было проверено 3,057,041,347,380 кандидатов). Таким образом, лишь 233,666,734,768 числа стали палиндромами, а приблизительно 92.36% всех кандидатов оказались числами Лишрел. Всего в диапазоне были найдены 8 новых наименьших отложенных палиндромов (шаги 217, от 224 до 226, а также шаги от 258 до 261).

Достижения дня: завершена проверка 19-значных чисел.


1 апреля 2020

Сегодня в 7:24 был найден новый отложенный палиндром: 19-значное число 9,000,000,000,255,353,839, дающее палиндром за 224 шага. Это последний из 8 известных отложенных палиндромов среди 19-значных чисел. Диапазон проверен на 94.474%, до завершения остаётся примерно две недели.

Достижения дня: найден отложенный палиндром для шага 224.


6 февраля 2020

Сегодня в 7:35 был найден новый отложенный палиндром: 19-значное число 3,000,000,022,999,288,679, дающее палиндром за 258 шагов.

Достижения дня: найден отложенный палиндром для шага 258.


3 февраля 2020

Сегодня в 16:58 был найден новый отложенный палиндром: 20-значное число 10,022,000,904,998,799,523, дающее палиндром за 255 шагов. На сегодняшний день проверены 1.286% всех 21-значных, 9.385% всех 20-значных, и 59.61% всех 19-значных чисел.

Достижения дня: найден отложенный палиндром для шага 255.


29 декабря 2019, "Первый в 21-значных"

Сегодня в 14:34 (UTC+10) был найден новый отложенный палиндром: 21-значное число 100,000,081,000,999,940,726, дающее палиндром за 252 шага. Это первый из новых наименьших отложенных палиндромов в диапазоне 21-значных чисел!

Отдельно хочу сказать о результатах Rob van Nobelen, которые Джейсон Дусетт опубликовал в конце августа этого года на странице своего проекта (скриншот). Там сказано, что им был проверен весь диапазон 21-значных чисел, и что в нём были найдены ранее неизвестные отложенные палиндромы для шагов 251 и 252 (остальные обнаруженные им новые отложенные палиндромы для шагов от 238 до 241 и от 245 до 250 относятся к диапазону 23-значных чисел). Дело в том, что поиск им вёлся непоследовательно, а указанные им числа не являются наименьшими отложенными палиндромами. Так, например, для шага 252 он приводит число 200,500,000,000,690,299,779, не являющееся наименьшим числом, которое становится палиндромом за 252 шага. Другими словами, приведённые им числа, — это некоторые случайно выбранные числа из соответствующих множеств всех отложенных палиндромов, разрешающихся за указанное количество шагов.

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

Достижения дня: найден отложенный палиндром для шага 252.


24 ноября 2019, "261 шаг"

Сегодня в 13:35 (UTC+10) был найден новый отложенный палиндром и установлен локальный рекорд: 19-значное число 1,186,060,307,891,929,990, дающее палиндром за 261 шаг. Это последний рекорд Джейсона Дусетта, установленный 30 ноября 2005 года, и являвшийся до недавнего времени мировым рекордом среди наиболее отложенных палиндромов.

С момента запуска проекта MDPN прошло 5 месяцев и 22 дня (всего 175 дней). За это время были полностью проверены диапазоны чисел от 1-значных до 18-значных, и примерно треть всех 19-значных чисел. От следующего известного мирового рекорда (288 шагов) меня отделяет громадное количество чисел, которые необходимо проверить, во много раз большее количества уже проверенных мной чисел. Так что это займёт какое-то время.

Достижения дня: найден отложенный палиндром для шага 261.


26 октября 2019

Сегодня вечером в 17:07 был найден новый отложенный палиндром: 19-значное число 1,060,000,000,523,124,995, дающее палиндром за 226 шагов. На сегодняшний день проверены 23.1% всех 19-значных чисел.

Достижения дня: найден отложенный палиндром для шага 226.


4 сентября 2019, "260 шагов"

Сегодня в 16:04 был найден новый отложенный палиндром и установлен локальный рекорд: 19-значное число 1,003,062,289,999,939,142, дающее палиндром за 260 шагов.

Скорость проверки чисел значительно меньше по сравнению с предыдущими диапазонами, так как оптимизация отсева не даёт такого же эффекта из-за огромных требований к размеру таблицы (в данный момент программа использует 10.6 Гб оперативной памяти, что в десятки раз меньше необходимого для эффективной работы объёма). К данному моменту проверены лишь 10.256% всех 19-значных чисел. А у меня пока нет времени на проект, чтобы наконец-то реализовать распределённые вычисления. Так что он работает в автономном режиме: вычисления ведутся одновременно на 2 ПК, проверяются диапазоны 19-, 20- и 21-значных чисел.

Достижения дня: найден отложенный палиндром для шага 260.


1 сентября 2019

Несколько дней назад я обнаружил, что информация на странице Джейсона Дусетта была обновлена. Оказывается, что 26 апреля 2019 года Rob van Nobelen, проверяя диапазон 23-значных чисел, нашёл новый мировой рекорд среди отложенных палиндромов: 23-значное число 12,000,700,000,025,339,936,491, которое становится 142-значным палиндромом за 288 шагов!

Помимо нового рекорда, в диапазонах 21- и 23-значных чисел им были найдены (ранее неизвестные) отложенные палиндромы для шагов: 238, 239, 240, 241, а также для шагов с 245 до 252. Rob сообщает, что проверил все 21-значные числа, но пропустил диапазон 22-значных, полагая, что вероятность найти новый рекорд будет выше в следующем за ним нечётном диапазоне.

Немного странно, что информация об этом рекорде появилась с такой большой задержкой. Выходит, что этот рекорд был найден примерно за месяц до старта моего проекта. Не знаю, с какой скоростью Rob проверяет сейчас диапазон 23-значных чисел, и как долго он уже это делает... Но с его слов, на конец апреля им были проверены примерно 2% диапазона (что соответствует 22 триллионам кандидатов). При моей текущей скорости проверки мне понадобится около 7 лет, чтобы проверить такое количество чисел.


24 июля 2019, "Все 18-значные"

Сегодня ночью в 4:15 была завершена проверка диапазона 18-значных чисел. Всего на проверку всех чисел диапазона потребовалось чуть более 30 дней. Первая часть диапазона до числа 101,004,400,809,971,994 проверялась старой версией программы в течение 17 дней и 22 часов. Вторая часть диапазона была проверена новой версией с отсевом чисел Лишрел за 12 дней и 15 часов.

Среди всех 18-значных чисел были обнаружены 276,826,698,805 первичных чисел Лишрел (всего было проверено 305,704,134,738 кандидатов). Таким образом, лишь 28,877,435,933 числа стали палиндромами, а приблизительно 90.55% всех кандидатов оказались числами Лишрел. Всего в диапазоне были найдены 17 новых наименьших отложенных палиндромов (шаги от 202 до 205, от 211 до 216, от 218 до 222, а также шаги 227 и 228).

Достижения дня: завершена проверка 18-значных чисел.


23 июля 2019

Сегодня днём в 13:04 был найден новый отложенный палиндром: 18-значное число 900,040,000,881,499,569, дающее палиндром за 218 шагов.

Достижения дня: найден отложенный палиндром для шага 218.


21 июля 2019

Сегодня рано утром в 5:47 был найден новый отложенный палиндром: 18-значное число 600,000,000,606,339,049, дающее палиндром за 227 шагов.

Достижения дня: найден отложенный палиндром для шага 227.


19 июля 2019

Сегодня ночью в 4:07 был найден новый отложенный палиндром: 18-значное число 300,000,000,128,545,799, дающее палиндром за 213 шагов. Как и предполагалось, после того как программа достигла "2" в старшем разряде, скорость поиска выросла: если раньше за сутки проверялось примерно 5.0% чисел диапазона, то теперь проверяется 8.98%. Такое увеличение скорости происходило на всех предыдущих диапазонах. Поэтому я рассчитываю на завершение проверки всех 18-значных чисел примерно через 4 дня.

Достижения дня: найден отложенный палиндром для шага 213.


18 июля 2019

Сегодня днём в 12:42 был найден новый отложенный палиндром: 18-значное число 195,030,047,999,791,993, дающее палиндром за 202 шага.

Достижения дня: найден отложенный палиндром для шага 202.


17 июля 2019

Сегодня утром был найден новый отложенный палиндром: 18-значное число 170,500,000,303,619,996, дающее палиндром за 228 шагов.

Достижения дня: найден отложенный палиндром для шага 228.


14 июля 2019

Сегодня утром был найден новый отложенный палиндром: 18-значное число 110,300,361,999,869,090, дающее палиндром за 212 шагов. А вечером были найдены ещё 2 новых 18-значных отложенных палиндрома: число 120,906,490,499,909,290 и число 121,506,542,999,979,993, дающие палиндромы за 216 и 220 шагов соответственно.

Достижения дня: найдены отложенные палиндромы для шагов 212, 216 и 220.


13 июля 2019

Сегодня ночью в 3:18 был найден новый отложенный палиндром: 18-значное число 106,096,507,979,997,951, дающее палиндром за 221 шаг.

Достижения дня: найден отложенный палиндром для шага 221.


12 июля 2019

Сегодня в 12:46 был найден новый отложенный палиндром: 18-значное число 104,300,000,514,769,945, дающее палиндром за 214 шагов.

Достижения дня: найден отложенный палиндром для шага 214.


10 июля 2019, "Все 17-значные"

Сегодня в 14:30 был найден новый отложенный палиндром: 18-значное число 100,980,800,839,699,830, дающее палиндром за 222 шага. А в 15:11 была завершена проверка диапазона 17-значных чисел. Всего на проверку всех чисел диапазона потребовалось 6 дней 14 часов 10 минут и 53 секунды. А на проверку всех чисел от 1 до самого большого 17-значного новой версии программы с отсевом сходящихся чисел Лишрел понадобилось 6 дней 22 часа 51 минута и 12 секунд. Проверка всех 17-значных чисел заняла значительно большее время, чем проверка всех предыдущих диапазонов. Причина проста — оптимизация отсева стала менее эффективной из-за того, что в этом диапазоне чисел Лишрел настолько много, что их не удалось уместить даже в 10.6 Гб оперативной памяти.

На данный момент размер базы данных отложенных палиндромов составляет 75.4 MiB, в 1067 файлах базы содержится 22,171,731 первичное число. Найдены все наименьшие отложенные палиндромы для шагов от 1 до 201, а также от 206 до 210 и от 229 до 236. Суммарное количество всех отложенных палиндромов, которые можно экспортировать из базы, превышает 765 миллиардов (не менее 1 миллиарда первых отложенных палиндромов для каждого количества шагов от 1 до 145).

Достижения дня: найден отложенный палиндром для шага 222; завершена проверка 17-значных чисел.


9 июля 2019

Сегодня поздно вечером был найден последний известный отложенный палиндром в 17-значном диапазоне: число 79,000,000,445,783,599, дающее палиндром за 229 шагов. До завершения проверки всех 17-значных чисел остается около 10.5%. При текущей скорости поиска это займет около 15 часов.

Достижения дня: найден отложенный палиндром для шага 229.


8 июля 2019

Сегодня ночью были найдены 2 новых отложенных палиндрома: 17-значное число 20,005,000,862,599,819, дающее палиндром за 206 шагов, и 18-значное число 100,710,000,333,399,973, дающее палиндром за 204 шага.

Достижения дня: найдены отложенные палиндромы для шагов 204 и 206.


7 июля 2019

Сегодня в 12:14 был найден новый отложенный палиндром: 18-значное число 100,700,000,509,609,622, дающее палиндром за 215 шагов. Позже в 19:32 был найден первый отложенный палиндром в диапазоне 20-значных чисел: число 10,000,000,039,395,795,416, дающее палиндром за 256 шагов! А ещё через 1 час и 5 минут был найден очередной палиндром: 20-значное число 10,000,000,039,513,841,287, дающее палиндром за 223 шага.

Достижения дня: найдены отложенные палиндромы для шагов 215, 223 и 256.


6 июля 2019

Сегодня в 12:10 я начал проверку диапазона 20-значных чисел на G3260, а базу 18-значных чисел перенёс на свой ПК. В данный момент работают 5 потоков, проверяя параллельно все диапазоны от 17-значного до 21-значного. А у меня пока не хватает времени, чтобы доделать многопоточную версию программы (чтобы задействовать все ядра CPU для проверки одного диапазона чисел).

Также сегодня были найдены 3 новых отложенных палиндрома: 17-значное число 11,450,360,479,969,994, дающее палиндром за 207 шагов; 17-значное число 12,000,009,694,736,291, дающее палиндром за 235 шагов; и 17-значное число 12,179,702,595,999,991, которое становится палиндромом за 210 шагов. Согласно проделанной другими исследователями работе, в этом диапазоне остаются ещё 2 отложенных палиндрома, которые я пока не нашёл.

Достижения дня: найдены отложенные палиндромы для шагов 207, 210 и 235.


5 июля 2019

Итак, на данный момент время работы новой версии программы составляет 33 часа и 54 минуты. За это время диапазон 17-значных чисел проверен на 16.436%. Средняя скорость проверки равна 216.69 тыс. чисел в секунду. Это ровно в 7.6 раза больше, чем средняя скорость работы старой версии программы без отсева чисел. Однако, уже достигнув отметки в 3.5%, программа исчерпала всю доступную ей память, и началось замещение элементов хеш-таблицы, что привело к значительно меньшей скорости работы (по сравнению с предыдущими диапазонами). Хорошая новость в том, что скорость остаётся стабильной, и я надеюсь, что, как и в предыдущих диапазонах, она ещё вырастет, начиная примерно от 50% диапазона.

И всё-таки мои ожидания от новой оптимизации не оправдались, и проверка 17-значного диапазона займёт намного больше времени, чем я думал. Новая версия программы не может работать в несколько потоков (вся память уже занята), поэтому на моём ПК так же, как и раньше продолжает работу старая версия, проверяя диапазоны 18- и 21-значных чисел. Я думал о том, что можно сделать работу многопоточной так, чтобы все потоки использовали один набор для отсева, но в этом случае всё очень сильно усложнится, вырастет вероятность где-нибудь напортачить, и на это точно уйдет много времени. В этом смысле переход к использованию SSE + многопоточность должен дать даже лучший результат при примерно тех же временных затратах, но только его эффект будет иметь перманентное действие, то есть это ускорение совершенно не будет ограничено диапазоном.

Update: В 15:12 старой программой был найден новый отложенный палиндром: 17-значное число 10,442,000,392,399,960, дающее палиндром за 236 шагов. А в 20:04 новая версия догнала старую на 21.409% 17-значного диапазона. Затрачено времени новой версией: 1d:19:03:51, старой версией: 13d:23:34:06.

Достижения дня: найден отложенный палиндром для шага 236.


3 июля 2019

Вчера проект отпраздновал свой первый маленький день рождения: ему исполнился ровно один месяц! Новых палиндромов за последние 3 дня найдено не было, и это немного грустно. Но программа работает и усиленно ищет палиндромы в диапазонах 17-, 18-, 19- и 21-значных чисел. Диапазоны чисел от 1-значных до 16-значных включительно уже давно проверены и все локальные рекорды в них найдены. За прошедший месяц было проделано много работы, проведены эксперименты, многие диапазоны были перепроверены по несколько раз, каждый новый раз всё с большей глубиной поиска и всё большей скоростью. На сегодняшний день от новых мировых рекордов меня всё ещё отделяют многие месяцы вычислений. Но я продолжаю искать способы ускорить работу программы и непрерывно её улучшаю.

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

По большей части из спортивного интереса, я перезапустил поиск новой программой с самого начала. На проверку всех диапазонов до 14-значного с глубиной поиска 650 шагов у неё ушло всего 10 минут и 11 секунд! На проверку диапазона 14-значных чисел ушло ещё 14 минут и 16 секунд. Ниже приведена полная таблица времени работы предыдущей и новой версий программы (полное время работы, часы:минуты:секунды):

Диапазон Предыдущая версия Новая версия
1-значные числа 00:00:00 00:00:00
• • • • • • • • •
7-значные числа 00:00:00 00:00:00
8-значные числа 00:00:02 00:00:00
9-значные числа 00:00:15 00:00:02
10-значные числа 00:00:53 00:00:05
11-значные числа 00:09:03 00:00:42
12-значные числа 00:26:27 00:01:28
13-значные числа 03:37:28 00:10:11
14-значные числа 10:44:06 00:24:27
15-значные числа 3 дня + 18:13:06 03:21:13
16-значные числа 11 дней + 17:49:49 08:40:19
21.409% диапазона 17-значных чисел* 25 дней + 17:23:55 2 дня + 03:44:10

Позже, когда новая программа догонит старую в 17-значном диапазоне, я дополню таблицу значениями времени, затраченного обеими версиями на достижение той точки в 17-значном диапазоне, в которой они сойдутся. В данный момент, диапазон 17-значных чисел проверен старой программой на 18.690%, затрачено времени 12d:03:28:57. По моему очень приблизительному расчёту новая программа (если ей хватит размера набора, а ей, скорее всего, его хватит до 3/4 диапазона 17-значных чисел) закончит проверять все 17-значные числа поздно вечером 5 июля.

Думаю, что стоит рассказать и о технических моментах. Мне удалось добиться снижения расхода памяти до 20 байт на 1 число набора: 16 байт занимает само число (1 байт длины числа и 30 знаков числа по 2 в каждом из 15 байт), и ещё 4 байта занимает индекс следующего элемента в цепочке элементов хеш-таблицы. Используется хеш длиной 27 бит, при котором программа использует 10.63 Гб памяти и хранит до 536.8 миллионов чисел. Если бы у меня было больше памяти на моём ПК, можно было бы хранить ещё больше чисел, но я не планирую апгрейд в ближайшее время. Ещё один важный нюанс: я изменил то, как хеш-таблица удаляет элементы, когда их становится слишком много. Раньше просто удалялась 1/8 часть, сейчас удаляется лишь самый старый блок в той же 1/8. Во-первых, благодаря этому из таблицы удаляются в первую очередь самые старые элементы. А во-вторых, теперь колебания размера таблицы не 1/8 её размера, а 1/80, что в теории (и на практике) приводит к немного большей скорости работы в том случае, когда размера таблицы не хватает для хранения всех чисел и она начинает интенсивно обновляться.


30 июня 2019

Сегодня я написал точный тест того, на каких шагах и сколько на самом деле отсеивается чисел Лишрел. Мои прошлые вычисления не были полностью корректны из-за того, что я, тестируя каждый "порядок", добавлял одно число в список несколько раз соответственно тестируемому порядку. А нужно было добавить его один раз (предварительно выполнив несколько операций RAA), а затем, проверяя следующие числа, проверять их сходимость, многократно выполняя операцию RAA + поиск в списке. Во-первых, это экономит память (одно число в списке вместо нескольких), во-вторых, позволяет отсеять намного больше чисел. Дело в том, что большая часть проверяемых чисел сходится к уже проверенным числам, имеющим меньший порядок. Т.е. если мы, например, добавили в список число Лишрел, предварительно применив к нему операцию RAA 12 раз, то следующие числа могут оказаться равными ему после выполнения над ними 1, 2, 3, 4, 5, ..., 11, 12, 13, и даже более операций RAA! Вот почему, чтобы проверить сходимость правильно, помещаемое в список число нужно предварительно сложить с обратным ему числом несколько раз.

В общем, посчитав всё правильно, я выяснил, что сходятся примерно 97% всех чисел Лишрел в каждом диапазоне! Теоретически это могло бы дать ускорение работы программы до 30 раз при условии, что все проверенные числа всегда будут в памяти. Однако, когда я попробовал эту оптимизацию в основной программе на начале диапазона 21-значных чисел, меня ждало разочарование: использовав около 6 Гб оперативной памяти, и имея в списке около 120 миллионов чисел, программа нисколько не ускорилась, и даже стала немного медленнее. А произошло это потому, что для диапазона 21-значных чисел, чтобы более или менее эффективно отсеивать числа Лишрел, сходящиеся к уже проверенным числам, размер списка должен быть хотя бы несколько миллиардов чисел (даже тратя на одно число 24 байта это будет 24 Гб для 1 миллиарда чисел). Столько памяти бывает только на мощных серверах, и очень редко в рядовых ПК. Вот такая печаль. А на диапазонах до 16-значного включительно эта оптимизация даёт просто шикарные результаты. И даже в 17-значном диапазоне при размере списка около 4 Гб получается примерно двухкратное ускорение работы.

Тем не менее, я ещё немного доработал свой контейнер (хеш-таблицу): увеличил количество частей до 8, чтобы размер был более равномерен при удалении одной из частей; и исправил ошибку хеш-функции, из-за которой у половины частей возникал перекос в размерах. Завтра я хочу сделать лёгкую версию класса числа, занимающую минимум памяти для использования её в хеш-таблице вместо полноценного класса. Это позволит при том же объёме используемой памяти удвоить количество элементов. И потом применить всё это для ускорения проверки 17-значного диапазона (для 18-значных чисел, эта оптимизация уже, скорее всего, будет бесполезна).

Update: Сегодня ровно в 5 часов вечера был найден новый отложенный палиндром: 18-значное число 100,072,100,489,999,238, дающее палиндром за 219 шагов. На конец дня диапазон 17-значных чисел проверен на 13.925%.

Достижения дня: найден отложенный палиндром для шага 219.


29 июня 2019

Благодаря реализованной и проверенной вчера оптимизации отсева чисел Лишрел удалось подсчитать полное количество чисел Лишрел до 14-значного диапазона включительно. На это понадобилось всего 36 с половиной минут. До этого подсчитаны были только числа до 12-значного диапазона. Так, среди всех 13-значных чисел существует 6,397,634,011,964 чисел Лишрел (71.085% от всех 9 триллионов чисел). А среди 14-значных чисел были найдены 68,863,723,437,406 чисел Лишрел, что составляет 76.515% от всех чисел диапазона.

Также благодаря доработке алгоритма удалось сократить количество используемой памяти примерно на 18% и увеличить размер набора при том же размере хеш-таблицы. Теперь для набора из примерно 6.5 миллионов чисел требуется около 400 Мб памяти. Завтра оптимизация отсева чисел Лишрел дойдёт и до основной программы поиска палиндромов. Очень интересно, какой прирост удастся получить там.

Update: Сегодня поздно вечером был найден новый отложенный палиндром: 17-значное число 10,059,430,139,999,234, дающее палиндром за 209 шагов.

Достижения дня: найден отложенный палиндром для шага 209.


28 июня 2019

Так вышло, что все последние дни я прозанимался проблемой производительности, а если конкретнее, — проблемой "отсева" чисел Лишрел, которые сходятся к уже проверенным числам не только за 1 шаг, но и за 2, 3, 4 и так далее. А начиналось всё очень безобидно: я просто решил быстренько перепроверить неразрешимость чисел Лишрел в уже проверенных диапазонах. И как обычно, сначала я решил написать простенький тест для проверки, сколько же вообще таких чисел можно отсеять. И его результаты меня, мягко говоря, шокировали.

Вообще, я был уверен, что большая часть чисел сходится за 1 шаг (из всех которые вообще как-либо сходятся), но предполагал, что числа, сходящиеся за 2, 3, 10 и т.д. шагов, конечно, существуют, но их количество очень мало. Это было очень неверное предположение! Забегая вперёд, скажу, что именно это стало поводом переключить фокус с работы над многопоточностью: в данный момент многопоточность не так актуальна, потому что несколько копий программы, проверяющих разные интервалы и диапазоны чисел, уже заняли все ядра моих CPU. А вот ускорить работу каждой из них за счёт отсева чисел Лишрел было бы весьма полезно!

Так, проведя тест на всех числах от 1-значных до 7-значных включительно, я выяснил, что уже до 15-го порядка сходятся 7 чисел Лишрел из 8! Так, например, общее количество чисел в диапазонах от 1-значного до 7-значного равно 9,999,999. Из них после отсева чисел, которые сходятся за 1 шаг, остаётся лишь 75,447 (та самая оптимизация с изменением пар симметричных цифр), из которых 15,607 (20.69%) являются числами Лишрел. После отсева чисел, сходящихся на 2-м шаге, осталось 6,666 чисел, т.е. менее половины! А после отсева чисел, сходящихся на шагах до 10-го включительно, осталось лишь 1,952 числа (т.е. почти ровно в 8 раз меньше)! Все подробности ниже в таблице.

Время  Количество  Порядок          Время  Количество  Порядок           Время  Количество  Порядок
06:01    15,607        1            00:50     2,134        7             00:44     1,904       16
02:34     6,666        2            00:47     2,042        8             00:44     1,902       18
01:27     3,767        3            00:46     1,984        9             00:44     1,902       20
01:11     3,031        4            00:46     1,952       10             00:44     1,901       25
01:01     2,619        5            00:45     1,918       12             00:44     1,901       30
00:55     2,344        6            00:44     1,909       14             00:44     1,901      100

Из всего этого я сделал вывод, что проверять можно лишь примерно 1/8 всех чисел Лишрел, что может очень существенно уменьшить требуемое время. И чем глубже поиск (актуально именно для задачи проверки неразрешимости чисел Лишрел), тем существеннее будет экономия времени. Однако выяснилось, что есть другая проблема... и её мне долго не удавалось решить.

Проблема заключается в том, что, проверив очередное число Лешрел, мы должны добавить его в список, чтобы далее с помощью этого списка для следующих чисел Лишрел проверять, не сходятся ли они к добавленному. Но если до 10-значного диапазона таких чисел 63,769, что сравнительно немного, то до 11-значного диапазона их уже 475,845, до 12-значного — 902,756, до 13-значного — 5,926,721, до 14-значного — более 11 миллионов, и дальше только ещё больше. Мало того, что стандартные контейнеры STL уже с трудом переваривают такое количество элементов, главная беда заключается в том, что мы физически не сможем добавлять числа всё время, потому что числа бесконечны, а оперативная память — нет.

Я попробовал разные варианты. Сначала я попробовал просто перестать добавлять в список элементы, когда он заполнится. Но выяснил, что после прекращения добавления элементов эффективность отсева начинает снижаться и в начале следующего диапазона составляет менее 50%. Потом я попробовал очищать список и просто начинать формировать его с той точки, где мы находились. Это было эффективнее, но в период сразу после очистки и до тех пор, пока список на заполнится до какого-то уровня, эффективность отсева была крайне низка (ощущалось резкое падение скорости работы, точных замеров не делал). В общем, нужно было сделать так, чтобы старые элементы удалялись, освобождая место новым. Таким образом мы бы смогли поддерживать размер списка на достаточном уровне и постоянно его обновлять.

К концу второго дня экспериментов с STL я понял, что мне нужен собственный контейнер, похожий на std::set, но который можно будет быстро частично очистить и в котором не будет массивных выделений/освобождений памяти, так как это критично для скорости работы. Так, я пришел к реализации хеш-таблицы, каждый элемент которой указывает на число, начинающее односвязный список чисел с таким же хешем. Весь набор я разбил на 4 четверти, а за выбор четверти у меня стали отвечать последние 2 бита хеша. Работает это так: когда в какой-либо из четвертей количество элементов достигает 150% от нормы, из таблицы удаляются все элементы этой четверти. То же самое происходит, если суммарное количество элементов достигло 100%: но в этом случае удаляются элементы только самой крупной четверти. Таким образом, размер таблицы поддерживается на уровне не менее примерно 3/4 его нормального размера. Все элементы (числа) выделяются однократно и существуют до окончания работы программы, кроме случаев превышения какой-либо из четвертей нормального размера: если это происходит, то после удаления четверти освобождается память только из-под "дополнительных" элементов. Так удаётся использовать эффективно меньшее количество памяти и не допускать сильного снижения размера таблицы при удалении одной быстро выросшей четверти.

Update: Сегодня почти ровно в полдень (в 12:00:42) новая программа завершила перепроверку диапазона 16-значных чисел с глубиной 650 шагов (предыдущая проверка с глубиной 603 шага завершилась вечером 22 июня). А после обеда был найден новый отложенный палиндром: 17-значное число 10,030,503,899,969,524, дающее палиндром за 234 шага!

Update: Как обычно, после реализации чего-то нового я сначала пишу тесты, чтобы убедиться, что всё работает как надо. Так и в этот раз, перепроверив корректность новой "оптимизации" вдоль и поперёк, я решил наконец продолжить то, с чего всё это вообще началось. Диапазоны чисел от 3-значных до 5-значных были перепроверены с глубиной поиска 1,000,000 шагов. На это программе понадобился 1 час и 23 минуты (проверено 75 чисел). Диапазоны чисел до 12-значных включительно были проверены с глубиной поиска 10,000 шагов за 1 час и 35 минут (проверено 902,756 чисел). А диапазоны до 14-значных чисел включительно были проверены с глубиной поиска 2,500 шагов за 11 часов и 24 минуты (за это время были проверены 89,773,194 числа).

Update: Специально с целью измерить разницу в скорости работы я запустил поиск во всех диапазонах до 14-значного включительно с глубиной поиска 600 шагов (на самом деле этого немного больше, так как в основной программе поиск в диапазонах до 9-значного идёт с глубиной 500 шагов, а в 10-значном — с глубиной 550 шагов). Последней версии программы без отсева чисел Лишрел понадобилось на это 10 часов 44 минуты. Новая версия с отсевом закончила этот объём работы за 1 час и 32 минуты. В общем, это 7-кратное ускорение! Ценой использования примерно 336 Мб оперативной памяти.

Update: Сейчас 20:50 и только что завершилась очередная перепроверка диапазонов чисел до 12-значного включительно. На этот раз с глубиной поиска 15,000 шагов. Программе понадобились 3 часа и 36 минут, чтобы проверить 902,756 чисел. Эта же проверка, но с глубиной 10,000 шагов заняла 1 час и 35 минут. Так, увеличение глубины в 1.5 раза приводит к замедлению работы в ~2.27 раза. При уменьшении глубины до 5,000 шагов время уменьшается до 24 минут 37 секунд, или в ~3.86 раза. Можно сделать вывод, что время работы имеет близкую к квадратичной зависимость от глубины поиска.

Достижения дня: найден отложенный палиндром для шага 234.


27 июня 2019, "259 шагов"

Сегодня ночью был найден новый отложенный палиндром: 17-значное число 10,009,000,275,899,569, дающее палиндром за 208 шагов. А в 18:42 по местному времени программа, работающая на втором ПК, нашла новый локальный рекорд в диапазоне 19-значных чисел: число 1,000,000,079,994,144,385, дающее палиндром за 259 шагов! До последнего известного мирового рекорда остается всего 2 шага! И это не может не радовать! Эти два последние рекорда расположены там же, в диапазоне 19-значных чисел. А новый мировой рекорд, предположительно, находится где-то в 21-значном диапазоне. Понятно, что между ними лежит просто огромная пропасть вычислений (количество 21-значных чисел, которые нужно проверить, в 19 раз больше количества 19-значных). Так что на это точно уйдёт какое-то время.

В данный момент поиск продолжается параллельно в диапазонах 17-, 18-, 19- и 21-значных чисел. Немного позднее будет начат поиск и в диапазоне 20-значных чисел.

Достижения дня: найдены отложенные палиндромы для шагов 208 и 259.


26 июня 2019

Рано утром программа, работающая на отдельном ПК (G3260), нашла новый отложенный палиндром: 19-значное число 1,000,000,038,990,407,538, дающее палиндром за 217 шагов.

Достижения дня: найден отложенный палиндром для шага 217.


25 июня 2019

Сегодня поздно вечером был найден новый локальный рекорд: 17-значное число 10,005,000,760,994,249, дающее палиндром за 233 шага. Другим важным событием стало завершение перепроверки диапазона 15-значных чисел, в этот раз с глубиной поиска 650 шагов.

Достижения дня: найден отложенный палиндром для шага 233.


24 июня 2019

Рано утром в диапазоне 18-значных чисел был найден новый отложенный палиндром: число 100,000,277,999,334,202, дающее палиндром за 211 шагов.

Достижения дня: найден отложенный палиндром для шага 211.


23 июня 2019

Сегодня ночью был найден первый отложенный палиндром в 18-значном диапазоне: число 100,000,002,973,751,552, дающее палиндром за 205 шагов. А утром был найден первый отложенный палиндром в диапазоне 19-значных чисел: число 1,000,000,005,577,676,468, дающее палиндром за 225 шагов. Около 9 часов вечера был найден ещё один отложенный палиндром в 18-значном диапазоне: число 100,000,078,999,111,766, дающее палиндром за 203 шага.

Достижения дня: найдены отложенные палиндромы для шагов 203, 205 и 225.


22 июня 2019, "Все 16-значные"

Сегодня в 19:44 старая программа полностью завершила проверку диапазона 16-значных чисел и была остановлена. Как и предполагалось, новых палиндромов со вчерашнего дня найдено не было. А новая программа в данный момент уже перепроверяет первую четверть 16-значного диапазона с большей глубиной.

Update: Поздно вечером собрал ещё один ПК из старых запчастей: простенький Intel Pentium G3260 3.3GHz с двумя ядрами. К моему удивлению этот малыш работает быстрее моего Core i7-2600K 8-летней давности, несмотря на гораздо меньший кэш, и даже немного более низкую частоту. А всё дело в том, что это свежее поколение, более оптимизированное и поэтому работающее быстрее при тех же частотах. А кэш, ну тут дело в том, что моя программа, по большому счёту, его не использует (самый интенсивный цикл сложения обходится всего парой килобайт памяти). Я просто не знаю, как изменить алгоритм, чтобы задействовать больше кэш-памяти и получить от этого прирост производительности (но подумаю об этом в ближайшее время).

В общем, уже после полуночи, около 10 минут первого ночи я запустил поиск в диапазонах 18- и 19-значных чисел на этом отдельном ПК. Теперь в сумме у меня работают 6 потоков вычислений. Процесс пойдёт быстрее. Но мне в любом случае нужно двигаться в сторону распределённых вычислений, чтобы с помощью всех (хотя бы только моих) мощностей проверять какой-то один диапазон кратно быстрее, а не проверять несколько диапазонов параллельно.


21 июня 2019

Сегодня около обеда был найден новый отложенный палиндром: 16-значное число 7,090,000,039,309,919, дающее палиндром за 193 шага. К настоящему моменту (уже поздний вечер) проверить остаётся менее 8% диапазона. И, видимо, это был последний новый палиндром среди 16-значных чисел. В диапазоне 17-значных чисел сегодня было найдено сразу 4 отложенных палиндрома, и один из них — новый локальный рекорд! Это 17-значное число 10,000,000,525,586,206, дающее палиндром за 232 шага.

Также, сегодня я в очередной раз доработал формат файлов базы данных, исключив из них инкрементальную статистику, оставив в каждом файле только лишь данные по проверенному в нём диапазону. Это даёт возможность запустить несколько копий программы, вычисляющих разные диапазоны. А потом просто скопировать файлы отдельных баз данных в одну директорию, получив полную базу без каких-либо дополнительных манипуляций! Поэтому сегодня параллельно к уже идущей проверке 21-значных чисел, я начал проверку диапазона 17-значных чисел. А в ближайшие дни начну также проверку 18-значных чисел. Позже, когда будет готова многопоточная версия, я просто объединю эти базы данных, а все ресурсы брошу на завершение проверки 17-значных чисел.

Достижения дня: найдены отложенные палиндромы для шагов 160, 193, 230, 231 и 232.


20 июня 2019

Сегодня вечером был найден новый отложенный палиндром: 16-значное число 6,000,000,039,361,479, дающее палиндром за 161 шаг. А я продолжаю работать над многопоточностью и клиент-серверной архитектурой новой программы.

Достижения дня: найден отложенный палиндром для шага 161.


18 июня 2019

Сегодня решил доработать анализ данных в базе. А точнее, сделать наконец вывод полного количества чисел, которые получаются путём изменения и перестановки пар цифр первичных чисел. Увидев результаты, я сначала не поверил: для некоторых шагов (в районе 80-100) количество чисел уже превышало все мыслимые пределы — счёт шёл на сотни триллионов (а изначально, мой план был получить всего по 10 миллионов первых чисел). Отсюда я сделал первый вывод: ограничение в 1 миллион первичных чисел для шагов от 15 и выше слишком высоко и в БД можно сохранять намного меньше, сильно сэкономив на размере (к данному моменту база разрослась уже до 279 мегабайт).

Вторым менее приятным открытием стал тот факт, что для многих шагов, благодаря ограничению просто по количеству, часть чисел в базе (от 10% до 90% для разных шагов) оказалась непригодна. Связано это с тем, что перестав добавлять в базу числа, к примеру, после проверки диапазона на 15%, использовать можно только ~4% сохранённых чисел, после проверки 50% диапазона — примерно 20% чисел. И всё потому, что для формирования именно последовательного ряда, последним в ряду станет первичное число, и до него будет добавлена лишь малая часть всех родственных чисел — только те из них, что окажутся меньше этого первичного. И так как большую часть родственных чисел генерируют именно младшие первичные числа, которые опять же, в основном сосредоточены в первых 15% диапазона, большую часть из них приходится просто отбрасывать. Отсюда я сделал второй вывод: сохранять в БД нужно либо все первичные числа диапазона, либо не сохранять совсем ничего.

По этой причине новая программа, запущенная ночью с пустой БД, сегодня была остановлена. И позже будет перезапущена снова.

Update: Отлично, теперь ограничение работает так: числа для шагов от 1 до 13 сохраняются в БД только до 11-значного диапазона включительно. Для шагов от 14 до 34 — до 12-значного диапазона включительно. Для шагов от 35 до 57 — до 13-значного, для шагов от 58 до 80 — до 14-значного. И для шагов от 81 до 99 — до 15-значного диапазона включительно. В абсолютных цифрах это, в основном, сильно меньше 1 миллиона первичных чисел. И только для самых малых шагов значения превышают 1 миллион. Таким образом, я смогу извлечь из БД не менее одного миллиарда первых отложенных палиндромов для каждого шага (речь про числа до 99 шага, которые не будут сохраняться в базе, начиная с 16-значного диапазона, для других чисел пока ограничений не будет). И при этом размер БД после завершения проверки 15-значного диапазона будет всего около 75 мегабайт!

Update: Тем временем, проверка 16-значного диапазона продолжается. И сегодня старой программой были найдены 2 отложенных палиндрома. А новая программа успела перепроверить все диапазоны чисел от 1-значных до 14-значных с глубиной большей, чем в прошлые попытки: все до 9-значного включительно — с глубиной поиска 500 шагов, диапазон 10-значных чисел — с глубиной 550 шагов, и диапазоны с 11-значного до 14-значного включительно — с глубиной поиска 600 шагов.

Достижения дня: найдены отложенные палиндромы для шагов 162 и 177.


17 июня 2019

Сегодня в очередной раз был изменён формат базы данных: теперь данные сжимаются, и каждый файл содержит значение минимальной глубины, с которой был проверен диапазон чисел, сохранённый в этом файле. Файлы теперь хранятся не в одной папке, а во многих (и чем больше файлов, тем больше папок, между которыми файлы распределяются равномерно). Кроме этого, теперь каждый файл содержит значение процессорного времени, затраченного на его вычисление. В базу данных теперь сохраняются числа с 25 шага (а не с 30 как раньше), и количество сохраняемых чисел (лимит) отличается для разных шагов: для меньших шагов сохраняется больше чисел, чем для больших (с 50-го шага количество ограничено 1 миллионом первичных чисел, т.е. таких, которые нельзя получить друг из друга путем изменения цифр в симметричных разрядах). Таким образом, теперь из базы данных можно будет извлечь не только первые 10 миллионов отложенных палиндромов, а гораздо больше (так, например, для 45-го шага их количество будет даже больше 1 миллиарда).

Также была изменена система выбора глубины поиска: теперь до 15-значного диапазона включительно глубина задаётся на весь диапазон (не меняется при нахождении рекорда), а её значение как минимум в 3.0 раза выше, чем самый большой известный шаг в этом диапазоне. Начиная с 16-значного диапазона, используется коэффициент 3.0, глубина не может быть меньше 605, а её значение всегда округляется вверх до 5.

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

Также было сделано много других менее значимых улучшений программы: изменено форматирование статистики, все найденные числа выравниваются по вертикали, добавлен вывод сообщения об изменении глубины поиска и ещё несколько других вещей. В 1:20 ночи новая программа стартовала с пустой базой данных. Ориентировочно к 10 часам утра завтрашнего дня она достигнет 15-значного диапазона. Дальше обе программы (старая и новая) будут работать какое-то время вместе. И так как обе они однопоточные, а мой CPU 4-ядерный, они друг другу практически не мешают. В ближайшие дни я планирую реализовать многопоточность, и тогда новая программа начнёт быстро догонять старую. В какой-то момент они поравняются, и старая программа будет остановлена.

Тем временем, поиск не прекращается ни на минуту. И за сегодня были найдены два отложенных палиндрома: 16-значное число 1,003,000,024,749,923, дающее палиндром за 195 шагов; и число 1,030,020,097,997,900, дающее палиндром за 197 шагов.

Достижения дня: найдены отложенные палиндромы для шагов 195 и 197.


16 июня 2019, "Все 15-значные"

Ночью, в 01:16 был найден новый отложенный палиндром: число 700,000,001,839,569, дающее палиндром за 163 шага. Около 9 часов утра были найдены сразу 2 подряд новых числа: 890,000,023,937,399, дающее палиндром за 169 шагов, и число 900,000,076,152,049, дающее палиндром за 178 шагов! В данный момент, диапазон 15-значных чисел проверен уже на 96.886%.

Update: Сгенерировал быстрым полным перебором 10 миллионов первых чисел для шагов от 1 до 29 включительно. Остальные палиндромы (начиная с шага 30) находятся в базе данных продолжительного поиска, и их можно очень быстро извлечь в любой момент. На поиск 290 миллионов первых чисел и вычисление их палиндромов потребовалось всего 26 минут и 49 секунд. Суммарный объем 29 файлов, содержащих в каждой строке по два числа — сам отложенный палиндром и его результирующий палиндром — равен 7,479,557,693 байтам (~6.97 GiB). Самое большое из всех найденных чисел — число 4,557,420,485, дающее палиндром 16655662199126655661 за 29 шагов, это 10-миллионное число в ряду всех отложенных палиндромов для шага 29.

Update: В 13:35 программа завершила проверку 15-значного диапазона (глубина поиска была не менее 564 шагов) и приступила к проверке 16-значного с глубиной поиска 603 шага. На его проверку должно уйти не более 6 дней при работе в 1 поток с текущей глубиной.

Update: К 23:43 найдены ещё 5 новых отложенных палиндромов (всего за день — 8). Новых рекордов пока нет. 16-значный диапазон проверен на 8.121%.

Достижения дня: найдены отложенные палиндромы для шагов 163, 168, 169, 175, 176, 178, 194 и 196.


15 июня 2019

Сегодня я снова решил вернуться к вопросу оптимизации, потому что для 64-битной версии были использованы ещё не все резервы (а именно — обработка по 8 цифр за итерацию). И переписывая алгоритм, понял, что делал лишние операции при создании маски (той самой, про которую я в прошлый раз говорил, что на её создание уходит много инструкций). Оказалось, что всё намного проще. И теперь и 32-битная версия программы, и 64-битная стали быстрее, чем раньше. Но 64-битная, по понятной причине, теперь практически вдвое быстрее 32-битной. И при сложении чисел на каждую цифру сейчас в среднем уходит около 1.18 такта (против 2.5 после предыдущей оптимизации; тест не изменился — это всё те же 400 циклов сложения 14-значного числа Лишрел).

Для разных случаев прирост получился разный. Так, например, при выполнении сложений для числа 196 скорость выросла в 2.4 раза (8 цифр за раз вместо 4, плюс меньше длина тела цикла). Главный алгоритм поиска получил меньший прирост, но тоже неплохо ускорился: со средних 19.4 тыс. чисел в секунду скорость проверки выросла до 34.2 тыс. чисел в секунду, то есть примерно в 1.76 раза!

По состоянию на 00:13 новых палиндромов не найдено, проверяется число 672,551,699,999,999, проверено 82.637% 15-значного диапазона. Расчётное время до завершения диапазона — около 13 часов.


14 июня 2019

Снова сегодня не дошли руки до оптимизации и многопоточности. Зато собрал все найденные палиндромы в одну большую красивую таблицу и вставил ссылки в записи дневника. Буду обновлять таблицу по мере нахождения новых чисел. За сегодня программой был найден только 1 отложенный палиндром: число 200,000,729,975,309, дающее палиндром за 155 шагов. К 23:53 программа добралась до числа 300,000,869,201,819, проверено чуть больше 61% чисел всего 15-значного диапазона.

Достижения дня: найден отложенный палиндром для шага 155.


13 июня 2019

Сегодня были найдены новые отложенные палиндромы: число 120,000,046,510,993, дающее палиндром за 180 шагов (в 8 часов утра), и число 130,000,074,931,591, дающее палиндром за 200 шагов (в 12:23). Сейчас на часах 23:00, и уже проверяется число 151,405,869,989,997. Я планировал заняться сегодня оптимизацией, но потратил всё время на работу над будущей веб-страницей проекта.

Достижения дня: найдены отложенные палиндромы для шагов 180 и 200.


12 июня 2019

Как и планировал, сделал сегодня замеры производительности. Прирост есть везде: и в алгоритмах с короткими числами, и там, где числа длинные. Так, время, необходимое для генерации 1 миллиона первых отложенных палиндромов для шагов от 1 до 20, уменьшилось с 74 до 48 секунд (1.54 раза), а время генерации 50 тысяч первых чисел для шагов от 1 до 60 уменьшилось с 611 до 350 секунд (1.75 раза). Наибольший прирост (как и ожидалось) получился при сложении длинных чисел (из тысяч знаков). Так, при выполнении сложений для числа 196 на достижение длины в 100 тысяч знаков раньше уходило 20.1 секунды, теперь — 7.5 секунды (2.68 раза), на достижение длины в 1 миллион знаков раньше уходило 33 минуты 53 секунды, теперь — 12 минут 30 секунд (2.71 раза).

Update: Сегодня в 19:55 программа преодолела контрольную точку 108,039,083,991,976 (это могло случиться на 2 часа раньше, но нужно было приостановить выполнение дважды на час для проведения точных замеров производительности). Итого, чтобы проделать ту же работу, что была проделана предыдущей версией с меньшей в среднем почти вдвое глубиной поиска, новой программе потребовалось 87 часов и 24 минуты, что на 97.4% дольше (т.е. практически вдвое). И это при том, что новая программа работает примерно вдвое быстрее последние 16 часов. Да, я действительно сильно недооценил эффект от увеличения глубины поиска.

Update: Ровно в 20:00 я запустил (с пустой БД) поиск чисел с начала 21-значного диапазона. Используется точно та же программа, что и для основного поиска, с тем лишь отличием, что минимальная глубина поиска задана как 783 (из расчета, что коэффициент равен 3.0 и самый последний найденный палиндром был на 261 шаге). В базу сохраняются числа для шага 60 и выше (чтобы не утяжелять базу, так как основной поиск, когда он пройдет диапазон 20-значных чисел, вероятнее всего, уже достигнет лимита чисел до 59-го шага включительно).

По имеющимся у меня данным, Vaughn Suite закончил поиск в диапазоне до 20-значных чисел включительно, и наибольший найденный шаг, по-прежнему равен 261. Я решил, что ничего не потеряю, если параллельно с основным поиском запущу с низким приоритетом (в фоне) поиск среди 21-значных чисел. Есть вероятность, что новый рекорд расположен где-то в начале диапазона. Таким образом, я начну делать ту работу, для которой ещё нет подтверждённых данных о том, что кто-либо её сделал.

Update: Сейчас 22:57, программа проверяет число 109,800,008,909,998. Несмотря на то, что мы уже немного дальше, чем в прошлый раз, новых палиндромов пока нет.


11 июня 2019, "Ещё быстрее"

Итак, сегодня было время подумать о том, что можно сделать, чтобы складывать числа быстрее. Основная проблема текущей реализации, на мой взгляд, в том, что в теле функции 2 цикла и каждый делает N/2 итераций (почти), где N — количество цифр числа. Первый цикл обрабатывает 2 знака за итерацию, второй — 1 знак. Итого, в среднем 1 итерация на каждую цифру числа. И это при том, что каждая цифра — это 1 байт.

Профилирование показало, что 97.1% времени программа тратит на сложение числа с обратным ему числом. Проверка того, что результат является палиндромом, выполняемая в отдельной функции, занимает около 2.3% времени (несмотря на громадное количество вызовов). Значит, узкое место находится в этих двух циклах.

У меня есть несколько идей, и я попробую их сегодня реализовать. Но прежде, чем начать что-то оптимизировать, я написал тест производительности, чтобы протестировать скорость работы текущей реализации сложения и будущих вариантов. Тест заключается в сложении 14-значного числа Лишрел 19,780,839,959,996 с обратным ему числом 400 раз подряд. То есть это примерно то, что мы делаем обычно, пытаясь проверить очередное число 14-значного диапазона. Так, я выяснил, что тот же самый код, скомпилированный в 64-битной конфигурации работает примерно на 8% быстрее. И если говорить о конкретных цифрах, тест показал, что текущая реализация сложения тратит в среднем 6.3 такта (для x86) и 5.8 такта (для x64) на каждую цифру числа. Что ж, пора начинать.

Update: Первая идея заключалась в том, чтобы использовать таблицу с заранее вычисленными значениями сумм цифр и обрабатывать их парами. Таблица получилась большая, и проблему почти не решила: обработка переносов не даёт циклу выполняться быстрее, потому что каждая следующая итерация ждёт результата предыдущей. И так как в цикле мы обрабатываем по 2 цифры, всё работает не очень быстро. В общем, использование таблицы позволило сократить цикл до 5.2 тактов в среднем на цифру. Неплохо, но такой вариант меня не устраивает.

Update: Вторая идея заключалась в том, чтобы обрабатывать цифры не по одной, а по несколько за раз. Я выбрал значение 4, потому что именно столько цифр помещается в 32-битный регистр. Одним из минусов стало то, что теперь сохранять результат пришлось во временный буфер, а в конце работы — копировать содержимое обратно в основной (но не всегда, а только при нечётном количестве шагов, и как показало тестирование, это почти не влияет на скорость, так как финальное копирование делалось всего раз на 401 цикл сложения). Ещё одно неудобство, а точнее вещь, на которую уходит много инструкций — это создание маски, с помощью которой мы обрабатываем переносы сразу 4 цифр. Итерации цикла теперь стали длиннее, но зато самих их стало в 4 раза меньше, так как теперь мы складываем сразу 4 цифры числа за раз. И как результат — теперь на одну цифру в среднем уходит 2.5 такта! Ускорение примерно в 2.3 раза. Вот теперь неплохо.

Update: Время 23:10. Программа проверяет число 100,620,929,499,080. До контрольной точки 108,039,083,991,976 ещё по-прежнему далеко. Видимо, я сильно недооценил эффект коэффициента глубины. Предыдущей версии программы с жестко установленной глубиной в 300 шагов понадобилось 44 часа и 16 минут, чтобы дойти до контрольной точки (полное время работы). Новая программа уже работает 68 часов и 39 минут (в полтора раза дольше), текущая глубина поиска 603 шага, и до контрольной точки, по расчетам, больше 20 часов.

Update: На часах 1:50. Оптимизация внедрена, код проверен, все тесты пройдены. Обновил исполняемый файл программы: скорость со среднего значения в 9.2 тыс. проверяемых чисел в секунду увеличилась до 20.3 тыс. чисел в секунду! Замечательно. Завтра сделаю подробные замеры производительности. А на сегодня всё.


10 июня 2019

Сегодня обновил программу сбора статистики, чтобы она могла работать с новой базой данных (хотя сейчас она уже не так актуальна, потому что есть файл журнала).

Пока программа работает, я прикинул, сколько времени ей понадобится, чтобы проверить отдельно 20-значный диапазон. По грубым расчетам, если даже запустить её в 4 потока, при текущей скорости и глубине поиска понадобится примерно 24 года. Долго. И вот какие пути сокращения этого срока я вижу: 1) самое простое и очевидное — задействовать несколько потоков (мой CPU имеет 4 ядра с технологией HT, и почти все современные CPU многоядерные); 2) оптимизация — то есть попытаться выжать максимум из оборудования, улучшив алгоритмы и оптимизировав код (вполне вероятно, что с помощью SSE можно перебирать числа гораздо эффективней, чем сейчас); 3) выполнить статистический анализ и подобрать коэффициент глубины поиска (возможно коэффициент 3.0 неоправданно большой и его можно уменьшить, оставив разумно невысокой вероятность пропустить число); 4) распределённые вычисления — это уже сложнее, но тоже вполне реализуемо (вот только, как привлечь людей в команду?).

И вот, что я сделаю. 1) Выполню профилирование кода (хотя подозреваю, что 99% времени программа складывает число с обратным ему числом). 2) Попробую изменить алгоритм сложения, не тратя на это слишком много времени (ну такая оптимизация с наскока). 3) Организую вычисления в несколько потоков (чтобы задействовать железо по максимуму). 4) Вернусь опять к шагу 2 и займусь вопросом оптимизации глубже. 5) Возьму статистику и проанализирую её, попробую подобрать меньший коэффициент глубины. 6) Снова вернусь к оптимизациям, но на этот раз это будет хардкорный ассемблер (или даже CUDA). 7) И лишь потом буду смотреть в сторону распределения вычислений (ну в самом деле, в чём смысл загружать кучу компов, если они все будут делать это неэффективно; сначала в любом случае нужно добиться максимальной эффективности для отдельно взятого потока вычислений).

Update: Все оставшееся время я думал о том, что такого можно сделать, чтобы складывать числа быстрее... пока ничего не придумал... Ну а программа к концу дня добралась до числа 100,008,093,953,488 (при текущей скорости до контрольной точки остается ещё более суток). Аналогично вчерашнему дню, единственное значимое событие сегодня — это завершение проверки 14-значного диапазона с глубиной поиска 564 шага.


9 июня 2019

Почти всё время сегодня было потрачено на рефакторинг, написание дополнительных тестов и другие мелкие доработки. А программа продолжает трудиться и медленно приближается к новым рекордам. К 10 часам утра были закончены все 12-значные числа и проверялось число 2,066,500,499,989. А к 23:00 программа уже преодолела отметку 12,900,000,013,992.

Из значимых событий стоит отметить то, что при проверке 12- и 13-значного диапазонов глубина в этот раз была равна 447, точнее, не менее 447, так как для части 13-значного диапазона она была даже выше (против 300 в предыдущей попытке).


8 июня 2019, "Перезапуск"

Сегодня были закончены работы над новой базой данных. Также был добавлен файл журнала (теперь точно ни одно событие не останется незамеченным!), улучшен вывод текущей статистики на экран, добавлен вывод количества чисел Лишрел (в процентах) при завершении диапазона, а также индикатор прогресса сканирования текущего диапазона, который позволяет примерно оценить оставшееся время. А также ещё много других мелких улучшений и доработок.

Как я уже говорил, форматы старой и новой баз данных несовместимы. Основная причина в том, что в старой базе отсутствует критически важная информация, получить которую можно только начав всё сначала. Помимо этого, в новой базе данных будут сохраняться числа для шагов от 30 (а не от 40 как в предыдущей). Поэтому сегодня в 15:26 старая программа была остановлена на числе 108,039,083,991,976. Общее время работы составило чуть более 44 часов. За сегодня новых рекордов найдено не было, но были найдены новые отложенные палиндромы для шагов от 156 до 159, 165, 166, 171, 172, 174, 189, 190, 192 и 199, в сумме 13 новых чисел.

После нескольких попыток стартовать (каждый раз я снова что-нибудь улучшал, перепроверял и снова перезапускал программу), ровно в 2:30 ночи процесс поиска был наконец-то перезапущен с самого начала. Это уже третий по счету перезапуск продолжительного поиска. Пройдёт более 3 суток до того, как программа найдёт новый отложенный палиндром (потому что ей сперва придётся проделать всё то, что успели сделать предыдущие версии, и лишь потом, обогнав их, начать искать там, где предыдущие версии не искали).

Одно большое отличие новой программы (и из-за этого она будет значительно медленнее предыдущей) в том, что теперь глубина поиска не постоянна и зависит от максимального из значений шага среди всех найденных палиндромов (т.е. последнего найденного рекорда). Так, на старте, значение глубины равно 100 (это минимальное начальное значение), после нахождения первого числа 10,548 с шагом 30, ничего не изменится, но при обнаружении числа 10,677 с шагом 53, значение глубины изменится на 3 * 53 = 159, и программа замедлится. Затем идут числа (рекорды) с шагом 54, 55, 58, 64 и так далее, увеличивая каждый раз значение глубины поиска сначала до 162, 165, 174, затем до 192 и так далее. Значение x3 выбрано эмпирически: 4 и 5 слишком замедляют программу, и, пожалуй, избыточны. Значение x2 слишком мало, и может привести к тому, что некоторые палиндромы будут пропущены.

По-хорошему, нужно будет сделать две вещи. Первое — выполнить поиск с очень большой глубиной (заведомо кратно большей) для всех чисел до 9-значного диапазона включительно (а лучше больше), чтобы убедиться, что нет других чисел, кроме уже найденных. И второе — проанализировать статистику появления новых рекордов, для того чтобы выбрать коэффициент меньше x3, но такой, для которого вероятность пропустить число будет разумно низкой. Эта задача стоит на одном уровне с задачей по оптимизации алгоритма RAA, так как она оказывает такое же сильное влияние на скорость поиска.

Достижения дня: найдены отложенные палиндромы для шагов от 156 до 159, 165, 166, 171, 172, 174, 189, 190, 192 и 199.


7 июня 2019, "Хрупкость"

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

Новый формат базы данных будет совершенно не совместим с прежним. Главное отличие новой базы в том, что в ней отдельные файлы самодостаточны, и база совершенно не боится повреждений. Если повредится какой-то из файлов, или исчезнет совсем, или даже если это будут несколько файлов, то это не станет проблемой. Просто эти файлы нужно будет заново "пересчитать" и всё (файлы формируются не реже, чем 1 раз в 15 минут, что не так уж и долго по сравнению с полным поиском с самого начала). В общем, дело идёт к тому, что поиск будет перезапущен сначала.

Тем временем, программа продолжает работу, и по состоянию на 23:00 она добралась до 15-значного числа 100,400,017,339,205. Сегодня ночью были установлены сразу 2 локальных рекорда: 187 и затем 188 шагов! В первой половине дня был найден новый палиндром-рекордсмен: число 100,000,090,745,299, которое становится палиндромом за 198 шагов! А вечером снова установлен новый локальный рекорд: число 100,120,849,299,260, дающее палиндром за 201 шаг! Также было найдено 19 других отложенных палиндромов.

Достижения дня: найдены отложенные палиндромы для шагов 138, 139, 140, от 150 до 154, 164, 167, 170, 173, 179, от 181 до 185, 187, 188, 191, 198 и 201.


6 июня 2019, "Прорыв"

Рано утром закончил рефакторинг. Программа добралась до числа 9,798,689,489, и за ночь были найдены два палиндрома: для шагов 100 и 103. И вот-вот начнётся перебор 11-значного диапазона (а я уже заметил, что большинство новых чисел находится в начале диапазонов). Это же здорово! Но когда я посчитал, сколько времени программе понадобится, чтобы проверить весь 11-значный и следующий диапазоны, я сильно расстроился. Так, на проверку 11-значного диапазона понадобится 24 дня, а на проверку 12-значного — примерно 8 месяцев... Я уже и не говорю, про 20 знаков (это на 8 десятичных порядков больше, т.е. в 100,000,000 раз!) Это непозволительно долго (если всё же интересно, то около 65 миллионов лет).

В общем, пока программа находила рекорды в начале нового диапазона, я думал о том, как перебирать меньше чисел. И увидел, что кроме обратных чисел, такой же результат (после первой операции RAA) дадут числа, полученные простой перестановкой симметричных цифр: например, 1234, 1324, 4231 и 4321 (обратное число здесь лишь один из случаев). Так, для 4- и 5-значных чисел мы отбрасываем 3/4 кандидатов, для 6- и 7-значных — уже 7/8 (так как пар здесь 3, а не 2). А для 8- и 9-значных мы бы проверяли только 1/16 всех вариантов, что было бы примерно в 8 раз быстрее, чем в текущей реализации программы. И с ростом длины числа выигрыш будет ещё больше!

Update: Я уже собирался внедрить новую оптимизацию, но решил сначала провести эксперимент и посмотреть, сколько же на самом деле чисел дают одинаковый результат (на примере 4- и 6-значных диапазонов). Около часа ушло на то, чтобы отдельно выполнить полный перебор всех 4- и 6-значных чисел, выделив уникальные, и построить последовательные ряды чисел, которые дают одно и то же значение после одной операции RAA. Результатом этого эксперимента я был удивлён ещё больше, чем сделанным час назад открытием: таких чисел оказалось гораздо, гораздо больше! Хм... значит, я увидел не всё. Есть ещё что-то, помимо перестановок.

Update: После нескольких часов, проведённых с ручкой и листом бумаги, мне "открылось" то, что можно с уверенностью назвать настоящим "прорывом" в скорости поиска! Возьмём, к примеру, то же самое число 1234, и будем менять пары цифр так, чтобы их сумма не менялась: начинаем с внутренней пары 1054, 1144, исходное 1234, далее 1324, 1414 и 1504. Теперь меняем цифры внешней пары и снова перебираем внутреннюю: 2053, 2143, 2233, 2323, 2413, 2503. И опять: 3052, 3142, 3232, 3322, 3412, 3502. Далее: 4051, 4141, 4231, 4321, 4411, 4501. И наконец: 5050, 5140, 5230, 5320, 5410 и 5500. Все эти числа (а их здесь 30), дают один и тот же результат после одной операции перевернуть-и-сложить! То есть из 30 чисел можно отбросить 29! И это против 3 из 4 в предыдущем варианте с перестановками, т.е. ещё в 7.5 раза лучше! А для 6-значного числа отбрасываемых кандидатов будет ещё примерно в 5 раз больше, чем для 4-значного! Получится просто экспоненциальная оптимизация (в том смысле, что чем дальше мы будем двигаться от самого маленького натурального числа ко всё большим числам, тем всё с большей скоростью мы будем это делать)!

Итак, суть оптимизации заключается в том, что, когда мы встречаем "неправильное" число, мы "проматываем" его до следующего "правильного". И чтобы это было быстро, делаем это не в цикле, каждый раз увеличивая исходное число на 1, а сравнивая симметричные (относительно середины) цифры числа и изменяя их на нужные. Чтобы не объяснять алгоритм, просто приведу пример: пусть есть число 1000, оно нам подходит, так же подходит 1001, 1002 и все до 1099 включительно, а 1100 не подходит, потому что из него можно получить, например, 1010, которое уже было проверено нами ранее. Получается, что при любом значении предпоследней цифры кроме 9, число вида 11xx подходить не будет, потому что цифру, меньшую 9, всегда можно увеличить на единицу, уменьшив при этом симметричную ей цифру в старшем разряде (и получив число меньше исходного). Поэтому сразу "проматываем" 0 до 9 в предпоследнем разряде и получаем подходящее число 1190. Числа 1191, 1192 и далее до 1199 также нам подходят. А с 1200 ситуация такая же, как и с 1100... В общем, надеюсь, что теперь смысл понятен.

Эти "правильные" подходящие числа проверяются программой, и либо становятся палиндромами за некоторое количество шагов, меньшее или равное N, либо считаются числами Лишрел. Остальные числа, которые можно получить из проверенного путём изменения пар симметричных цифр, просто отбрасываются. Все эти проверяемые программой числа я назвал первичными (англ. primary numbers). Среди тех из них, что не становятся палиндромами, часть является базовыми числами Лишрел (англ. seed numbers), а часть — родственными числами (англ. kin numbers) для потоков других базовых чисел Лишрел. Отбрасываемые же числа целиком принадлежат множеству родственных чисел. Число N я назвал глубиной поиска (англ. search depth). Подробнее о базовых и родственных числах Лишрел можно узнать на главной странице проекта.

Update: К 7 часам вечера оптимизация была закодирована, были написаны тесты, и всё несколько раз перепроверено. Ровно в 19:10 новая программа была запущена с пустой базой данных. В этот раз я решил сохранять все числа от 40-го шага, и снизить глубину поиска до 300 шагов (которая пока жёстко задана в коде и никогда не меняется). Примерно через 6 с половиной минут новая программа добралась до числа, которое проверяла старая, и стремительно обогнала её. Через 29 минут от начала работы новая программа уже приступила к 12-значному диапазону (старой программе на это потребовалось бы около 26 дней), а ещё через полтора часа преодолела границу 13-значного.

В 19:17, после 65 часов и 17 минут работы старой программы, она была остановлена. За это время она нашла много рекордов. В том числе сегодня были найдены палиндромы для шагов 100, 102, 103, 106, 107, от 110 до 115, 123, 131, от 133 до 136 и от 147 до 149. Это не так уж и мало!

В 22:24 (через 2 часа и 14 минут) новая программа установила локальный рекорд, найдя число 1,000,006,412,206, которое становится палиндромом за 186 шагов! Всего к 23:00 (через 3 часа и 50 минут работы) новая программа нашла, помимо указанных палиндромов, палиндромы для шагов от 116 до 122, от 124 до 130, 132, 137 и от 141 до 146.

Достижения дня: найдены отложенные палиндромы для шагов 100, 102, 103, 106, 107, от 110 до 137, от 141 до 149, а также 186.


5 июня 2019

Сегодня занимался рефакторингом, доработкой статистики и написанием тестов. Программа продолжает работать: сейчас 22:15 и проверяется число 6,258,349,189. За весь день было найдено лишь число 5,020,089,949 для шага 108. Для шага 51 уже найдено более 1.7 миллиона первых отложенных палиндромов.

Достижения дня: найден отложенный палиндром для шага 108.


4 июня 2019

К 9 часам утра программа уже закончила поиск в 9-значном диапазоне и сейчас находится на числе 1,283,661,899. Листая файлы данных (а их уже 120, по 512 KiB каждый), я увидел, что найдены первые отложенные палиндромы до 104 шага (как минимум). Но сколько их, не понятно, — нужно как-то проанализировать данные и вывести статистику (просмотреть всё вручную — так себе идея). Этим я сегодня и займусь.

Update: Написал простенькую программу для анализа БД, которая выводит количество найденных чисел для каждого шага, а также первое (наименьшее) и наибольшее найденные числа. К 17:00 найдены все первые отложенные палиндромы (рекорды) от шага 1 до шага 99, а также палиндромы для шагов 101, 104, 105 и 109, в данный момент проверяется число 2,182,658,228. Для шага 51 уже найдено более 600 тысяч первых отложенных палиндромов (без учёта обратных чисел, с ними будет ещё больше). Двигаемся дальше.

Update: Дорабатывая сбор и вывод статистики, я решил, что не стоит сохранять в базу данных обратные числа (их можно будет потом быстро сгенерировать во время экспорта данных из БД). Это сократит размер БД вдвое без какого-либо вреда. Сказано — сделано: остановил поиск, удалил из БД обратные числа, теперь (в 17:15) БД занимает всего 63.5 MiB.

Update: Очередная оптимизация алгоритма RAA: теперь процесс разбит на 2 цикла: в первом за N итераций (где N равен (L + 1) / 2, а L — количество цифр числа) мы складываем две цифры числа (из младшей и старшей частей) и сохраняем их обратно, сразу учитывая перенос для младших знаков (т.е. до середины числа). Во втором цикле мы обрабатываем переносы для оставшейся старшей половины разрядов числа. Таким образом, удалось избавится от копирования числа во временный буфер и ещё увеличить скорость работы примерно на 20%. Сейчас на часах 01:34, новых рекордов пока нет, проверяемое число 3,086,738,473. Для шага 51 найдено более 880 тыс. первых отложенных палиндромов.

Достижения дня: найдены отложенные палиндромы для шагов от 51 до 99, а также 101, 104, 105 и 109.


3 июня 2019, "Долго искать"

Сегодня, в 2:58 ночи моя программа прекратила работу. Из-за утечки памяти при копировании чисел она за несколько часов исчерпала все доступные ей 2 гигабайта и скрашилась. За это время она успела найти по 10 миллионов первых отложенных палиндромов до 27 шага включительно, и только 956 тысяч для шага 50. Вывод: так не пойдет, — в смысле, так цели не достичь. С ростом количества шагов сложность растет нелинейно и поэтому такой способ точно не подходит из-за его низкой скорости.

Так как искать отложенные палиндромы придётся долго (видимо, как минимум, несколько месяцев), то я решил сделать так, чтобы, во-первых, при завершении программа сохраняла данные, а при запуске продолжала поиск с того же места. Я назвал этот режим продолжительным поиском (в отличие от текущего режима быстрой генерации). Во-вторых, нужно отрефакторить тот код, что я написал вчера, исправить утечку памяти и попробовать хотя бы немного оптимизировать процесс поиска.

Update: Переписал алгоритм Reverse-And-Add (теперь это одна функция, а не 2). Избавился от необходимости "переворачивать" число перед сложением. А в самом цикле избавился от условного перехода при обработке переноса путём замены условия на арифметические операции. Скорость операции RAA выросла более, чем вдвое. Но перед сложением исходное число приходится копировать во временный буфер, а цифры числа по-прежнему обрабатываются по одной за итерацию. Оставлю всё пока так.

Подумав ещё немного, понял, что нет смысла просматривать все числа подряд, ведь число, сложенное с обратным ему числом, даст тот же результат, что обратное число, сложенное с исходным (будь это палиндром или число Лишрел). Если обратное проверяемому число окажется меньше проверяемого, но при этом проверяемое число не оканчивается на 0, значит его можно пропустить. Эта оптимизация исключила примерно 45% чисел и ускорила поиск почти вдвое! Однако теперь есть небольшая проблема: числа уже не получится просто так выводить в файл подряд — нужно ещё выводить и обратные. И чтобы они шли по порядку, их придётся сортировать. На лету это будет слишком медленно, значит, нужно сначала сохранить все найденные числа куда-нибудь, и затем (когда поиск будет закончен) их обработать. Это как раз подходит для режима продолжительного поиска, потому что в этом режиме найденные числа (оба: и первое, и обратное ему) будут просто сохраняться в базу данных по мере их нахождения.

Update: Уже поздно ночью, в 2:30 я запустил продолжительный поиск с самого начала. Файла журнала пока нет, подробная статистика на экран тоже не выводится, нет даже индикатора прогресса, отображается только текущее проверяемое число и скорость перебора. Глубина поиска ограничена максимум 365 шагами (т.е. если предположить, что мы встретим число, дающее палиндром за 366 или более шагов, то мы примем его за число Лишрел, но, думаю, вероятность этого крайне мала). В базу данных сохраняются только числа для шага 51 и выше (я решил, что 10 миллионов чисел до 50 шага очень сильно увеличат размер БД, и что будет лучше, если я их найду позже "быстрым полным перебором"). Я ушёл спать, а программа будет работать.

Достижения дня: найдены отложенные палиндромы для шагов: 41, 42, 43, 44, 48 и 49.


2 июня 2019, "Первые эксперименты"

Примерно за 4 часа я написал на C++ минимально функциональную программу, которая умела переворачивать и складывать большие десятичные числа, проверять, является ли заданное число палиндромом, и выводить результаты в файл. После часа отладки, убедившись, что серьёзных ошибок нет, я запустил поиск. Это был примитивный полный перебор всех чисел от 1 и далее по возрастанию и проверка для каждого, за какое число операций оно даёт палиндром. Я обнаружил, что далеко не все числа становятся палиндромами (и первое такое число — то самое число 196).

Натуральные числа, которые не могут стать палиндромами с помощью итеративного процесса перевернуть-и-сложить в десятичной системе счисления принято называть числами Лишрел. А сам процесс часто называют 196-алгоритмом. Название «Lychrel» было придумано Уэйдом ВанЛэндингхэмом (Wade VanLandingham) и является примерной анаграммой имени его девушки Шерил (англ. Cheryl).

Вторым интересным наблюдением стало то, что с ростом длины проверяемых чисел, количество чисел Лишрел также росло. Например, среди 1- и 2-значных чисел все числа становятся палиндромами. Среди 3-значных чисел существует 13 чисел Лишрел (примерно 1.4% от всех чисел). Среди 4-значных их уже 236 (примерно 2.6%), а среди 5-значных — 5,842 или 6.5%!

Поэтому я ограничил глубину поиска до 20 шагов, лишив себя этим возможности найти числа для шагов, больших чем 20, но значительно ускорив поиск. Через 3 минуты работы программы было найдено более 10 миллионов первых отложенных палиндромов для шагов 1, 2, 3, 4 и 5. Вроде неплохо. Однако, для шага 10 за это время было найдено 3.9 миллиона первых чисел, а для шага 20 — чуть больше 1 миллиона. Моя цель — 10 миллионов, значит для этого программе потребуется примерно 30 минут. Терпимо. Но это всего лишь 20 шагов, верно? Нужно больше.

Я увеличил глубину поиска до 50 шагов и запустил программу снова. Скорость поиска упала в несколько раз и теперь за 1 секунду программа проверяет около 335 тысяч чисел (на моём стареньком Core i7-2600K 3.4GHz). Даже не знаю, много это или мало. Но впереди весь вечер и ночь. Через 20 минут работы были найдены первые 10 миллионов чисел для каждого из шагов от 1 до 9 включительно. Ещё через 32 минуты были проверены все 9-значные числа, и найдены первые 10 миллионов чисел для всех шагов до 15 включительно. Оставил программу работать до утра.

Достижения дня: найдены отложенные палиндромы для шагов от 1 до 40, а также 45, 46, 47 и 50.


2 июня 2019, "Цель проекта"

Судя по названию проекта, я собираюсь заниматься поиском наиболее отложенных палиндромов, то есть таких чисел, которые при сложении с обратными им числами дают в результате палиндром — число, читающееся в обе стороны одинаково. Например, число 121 — это палиндром. А число 19 — отложенный палиндром: 19 + 91 = 110, 110 + 011 = 121. То есть, чтобы число 19 стало палиндромом, над ним нужно дважды выполнить операцию перевернуть-и-сложить (англ. Reverse-And-Add или просто RAA). Говоря проще, это число становится палиндромом за 2 шага. Обычно, говорят "2 итерации", но мне слово шаг нравится больше, чем слово итерация, поэтому далее я везде буду употреблять только его, когда буду говорить о том, сколько раз число нужно сложить с его обратной записью для получения палиндрома.

А что же значит "наиболее отложенный палиндром"? А это такое число, которое требует самого большого количества шагов, чтобы стать палиндромом. Например, число 69 становится палиндромом за 4 шага, число 89 — за 24, а число 10,911 — за 55 шагов! Интересно, какое наименьшее число становится палиндромом за 250 шагов? Сколько в нём знаков? И сколько знаков в его палиндроме?

Немного отвлекусь... Дело вот ещё в чём: сейчас 2019 год, а смежной проблеме (она так и называется, проблема 196) уже более 20 лет. И естественно, я — не первый, кто уже делал что-то похожее (и даже очень) на то, что собираюсь делать я. И эти кто-то даже достигли очень значимых результатов! [Тут я оговорюсь, что, конечно, я искал в сети информацию, и кое-что нашёл, но ссылка будет ниже.] Так вот, результаты есть, и мне на то, чтобы просто проделать то же самое (т.е. повторить то, что уже было сделано другими), понадобится весьма немало времени. А чтобы добиться большего (см. ниже), понадобится времени ещё больше. И вот тут есть один интересный момент. [Опять оговорюсь: возможно, я недостаточно тщательно искал. И если честно, я и не хотел бы найти подтверждения того, что мне не стоит даже начинать проект, просто потому, что это абсолютно не мотивирует.] Последнее значимое событие (см. ниже) датируется началом 2008 года, что может означать, что люди, которые занимались поиском отложенных палиндромов, по какой-то причине прекратили работать над своими проектами. И Википедия также не содержит никакой новой информации о достижениях в области отложенных палиндромов. Всё это даёт мне надежду, что я не проделаю огромную работу напрасно.

Итак, цель этого проекта в том, чтобы найти ненайденные отложенные палиндромы и установить новый мировой рекорд среди отложенных палиндромов (и далее продолжать их поиск). Помимо этого, я собираюсь найти как минимум по 10 миллионов первых чисел для каждого из шагов до 100 включительно. В отличие от других исследователей, которые сохраняли лишь первое найденное (наименьшее) число.

Текущий мировой рекорд — 261 шаг: 19-значное число 1,186,060,307,891,929,990 на 261 шаге становится 119-значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544. Это число было найдено Джейсоном Дусеттом (Jason Doucette) 30 ноября 2005 года. С тех пор Vaughn Suite были полностью проверены 19- и 20-значные диапазоны, в которых были найдены другие числа, дающие палиндром за меньшее количество шагов (дело в том, что часто раньше находятся числа с большим шагом, оставляя ненайденными числа для меньших шагов, которые позже уже не станут рекордами, но по-прежнему так же важны). И вплоть до января 2010 года (когда, видимо, работы над проектами были остановлены) так и не было найдено ни одного нового рекорда. Последнее обновление информации на сайте Джейсона было 23 января 2010. Последняя известная информация об успехах Vaughn Suite имеет ещё более раннюю дату — 3 февраля 2008 года. Мне не известна судьба этих проектов, я не смог найти никакой информации о том, что было после января 2010 года. На сегодняшний день остаются неизвестными числа, дающие палиндром за 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251 и 252 шага. Вот ссылка на страницу Джейсона Дусетта с самой актуальной на данный момент информацией (имеются и другие ссылки, но эта — единственная известная мне рабочая ссылка).

Ну что ж, вступление окончено. Пора за работу! Удачи мне и этому проекту!


2 июня 2019, "День рождения"

Привет! Давай знакомиться! Меня зовут Дмитрий. По профессии я программист. Мне очень нравятся числа, и часто я ловлю себя на том, что могу очень долго наблюдать за бегущими на экране монитора цифрами... Для меня это, наверное, как смотреть на горящий огонь.

В последнее время мне всё больше не дает покоя мысль о том, что огромные вычислительные мощности современных компьютеров большую часть времени просто не используются. Возьмём, например, обычный домашний ПК. Если Вы не участвуете в каком-нибудь проекте распределённых вычислений (скажем, WCG или GIMPS), не играете в видеоигры сутками, не монтируете видео, то почти всё время, пока Ваш ПК включен, его процессор используется менее, чем на 1%!

Я думаю, что было бы здорово, если бы в свободное время эти компьютеры занимались чем-нибудь, пусть даже не очень значимым с точки зрения науки. Например, поиском каких-нибудь интересных чисел. И вот сегодня, когда я набираю на клавиатуре эти буквы и слова, на календаре уже 12 июня, то есть 10 дней позднее той даты, события которой я собираюсь описать. Начало, пожалуй, будет сумбурным, но я постараюсь всё объяснить и не запутаться. :)

Итак, этот день, воскресенье 2 июня 2019 года, можно считать днём рождения проекта. В этот день я начал писать первые строки кода (а саму идею, скорее всего, я обдумывал на тот момент уже третий день — ещё с пятницы). Сначала я назвал проект просто "Палиндром" (Palindrome), и полагал, что в будущем он станет частью других моих математических околонаучных исследований (этот большой проект, состоящий и разных проектов помельче, я бы назвал акронимом ILWN, что расшифровывается как In Love With Numbers).

Немного позднее в этот же день, после нескольких коротких экспериментов, я окончательно определился с целью проекта, и решил дать ему более подходящее название. Так, он стал называться MDPNMost Delayed Palindromic Number, что в переводе на русский означает "наиболее отложенное число-палиндром".

В этом дневнике я буду рассказывать, в основном, о задачах и проблемах проекта, их решении, и достигнутых результатах.