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

[Dmitriy40]

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

Что изменится, если я смягчу критерий и скажу про 30-значные?

Что изменится если я приведу и 58-значные примеры? Дело не в значности аргумента, а в алгоритме.
Да и вот он:
3068116869172087761177210402011159793623043312278257436879: [1, 6, 465835188239624691170389341124218347, 6586271167634194621357]
Надо ещё больше числа? Или уже хватит? Я могу и 100-значных наловить.

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

Может вы неправильно понимаете в чём заключалось моё утверждение.

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

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

Дальше со своими утверждениями и их пониманием разбирайтесь сами.


Кстати Z_pollardbrent тоже не свободна от этого недостатка:

? Z_pollardbrent(535500,100,2)
%1 = [4284, 125]

[Yadryara]

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

Дальше со своими утверждениями и их пониманием разбирайтесь сами.

Как-то это не очень дружелюбно, что ли.

Я-то разобрался со своим утверждениями, а точнее предположениями. А вот вы их, похоже, пока не понимаете.

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

Что изменится если я приведу и 58-значные примеры?

Смотря сколько примеров приведёте. Я хотел привести 6 сотен с чем-то, но опубликовать не смог. Но сто с лишним смог.

Вроде оба моих предположения очень трудно опровергнуть.

[Dmitriy40]

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

Чтобы этого не происходило, нужна вспомогательная функция
isNULL(x=0)=x
И запускать через неё,

Можно проще, обернуть Z_pollardbrent в iferr и всё:

? Z_pollardbrent(127,100,2)
  ***   at top-level: Z_pollardbrent(127,100,2)
  ***                 ^-------------------------
  *** Z_pollardbrent: bug in , please report.
  ***   Break loop: type 'break' to go back to GP prompt
break> break

? iferr(Z_pollardbrent(127,100,2),E,[])
%2 = []
? iferr(Z_pollardbrent(127,100,8),E,[],errname(E)=="e_BUG")
%3 = []

Можно конечно и не только пустой вектор возвращать, тут уж по желанию.

[Yadryara]

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

алгоритм Полларда не гарантирует нахождение ни наименьшего делителя, ни его простоты.

Конечно не гарантирует. И что? Именно потому что не гарантирует я и предлагал проверять и его и частное на псевдопростоту:

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

Находить один фактор, а затем проверять и его и кофактор на псевдопростоту.

Так как вы опровергли мои утверждения?

[wrest]

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

Кстати Z_pollardbrent тоже не свободна от этого недостатка:

Ага, и почему-то не разложило найденный множитель хотя бы на два.

-- 16.03.2026, 16:47 --

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

Можно проще, обернуть Z_pollardbrent в iferr и всё:

Помойму это так же (эквивалентно). За исключением что NULL это точно не нашёл, а iferr это то ли не нашёл, то ли стек переполнился.

-- 16.03.2026, 16:50 --

Dmitriy40
Интересные находки (насчёт полларда). Это говорит нам о том, контролировать факторизацию просто только в случае табличного поиска. Остальное (поллард и далее со всеми) носит случайный характер.

[Yadryara]

wrest, вот вы в последнее время меня хорошо понимаете. Как вы считаете, Дмитрий опроверг мои утверждения, которые сегодня процитировал?

-- 16.03.2026, 17:01 --

Вот мои предположения:

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

На всякий случай: при каждом вызове реализованный алгоритм Поллард ищет не мелкие множители, а ровно один фактор, который, вероятнее всего, самый мелкий и к тому же простой.

[Dmitriy40]

Yadryara
Слова "вероятнее всего" мне проверять и опровергать лень. Слишком много надо набрать статистики чтобы закрыть все лазейки осмысливания что может значить "вероятнее всего".

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

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

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

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

а iferr это то ли не нашёл, то ли стек переполнился

А вот для этого и есть последнее условие в iferr, что ошибка именно e_BUG, а не e_STACK и не какая-нибудь ещё.

[Yadryara]

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

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

Вот именно. Я же об этом и говорил, что трудно опровергнуть. На всякий случай специально сделал аккуратную оговорку: вероятнее всего, то есть вероятнее других исходов. Которые в обоих случаях сводятся к одному исходу, противоположному. Так что и не надо какие-то лазейки искать.

Смысл-то простой:

Фактор будет меньше частного чаще чем не меньше.
Фактор будет простым чаще чем составным.

[Dmitriy40]

Та же проблема и для ECM:

? Z_ECM(3068116869172087761177210402011159793623043312278257436879,10,2,3500)
%1 = 289867
? factor(%)
%2 =
[17 3]

[59 1]

Хотя тут зависимость уже от двух чисел, и от seed, и от B1.

Ещё интересный пример:

n=4178525; print(n,": ",Z_pollardbrent(n,100,2))
4178525: [25, 169, 989]

Все три делителя составные и взаимно простые.

wrest
Iferr оказывается может и не сработать, а вот Ваша isnull справляется:

