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

[wrest]

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

Разве что-то мешает скомпилить под винду?

Что-то явно мешает, ибо уже б давно кто-то бы сделал, но нет.

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

Ну и свет клином на GMP не сошёлся, уж не может быть не быть библиотек длинной арифметики под винду, да сразу и с ECM факторизацией.

Да, но тогда ваша программа превращается... превращается... Надо писать инсталлятор, версию венды проверятор и всё такое.

Ну то еть у вас лично работать может и будет, а Yadryara как же?

[Dmitriy40]

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

Надо писать инсталлятор, версию венды проверятор и всё такое.

Нафик-нафик. Один самодостаточный exe и всё. В котором всё уже учтено, и библиотека, и версия винды, и тип проца. Как все мои проги (в том числе и на асме) и сделаны.

[wrest]

Yadryara
В общем, пока вас не было, у нас для вас революция.
Доделывайте таймер, и пробуйте инновацию в виде прерываемого parfor
Синтаксис надо проработать, гляньте две страницы перед этой, например моё сообщение тут post1719845.html?sid=59ed497da20bed2b2a3b4326171c90c5#p1719845 -- там факторизация остановилась через 11мс на 3-ем числе. Хотя первое число полностью факторизуется 5 секунд
Будут параллельно факторизоваться числа по количеству [свободных] потоков (если конечно остальные потоки уже не заняты параллельными сессиями), и как только найдется "плохое", сработает прерывание. Ну или все числа дофакторизуются если плохих нет -- тогда бинго, победа.

[Yadryara]

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

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

70 дней вместо 100 — это ускорение почти на 43%, а не на 30%.

Соглашусь, если речь про ускорение (изменение скорости работы), то так и есть.

И обратите внимание, что у меня стоит именно это слово — ускорение.

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

Но часто путается

И эта путаница возникла именно у вас, а не у меня.

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

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

Вы считаете скорости (работ в час) а не темпы (часов на работу) - ну, ваше право

Я использую слова в самом что ни на есть общепринятом смысле. Что в физике, что в быту скорость традиционно измеряется в километрах в час (км/ч) или в метрах в секунду (м/с). Видите что время оба раза стоит в знаменателе?

Допустим, я вышел из Бордуков и мне идти до Москвы 130 км. Иду я со скоростью 1000 метров в день. За 130 дней я до Москвы дойду.

Через какое-то время мне снова понадобилось идти из Бордуков в Москву. И вот я невероятным усилием воли заставил себя увеличить скорость на 30% и теперь иду со скоростью 1300 метров в день. За 100 дней дойду.

О чём здесь спорить-то?

И вот опять мне нужно добраться из Бордуков в Москву. Только дойти надо уже за 70 дней.

Чудовищным напряжением всех сил я смог увеличить скорость почти на 43% и теперь иду со скоростью 1858 метров в день. За 70 дней дойду.

Это что, какой-то сложный или ошибочный подсчёт?

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

Yadryara
В общем, пока вас не было, у нас для вас революция.

Почитаю.

[Yadryara]

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

В общем, пока вас не было, у нас для вас революция.
Доделывайте таймер, и пробуйте инновацию в виде прерываемого parfor

Пока не понял в чём революция. В другом способе прерывания?

И не понял что значит "доделывайте таймер". Вроде бы есть уже несколько довольно-таки рабочих вариантов. И я в них даже немного запутался.

Если пробовать ещё один способ, то по какой причине? Он быстрее работает? Или проще в реализации?

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

там факторизация остановилась через 11мс на 3-ем числе. Хотя первое число полностью факторизуется 5 секунд

Ещё бы, ведь ваш пример со 192 делителями, да ещё и с длиной 20. А мировой рекорд по длине — 14.

Так что не очень в тему, ибо я нынче занимаюсь 96-ю делителями с длиной 20. Мировой рекорд по длине — 19.

Кстати, забыл: как вы сделали, чтобы интерпретатор время счёта показал?

[wrest]

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

Он быстрее работает? Или проще в реализации?

Предположительно, и то и другое. Но надо проверять, конечно.

-- 11.03.2026, 08:10 --

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

И не понял что значит "доделывайте таймер". Вроде бы есть уже несколько довольно-таки рабочих вариантов.

Вот хорошо бы иметь один финальный, чтобы с ним сравнивать.

[Yadryara]

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

