2014 dxdy logo

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

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




На страницу Пред.  1 ... 41, 42, 43, 44, 45, 46, 47 ... 59  След.
 
 Re: Как писать быстрые программы
Сообщение04.03.2026, 20:30 
Yadryara в сообщении #1719443 писал(а):
Потому что у них есть факторы и дивизоры. И они обозначают этими разными словами разные понятия.

[простые] Множители и делители же :D Число 15 является делителем, но не является [простым] множителем числа 12345
Как-то так...

-- 04.03.2026, 20:33 --

Dmitriy40 в сообщении #1719442 писал(а):
Вообще-то фильтрация по словарю простых это ещё и про структуру addprimes(), которая используется примитивами факторизации.

Ну она "срабатывает" только при повторной факторизации того же числа.

-- 04.03.2026, 20:34 --

Yadryara в сообщении #1719443 писал(а):
Вроде место в цепочке это простое понятие.

"Место в цепочке" да, а просто "место" -- нет.

-- 04.03.2026, 20:38 --

Yadryara в сообщении #1719443 писал(а):
А раньше вы это прекрасно понимали

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

 
 
 
 Re: Как писать быстрые программы
Сообщение04.03.2026, 20:42 
Аватара пользователя
wrest
Вот нашёл такой ваш пост:

wrest в сообщении #1711796 писал(а):
Ну в общем вот код

my(nu=[3, 2, 3, 3, 3, 3, 3, 2, 4, 3, 4, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3]);\\Сколько разных простых делителей должно быть в каждой позиции

my(d); \\ индекс числа от начала цепочки
my(nf=vector(len,d,1)); \\Вектор количества делителей (omega)

\\ вычисляем положение числа которое делится на это простое относительно начала цепочки

nf[d]++; \\ на i-е простое разделился d-й член цепочки накопим по нему омегу

\\Если уже перебор множителей, то отбрасываем всю цепочку

\\Проверка что разложение закончено, а делителей меньше требуемого

"Сколько разных простых делителей должно быть в каждой позиции" — это и есть сколько
факторов надо.

"индекс числа от начала цепочки" — это и есть место. (правда, может на 1 отличаться)

"my(nf=vector(len,d,1)); \\Вектор количества делителей (omega) " — это и есть количество
факторов. Что такое nf ? Разве не number factors ?

"вычисляем положение числа которое делится на это простое относительно начала цепочки" — определяем место.

"накопим по нему омегу" — это и есть сбор факторов.

"Если уже перебор множителей" — это и есть факторов больше чем надо.

"делителей меньше требуемого" — это и есть факторов меньше чем надо.

 
 
 
 Re: Как писать быстрые программы
