Комментарии 21
Круто! Вам бы в репозиторий prime95 зайти - может, мы сидим уже который год и бездарно тратим лишние мегаватты.
Если вы многократно делите на одно и то же число, то можно серьёзно ускорить деление без перехода на числа с плавающё точкой. Деление заменяется на умножение и сдвиги., а взятие остатка можно сделать сразу, не вычисляя частное и затем вычитая. См. https://github.com/lemire/fastmod и https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/
Спасибо за ссылку! Я видел информацию о подобных алгоритмах, и мне они не подходят, поскольку в данном случае делитель - не константный, а зависит от тестируемого числа n.
О, я примерно тем же путём шел когда решал https://highload.fun/tasks/10
Правда у меня в итоге векторизованная где-то в 2 раза быстрее не векторизованной, но и другие трюки использовал. Обязательно поделитесь результатом.
С удовольствием бы посмотрел на ваш код! Мне, как видите, воображения не хватило.
Хотя тут, наверное, можно применить и другой подход - одновременно проверять 4/8 различных чисел из входного потока. Даже не представляю, чем пользовались люди из топа таблицы лидеров.
EDIT: невекторизованная целочисленная версия - Your best score: 248,606, это 23-е место. Если поднажать, наверное смогу стать 22-м =)
EDIT2: интересно, какая часть этого времени ушла на fread, невыгодно же по одной записи дёргать наверное. Это вы мне интересную задачу подкинули...
Да, проверяю по 4 числа одновременно. Главное заранее отсекать большую часть работы (5/6) проверкой на делимость на маленькие делители, довольно красиво сделано, но видимо можно сделать лучше, я использовал для больших libdivide_u32_do_vec256, а для маленьких (2,3,5,7) сообразил трюк с _mm256_shuffle_epi8. Тоже в восторге от результатов первой тройки. Ах да, еще нужно чтение через mmap организовать, в справке от сайта есть пример.
А как проверять сразу по 4? Там же код делает умножения в зависимости от числа нулей числа n-1. Ну и в возведении в степень тоже кол-во умножений зависит от входного числа.
Число нулей и сдвиги можно вычислить невекторизованно. А дальше тест Миллера-Рабина, к примеру, состоит из 2-х частей - возведения в степень и потом возведения в квадрат в цикле.
Возводить в степень сразу 4 числа легко, просто каждый раз, когда произведение каких-то чисел вам не нужно, вычисляйте в этом месте произведение на единицу и число останется неизвенным.
Что касается возведения в квадрат - алгоритм устроен таким образом, что если сделать больше итераций, чем нужно, то корректность проверки не изменится. Надеюсь эти намёки вам помогут.
Я боюсь что в этом случае количество умножений может сильно вырасти. Если кто-то подсунет плохие данные на входе. Тут можно было бы отсортировать или ещё что-то сделать, но это затормозит общий случай. В условии к задаче на хайлоад к сожалению ничего не сказано про данные. Вдруг там на входе все числа составные и код который печатает ноль побеждает.
Максимально дубовая реализация монтгомери вместе с делением по Лемиру улучшила мой результат с 27,223 до 21,820 . Даже обидно как-то, получается раньше я вообще не в ту сторону смотрел. Но теперь до первых мест рукой подать, скорее всего можно те же вызовы _mullo_epi32 в два раза реже делать (у меня на 1 mulmod 3 simd умножения, из которых только два полноценное, и одно урезанное), или от бранча для переполнения вычитания как-то отказаться, его обработка съедает четверть всего времени. Теоретически можно оптимально распланировать умножения по битам степени, и вместо маскировки делать их только тогда когда нужно, это тоже может дать до трети всего времени (умножаем только на половину всех битов).
Я понимаю, что речь в основном шла на векторизацию, но можно было бы упомянуть о быстром делении через сдвиги или оптимизацию монтгомери, ну или о великой оптимизации с использованием хэш-таблиц, чтобы вызывать лишь 1 свидетеля
Умножение Монтгомери позволило бы работать с 32-битным диапазонов, но что-то в данном конкретном случае для 26-битного диапазона оно не быстрее double, почему? И векторизовать там непонятно как, нехватает сильно функций возвращающих верхние биты умножения двух целых чисел.
P.S. Кстати, в Java же добавляют Vector API.
Оптимальным решением по скорости проверки в данном случае было заранее вычислить все простые числа, соответствующие нашим требованиям, и положить их в массив/хеш-таблицу, чтобы потом делать там поиск. Всего их вышло бы около 105 миллионов. Этого я делать не буду, чтобы избежать долгих предварительных вычислений.
Всё-таки не хватает сравнения с этим вариантом. Насколько я помню из своих экспериментов, хорошее решето Эратосфена на этих числах будет очень эффективным и "долгие предварительные вычисления" безо всяких векторизаций укладываются в несколько секунд или около того. Для "хорошести" надо использовать wheel optimization и не совершать грубых ошибок (часто забывают, что "вычёркивать" надо числа начиная с квадрата простого). Хранить числа конечно же стоит в битовом массиве - это 256 МБ всего лишь даже без оптимизаций. С той же wheel optimization в 3-4 раза меньше.
Wheel optimization это когда мы учитываем, что простые числа могут давать только некоторые из остатков от деления на небольшие произведения различных простых чисел. Если wheel только число 2, то остаются только нечётные и 2, если wheel = 2 * 3 = 6, то простые числа больше 3 дают только +-1 по модулю 6 (уже 1/3 чисел осталась), если wheel = 2*3*5 = 30, то остаются 1,7,11,13,17,19,23,29 - 8 из 30. Цикл 2*3*5*7 уже не очень практичен, но возможен. Это можно использовать и в цикле решета и при хранении.
Миллер, Рабин, вектор