Мне нужна программа на PARI/gp. Нужно чтобы факторизация числа была именно прервана, как только станет ясно чему равны фактор и кофактор. Числа, которые подаются на вход заведомо составные.

Вот пример:

Число 83249599403652415669870228237450726343942320967741813929973 раскладывается на 5 факторов. Но меня интересуют только вот эти два числа:

70199 и 1185908622681981448024476534387252330431235786375045427

Потому что
70199 * 1185908622681981448024476534387252330431235786375045427 =
83249599403652415669870228237450726343942320967741813929973

То есть для данного примера нужно в качестве результата получить первый, самый маленький фактор 70199 и второй множитель 1185908622681981448024476534387252330431235786375045427, который не надо пытаться ракскладывать.

factorint(n,1) не выполняет задачи. Он не останавливает факторизацию, когда уже известен первый фактор и второе число(кофактор).

Моя программа называется TestFac_1.gp

[wrest]

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

Так что не очень в тему, ибо я нынче занимаюсь 96-ю делителями с длиной 20.

Это нерелевантные рассуждения. Проверялся случай, когда в цепочке есть числа, которые факторизуются долго и которые быстро. Надо было чтобы цепочка была отброшена как можно скорее. Времена факторизации первых восьми чисел в однопоточном режиме: 4321, 227, 57, 11, 14, 840, 517, 46. Счёт завершился за 11мс на 4-м числе, потрачено соответственно не более 88мс по сумме всех потоков. В конкретном запуске потрачено 11мс реального времени и 25мс по сумме всех потоков. При установке таймера на 50мс, было бы потрачено 161мс реального и столько же по сумме потоков.

-- 11.03.2026, 08:43 --

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

Я сейчас увлёкся другой идеей оптимизации.

Ок, революция подождёт.

-- 11.03.2026, 08:46 --

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

Кстати, забыл: как вы сделали, чтобы интерпретатор время счёта показал?

default(timer, 1)

[DemISdx]

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

А как оборвать не только parfor, но и запущенный в нём унутри factor?! Я способа не знаю. Оно даже по Ctrl+C не всегда обрывается.

Да вроде и нет такого способа.
Поток, если запущен, может только сам завершиться.
Никакого управления, контроля (типа поставить на паузу), над ним (т.е. из запустившего уровня кода) нет.
Можно делать это изнутри потока, кодом, но это всегда чревасто резким замедлением исполнения.
Т.к. переменные внутри потока - атомарны.
Т.е., скажем, некая переменная "а" в первом потоке имеет значение 1, а во втором значение 3, в один и тот же момент времени.
Единственный способ прочитать ее действительное значение для некоего потока, это приостановить поток "на паузу" изнутри, но при этом приостанавливаются все запущенные потоки.
Что сводит на нет все плюсы от многопоточности, если хочется в коде контроллировать (выводить наружу) значение переменных.
Поэтому потоки хороши в своей первичной ипостаси, т.е. "запущенный поток должен завершиться".
Что не очень красиво для длительных вычислений.

[Yadryara]

wrest
Спасибо.

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

Это нерелевантные рассуждения.

С чьей стороны?

Я понял, что вы хотели сказать. Но подозреваю, что вы не поняли о чём хотел сказать я.

Конечно же цепочка-кандидат на 20 чисел с 192 делителями будет быстро отброшена. Да, всё-таки вы проверяли именно первые 8 мест, а не места с 16-го по 20-е не трогали. Но всё равно лучше всё же брать актуальные числа, ибо 192 делителя встречаются гораздо реже чем 96.

[wrest]

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

С чьей стороны?

С вашей. Ваши рассуждения похожи на рассуждения Буратино в диалоге:

Цитата:

Мальвина: Предположим, что у вас в кармане два яблока. Некто взял у вас одно яблоко. Сколько у вас осталось яблок?
Буратино: Два.
Мальвина: Подумайте хорошенько.
Автор: Буратино сморщился, — так здорово подумал.
Буратино: Два…
Мальвина: Почему?
Буратино: Я же не отдам некту яблоко, хоть он дерись!

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

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

Да, всё-таки вы проверяли именно первые 8 мест, а не места с 16-го по 20-е не трогали. Но всё равно лучше всё же брать актуальные числа, ибо 192 делителя встречаются гораздо реже чем 96.

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

Вот DemISdx например не верит, что это возможно сделать без залезания в глубины кода.
Зачем это? Вот:

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

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

-- 11.03.2026, 10:11 --