Сообщение04.03.2026, 21:14 
Dmitriy40 в сообщении #1719439 писал(а):
Хм, и под юниксом возможно и не получится, там в pari_alarm() из pari-2.11.0\src\language\gplib.c вызывается просто alarm(s), в секундах, без пересчёта. :-(

Да, кажись я на это и наткнулся. Ну можно вызов alarm() на что-то другое заменить, но это поломает совместимость. Или делать какой-то свой alarm_ms() который будет считать в миллисекундах, но надо перекомпилировать ядро. Можно ли обойтись сторонней функцией, через install(), не знаю :D

-- 04.03.2026, 21:16 --

Yadryara в сообщении #1719447 писал(а):
Вот нашёл такой ваш пост:

У меня голова не дом советов. Если вы намекаете что надо бы выучить наизусть что написано (в том числе мной) в этой теме, то увы, мне это не по силам.

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

 
 
 
 Re: Как писать быстрые программы
Сообщение04.03.2026, 21:28 
Аватара пользователя
wrest в сообщении #1719449 писал(а):
Если вы намекаете

Совершенно не намекаю. Я подробно прокомментировал конкретные фразы и показал что говорю про то же самое. Надеюсь теперь непоняток у вас нет. Или всё-таки есть?

wrest в сообщении #1719435 писал(а):
Другое дело, конечно, что "потом" может выясниться, что раскладывать трудноразложимое число не надо так как в цепочке нашлось другое слабое звено из-за которого цепочку отбрасываем.

Это уже неоднократно подчёркивалось. И мной и Дмитрием. Нужно как можно быстрее найти причину отбросить цепочку, а вовсе не полностью её, цепочку, разложить.

wrest в сообщении #1719435 писал(а):
Но если не проверять, до уверенности в проверке, все числа в цепочке, то Yadryara не сможет полноценно коллекционировать дротики, ласточек и прочую фауну :D

Насчёт этого не парьтесь, для этого и существует финальная долгая примитивная проверка по numdiv. Но допускаются до неё очень-очень немногие цепочки.

 
 
 
 Re: Как писать быстрые программы
Сообщение04.03.2026, 21:41 
wrest в сообщении #1719449 писал(а):
Или делать какой-то свой alarm_ms() который будет считать в миллисекундах, но надо перекомпилировать ядро.
Если про ядро ОС, то очевидно не надо: в ОС должны быть таймеры на времена меньше секунды. В тиках или мс не знаю, но точно не только в секундах. Так что исправление должно свестись лишь к файлу gplib.c в PARI.

 
 
 
 Re: Как писать быстрые программы
Сообщение04.03.2026, 22:19 
Dmitriy40 в сообщении #1719452 писал(а):
Если про ядро ОС, то очевидно не надо: в ОС должны быть таймеры на времена меньше секунды.

Ядро pari/gp, то место примерно, на которое вы ссылались в /src/language/gplib.c
Используется синтаксис C++
pari_alarm(long s)
{
  if (s < 0) pari_err_DOMAIN("alarm","delay","<",gen_0,stoi(s));
  if (s) timer_start(&ti_alarm);
#ifdef _WIN32
  win32_alarm(s);
#elif defined(HAS_ALARM)
  alarm(s);
#else
  if (s) pari_err(e_ARCH,"alarm");
#endif
}
 


Вместо alarm(s) можно использовать ualarm(ms), см. https://man7.org/linux/man-pages/man3/ualarm.3.html тоже самое что alarm() но в микросекундах.
Ну и вокруг походить - заголовки и прочее, т.е. только к файлу gplib.c не сведётся, если делать свою функцию, и оставть оригинальный alarm() для совместимости.

 
 
 
 Re: Как писать быстрые программы
Сообщение04.03.2026, 22:53 
wrest
Да.

 
 
 
 Re: Как писать быстрые программы
Сообщение05.03.2026, 03:37 
Аватара пользователя
Пока просто попытался заменить alarm(1,factor( который корректно работает (если не считать 4 остановок за полдня) на ualarm(900,factor(.

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

Код:
Rab_243_20_0_test.gp.c:970:66: warning: passing argument 2 of ‘ualarm’ makes integer from pointer without a cast [-Wint-conversion]
  970 |                                     if ((typ(kfnew = ualarm(900, factor(gdiv(gsubgs(gadd(n, gel(ostmes, j)), 1), gmul(gel(v, gtos(gel(ostmes, j))), gel(pro, gtos(gel(ostmes, j)))))))) != t_ERROR) && (glength(gel(kfnew, 2)) > 2))
      |                                                                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                                                                  |
      |                                                                  GEN {aka long int *}
In file included from /usr/include/x86_64-linux-gnu/pari/pari.h:31:
/usr/include/unistd.h:472:64: note: expected ‘__useconds_t’ {aka ‘unsigned int’} but argument is of type ‘GEN’ {aka ‘long int *’}
  472 | extern __useconds_t ualarm (__useconds_t __value, __useconds_t __interval)
      |                                                   ~~~~~~~~~~~~~^~~~~~~~~~
Rab_243_20_0_test.gp.c:970:52: warning: assignment to ‘GEN’ {aka ‘long int *’} from ‘__useconds_t’ {aka ‘unsigned int’} makes pointer from integer without a cast [-Wint-conversion]
  970 |                                     if ((typ(kfnew = ualarm(900, factor(gdiv(gsubgs(gadd(n, gel(ostmes, j)), 1), gmul(gel(v, gtos(gel(ostmes, j))), gel(pro, gtos(gel(ostmes, j)))))))) != t_ERROR) && (glength(gel(kfnew, 2)) > 2))

Потом правда всё же успешно компилит и запускает программу, но позже вылетает по сегментации.

 
 
 
 Re: Как писать быстрые программы
Сообщение05.03.2026, 07:47 
Yadryara
Не, так просто это не заработает. :D

 
 
 
 Re: Как писать быстрые программы
Сообщение06.03.2026, 12:01 
Аватара пользователя
wrest в сообщении #1719461 писал(а):
Не, так просто это не заработает. :D

А как заработает?

Сейчас ситуация такая, что прогресс в такой проверке может стать очень важным, потому что есть хорошая серия с нулевым количеством простых и полупростых. Шаг в 100 с лишним раз меньше.

 
 
 
 Re: Как писать быстрые программы
Сообщение06.03.2026, 13:55 
Yadryara в сообщении #1719515 писал(а):
А как заработает?

Сперва надо определиться вставлять ли новую функцию в ядро или делать в стороне и подключать через паришный install
Затем выяснять как устроена сигнализация в pari/gp чтобы в неё беспроблемно встроиться.
Ну и потом приступать к реализации задуманного.
Т.е. нужно провести R&D :) Для чего нужен специалист, ну или долгое общение с ИИ.
Я спрашивал у Qwen, вот отрывки из его ответа
Цитата:
Поскольку ваша цель — **прерывание долгих вычислений** (например, факторизация, вычисление L-функций и т.д.), вам критически важно, чтобы таймер работал **асинхронно**. То есть он должен прервать вычисление даже внутри встроенных функций ядра PARI, которые не проверяют время в циклах GP.

Подтверждаю предыдущий ответ: **при помощи только `gp2c` это сделать невозможно**. `gp2c` компилирует логику скрипта, но не имеет доступа к системным вызовам установки таймеров с точностью ниже секунды.

Единственный рабочий способ — написать **минимальный C-модуль**, который вызывает системный `setitimer`, и подключить его к GP. Это стандартная практика для расширения функциональности PARI/GP.

Вот готовое решение для Unix-систем (Linux/macOS).


Цитата:
### Почему это работает для прерывания вычислений?

1. **Сигналы:** `setitimer` работает на уровне ядра ОС. Когда время истекает, ОС посылает процессу сигнал `SIGALRM`.
2. **Обработчик PARI:** При старте `gp` регистрирует свой обработчик сигнала `SIGALRM`. Этот обработчик не выполняет код сразу, а устанавливает внутренний флаг или делает `longjmp`, который приводит к выбросу ошибки `"alarm interrupt"`.
3. **Асинхронность:** Это прервет даже функцию `factor()`, `ellinit()` или любую другую встроенную функцию на языке C, которая выполняется долго. Чистый GP-цикл с проверкой `gettime()` так не сможет.

### Важные нюансы

1. **Один таймер:** Как и стандартный `alarm()`, этот таймер одиночный. Вызов `alarm_usec()` сбрасывает предыдущий таймер.
2. **Отмена:** Чтобы отменить ожидающее прерывание (если вычисление закончилось раньше), обязательно вызовите `alarm_usec(0)`.
3. **Вложенность:** Не рекомендуется вызывать эту функцию рекурсивно или из разных потоков (хотя GP однопоточный).
4. **Точность:** Точность зависит от планировщика ОС. Микросекунды поддерживаются, но реальное срабатывание может иметь задержку в несколько миллисекунд под нагрузкой.

Это единственный надежный способ реализовать субсекундный таймаут для прерывания тяжелых вычислений в экосистеме PARI/GP.


Ну как по мне, написано логично.
Промпт:
Цитата:
Можно ли при помощи gp2c создать пользовательскую функцию alarm_usec() в pari/gp которая будет аналогична встроенной alarm() но в качестве аргумента принимать не целые секунды а доли, например микросекунды или миллисекунды? Функция нужна для прерывания долгих вычислений.


-- 06.03.2026, 13:58 --

Yadryara в сообщении #1719515 писал(а):
Сейчас ситуация такая, что прогресс в такой проверке может стать очень важным, потому что есть хорошая серия с нулевым количеством простых и полупростых. Шаг в 100 с лишним раз меньше.

То есть, вы уверены, что уменьшение порога прерывания "долгой факторизации" с 1с до 0,1с заметно ускорит вычисления?

 
 
 
 Re: Как писать быстрые программы
Сообщение06.03.2026, 14:26 
Аватара пользователя
wrest в сообщении #1719531 писал(а):
То есть, вы уверены, что уменьшение порога прерывания "долгой факторизации" с 1с до 0,1с заметно ускорит вычисления?

Не, я уже настроился на миллисекунды. Чего там мелочиться с 10-кратным уменьшением порога :-) Заметно ускорит, конечно. Особенно для длинных цепочек.

Но в железе, процах, переcборках ядер, коде на C и многом другом, я ничегошеньки не понимаю :-)

Шаг уже сделал в 700 тысяч раз меньше. Но вы на это пока не обращайте внимания :-)

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

 
 
 
 Re: Как писать быстрые программы
Сообщение06.03.2026, 14:40 
Yadryara
Судя по тону и смайликам, последнее сообщение целиком состояло из юмора/сарказма, без смысловой нагрузки. Ок, пропускаю мимо ушей.

 
 
 
 Re: Как писать быстрые программы
Сообщение06.03.2026, 14:51 
Аватара пользователя
Неправильно поняли. Сарказма вроде вообще нет.

Ежели желаете сухой остаток моего предыдущего поста:

1. Полагаю, что реально не просто в 10 раз уменьшить порог, а именно в тысячу, до миллисекунд. До тактов — не знаю.

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

 
 
 
 Re: Как писать быстрые программы
Сообщение06.03.2026, 17:28 
Yadryara в сообщении #1719537 писал(а):
1. Полагаю, что реально не просто в 10 раз уменьшить порог, а именно в тысячу, до миллисекунд. До тактов — не знаю.

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

 
 
 [ Сообщений: 874 ]  На страницу Пред.  1 ... 41, 42, 43, 44, 45, 46, 47 ... 59  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group