2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 101, 102, 103, 104, 105, 106, 107 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение26.07.2022, 20:11 
Аватара пользователя


29/04/13
7227
Богородский
Dmitriy40 в сообщении #1561147 писал(а):
Проверять один-два-десять паттернов смысла нет, проверять надо весь комплект из 46080 штук.

Конечно. Это же для тестов. Проверили один паттерн(тот самый) и (о чудо!) сразу нашли 15-шку :-)

Dmitriy40 в сообщении #1561147 писал(а):
если там поддерживается AVX2

Удалённый комп: Intel Xeon E3-1240 v5.

Пересылать каждый раз пусть даже не 3, а 1ГБ - трафика может не хватить. У меня 15ГБ почти на месяц.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение26.07.2022, 21:11 
Аватара пользователя


11/12/16
13311
уездный город Н
Yadryara в сообщении #1561167 писал(а):
Intel Xeon E3-1240 v5.


4 ядра, всего 8 потоков. 3.5 ГГц. AVX2.
Если в монопольное использование, то примерно раза в два больше чем у меня:
потоков столько же, но сильно выше частота и AVX2.
Вы не хотите рекордные цепочки посчитать?
Если качать ускорители из облака сразу на сервер, то Ваш локальный трафик не будет расходоваться :wink:

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение26.07.2022, 21:57 
Заслуженный участник


20/08/14
11177
Россия, Москва
Yadryara в сообщении #1561167 писал(а):
Удалённый комп: Intel Xeon E3-1240 v5.
Пишут AVX2 поддерживается.
Запустите там любой ускоритель (.exe файл с двумя параметрами, можно взять у меня из облака любой вариант, M12n15 или M36n13, в них есть AVX2 версии, скачать кажется можно и один .exe из архива, не обязательно весь архив) и посмотрите не будет ли ошибок и будет ли более-менее адекватный выхлоп (можно сравнить с выхлопом x32 SSE версии), т.е. список найденных кандидатов. Даже и PARI не нужен, только один .exe.
Yadryara в сообщении #1561167 писал(а):
Пересылать каждый раз пусть даже не 3, а 1ГБ - трафика может не хватить. У меня 15ГБ почти на месяц.
Организуйте и компиляцию там. Под x64 PARI она будет и быстрее вашей. Останется пересылать только файлы M12mods1.patterns и Yadryara5.gen.gp и ... и всё, пределы счёта и так одинаковые.

Кстати, компиляцию (не только там, у Вас тоже) можно ускорить где-то вдвое (с 0.5с у меня до 0.25с) заменив в Yadryara5.gen.gp обратно накопление длинной строки в переменной на вывод в файл, только не каждого слова (как у меня было изначально), а строки выходного файла. Вот два файла, Yadryara5.gen.gp и Yadryara6.gen.gp, т.е. старый (что у Вас должен быть, за исключением параметров в начале) и новый с 6-ю отличиями (оба кстати показывают время на компиляцию, удобно сравнивать): https://dropmefiles.com/XI7tz - надо будет в M12mods1.cmd поменять Yadryara5.gen.gp на Yadryara6.gen.gp, остальное менять не нужно, файл .inc оставлен под той же пятёркой, как и .v, в общем разберётесь (добейтесь сначала чтобы 6-я версия генерировала идентичный старым файл .inc, а потом уж сравнивайте скорость и запускайте в работу для всех паттернов).

EUgeneUS в сообщении #1561174 писал(а):
4 ядра, всего 8 потоков. 3.5 ГГц. AVX2.
Yadryara
Вот кстати, я не обратил внимания что ядер 4, а потоков 8, если Вам выделят один поток, то не факт что он будет реально считать на указанной скорости, тут сильно зависит от того что ещё считается на компе. Но AVX2 (да и SSE) там очень вряд ли задействуется (кажется PARI в таком не замечен), так что скорость AVX2 команд будет максимальной, ну а остальное уж как получится, но этого остального в коде немного. Хотя без эксперимента я не берусь оценивать скорость.
Зато кэш L3 уже 8М против ваших 1М, можно сильнее развернуть внутренний цикл (массив bb[]) и ещё ускорить счёт. Но нужны тесты для выбора оптимального варианта.

