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

[Dmitriy40]

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

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

составных остатков-частных оказалось

Вы это проверяли обычным if(!ispseudoprime(...),1)? У меня пока так делается.

Так вот, с 1 нельзя проверять составное (или простое) ли число. Потому что на некоторые составные вернёт 1 (псевдопростое).
С 1 можно проверять только если функция вернёт что оно составное, то надо предпринять какие-то действия, а если оно простое или вероятно составное/простое (и функция вернула 1 - псевдопростое) - ничего не делать. В коде так и делается, потому и можно с 1. Но это не проверка составное ли число.

--- Added ---

Грубо говоря, в коде if( ! ispseudoprime(x), <code> ) можно добавить вторым аргументом 1, но только в такого вида коде, когда нужен именно факт составного, причём ради скорости не 100% точного (не все составные выявятся, но простые точно никогда не попадут).
Без "!" или с веткой else - добавлять 1 нельзя (в смысле могут быть ошибки).

[Yadryara]

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

Но вы писали, что никакие не делятся до 2^19-2

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

Посмотрите свою функцию, вроде она называется em3, хоть старую, хоть новую. Разве у вас не так?

И если число один раз разделилось на 163, то это учтено в частном. Но оно может и второй раз разделиться, и третий.

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

[wrest]

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

Посмотрите свою функцию, вроде она называется em3, хоть старую, хоть новую. Разве у вас не так?

В em3 да, и это меня тяготило. Мне тут объясняли неоднократно (и вы), что надо частное считать свободным от квадратов. В последней версии, em4, опубликованной тут на 63 странице, высшие степени табличных простых у меня также проверяются post1720864.html#p1720864 :

      \\ на i-е простое разделилось d-е число цепочки
      \\ выясняем не входит ли i-е простое в более высокой степени чем 1
      ai=valuation(n0+k*m+d-1,pr[i]);
      \\ теперь ai равно степени в которой i-е простое вошло в разложение
      ns[d]*=ai+1; \\ накопили сигма-ноль

Но причём тут я? Это же вы писали, что не делится на табличные простые. Дело не в том делится или нет, а в том что вы меряете удава в попугаях, а я в слонятах или наоборот).
Но ещё раз: проверяете на "своих" числах -- дело ваше, не всем нравится сотрудничество и общий язык, понимаю!

[wrest]

Ну в общем и целом получается так, что с этими 270 числами ускорить будет весьма неспросто.
Те из них, которые легко факторизуются "кастомным" ECM, легко факторизуются и встроенным factorint(). В итоге, на "трудные" числа расходуется время как предварительного ECM так и основной факторизации и в сумме выигрыш незаметен.

[Yadryara]

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

Это же вы писали, что не делится на табличные простые.

Я не вполне понимаю что происходит. Уже цитировали что я не робот, а человеку свойственно ошибаться.

И почему если я ошибся, причём несущественно, а затем не только признал ошибку, но и извинился, вы продолжаете об этом говорить? Мои извинения приняты? Ведь надо исправлять ошибки и идти вперёд, не правда ли? Или что?

Вот ваши совсем недавние ошибки:

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

Да. Не оттуда скопипастил.

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

А, ну да

Вы их признали, извиняться не стали. Ну и ладно, никто вроде на вас не обиделся, ни я, ни Дмитрий, хотя Дмитрий считал по этим вашим ошибочным данным.

Признали ошибки, идём дальше. Что не так?

Тем более моя ошибка-то была несущественной. Да, я забыл упомянуть, что квадраты и, возможно, более старшие степени иногда проскакивают. Но настолько редко, что это несущественно.

Вот среди тех 270 чисел с которыми вы работали, много вы видели факторов, которые меньше чем 2^19?

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

Дело не в том делится или нет, а в том что вы меряете удава в попугаях, а я в слонятах или наоборот).
Но ещё раз: проверяете на "своих" числах -- дело ваше, не всем нравится сотрудничество и общий язык, понимаю!

Я как раз наоборот, замечаю, что мы наконец-то уже говорим почти на одном языке. Да, числа я пока брал не ровно те же самые, но однотипные, которые мне выдала программа, это числа которые прошли через 9 фильтров.

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

не всем нравится сотрудничество и общий язык, понимаю!

Шутить изволите?

[wrest]

Yadryara
Я бы рпкомендовал, для дальнейших размышлений, сделать вектор с временами факторизации, например так (Y270.txt -- файл с числами что вы вкладывали).