DemISdx в сообщении #1719880 писал(а):

Поэтому потоки хороши в своей первичной ипостаси, т.е. "запущенный поток должен завершиться".

В нашем случае, первый завершившийся с нужным нам результатом поток прерывает остальные.

-- 11.03.2026, 10:36 --

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

Да, всё-таки вы проверяли именно первые 8 мест, а не места с 16-го по 20-е не трогали.

До мест с 16 по 20 просто не дошла проверка, т.к. закончилась раньше. Чего и хочется, в общем-то.

[Yadryara]

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

Ваши рассуждения похожи на рассуждения Буратино в диалоге:

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

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

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

Это я сразу понял как увидел вашу программу. Я её запускал. И что?

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

Неважно какие и сколько чисел я брал.

Ещё как важно.

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

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

Это я сразу понял как увидел вашу программу. Да, прерывает. Код который мы с Квеном наваяли, тоже прерывает.

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

Зачем это? Вот:

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

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

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

Понятно что для одной цепочки это можно реализовать, но цепочки-то проверяются по меньшей мере тысячами.

[Yadryara]

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

А версию с таймером пока отложу. Тем более что при прерывании всех потоков, она вроде и не очень нужна и может запутать.

Итак, вот цикл на PARI/gp. Как мне его сделать многопоточным? То есть нужно как-то корректно заменить for на parfor?

Оставшихся мест довольно много, обычно больше чем мои 12 потоков. Так что в не более чем 12 потоках надо проверять только места, где выполнится условие if(nu[ostmes[j]] - kolfac[ostmes[j]] == 1, . Получается, надо заранее этот список составить? И назвать его ostmes1. И цикл делать уже от 1 до #ostmes1.

Но что делать если длина #ostmes1 всё-таки превысит 12?

Квен мне предложил через parvector делать...

for(j = 1, #ostmes,

if(nu[ostmes[j]] - kolfac[ostmes[j]] == 1,

t3=getwalltime();

my(res = pollardRho( cha = (n+ostmes[j]-1)/(v[ostmes[j]]*pro[ostmes[j]]) ) );
my(cofac = cha/res);

\\print;print(res, "   ", cofac,"      ", cha);print;

if (!ispseudoprime(cofac,1),

print(ostmes[j], ".  Потрачено ", strtime(getwalltime()-t3), "   Факторов слишком много ");
print(res, "   ", cofac,"      ", cha);
next(2)

,
hormes = concat( hormes, ostmes[j]);
);

));

[Dmitriy40]

DemISdx в сообщении #1719880 писал(а):

Да вроде и нет такого способа.
Поток, если запущен, может только сам завершиться.
Никакого управления, контроля (типа поставить на паузу), над ним (т.е. из запустившего уровня кода) нет.

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

DemISdx в сообщении #1719880 писал(а):

Единственный способ прочитать ее действительное значение для некоего потока, это приостановить поток "на паузу" изнутри, но при этом приостанавливаются все запущенные потоки.

Разумеется нет, читать можно что угодно откуда угодно (пока оно в пределах адресного пространства, но дочерние потоки всегда в нём, работаем в системе с общей памятью). Другое дело что если не хочешь неопределённого значения нужен арбитраж разграничения доступа по записи делающий её атомарной и блокирующей любой другой доступ, читать read only переменные (и некоторые другие, что уже аппаратно зависимо) можно спокойно без арбитража. Мне для арбитража хватает критических секций, гарантирующих лишь эксклюзивный доступ к ресурсу.

-- 11.03.2026, 12:44 --

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

Как мне его сделать многопоточным? То есть нужно как-то корректно заменить for на parfor?

Да.

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

Оставшихся мест довольно много, обычно больше чем мои 12 потоков. Так что в 8 потоках надо проверять только места, где выполнятся это условие. Получается, надо заранее этот список составить?

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

[wrest]

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

А версию с таймером пока отложу. Тем более что при прерывании всех потоков, она вроде и не очень нужна и может запутать.

Я бы посоветовал не откладывать, а доделать. Т.е. выжать из способа с таймером всё что можно, и записать выигрыш. Чтобы было с чем сравнивать.

-- 11.03.2026, 12:48 --

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

Итак, вот цикл на PARI/gp. Как мне его сделать многопоточным? То есть нужно как-то корректно заменить for на parfor?

Не просто на parfor, а на parfor в обёртке iferr.