EUgeneUS в сообщении #1561174 писал(а):
Вы не хотите рекордные цепочки посчитать?
Если качать ускорители из облака сразу на сервер, то Ваш локальный трафик не будет расходоваться :wink:
Yadryara
Тут имелось в виду уже выложенные у меня в облаке ускорители.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение27.07.2022, 06:00 
Аватара пользователя


29/04/13
7227
Богородский
EUgeneUS в сообщении #1561174 писал(а):
Вы не хотите рекордные цепочки посчитать?

Хочу и считаю. 4-й месяц уже в одиночку считаю. 3 рекордных цепочки нашёл. О чём ещё мечтать? :-)

EUgeneUS в сообщении #1561174 писал(а):
Если качать ускорители из облака сразу на сервер, то Ваш локальный трафик не будет расходоваться :wink:

На какой сервер? И откуда они в облаке возьмутся?

Dmitriy40 в сообщении #1561179 писал(а):
Тут имелось в виду уже выложенные у меня в облаке ускорители.

Ну так они же для других задач.

EUgeneUS, Вы мне предлагаете бросить то что я делаю и заняться другими задачами? А почему? Мы же так и не выяснили что полезней для человечества.

Dmitriy40, Огромное Спасибо. Конечно я изучу что Вы написали. Но сегодня целый день в отъезде буду.

А вместо того, чтобы качать туда-сюда гигабайты, предлагаю вернуться к моему старому предложению:

Yadryara в сообщении #1552455 писал(а):
каждый компилит у себя.

Я этому научился. И другие наши коллеги при желании смогут.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение27.07.2022, 08:33 
Аватара пользователя


29/04/13
7227
Богородский
Отличная новость. Вчерашняя, правда. Тот тестовый прогон по поиску уже известной 15-шки, который у меня выполнился за 13 минут 10 секунд, на Xeon-е выполнился за 5 минут! И это ведь без всякой оптимизации!

А другой комп, знаменитая Черепашка, AMD E2-3200
APU with Radeon. Модель p6-2000ru. На нём тоже был запуск, но совместно с ещё двумя прогами. 20 минут. Можно ли делить 20 на 3 и считать, что в чистом виде прога работала 7 минут?

Кстати, можно ведь в переборную пари-программу вставить и автоматическое засекание скорости. Всё, убегаю.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение27.07.2022, 13:58 
Заслуженный участник


20/08/14
11177
Россия, Москва

(Оффтоп)

Yadryara в сообщении #1561200 писал(а):
И другие наши коллеги при желании смогут.
Могут. При желании. Пока что у некоторых даже желание использовать ускорители не дошло до практического воплощения, что уж говорить об сильно сложнее компиляции.
Плюс одной компиляцией подготовка к счёту не ограничивается, по хорошему надо бы проводить тесты на максимально скоростной вариант (это хорошо Вам когда все паттерны почти одинаковые и числа в одном диапазоне и потому можно выбрать оптимум один раз и потом уже не париться, потеря скорости если и будет, то незначительная), да ещё и bb[] каждый раз заполнять можно (и желательно) по разному.
А если паттерны с заметно разным количеством проверяемых мест, то ещё и алгоритм допроверки в PARI переборе можно менять туда-сюда, для разной величины чисел он тоже имеет разные оптимальные варианты.
Для выкладываемых комплектов ускорителей это всё делаю я, после компиляции и до выкладывания в облако, и это занимает бОльшую часть времени подготовки. Иногда я даже забиваю на некоторые этапы и беру приблизительно оптимальный вариант, не проверяя так ли это на самом деле.
В общем пока зоопарк комплектов ускорителей не слишком велик, проще самому всё проделать и выкладывать (почти) готовый результат, ну пока место в облаке не кончилось. :-)

