Спасибо. Но можно ли как-то поподробнее?
Например, что такое слишком слабая проверка на простоту в ускорителях ?
Провёл дополнительное исследование, вот что получается.
Запуск исходной программы VAL (с незначительными изменениями):
N=37832460/16879458/1298669, 229.467s (228.791s in PARI) per round 603914e35.
Здесь 37832460 кандидатов осталось после исключения модулей 2 и 3 (это делается неявно выбором
и
в формуле
), именно столько передано на проверку индексов; 16879458 кандидатов осталось после проверки индексов и передано на первую isprime; 1298669 прошло первую isprime и передано на длинный if; всего ушло 230с (секундная погрешность это дефекты PARI); проверенный интервал 1e35.
Скорость проверки по длинному if (расходы на вывод результатов игнорирую, туда попали всего один раз из более чем миллиона) составила примерно
кандидатов в секунду (коэффициент 11/10 учитывает что проверок в if всего 10, а время считается для 11-ти проверок плюс циклы).
Скорость проверки всех 11-ти мест составила примерно
кандидатов в секунду.
В "натуральном" выражении скорость проверки составила
в секунду или 991e3 шагов/попыток в секунду.
Запуск ускорителя по тому же паттерну фактически в той же программе (только циклы и вычисление
заменены):
N=226994743464/1973614/335311, 156.011s (37.362s in PARI) per round 603e38.
Здесь 226994743464 всего попыток; 1973614 кандидатов вернулось из ускорителя; 335311 из них прошли проверку первой isprime (аналогично программе VAL) и передано на длинный if; всего ушло 156с, из них на долю PARI 37.4с; проверенный интервал 1e38.
Коэффициент фильтрации
.
Расчётное время 11-ти проверок всех 226994743464 попыток без ускорителей составило бы
секунд, что в 19740 раз больше 156с с ускорителями.
Разница 19740х и коэффициента фильтрации 115015 на 72% объясняется большим временем работы ускорителя.
Разница 3080c (для интервала 1e35) и 229с объясняется наличием во втором случае фильтрации по модулям 2 и 3 и индексам, ведь на первую isprime приходит уже в
раз меньше кандидатов.
Скорость проверки по длинному if составила примерно
кандидатов в секунду, в 1.6 раза больше программы VAL.
Скорость проверки всех 11-ти мест составила примерно
кандидатов в секунду, в 1.4 раза меньше программы VAL.
Отличие этих двух скоростей от программы VAL иллюстрирует недостаточную адекватность таких оценок скорости.
В "натуральном" выражении скорость проверки составила
в секунду или 1.455e9 шагов/попыток в секунду, ускорение от программы VAL составило 1468х.
Запуск ускорителя для более коротких интервалов проверки:
N=22699474348/196860/33212, 15.428s (3.775s in PARI) per round 6039e37.
N=2269947437/19624/3316, 1.563s (0.436s in PARI) per round 60391e36.
N=226994746/1961/345, 0.222s (0.093s in PARI) per round 603914e35.
N=22699476/170/41, 0.091s (0.062s in PARI) per round 6039142e34.
N=2269949/14/2, 0.075s (0.046s in PARI) per round 60391422e33.
N=226996/2/1, 0.073s (0.047s in PARI) per round 603914228e32.
Как видно линейность сохраняется лишь до интервала (круга) 1e36, на меньших интервалах резко возрастает влияние накладных расходов и погрешности измерения времени.
Для используемого интервала 1e35 скорость в "натуральном" выражении снижается c 6.41e35 до 4.5e35 или лишь 1030х от программы VAL. Разница между 1468х и 1030х именно из-за недостаточно большого интервала (круга, step) проверки, накладные расходы на множество ускорителей сюда ещё не включены, тут ускоритель ровно один.
Но из этой кучи цифр так и непонятно почему при коэффициенте фильтрации 115015 до проверки на простоту скорость повышается лишь в 1468 раз. Будем разбираться.
Для начала отмечу что в программе VAL тоже присутствует фильтрация (только не внешними ускорителями, а прямо в коде PARI) и фильтрует она в 13.45 раз (в 6 раз учётом модулей 2 и 3 выбором
и
в формуле
и в 2.24 раза по индексам). Этим преимущество ускорителей снижается примерно в 13.45 раз, с 115015 до 8551 раза.
Далее, ускорители выполняются не мгновенно, а за 118.6с, этим коэффициент снижается ещё в
раз, до 2048.
На что списать разницу между 2048х и 1468х я не знаю.
Есть соблазн списать это на то что после первой (и вероятно каждой) isprime количество кандидатов в программе VAL уменьшается в 13.45 раз, а с ускорителями это же количество уменьшается только в
раза, т.е. дальше на длинный if проходит относительно больше кандидатов и соответственно проверка каждого несколько замедляется. Несмотря на якобы бОльшую скорость проверки длинного if, думаю это огрехи метода измерения скорости. Для проверки этого предположения разделил цикл проверки на три с сохранением промежуточных результатов в массив и замерил время каждого этапа — время на фильтрацию (13.45х в PARI для программы VAL или 115015х в ускорителях) + время на первую isprime + время на длинный if:
N=37832460/16879458/1298669, 245.193s=34.634s+197.849s+12.710s per round 603914e35.
Программа VAL, скорость первой isprime
в секунду, скорость длинного if
в секунду, их отношение
.
N=226994743464/1973614/335311, 156.982s=119.681s+32.098s+5.203s per round 603e38.
Ускоритель, скорость первой isprime
в секунду, скорость длинного if
в секунду, их отношение
.
Ну, скорость всех isprime явно ниже и если с длинным if это ещё хоть как-то понятно, то почему замедляется одна первая isprime не совсем ясно (возможно из-за отсутствия малых делителей ей приходится выполнять больше работы).
В итоге предположение верно, скорости isprime меньше, а не больше, выше то был артефакт метода измерения.
Эффективная скорость проверки всех 11 мест в программе VAL составила
кандидатов в секунду, с ускорителями
кандидатов в секунду, в 1.515 раза меньше, что уменьшает выигрыш ускорителей с 2048х до 1352х вместо реальных 1468х.
Вот они и нашлись. А разницу 1352х vs 1468х спишу на погрешности и разницу в коде.
Резюмируя, превращение коэффициента фильтрации 115015 в ускорение всего лишь 1030х получается из-за следующих факторов:
1. В программе VAL тоже есть быстрая (15% общего времени) фильтрация с коэффициентом примерно 13.5.
2. Ускорители выполняются не мгновенно и даже не 15% общего времени, а скорее 76%.
3. Ускорители проверяют простоту чисел не точно, потому
относительно больше кандидатов проходит через каждую isprime, что увеличивает время проверки и снижает скорость.
4. Величина круга (step) 1e35 недостаточна для нивелирования накладных расходов, лучше бы её делать раза в три больше (разумеется пропорционально увеличится время проверки всех паттернов).