Я разрабатываю библиотеку bignum: http://pastebin.com/nFgF3zjW Я реализовал алгоритм Миллера-Рабина (isprime() ), но он очень медленный по сравнению, например, с BN_is_prime_fasttest OpenSSL.
Я пробовал профилировать, и больше всего выполняются функции bn_shr_atomic и bn_cmp. Любая идея, как я могу сделать это быстрее?
Библиотека арифметики множественной точности GNU реализует Миллера-Рабина. Его документация находится здесь:
http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions
Я бы предложил изучить их реализацию на наличие указателей на ускорение ваших вычислений. Однако арифметика с произвольной точностью по своей сути будет медленнее, чем работа с числами, которые помещаются в регистры.
Редактировать:
Существует также компромисс между используемым алгоритмом и качеством результирующей вероятности. Тем не менее, я не уверен, какой тест использует OpenSSL.
BN_is_prime_fasttest_ex() использует тщательно оптимизированный протокол Миллера-Рабина.
- person President James K. Polk; 27.11.2010
Большая догадка: если вы действительно хотите использовать свою собственную библиотеку, я бы сначала заменил алгоритм деления на длинное деление.
Чтобы подтвердить мою догадку: у вас есть cmp и shr во внутреннем цикле вашего отдела, эти звонки вносят основной вклад в ваш профиль или они поступают откуда-то еще? В целом, когда вы профилируете, вы должны сначала посмотреть на функции более высокого уровня, которые вносят большой вклад, изменение алгоритмов обычно более полезно, чем настройка функций низкого уровня.