Yadryara в сообщении #1561204 писал(а):
На нём тоже был запуск, но совместно с ещё двумя прогами. 20 минут. Можно ли делить 20 на 3 и считать, что в чистом виде прога работала 7 минут?
В данном случае процессор не поддерживает гипертрейдинг, потому квантование времени происходит по целым ядрам и прогам, а значит можно считать что два ядра выполнили три проги (точнее одну прогу и два куска других прог по 20 минут каждый) за 20 минут, значит одно ядро выполнило бы за 40 минут, значит одно ядро одну программу выполнило бы за 40/3=13 минут. Две идентичные программы (или одну в двух диапазонах) можно было выполнить на двух ядрах тоже за 13 минут. Не за 7 минут! Чтобы одна программа выполнялась на двух ядрах за 7 минут надо в неё саму вводить распараллеливание по ядрам/потокам, чего в ускорителях нет и видимо не будет (ибо мне лень писать нормальный интерфейс с пользователем, это сложнее чем весь уже работающий код, а без него будет неудобно пользоваться, это полезно лишь тем кто "скачал, запустил и забыл").

Для процессоров с гипертрейдингом (как Xeon) ситуация сильно сложнее: если другие проги не использовали активно AVX2 или SSE, то так считать уже нельзя. Вообще делить общее время на количество потоков можно только для идентичных прог, в любом другом случае зависимость скорости может быть любой, от 1/n до 1/1. Потому что AVX/SSE команды могли выполниться с полной скоростью 1/1 (ведь команд от других потоков нет и можно выполнять только от вашего потока), а весь остальной код со скоростью 1/n, но вот реальную долю AVX/SSE команд никто не измерял (не в штуках, а в тактах, тем более для конкретно того процессора). Навскидку доля AVX/SSE команд больше 80%, но ... это сильно "на глаз".

Yadryara в сообщении #1561204 писал(а):
Кстати, можно ведь в переборную пари-программу вставить и автоматическое засекание скорости.
Так ведь такое измерение есть давным давно, вот эти числа в секундах: N=22773549, 2574.036s (398.021s in PARI) per round 500e35.
Другое дело что эти времена не слишком точные (особенно второе), но тут уж ничего не поделать, нет в PARI нормальной функции замера времени (на самом деле это ещё сильно повезло что одна функция из трёх выдаёт время только самого PARI, без внешних прог, вообще говоря это глюк, но оказался полезным). Замерить время в ускорителе можно, не просто, но можно, но будет большая погрешность (не менее 20мс на каждый вызов ускорителя, т.е. на 46080 паттернов погрешность составит не менее 15 минут) и особой надобности в этом я не вижу (в отладочных версиях ускорителей замер времени встроен, но в PARI оно не передаётся). По идее полного времени на круг достаточно (а оно достаточно точное, мс 20-50, если колебания на одном и том же диапазоне чисел больше, то это уже из-за вмешательства ОС), именно оно важно для планирования работы, остальное лишь информация к размышлению и оптимизации.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение27.07.2022, 16:49 
Заслуженный участник


27/06/08
4058
Волгоград
Dmitriy40
Помнится, Вы где-то приводили пример того, как организуется на PARI факторизация с ограничением по времени. Сейчас порылся в теме, но не нашел :cry:

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение27.07.2022, 18:06 
Заслуженный участник


