Юху! Давно хотел написать данный блог, да никак руки не доходили..

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

Когда дело доходит до проверки маленьких чисел на простоту, то оказалось, что алгоритм можно сделать настолько быстрым, что ввод-вывод даже с безумными функциями по типу __getchar_unlock работает слишком медленно, из-за чего нужно симулировать ввод-вывод через генераторы чисел — я выбрал линейно-конгруэнтный, как "достаточно случайный и быстрый", поэтому из конечного времени алгоритма нужно было вычесть время выполнения генератора(5 ns работал генератор на каждое число в среднем).

Итак, что же за алгоритм я создал?

Всего вышло 2 крутых алгоритма:

1. Оптимизированное решето Эратосфена
2. Миллер Рабин по хэш-таблице с быстрым делением.

1. Здесь мало что можно сказать об алгоритме. 500 ms уходит на генерацию решета, 62 МБайта(1 миллиард чисел было "просеяно") на хранение данных, 3-4 ns уходит на обращение к случайному элементу. Оригинальный код я практически полностью взял откуда-то(уже и не помню откуда, да простит меня тот человек у которого я это взял) и немного модифицировал. Основная идея: сжатие данных при помощи "простых колёс", немного бинарных оптимизаций и кэша процессора делают магию...

2. Алгоритм выходит дольше, чем первый, но у него есть потенциал для улучшений.

• Префакторизация. Проверим на делимость на некоторых малых простых. Важно это делать не циклом по массиву, а "в тупую", тогда компилятор точно умно оптимизирует деление.
• Использование хэш-таблиц. Эту идею я полностью взял из одной бумаги. Идея чем-то напоминает Детерминистского Миллера-Рабина, только вот вместо того, чтобы использовать заранее известные "штук 5 свидетелей" мы проворачиваем числа через хэш функцию мапим к соответствующему значению и используем одного этого свидетеля. Естественно, нужно иметь эту магическую мапу, она тратит память, однако 256 элементов uint16_t занимают половину килобайта, так что проблем с памятью быть не должно.
• Быстрое деление. Чтобы поделить 64битное число на другое 64битное число можно использовать идею быстрого деления. Не хочу сейчас входить в подробности, но для этого всего безумия нужно много раз вычислять "верхние 64 бита в 64x64 умножении". Конечно же, можно использовать __uint128_t, но я пошёл дальше и нашёл ассемблерную вставку, которая примерно в 1.7 раз быстрее, чем умножение __uint128_t.

Казалось бы, первый алгоритм быстрее, хоть и ценой предпросчёта и памяти, однако первый может стать более интересным, если речь идёт о проверке чисел не из диапазона int32, а из диапазона int64. В той же бумажке есть ещё и таблица для int64, правда она уже побольше. При таких числах можно уже использовать оптимизацию Монтгомери(с ассемблерными вставками, разумеется).

Ладно, пока что это всё. Это был мой первый блог в этой потрясающей платформе secroFedoC, так что "подача и форматирование" наверняка "не очень", но мне как-то всё равно. Давно хотел написать на это тему тут, да никак руки не доходили. "Лучше хоть так, чем никак" — подумал я и наконец это сделал. Поки^^