? iferr(Z_pollardbrent(99053,1000,2),E,print(E))
error("bug in , please report.")
? iferr(Z_pollardbrent(99053,10,2),E,print(E))
  ***   bug in simplify, NULL input, please report.
  ***   Break loop: type 'break' to go back to GP prompt
break>break

? isnull(Z_pollardbrent(99053,10,2))
%4 = 0

[wrest]

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

Как вы считаете, Дмитрий опроверг мои утверждения, которые сегодня процитировал?

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

-- 16.03.2026, 18:41 --

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

Iferr оказывается может и не сработать, а вот Ваша isnull справляется:Код:

Isnull придумал ув. maxal (я по крайней увидел именно у него).
Ну и там же тоже можно не ноль вернуть, а что что хочешь. isnull(x=[])=x вернёт пустой вектор

? isnull(x=[])=x
%1 = (x=[])->x
? isnull()
%2 = []
?

-- 16.03.2026, 18:44 --

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

*** bug in simplify,

Кстати, если убрать simplify (в defaults) то выпадает в segmentation fault
Т.е. результат возвращается интерпретатор ному упрощателю, и тот падает от null. А если упрощателя убрать, то возвращается куда-то в другое место в интерпретаторе, где и падает

[Yadryara]

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

Ага.

Что значит "Ага"? Это значит опроверг или нет?

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

Ну я не берусь разбирать ваши утверждения буквально,

Буквально и не надо. Вам понятен смысл моих предположений?

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

Dmitriy40 привёл очень хорошие примеры, показательные.

И что они показывают? То, что фактор(3-е возвращаемое число) может быть больше чем частное(4-е возвращаемое число)? Да, показывают. Но ведь с этим ни вы, ни я и не спорили.

Что они показывают? То, что фактор(3-е возвращаемое число) может быть составным? Да, показывают. Но ведь с этим ни вы, ни я и не спорили.

Так чем они очень хороши? Разве они опровергают мои слова? Ведь у меня было гораздо примеров обратного.

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

А мои примеры не очень хороши? Может мне и сейчас надо было конкретные числа указать? И на простоту проверить? Сейчас попробую сделать и то и другое.

[Yadryara]

Ну вот в 7-ю фильтрацию вставил печать того, что возвращает алгоритм Полларда с добавленной проверкой фактора (3-го числа) на простоту:

1   10426      34512619         63517972052849054548564343392831355323702004719   prime
1   14199      64943363         11446375784742884927749687881882528837160267183   prime
1    8055      174180977            1740399303562094405742496506324740244030089   prime
1    2188      10639439      11612955332427050125552424293175700773641442844001   prime
1   71576      70164304943        612701851079948693487917408776112632174654273   prime
1   83160      67297664779       2382635585296359797479355322194182075184761901   prime
1    4075      103377761        65308074960365740769755156281346411292819822917   prime
1    2056      1259689        2644529054533071945584218359769757157597724048817   prime
1    1575      2223113        1631688533070575452003585541800345950205261000933   prime
1    4347      35591483       3839356334472375496725161602164268654683930713053   prime
1     947      4087253       23636700325046227864963403566443339262587327490483   prime
1   18483      125270333        31081166603132153189997434358901733491314602761   prime
1    4150      41636339         49852726218624830712294588102835806188946635371   prime
1   10512      163097009        11799667468598063769947899901023597173432281273   prime
1   57229      852860663       159353452085035439792592470066123103591014371273   prime
1    3148      9358081         151862052862428834195192446706770741734718120849   prime
1    5964      116664521         7914654029425246357349562985527498996925551179   prime
1    1157      1185979          38086160586036598280420604122014970772466256183   prime
1    1558      1351829       41835728814978999255901571065016019689835460333171   prime
1     612      2241691         739119478926709655735851718695513294654151698777   prime

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

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

[Yadryara]

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

Дано.
Число $n$ не делится нацело ни на одно простое от $0$ до $2^{20}$.
Реализация алгоритма Полларда.
__________________________________________________________________________
Если эта реализация для числа $n$ возвращает в качестве 3-го параметра число длиной не более 12-ти десятичных знаков, то это число равно $p^m$, где p — простое, m — целое положительное.

[wrest]

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

Число $n$ не делится нацело ни на одно простое от $0$ до $2^{20}$.

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

[Yadryara]

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

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

С моей стороны да, я продолжаю именно об этом говорить, ибо проверка до $2^{20}$ делается уже в 4-й фильтрации. Она же была ещё у вас в функции и никуда с тех пор не делась, разве что степень я чуть менял. Освежили воспоминания?

Но Дмитрий, похоже, этого не понимает.

Вы имели в виду примеры очень показательны тем, что они этого не учитывают?

Число, которое Дмитрий привёл в обоих примерах, раскладывается аж на 11 факторов и все они меньше этого порога:

? factor(465835188239624691170389341124218347)
%22 =
[   17 3]

[   53 1]

[   59 1]

[  157 1]

[  211 1]

[  239 1]

[ 2039 1]

[10861 1]

[38747 1]

[45833 1]

[97381 1]

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

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