20/08/14
11177
Россия, Москва
VAL в сообщении #1561241 писал(а):
Помнится, Вы где-то приводили пример того, как организуется на PARI факторизация с ограничением по времени. Сейчас порылся в теме, но не нашел :cry:
Да похоже я и не приводил в теме код, только в комплекте к ускорителям.
Делается так:
1. В начале отдельной строкой включаем запоминание больших простых: default(factor_add_primes,1);
2. Ограничиваем время факторизации скажем 4-мя секундами: alarm(4,factor(n));
3. Либо проверяем что она вылетела по ошибке (окончания времени) условием типа if(type(alarm(4,factor(n)))=="t_ERROR", f=factor(n,2^24); , k=numdiv(n);); - если ошибка, то быстро получаем что нашлось (факторизация по простым до 2^24 быстрая, а бОльшие простые сохранились от предыдущей factor), иначе (вылет не по ошибке окончания времени) получим точное количество делителей (это быстро, ведь факторизация уже была проведена до конца).
4. Либо получаем всю найденную факторизацию командой f=factor(n,2^24); (делители до 2^24 проверит снова, а остальные сохранились от предыдущей factor) и проверяем что последнее число простое ispseudoprime(f[matsize(f)[1],1]) — значит факторизация закончена.
5. По окончании факторизации одного числа или всей цепочки хорошо бы очистить таблицу найденных больших простых командой removeprimes(addprimes());

Но имейте в виду что alarm() глючит.

Ещё можно ограничить время факторизации прямо в factor(n,max_p), но тогда делители больше max_p обнаружены не будут (если они не были найдены до того или не добавлены в таблицу простых командой addprimes([]);), вероятно за исключением одного наибольшего.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение27.07.2022, 18:38 
Заслуженный участник


27/06/08
4058
Волгоград
Dmitriy40
Спасибо!

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение28.07.2022, 03:23 
Аватара пользователя


29/04/13
7227
Богородский
Dmitriy40 в сообщении #1561179 писал(а):
Кстати, компиляцию (не только там, у Вас тоже) можно ускорить где-то вдвое (с 0.5с у меня до 0.25с)

Что ж Вы раньше-то молчали :-) Я уже 16 комплектов скомпилил старым способом. 737 тысяч паттернов.

При компиляции 17-го комплекта попробовал 6-ю версию файла Yadryara6.gen.gp. Правда, с 5-й тщательно не сверял.

Первоначально было ускорение. Но не вдвое, а на 20%. Потом скорость вернулась к прежней. Позже понял, что надо держать каталог Фасма закрытым, потому что происходит постоянное переписывание Yadryara5.gen.v. и отображение этого: файл то появляется в каталоге, то исчезает. Ускорение снова появилось.

Кстати, я имел в виду более удобную засечку времени. Например, сколько времени тратится на группу(720 паттернов). Потому что время компиляции для отдельных паттернов сильно скачет: я видел значения от 62 до 140 миллисекунд(ms).

Раньше было больше 9.5 минут на группу, теперь порой удаётся уложиться в 8 минут, то есть до 22% ускорение достигается.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение28.07.2022, 04:57 
Аватара пользователя


29/04/13
7227
Богородский
Компиляция очередного подкласса(11-192) закончена.

46080 программ ждут, когда ими займётся Ахиллес. Тот, который Xeon. Даже учитывая, что это 32х проги, ему понадобится всего лишь 15-20 часов на полный обсчёт до 11е35.

Dmitriy40, напишите, пожалуйста, инструкцию. Как заархивировать с почти 3-х Гб до одного. Как переслать через ф/о. И что делать получателю.

А сам не буду как обычно запускать счёт, а попробую скомпилить ещё один подкласс 11-210.

Dmitriy40 в сообщении #1561179 писал(а):
Организуйте и компиляцию там. Под x64 PARI она будет и быстрее вашей.

О чём и речь. Доступ к Ахиллесу ведь не у меня, а у нашей общей знакомой. Если пойдёт навстречу и научится сама комплить, то дело пойдёт с головокружительной быстротой.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение28.07.2022, 09:48 
Заслуженный участник


27/06/08
4058
Волгоград
Dmitriy40 в сообщении #1561248 писал(а):
Делается так:[..]
Реализовал, запустил.
Dmitriy40 в сообщении #1561248 писал(а):
Но имейте в виду что alarm() глючит.
К сожалению, регулярно происходит именно то, что описано в ссылке. Запустил на ночь несколько потоков. Все вылетели примерно через час.

