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

[Dmitriy40]

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

Для мелких делителей (до 2^20..2^22) самый быстрый способ их найти -- перебор.

Это ещё как посмотреть:

? z=vector(10^4,i, nextprime(random([2^15,2^20])) * nextprime(random([10^35,10^36])) );
? n=0; for(i=1,#z, forprime(p=2^15,2^20, if(z[i]%p==0, n++; break) ) ); n
time = 47,800 ms.
%2 = 10000
? n=0; for(i=1,#z, if(isnull(Z_ECM(z[i],3,1,70))>0, n++) ); n
time = 33,712 ms.
%3 = 10000

? z=vector(10^4,i, nextprime(random([2^15,2^22])) * nextprime(random([10^35,10^36])) );
? n=0; for(i=1,#z, forprime(p=2^15,2^22, if(z[i]%p==0, n++; break) ) ); n
time = 2min, 56,142 ms.
%5 = 10000
? n=0; for(i=1,#z, if(isnull(Z_ECM(z[i],5,1,70))>0, n++) ); n
time = 42,292 ms.
%6 = 10000

Тут конечно "подгонка под ответ" (rounds и B1), но всё же, даже для делителей до 2^20 (не говоря уж про 2^22) ECM вполне сравним с перебором. Зато может "случайно" найти и бОльшие делители, в чём его преимущество.

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

Для сравнения Поллард над последним массивом (с делителями до 2^22):

? n=0; for(i=1,#z, f=isnull(Z_pollardbrent(z[i],400,1)); if(type(f)=="t_VEC" && #f>1, n++)); n
time = 12,044 ms.
%7 = 10000

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

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

И это ещё параметры и ЕСМ и Поллард подобраны чтобы они нашли все делители, если же несколько штук оставить ненайденными (на следующий этап), то будет ещё существенно быстрее и тот и тот.

[wrest]

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

Тут конечно "подгонка под ответ" (rounds и B1), но всё же, даже для делителей до 2^20 (не говоря уж про 2^22) ECM вполне сравним с перебором.

Надо не forprime(), a factor(n, 2^20):

? z=vector(10^4,i, nextprime(random([2^15,2^20])) * nextprime(random([10^35,10^36])) );
time = 873 ms.
? n=0; for(i=1,#z, if(isnl(Z_ECM(z[i],3,1,70))>0, n++) ); n
time = 19,483 ms.
%10 = 10000
? n=0;for(i=1,#z,if(numdiv(factor(z[i],2^20))>2,n++));n
time = 2,422 ms.
%11 = 10000
?

Чтобы factor(n,2^22) тоже быстрый был, надо в gprc добавить default с пределом по перебору простых в 2^22 т.е. default(primelimit,2^22)
При том, factor(n,2^22) гарантированно найдёт все множители до 2^22

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

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

Намного быстрее и перебора и ECM.

Быстрее ECM, но не быстрее перебора, конечно.
Тут всё украдено же до нас. Скорость на случайных числах будет выше у встроенной в pari/gp факторизации т.к. они там на этом собаку съели. Обогнать можно только используя специальные знания о предполагаемых делителях. Тогда можно "тонко" настроить Полларда и ECM, под "своё" распределение множителей по их величине.

[Dmitriy40]

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

Надо не forprime, a factor(n, 2^20):

Вообще-то мы отказались от factor(x,2^20) в пользу именно forprime уже достаточно давно ибо factor не умеет проверять несколько чисел цепочки, а с forprime это легко.

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

Тут всё украдено же до нас. Скорость на случайных числах будет выше у встроенной в pari/gp факторизации т.к. они там на этом собаку съели. Обогнать можно только используя специальные знания о предполагаемых делителях. Тогда можно "тонко" настроить Полларда и ECM, под "своё" распределение множителей по их величине.

Тут Вы опять говорите о факторизации одного числа (или вектора независимых чисел), а не всех чисел цепочки до первой неудачи.
Вспомните, с factor(x,2^20) приходилось разбивать один цикл с factor на несколько циклов по всей цепочки с разными пределами в factor. А потом от циклов с factor перешли к одному циклу forprime чтобы делать ровно одно деление независимо от длины цепочки (пока делитель не найден). Т.е. factor должен быть где-то в len раз быстрее forprime, а он быстрее лишь раз в 8, так что для длинных цепочек он по любому невыгоден.
Так что скорость встроенного factor(x,2^20) роли не играет, это позапрошлый этап, он оказался недостаточно быстрым.

[wrest]

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

Вообще-то мы отказались от factor(x,2^20) в пользу именно forprime уже достаточно давно ибо factor не умеет проверять несколько чисел цепочки, а с forprime это легко.

Так ведь и ECM не умеет проверять несколько чисел цепочки.
Я, кстати, для нескольких чисел цепочки использовал не forprime, а обычный for по своей таблице простых.

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

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

Т.е. factor должен быть где-то в len раз быстрее forprime, а он быстрее лишь раз в 8, так что для длинных цепочек он по любому невыгоден.

Ессно, но сравнивать-то надо сравнимое :)

[Dmitriy40]

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

Ессно, но сравнивать-то надо сравнимое :)

Вот поэтому я и сравнивал варианты текущей реализации, а не позапрошлой. Сейчас factor(x,2^20) уже неприменим (точнее от него отказались как от слишком медленного) и потому его скорость вообще не интересна.

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

Я, кстати, для нескольких чисел цепочки использовал не forprime, а обычный for по своей таблице простых.

Это уже должно быть без разницы (по сравнению со всем остальным).

[wrest]

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

Так что скорость встроенного factor(x,2^20) роли не играет, это позапрошлый этап, он оказался недостаточно быстрым.

У Yadryara через фильтр пробного деления пролезают мелкие множители, потому что в том фильтре не проверяется высшая степень найденного множителя, вот и пролезают квадраты и кубы мелких (табличных) простых. Поэтому (наверное) Yadryara вынужден занижать B1 в ECM, чтобы довыловить эти мелкие множители (квадраты и кубы простых). Мне такой подход представляется неверным.

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

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

Это уже должно быть без разницы (по сравнению со всем остальным).

Ну это позволяет не проверять, например, уже вставленные простые. И не зависеть от primelimit и соответственно - размера встроенной таблицы. Если у вас primelimit=2^20, а в forprime вы ставите 2^22 - имеете проблему со скоростью.

[Dmitriy40]

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

Я, кстати, для нескольких чисел цепочки использовал не forprime, а обычный for по своей таблице простых.

И это как оказалось худший вариант:

? pr=primes([2^15,2^22]);
? n=0; for(i=1,10^3, forprime(p=2^15,2^22, if(z[i]%p==0, n++; break) ) ); n
time = 17,410 ms.
%9 = 1000
? n=0; for(i=1,10^3, foreach(pr,p, if(z[i]%p==0, n++; break) ) ); n
time = 16,927 ms.
%10 = 1000
? n=0; for(i=1,10^3, for(j=1,#pr, if(z[i]%pr[j]==0, n++; break) ) ); n
time = 21,044 ms.
%11 = 1000

Разницу 17.4 и 16.9 сильно значимой не считаю (меньше 3%).
Т.е. даже foreach по вашей же таблице простых всё равно лучше for по ней же. По крайней мере в интерпретаторе.

[wrest]

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

Сейчас factor(x,2^20) уже неприменим (точнее от него отказались как от слишком медленного) и потому его скорость вообще не интересна.

Я же утверждал, что trial division быстрее чем ECM и Поллард для поиска множителей до 2^20..2^22, вы привели неоптимальный код (для одного числа, а не цепочки) с forprime, в качестве контрпримера этому утверждению, на что я и указал (неоптимальность/нерелевантность кода с trial division).

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

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

И это как оказалось худший вариант:

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

По крайней мере в интерпретаторе.

Именно! Выигрыш получается при аккуратной типизации и компиляции через gp2c

[Dmitriy40]

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

Вот поэтому я и сравнивал варианты текущей реализации, а не позапрошлой.

Э, тут я не прав, выходит я сравнивал прошлый вариант, где каждое число цепочки делилось на простое, а не текущий, где деление всего одно вместо len.

wrest
Тогда соглашусь с Вами: да, для длинных цепочек перебор простых (циклом с делением) будет выгоднее. Хотя сам по себе перебор делителей и сильно медленнее (ручной, не внутри factor). Получается снова вопрос терминологии (скорость в каких условиях сравниваем).

[wrest]

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

Получается снова вопрос терминологии (скорость в каких условиях сравниваем).

Мы (ну как мы... Yadryara, в основном), сравнивает Полларда, ECM подбирая параметры, для его "фильтрации" которая идёт после пробного деления. Но через его пробное деление пролезают степени малых простых, и поэтому ECM/Поллард должны их находить. Так вот я считаю, что на ECM/Поллард не должны попадать числа с делителями, которые гораздо быстрее отлавливаются пробным делением. Соответственно, B1 надо ставить не 80, а больше.

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

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

Хотя сам по себе перебор делителей и сильно медленнее (ручной, не внутри factor).

При интерпретации медленнее, при компиляции быстрее :) Внутри factor так и вообще, пробное деление отдельно на 2,3,5,7 не делается, сразу по модулю 210 проверяют :)

[Yadryara]

Всё-таки решил для 8-к посмотреть ещё 13 потоков в сравнении с 12-ю. Для этого взял количество паттернов, которое делится и на 12 и на 13:

8-я фильтрация: ECM 1,1,80   9-я: ECM 1,1,80

Potoki   Count     Found    Тime    ms/      Speed
(okna)     pat   D(192,8)    sеc    pat    kor/24h

     6     936       844     858    916      85080
    12     936       844     659    704     110702
    13     936       844     660    704     110642

8-я фильтрация: ECM 1,1,90   9-я: ECM 1,1,80

Potoki   Count     Found    Тime    ms/      Speed
(okna)     pat   D(192,8)    sеc    pat    kor/24h

    12     936       844     650    694     112338
    13     936       844     645    688     113195

Теперь снова взял по три паттерна в юните, а не по 6. На этот раз это дало ускорение со 112 до 118 тысяч:

   Filter   Potoki   Count     Found    Тime    ms/      Speed
    8   9   (okna)     pat   D(192,8)    sеc    pat    kor/24h
ECM b1=
   70  70       12     360       337     249    689     117369
   70  80       12     360       337     246    683     118445
   80  70       12     360       337     249    689     117332
   80  80       12     360       337     246    682     118512
   80  90       12     360       337     248    687     117732
   90  80       12     360       337     247    685     118140
   90  90       12     360       337     247    686     117961
  100  80       12     360       337     248    688     117620

Делал и другие тесты.

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

Так вы ж советов не слушаете

Слушаю. Только на слово обычно не верю, а стараюсь проверять.

Перечислить сколько ваших советов я не просто выслушал, но и выполнил?

А Вы слушаете советы? Пробовали искать цепочки со 192 делителями? Пробовали засекать скорость нахождения?

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

У Yadryara через фильтр пробного деления пролезают мелкие множители, потому что в том фильтре не проверяется высшая степень найденного множителя, вот и пролезают квадраты и кубы мелких (табличных) простых. Поэтому (наверное) Yadryara вынужден занижать B1 в ECM, чтобы довыловить эти мелкие множители (квадраты и кубы простых).

Чего ж фантазировать-то? Вы понимаете, что есть вещи важные, а есть второстепенные? Вы понимаете насколько редко пролезают высокие степени?

Я беру те значения, которые диктует его величество эксперимент.

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

Поэтому я и спрашиваю, сколько и какие цепочки вы нашли? У вас теперь есть стационарный комп? Советы могу давать тока так Раздобудьте комп, посчитайте те же цепочки, что и я, тогда вы будете гораздо лучше понимать меня, а я — вас.

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

Вообще B1 меньшие 100 это дичь какая-то
Там должен трудиться Поллард.

Почему дичь? Сколько у вас нашлось цепочек и с какими настройками?
Где "там"? Почему должен? Он у кого-то занимал или какие-то обязательства давал? Пока нет достаточного обоснования.

Вот у меня нашлись в одной подборке экспериментов 844 цепочки, в другой — 337, показаны здесь же, в этом посте. В третьей — 12, в четвёртой — 13.

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

Я не говорю, что если программа не находит цепочки, то грош цена такой программе. Но всё-таки хотелось бы видеть итоговый результат, а не общие слова.

Вы понимаете как работает программа с 1-й страницы "Пентадекатлона мечты"? Какие с тех пор изменения сделаны в ней?

[wrest]

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

Пробовали искать цепочки со 192 делителями?

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

сколько и какие цепочки вы нашли? У

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

Сколько у вас нашлось цепочек и с какими настройками?

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

[Yadryara]

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

Напоминаю, что мы не в теме про цепочки. Мы в теме про ускорение вычислений.

Напоминаю, что в последнее время речь идёт не о каком-то ускорении вычислений, а именно что об ускорении поиска цепочек.

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

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

Ну нет конечно, как уже написал выше, мне интересны разные советы. И чёрного списка у меня нет и не было. Я читаю мнения разных людей.

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

я не собираюсь искать цепочки.

Ну так соберитесь. В этом же и состоит мой совет. И просьба. Потому что мне интересен более предметный разговор.