Обязательно ли в десятичной записи числа будут единицы?

[Dmitriy40]

photon
Ну вот, за 8ч рано утром досчиталось от $10^{18}$ до $10^{19}$. Ничего не найдено. Значит до $2^{64}$ решение всего одно. Дальше считать не вижу смысла (лень программу переписывать, да и медленно уже).
Удивительно.

(Оптимизации)

kotenok gav
Их несколько.
- Вместо подсчёта квадрата произведения цифр для каждого числа предварительно просчитана табличка для чисел 0..99999$. Забавно что все возможные квадраты произведений цифр вмещаются в uint32 (т.е. $<2^{32}$). Именно поэтому выбрано деление на такие группы цифр.
- Соответственно всё число делится на группы по 5 цифр и для них таблично определяется квадрат произведения цифр, перемножив которые получаем результат.
- Как только этот результат превышает величину $2^{64}$ или проверяемое число - переходим к следующему числу, бывает даже не заходя во внутренний цикл.
- Таблица отсортирована по возрастанию квадрата произведений цифр, вместо цикла перебора $0..99999$ в каждой группе сделан лишь проход по таблице для чисел $22222..99999$ (с обрывом цикла по превышению), заодно исключены и все "лишние" числа (с нулями или единицами в записи), из ста тысяч осталось лишь ровно $32768$.
- Парочка мелких оптимизаций на ассемблере во внутреннем цикле, оставлено минимально необходимое количество операций: одно умножение 64х64 и одно деление 64:64, остальное вынесено наружу. Плюс все условные переходы оптимизированы чтобы в большинстве случаев не выполнялись, кроме единственного перехода организации цикла. Плюс точка начала цикла выравнена на 16 байт. Плюс размер таблицы урезан до минимального чтобы вмещалось в кэш. Плюс таблица организована для линейного прохода. Плюс все операции в регистрах, без обращений в память, кроме одной таблицы. Но это уже мелочи, по сравнению с операцией деления на почти сотню тактов. Подумывал разделить одну операцию деления 64:64 на две 64:32 (это и само по себе быстрее, и вторую очень часто можно не выполнять), но лень значительно переписывать программу ради выигрыша 3-4-х часов счёта.
Ну пожалуй и всё, как видите ничего сложного, всё самые обычные техники оптимизации программ.
Наибольший эффект дают разумеется четыре вещи: уменьшение операций деления (ну и умножения) во внутреннем цикле; замена вычислений на таблицу в кэше; сортировка таблицы по возрастанию; своевременный обрыв перебора.