PS: Кстати, удалось обойтись без ispseudoprime. Вот фрагмент кода.
Код:
if(type(alarm(10,factor(nn)))=="t_ERROR",
      g=factor(nn,2^24);nb=matsize(g)[1];if(nb<4,tt=tt+1;E[u[j]]=0,break),
      g=factor(nn); if(numdiv(nn)==16,ss=ss+1,break))

PPS: Я правильно полагаю, что последний factor можно опустить?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение28.07.2022, 14:48 
Заслуженный участник


20/08/14
11177
Россия, Москва
Yadryara в сообщении #1561260 писал(а):
Что ж Вы раньше-то молчали :-)
Дык сам не знал, вот решил проверить и оказалось что лучше именно так, сразу и сообщил.
Кстати, замер времени через gettime() оказался бракованным, она выдавала 3.3с (видимо столько работал именно PARI), а реально тратилось 12с (а это тратилось где-то вне PARI). Видимо надо переделать на getwalltime().
Yadryara в сообщении #1561263 писал(а):
Dmitriy40, напишите, пожалуйста, инструкцию. Как заархивировать с почти 3-х Гб до одного. Как переслать через ф/о. И что делать получателю.
Взять любой архиватор, поддерживающий solid режим архивации (когда архивируются похожие файлы), например свободный 7-zip. Заархивировать (лучше каждую группу отдельно чтобы архивы получились поменьше, не все ф/о допускают гигабайтные файлы), причём лучше вместе с общей папкой в которой всё и лежит. Выложить в файлообменник. Переслать ссылку получателю. Там скачивают сразу на целевой комп и разархивируют (либо тем же архиватором, либо может даже сама винда сможет .zip открыть), получая сразу отдельную папку с готовыми к запуску программами. Запускают (тут снова много вариантов как это организовать). Сообщают Вам что насчиталось и/или передают любым способом логи.
Разумеется чтобы там было поменьше вопросов надо самому всё сначала проверить, можно на небольшом подмножестве всех паттернов (тупо оставить по паре в каждой группе).
Ф/о можно любой, хоть тот же dropmefiles.com, хоть гуглодиск, хоть яндексдиск, хоть мейлоблако, любой кто даст выложить нужный объём.
Гигабайт вроде даже и почтой можно переслать, не любой, но попробуйте.
Yadryara в сообщении #1561263 писал(а):
О чём и речь. Доступ к Ахиллесу ведь не у меня, а у нашей общей знакомой. Если пойдёт навстречу и научится сама комплить, то дело пойдёт с головокружительной быстротой.
Последнее не обязательно, да и я бы на это не надеялся, а сделал полностью готовый комплект файлов в одном архиве с .cmd, чтобы только распаковать и запустить .cmd для компиляции и потом .gp для счёта и всё. Всю папку FASM вполне можно положить прямо вместе с исходником, возможно надо только переменные среды настроить чтобы он знал где искать свои .inc файлы. Это точно проще чем научить другого(-ю) компиляции.

VAL в сообщении #1561275 писал(а):
К сожалению, регулярно происходит именно то, что описано в ссылке. Запустил на ночь несколько потоков. Все вылетели примерно через час.
Ну извините, гарантированного способа это исправить я не знаю, только исправление исходника PARI и перекомпиляция.
Я перед alarm() делаю один-два прохода по цепочке просто factor(n,max_p) с max_p=2^15 и 2^24 (второй так как он заметно медленнее первого и на этом тоже можно экономить), относительно много чисел имеют малые делители и не доходят до alarm(), соответственно и глюки возникают реже (на удивление у меня вот уже месяц их не было вообще). Вот кусок работающего кода (тут второй проход 2^25, я не упираюсь в конкретные значения, главное чтобы не меньше 2^24):

(Оффтоп)