v=readvec("Y270.txt");
t=vector(#v);
for(i=1,#v,t0=getwalltime();factorint(v[i],4);t[i]=getwalltime()-t0);

И дальше посмотреть что там происходит. Поанализировать...

Можно записать эти времена как бенчмарки.

[Yadryara]

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

Вот среди тех 270 чисел с которыми вы работали, много вы видели факторов, которые меньше чем 2^19?

Что мне самому отвечать на свой вопрос? Ну я попробую. Вот вы привели стату, спасибо.

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

Используется синтаксис Text

Статистика по наименьшим простым множителям
10^6:1
10^7:10
10^8:14
10^9:17
10^10:25
10^11:23
10^12:23
10^13:19
10^14:23
10^15:19
10^16:11
10^17:6
10^18:10
10^19:11
10^20:2
10^21:8
10^22:16
10^23:4
10^24:3
10^25:6
10^26:9
10^27:5
10^28:4
10^29:1

Вижу, что 6-значный фактор только один. Он больше чем 524286 ? Почти наверняка больше.

Почему я так считаю? Да потому что гораздо более вероятно, что через фильтры проскочит именно маленький квадрат. Помню, что рассказывал как проскочил не просто маленький, а именно что минимальный квадрат, который от первого свободного простого — 79. Сейчас рассказал как проскочил квадрат 163, который тоже от одного из первых свободных простых — вроде там свободных простые начинались то ли со 127, то ли со 131.

То есть ни одно маленькое простое число в эти 270 избранных не проскочило?

И, судя по разбросу величин найденных факторов, с помощью ЕСМ они ищутся гораздо более сложным способом, который напрямую не привязан к величине числа. Тогда как вы устанавливали лимит в 10^9 и 10^12 ? Уже после того, как функция выдала вам фактор?

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

Я бы рпкомендовал, для дальнейших размышлений,

Подумаю, я сейчас уже более длинные n смотрю.

[wrest]

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

И, судя по разбросу величин найденных факторов, с помощью ЕСМ они ищутся гораздо более сложным способом, который напрямую не привязан к величине числа.

Приложенная статистика по величинам наименьших простых множителей в 270 числах - это из полной факторизации factor()-ом.

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

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

Тогда как вы устанавливали лимит в 10^9 и 10^12 ?

Наугад, по формуле
B1=floor(exp(0.0750*logint(limit,2)+5.332)/2);
Где limit - это ожидаемый максимальная ожидаемая величина делителя.

Но я понаблюдал как работает встроенный механизм факторизации. Они на "начальной фазе" просто ставят последовательно  B1=800,1000,1300,1600,2200 и проверяют по одной (кажется) кривой на каждое B1, и если не получилось - переходят к MPQS. До второй ("тяжелой") стадии ECM, которая наступает если MPQS не справилось, вроде ни разу не дошло.

[Yadryara]

Есть хорошие новости. Уже удалось получить выигрыш 60% по скорости.

Взял побольше чем обычно: resecm = my_ecm(cha = (n + mes - 1) / (pro[mes] * v[mes]), 5, 1, 5000);

И вот она красавица 74-значная 12-ка нашлась и при такой настройке. Скорее всего можно ещё уменьшить параметры, а она всё равно найдётся.

26312224168260411241527011800317577174205557576749312900680713326735456245     13   12

[Dmitriy40]

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

До второй ("тяжелой") стадии ECM, которая наступает если MPQS не справилось, вроде ни разу не дошло.

Тут Вы кажется плохо понимаете алгоритм: вторая стадия ECM не "тяжелая", а наоборот легкая (потому что достаточно до корня четвёртой степени уже, а часто и ещё сильно меньше), ведь она лишь доразлагает составные делители от MPQS, который кстати не может не справиться, но может найти не простые делители, вот их и доразлагают ECM.
И хотя я это говорю не про PARI, а скорее вообще про QS (в том числе и MPQS и SIQS), но в PARI реализация должна быть похожей.

(MP,SI)QS не может не справиться потому что он строит систему линейных уравнений и потом её решает. И строит её так чтобы количество уравнений превысило количество переменных, т.е. решение есть обязательно (разумеется система получается совместной, т.е. имеющей решения, если на вход подаётся составное число). Это примерно как в КТО выбрать достаточно много модулей чтобы перекрыть их произведением нужный диапазон чисел - тогда восстановление из остатков будет единственным (по общему модулю). Потому не справиться не может, вопрос лишь насколько большая потребуется система уравнений, вот эта оценка иногда чуть ошибается и приходится дополнять систему ещё уравнениями. И потом ещё её решать, что тоже весьма не быстро, но гарантированно. Так что вопрос лишь в требуемой памяти и времени, но делители гарантированно найдутся.

[Yadryara]

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

И вот она красавица 74-значная 12-ка нашлась и при такой настройке. Скорее всего можно ещё уменьшить параметры, а она всё равно найдётся.

Да. Уменьшил с 5,1,5000 до 4,1,4000 и запустил на больший интервал, где старым способом нашлись 6 12-к. И... хотя комп и считал со скоростью на 70-80% быстрее, 4 цепочки из 6 не обнаружил.

Если кто желает поиграться или всерьёз исследовать, то вот они:

26312224168260411241527011800317577174205557576749312900680713326735456245     13   12
63971136825343048749094978892676683299750421994056100801247474889909856245     12   12
99471308849189565569519524313540894542647444653689835226307122441653856245     13   12
30470088979000909073642116609093411675480368362620434836912695687311456245     12   12
15510467269353741786670691981065171840454292652038336512888265822581856245     13   12
28572167827864311031455307068742679898732876112210366031848283524469856245     12   12

1-я и 4-я нашлись, причём для их нахождения достаточно даже 3,1,4000. Кстати, 2,1,4000 ещё не пробовал.

[wrest]

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

Тут Вы кажется плохо понимаете алгоритм: вторая стадия ECM не "тяжелая", а наоборот легкая (потому что достаточно до корня четвёртой степени уже, а часто и ещё сильно меньше),

Меня смутило описание

Цитата:

?factorint
factorint(x,{flag=0}): factor the integer x. flag is optional, whose binary digits mean 1: avoid MPQS, 2: avoid first-stage ECM (may fall back on it later), 4: avoid Pollard-Brent Rho and Shanks SQUFOF, 8: skip final ECM (huge composites will be declared prime).

[Dmitriy40]

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

Меня смутило описание

Да, тут именно и сказано что большие делители после MPQS (да и Полларда с Шенкса) могут оказаться составными, хотя будут выданы как простые. Большие тут имеется в виду не то что MPQS не справится и оставит почти исходное число для финального ECM, а что просто делители после MPQS могут быть сильно больше предварительного ECM, в этом смысле большие.
И тем более что MPQS может и не запускаться, а делители получатся от Полларда и Шенкса (если получатся, эти не гарантируют разложение).
Грубо говоря, делители что не найдёт предварительный ECM и найдут другие методы могут оказаться составными и соответственно существенно больше и для них и запустится финальный ECM.
Конечно если MPQS запрещён, а Поллард и Шенкс не справились, то финальный ECM окажется именно что тяжёлым, но при разрешённом MPQS такого быть не может, он находит делители гарантированно.

[Yadryara]

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

Если кто желает поиграться или всерьёз исследовать

Сам-то я именно что играюсь, меняя в основном эти самые два параметра из 4-х, то есть rounds и b1 из (cha, rounds, seed, b1).

Толком не понимаю как работает ECM. Пытался разобраться, понял что сложно и пока отложил.

Вот у этого числа
26312224168260411241527011800317577174205557576749312900680713326735456248

функция находила 29-значный фактор, но никак не хотела находить 23-значный.

Даже вот так не получалось: resecm = my_ecm(cha = cha/resecm, 100, 1, 100000);

А вот так получилось:

resecm = my_ecm(cha = cha/resecm, 120, 1, 60000);

[wrest]

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

И дальше посмотреть что там происходит. Поанализировать...

Yadryara
Вот как распределились времена факторизации встроенным factorint() по 270 числам:

0000..0010 мс : 10
0011..0020 мс : 12 
0021..0030 мс : 16 
0031..0040 мс : 8
0041..0050 мс : 10 
0051..0060 мс : 8
0061..0070 мс : 6
0071..0080 мс : 3
0081..0090 мс : 4
0091..0100 мс : 5 
0101..0200 мс : 35 
0201..0300 мс : 28 
0301..0400 мс : 6
0401..0500 мс : 1
0501..0600 мс : 2
0601..0700 мс : 4
0701..0800 мс : 5
0801..0900 мс : 4
0901..1000 мс : 4 
1001..2000 мс : 63 
2001..3000 мс : 29 
3001..4000 мс : 7

По секундам:

0..1 с : 171
1..2 с : 63 
2..3 с : 29
3..4 с : 7

Мне все-таки кажется, что если вы хотите факторизовать (вернее, проверить) все числа (из 270) то обогнать встроенный factorint() будет непросто, и пока непонятно как.
Ускорение может быть, если проверить можно не все числа. То есть, если это числа не из 270 разных цепочек.
Но тогда надо вернуться к вопросу постановки задачи.