Пентадекатлон мечты

[Yadryara]

VAL в сообщении #1714183 писал(а):

Поправил Location в 3-й строке.

Здесь мне удобней равнять по левому краю. А вот если смотреть на попутные рекорды по всему полю, то уже стараюсь равнять строго по месту. 1-я позиция находится под буквой L, а 31-я — под буквой l. Заодно видно положение полосы на поле.

Start                                                     Location                    Valids
860271072720571112089954456681650511473773778437340720921    1 1  11111111 11111111111111 24 Vl
8276466129185709384898037667333514567718482446345938       11111111111111111 1111   11    23 De
9204926595955930659029610200709650474407650679458585         1    1111111111111111111111  23 Vl
12928151557178753218526554700017805780952517953844761        1     1111111111111111111111 23 Vl
8495059548859626592773879865662858605488940747161295961      1    1111 111111111111111111 23 An
15760230758531706844376995032385338075337309353237290641  1111111111111111 111111    1    23 Vl

[Dmitriy40]

Yadryara в сообщении #1714947 писал(а):

Только этого перебора уже давно нет в программе. Мы ведь обсуждали. Применяется короткая арифметика по 20-й степени 2-ки, а не по 15-й. Я тестировал. Оптимальна была 20-21 степень, а не 15-я.

Я его и имею в виду.
Последнее к чему пришли, это к перебору d=n%p по простым и подсчёте nf[#v-d] и как только nf==nu, так проверка isprime. Цикл по n при этом сделан через накопление готовых остатков с Mod. Медленный цикл foreach+factor с порогом 2^20 (и с 2^18) выполняется уже после этой предпроверки (фактически заменяющей factor с меньшими порогами). Во всяком случае у меня в коде именно такая версия последняя.
15-я степень удобно ложится в AVX, следующая удобная 31 (ну или любое простое меньше), но их вдвое меньше в регистрах и потому почти вдвое медленнее цикл, а уж из-за возрастания числа операций медленнее намного (ещё пропорционально количеству простых).
Чисто в принципе могу и написать ispseudoprime на асме для чисел до 6e57 (192 бита) или сразу до 1e77 (256 битов), но это куча нового непроверенного кода, 24 умножения в первом случае и 42 во втором плюс море сложений и пересылок (это всё в произведении по модулю, которое нужно для степени по модулю, которая нужна для теста Ферма на простоту).

[EUgeneUS]

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

Чисто в принципе могу и написать ispseudoprime на асме для чисел до 6e57 (192 бита) или сразу до 1e77 (256 битов), но это куча нового непроверенного кода, 24 умножения в первом случае и 42 во втором плюс море сложений и пересылок (это всё в произведении по модулю, которое нужно для степени по модулю, которая нужна для теста Ферма на простоту).

Если переписать на asm'е

а) расчет запрещенных остатков и проверку на него.
б) ispseudoprime

То это, в купе с моей идеей, которую обсуждали ранее в ЛС, может открыть возможность нахождения $D(36,14)$.
Пока для нахождения $D(36,14)$ не хватает где-то трех порядков в быстродействии, что скрипта PARI\GP, что pcoul.

Числа там будут как раз где-то 1e77. Плюс минус пять порядков

[Yadryara]

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

И да, вопросы ускорения факторизации лучше продолжать в другой вашей теме, где они уже и были.

Вот там и отвечу. И код покажу.

[Dmitriy40]

Прикинул грубо, время ispseudoprime(x,1) для чисел до 6e57 (192 бита) составит порядка 20000 тактов. Для чисел до 1e77 (256 битов) аппроксимирую (код ещё не написал) до 38000 тактов и до 75000 тактов для чисел до 2e96 (320 битов).
При этом вычисление остатков по всем простым до 2^15 для каждого следующего n занимает всего 600 тактов (а до 2^20 порядка 28000 тактов). Плюс проверка если какой-то из них оказался меньше #v, но без ispseudoprime она относительно быстрая (для каждого простого, но не знаю сколько их будет из всех 3500шт).
И получается похоже что выгоднее увеличить базу простых в разы (от 2^15) чем даже однажды запустить ispseudoprime, а ведь она может запуститься почти для каждого места паттерна ...