Код:
            n=p0+pm*vi[t];
            if(n<h || n>=h+step, next); \\Исключение возможного дублирования цепочек на краях интервала step
            if(!ispseudoprime((n+d1-1)/vv[g,d1]) || !ispseudoprime((n+d2-1)/vv[g,d2]) || !ispseudoprime((n+d3-1)/vv[g,d3]), next);
            s=nd*zz[g,]; removeprimes(addprimes()); rr1=0; rr2=0; rr3=0; rr4=0; rr5=0; rr6=0;
            a=nn\2+1; while((a--)>0,
               if(s[a]==nd, next, s[a]>0, break); if(ispseudoprime((n+a-1)/vv[g,a]), s[a]=numdiv(n+a-1); break);
               f=factor(n+a-1,2^15); fn=matsize(f)[1];
               if(ispseudoprime(f[fn,1]), s[a]=numdiv(n+a-1); if(s[a]==nd, next, break));
               if(prod(i=1,fn-1,f[i,2]+1)>nd/3, s[a]=1; break);
            );
            if(a>0, next);
            b=nn\2; while((b++)<=nn,
               if(s[b]==nd, next, s[b]>0, break); if(ispseudoprime((n+b-1)/vv[g,b]), s[b]=numdiv(n+b-1); break);
               f=factor(n+b-1,2^15); fn=matsize(f)[1];
               if(ispseudoprime(f[fn,1]), s[b]=numdiv(n+b-1); if(s[b]==nd, next, break));
               if(prod(i=1,fn-1,f[i,2]+1)>nd/3, s[b]=1; break);
            );
            rr1=b-a-1;
            if(rr1<nn, next);
            if(rr1>=nn,
               a=nn\2+1; while((a--)>0,
                  if(s[a]==nd, next, s[a]>0, break);
                  f=factor(n+a-1,2^25); fn=matsize(f)[1];
                  if(ispseudoprime(f[fn,1]), s[a]=numdiv(n+a-1); if(s[a]==nd, next, break));
                  if(prod(i=1,fn-1,f[i,2]+1)>nd/3, s[a]=1; break);
               );
               b=nn\2; while((b++)<=nn,
                  if(s[b]==nd, next, s[b]>0, break);
                  f=factor(n+b-1,2^25); fn=matsize(f)[1];
                  if(ispseudoprime(f[fn,1]), s[b]=numdiv(n+b-1); if(s[b]==nd, next, break));
                  if(prod(i=1,fn-1,f[i,2]+1)>nd/3, s[b]=1; break);
                  );
               rr2=b-a-1;
         \\      if(rr2<nn, next);
            );
            if(rr2>=nn,
               a=nn\2+1; while((a--)>0,
                  if(s[a]==nd, next, s[a]>0, break);
                  if(type(alarm(1,factor((n+a-1)/vv[g,a])))!="t_ERROR", s[a]=numdiv(n+a-1); if(s[a]!=nd, break);
                  ,   f=factor(n+a-1,2^25); fn=matsize(f)[1];
                     if(ispseudoprime(f[fn,1]), s[d]=numdiv(n+a-1); if(s[a]==nd, next, break));
                     if(prod(i=1,fn-1,f[i,2]+1)>nd/4, s[a]=1; break);
                  );
               );
               b=nn\2; while((b++)<=nn,
                  if(s[b]==nd, next, s[b]>0, break);
                  if(type(alarm(1,factor((n+b-1)/vv[g,b])))!="t_ERROR", s[b]=numdiv(n+b-1); if(s[b]!=nd, break);
                  ,   f=factor(n+b-1,2^25); fn=matsize(f)[1];
                     if(ispseudoprime(f[fn,1]), s[b]=numdiv(n+b-1); if(s[b]==nd, next, break));
                     if(prod(i=1,fn-1,f[i,2]+1)>nd/4, s[b]=1; break);
                  );
               );
               rr3=b-a-1;
         \\      if(rr3<nn, next);
            );
            if(rr3>=nn,
               a=nn\2+1; while((a--)>0,
                  if(s[a]==nd, next, s[a]>0, break);
                  if(type(alarm(7,factor((n+a-1)/vv[g,a])))!="t_ERROR", s[a]=numdiv(n+a-1); if(s[a]!=nd, break);
                  ,   f=factor(n+a-1,2^25); fn=matsize(f)[1];
                     if(ispseudoprime(f[fn,1]), s[d]=numdiv(n+a-1); if(s[a]==nd, next, break));
                     if(prod(i=1,fn-1,f[i,2]+1)>nd/4, s[a]=1; break);
                  );
               );
               b=nn\2; while((b++)<=nn,
                  if(s[b]==nd, next, s[b]>0, break);
                  if(type(alarm(7,factor((n+b-1)/vv[g,b])))!="t_ERROR", s[b]=numdiv(n+b-1); if(s[b]!=nd, break);
                  ,   f=factor(n+b-1,2^25); fn=matsize(f)[1];
                     if(ispseudoprime(f[fn,1]), s[b]=numdiv(n+b-1); if(s[b]==nd, next, break));
                     if(prod(i=1,fn-1,f[i,2]+1)>nd/4, s[b]=1; break);
                  );
               );
               rr4=b-a-1;
         \\      if(rr4<nn, next);
            );
