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

[Yadryara]

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

Ещё, раз код именно такой, то в нём оказывается нет "терапевтики" т.е. отброса цепочек в которых простые 3..53 попали внутрь цепочки и увеличили степень.

Только недавно написал, что у меня она есть.
На 2-й фильтрации терапевтика по 2 и 3.
А на 3-й фильтрации — остальная, до 73 включительно.

И уже ранее писал, что степень 3-ки в нужном месте именно 5-я, так как я делаю 6-кратный шаг, но в отдельных программах задаю остатки 243 и 486 по модулю 729. Но не 0.

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

Этим кажется Антон и занимается.

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

И подчеркну, куб может сыграть только для бо́льших простых, начиная с 79.

[Dmitriy40]

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

Так я-то думал что их там просто не может быть

Вот потому я и спрашивал про какой конкретно код речь, у меня и у Антона их быть не может, цепочки с ними исключаются ещё до попыток факторизации. А у Вас оказывается нет.

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

Тут сейчас назревает вопрос: а нифиг нам вообще знать из какого паттерна собрана цепочка...
Просто считать делители, да и всё.

Да, разумеется можно и так. Только придётся подсчитать и простые начиная с 2, а это типа лишняя работа уже проведённая при составлении паттерна.
Плюс паттерн нам нужен для получения n0 и m и потом из них n цепочки. Не для факторизации - если не обращать внимания что простые 2..53 из чисел цепочки уже исключены (кроме высших степеней) как раз паттерном.

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

После проверки переполнения по таблице простых, я сейчас проверяю нет ли чисел, у которых делителей заведомо нехватит. Таких чисел, по всей видимости, очень много. По крайней мере фильтр проходят очень мало.

Так это тоже требует вызова ispseudoprime, причём уже без второго аргумента, ибо ошибка тут уже недопустима! И немало таких вызовов будет впустую, она вернёт 0 и придётся копить делители дальше и снова вызывать её же. Фактически должно получиться что ispseudoprime вызывается не раз на цепочку, а для каждого найденного делителя для любого места в цепочке - чтобы проверить точную недостаточность делителей. Т.е. в разы больше раз на цепочку. А ispseudoprime как раз самая медленная из всех использованных и Вы хотите её вызывать чаще ... Т.е. фильтровать то будет наверное лучше, это да, но зато сильно тормознее.

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

Только недавно написал, что у меня она есть.

А я комментировал не Ваш код, а wrest-а по его ссылке.

[Yadryara]

wrest
Сейчас глянул ваше число. Так оно всего лишь 48-значное. Поиск D(48,21) разве ж актуален... Между 48-ми и 58-значными очень неслабая разница.

Я же вам актуальные наборы дал, для D(96,20). Или у вас не получается запустить?

Специально посмотрел, думаю: разве ж у Дмитрия на 24-странице терапевтики не было?? Да вот же она:

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

for(i=1,oo,\\Не знаю до какого индекса перебирать чтобы накопить 100000 кандидатов на проверку
if(kpod==100000, break);\\Будем копить 100000 кандидатов на проверку
n=n0+m*i*2;\\Получение числа начала кандидата
if((n+#v-1)%3^6==21-19, next);\\Такие n не подходят
if((n+#v-1)%5^3==21-7, next);\\Такие n не подходят
if((n+#v-1)%7^3==21-8, next);\\Такие n не подходят
if((n+#v-1)%11^3==21-14, next);\\Такие n не подходят
if((n+#v-1)%13^3==21-14, next);\\Такие n не подходят
if((n+#v-1)%17^3==21-3, next);\\Такие n не подходят
if((n+#v-1)%19^3==21-2, next);\\Такие n не подходят
kpod++; removeprimes(addprimes());\\Оставшиеся n подходят, будем их проверять и только такие учитываются в 100000

Она конечно весьма ручная, но зато может лучше понятно как делается.

Можете и для моих чисел сделать так же. Только 3^6 проверять не надо.

И цепочки у меня перебираются чуть иначе:

не n=n0+m*i*2

а n = v[1] * (n0 + m * i)

[Dmitriy40]

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

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

И подчеркну, куб может сыграть только для бо́льших простых, начиная с 79.

Может. Но вероятность слишком мала чтобы реально учитывать.
Смотрите, вероятность что в цепочку попадёт квадрат простого $p$ примерно $20/p^2$ (для цепочки длиной 20), а вероятность что в цепочку попадёт куб примерно $20/p^3$. Уже для $p=79$ она всего лишь $20/79^3\approx0.004\%$. И с ростом p она дальше падает. Т.е. с такой вот вероятностью куб простого не будет обнаружен и цепочка пойдёт проверяться дальше и может дойти до факторизации (если она есть в проверках) и куб снова будет найден. Либо, если факторизации нет, то дойдёт до записи в лог и будет перепроверен правильным numdiv и даст правильный valids.
Единственный вариант когда куб может быть полезен - в варианте $p^3q$ вместо требуемых $pqrs$, когда он в паре с ispseudoprime даёт причину отбросить цепочку. В остальных случаях что есть он (и проверили), что нет или не проверили - разницы никакой, цепочка будет проверяться дальше (а время на проверку куба и вызов медленной ispseudoprimt потрачено!). Учитывая редкость такого варианта тратить на него время не считаю выгодным.