Как писать быстрые программы

[Dmitriy40]

wrest в сообщении #1731504 писал(а):

Интересное приключение.

Согласен.
Учитывая что сама primecount считает в один поток до 1e12 за 0.03с, а до 1е13 за 0.1с ... И легко вызывается из PARI.

[wrest]

Dmitriy40 в сообщении #1731510 писал(а):

Учитывая что сама primecount считает в один поток до 1e12 за 0.03с, а до 1е13 за 0.1с ...

Да, ну вот лишенная низкоуровневых оптимизаций (они отданы на откуп компилятору) и многопоточности, на Си++ считает 1е12 за 1.5с, а 1е13 за 5с
Я может потом посмотрю что же так ускоряет, но пока кажется, что это libdivide. Там в "тяжёлой" части алгоритма много делений которые хитро заменяются на умножения.

-- добавлено через 9 минут --

Dmitriy40 в сообщении #1731510 писал(а):

И легко вызывается из PARI.

Я ещё думал то, что написано на pari/gp, подготовить к компиляции в gp2c и посмотреть как поможет, по идее должно. Но главное, что время растёт как $O(x^{2/3})$ а не линейно, а это оч. круто.

И теперь я понял как надо вайбкодить. Кстати рефакторинг primecount в "простой" Си++ я еделал в одной иишке, а рефакторинг в pari/gp в другой. Главная проблема - потеря контекста, оно в самый неподходящий момент начинает забывать что происходит и надо контекст держать наготове.