Где-то это в виде функций оформлял, где-то копипаста, не суть, главное идея что сначала прохожу factor (тут от центра к краям), потом, если цепочка не отброшена, уже alarm.
VAL в сообщении #1561275 писал(а):
PPS: Я правильно полагаю, что последний factor можно опустить?
Да, он ничего полезного не делает (если вам нужно только количество делителей, а не полное разложение), numdiv и сама справится с разложением, раз уж оно завершилось успешно.
Кстати рекомендую alarm запускать минимум дважды (а лучше трижды): очень часто factor хватает и секунды найти один-два больших делителя и установить что делителей больше (или меньше) нужного. Потому я обычно делаю проверки по 1-7-60 секунд.
VAL в сообщении #1561275 писал(а):
Кстати, удалось обойтись без ispseudoprime.
Я бы не убирал: возможна ситуация, когда первая factor вылетела по окончанию времени, но при этом нашла большой делитель и не успела проверить остаток на простоту, а вторая factor использовала найденный делитель и быстро установила простоту остатка, т.е. разложение фактически завершилось, но выполнение пошло по ветке окончания времени. Маловероятно, но вдруг.
Плюс проверка matsize<4 конечно правильная, но она пропустит решение например с кубом большого простого вместо произведение двух. Это вообще нереально, но всё же. Я для себя отказался от таких простых проверок в пользу более универсальной, пусть и медленнее, она не столь часто выполняется и уж точно на порядки быстрее factor.

-- 28.07.2022, 15:04 --

Yadryara в сообщении #1561260 писал(а):
Кстати, я имел в виду более удобную засечку времени. Например, сколько времени тратится на группу(720 паттернов). Потому что время компиляции для отдельных паттернов сильно скачет: я видел значения от 62 до 140 миллисекунд(ms).
Проблема (моих исходников) в том что для них нигде нет разницы к какой группе принадлежит паттерн, они вообще не делятся по группам (в PARI программах), деление на группы есть только в .cmd, а там замерить время нереально. Хотел я сделать деление паттернов по группам в PARI (зачатки этого уже есть, для вывода инфы в заголовок окна), но потом плюнул, не так уж это надо.
Ну и скачки времени 60-140 мс вообще говоря ни о чём, там же минимум 20мс погрешность, плюс на таких масштабах это сильно зависит от внешних факторов (ОС, как быстро файл прочитается и запишется, не вмешаются ли другие процессы на пару квантов 20мс переключения задач, да ещё и частота процессора может скакать, и т.д.). Вообще любые измерения менее нескольких секунд следует считать не слишком адекватными, погрешность может достигать нескольких десятых секунды. Чтобы мерить время точнее надо существенно усложнять метод измерения, никакой реальной потребности в этом не вижу (когда важно сравнить именно чистые скорости выполнения, тогда и тесты пишутся специальные, с замером количества тактов процессора).

