2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Обязательно ли в десятичной записи числа будут единицы?
Сообщение17.07.2017, 13:57 


20/08/14
2517
Россия, Москва
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-х часов счёта.
Ну пожалуй и всё, как видите ничего сложного, всё самые обычные техники оптимизации программ.
Наибольший эффект дают разумеется четыре вещи: уменьшение операций деления (ну и умножения) во внутреннем цикле; замена вычислений на таблицу в кэше; сортировка таблицы по возрастанию; своевременный обрыв перебора.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group