А, да, время компиляции легко определить по дате/времени готовых .exe, не между соседними, а между сотнями или группами.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение28.07.2022, 15:39 
Заслуженный участник


27/06/08
4058
Волгоград
Dmitriy40 в сообщении #1561289 писал(а):
Ну извините, гарантированного способа это исправить я не знаю, только исправление исходника PARI и перекомпиляция.
Я не в упрек. Наоборот, спасибо, что предупредили! А то бы я часов несколько ошибку у себя искал.
Кстати, сегодня с утра всего один раз слетело. А потоков запущено больше, чем на ночь.
Dmitriy40 в сообщении #1561289 писал(а):
Я бы не убирал: возможна ситуация, когда первая factor вылетела по окончанию времени, но при этом нашла большой делитель и не успела проверить остаток на простоту, а вторая factor использовала найденный делитель и быстро установила простоту остатка, т.е. разложение фактически завершилось, но выполнение пошло по ветке окончания времени. Маловероятно, но вдруг.
Учитывая временные затраты на factor и ispseuoprime, полагаю это практически исключено.
Но чисто теоретически... В общем, если не лень будет, переделаю.
Dmitriy40 в сообщении #1561289 писал(а):
Плюс проверка matsize<4 конечно правильная, но она пропустит решение например с кубом большого простого вместо произведение двух. Это вообще нереально, но всё же. Я для себя отказался от таких простых проверок в пользу более универсальной, пусть и медленнее, она не столь часто выполняется и уж точно на порядки быстрее factor.
Ну, это, вообще, экзотика (в терминологии Евгения). Правда, один случай, когда в наименьшей подходящей цепочке участвует $p^5$ вместо $p^2q$ известен. Это $T(3,4)=242$. Но, вполне возможно, что он и есть единственный.

-- 28 июл 2022, 15:45 --

Что касается последовательных фильтров, то я их уже использую.
Сначала просто factor(n,2^16), потом alarm(10,..) и и затем alarm(60,..).

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение28.07.2022, 16:46 
Заслуженный участник


20/08/14
11177
Россия, Москва
VAL в сообщении #1561292 писал(а):
Сначала просто factor(n,2^16), потом alarm(10,..) и и затем alarm(60,..).
Я и говорю, это не слишком оптимально: все трудно разложимые места, не имеющие делителей до 2^16, будут проверяться по 10с, даже если там есть 100500 легко находимых делителей больше 2^16 и пара (и более) трудно находимых, что в общем не редкость, хотя часто хватило бы и 1с или 3с (найти достаточно делителей чтобы отбросить всю цепочку). Жаль что нельзя поставить меньше 1с.
Потому считаю оптимальной проверку factor с удобным пределом (не более 2^20, дальше уже заметно медленнее), может и дважды (я когда то приводил Вам пример вашей же программы когда две проверки 2^14+2^22 были быстрее одной 2^22) и потом alarm с 1с-3с, это отбросит практически все легко разложимые варианты, а вот дальше уже можно и десятки и сотни секунд выделять.
Использовать ли factor с 2^24 после 2^16 это вопрос, с одной стороны она тоже неплохо фильтрует (не одно число, а все числа в цепочке), с другой занимает время. Factor без ограничения не очень понятно до какого порога проверяет малые простые, мне кажется я видел случаи когда она находила большой делитель пропуская при этом даже делители до 2^15, но не очень уверен.

-- 28.07.2022, 16:52 --

VAL в сообщении #1561292 писал(а):
Учитывая временные затраты на factor и ispseuoprime, полагаю это практически исключено.
Я бы оценил как примерно 1 к миллионам (ispseudoprime выполняется сотни тысяч раз в секунду, а время на factor Вы выделили 10с), но на миллиардах проверок это вполне может сработать и не однажды ... Правда ничего страшного не будет, ну найдётся следующая цепочка и всё, Вы же не минимальность доказываете. В общем да, перфекционизм. ;-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3218 ]  На страницу Пред.  1 ... 101, 102, 103, 104, 105, 106, 107 ... 215  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group