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

[wrest]

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

Вроде как раз есть. Если количество делителей для любого из 270 приведённых чисел (numdiv(cha)) не равно 4, то цепочка выкидывается.

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

[Yadryara]

Ну вот вы же сами писали.

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

Для протокола, полная факторизация этих 270 чисел у меня на планшете 260 секунд.

"Полная факторизация" делалась через factor или через numdiv? Вроде как numdiv не делает полную факторизацию, но она и не обязательна, то есть нужно только знать равно количество делителей 4-м или нет.

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

Нахождение делителя у 135 чисел при помощи "кастомного" вызова встроенной ECM - 35 секунд.

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

[wrest]

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

По прежнему не понимаю, что это значит и не понимаю почему ровно половина чисел взята.

При заданных (мной) параметрах делитель нашёлся у половины чисел, у второй половины - не нашёлся.

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

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

"Полная факторизация" делалась через factor или через numdiv? Вроде как numdiv не делает полную факторизацию,

Обе делают полную.

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

Ваш (с Квеном) код

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

Самая короткая попытка реализации:

ecm_fast_capped(cha, max_size = 10^12, tries = 15, timeout_sec = 1) = {
\\ B1=10000 покрывает факторы до ~10^12 с вероятностью >90%
my(B1 = 10000);

alarm(timeout_sec, return(1)); \\ Жёсткий таймаут на весь поиск

for(t = 1, tries,
my(f = ellfacteur(cha, 0, B1)); \\ Stage 1 ECM, возвращает первый найденный фактор
if (f && f < cha,
if (f <= max_size, return(f)); \\ Нашли маленький → возвращаем
\\ Если фактор > max_size, пропускаем эту кривую
);
);
return(1); \\ Подходящий делитель не найден
}

Работать не будет, функция которую вы хотите использовать, объявляется (файл /pari/src/basemath/ifactor1.c) так:

/* ellfacteur() tuned to be useful as a first stage before MPQS, especially for
 * large arguments, when 'insist' is false, and now also for the case when
 * 'insist' is true, vaguely following suggestions by Paul Zimmermann
 * (http://www.loria.fr/~zimmerma/records/ecmnet.html). --GN 1998Jul,Aug */
static GEN
ellfacteur(GEN N, int insist)
{

То есть принимает два параметра, а не три.

[Yadryara]

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

При заданных (мной) параметрах делитель нашёлся у половины чисел

Понял, это так совпало, что ровно половина — 135 из 270.

Какие величины делителей? Можно глянуть на что-то типа таблички?

К примеру:

7-значные — 40 штук; 114 миллисекунд на штуку.
8-значные — 34; 198 миллисекунд на штуку.
9-значные — 21;
10-значные — 15;
...
13-значные — 1;

Статистика конечно интересна. Я сам планирую собирать, но хочу это делать на пустом компе, а он пока занят. Кстати, могу ещё сгенерить наборы — там числа будут в среднем на 4-5 порядков больше. Это уже для 12-к.

[wrest]

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

Какие величины делителей? Можно глянуть на что-то типа таблички?

Можно было бы, если бы в ТЗ давалась эталонная функция которая делает табличку, требовалась бы табличка, а не просто "если количество делителей не равно 4, отбросить"
Ну вот что есть.
Лимит 10^12

? fact_vec("Y270.txt",10^12,2)
Загружаем вектор из файла Y270.txt
Загружено 270 чисел, начинаю проверку ECM. | Лимит: 10^12 | кривых: 2 | B1=1927

Всего факторизовано: 141 из них | отброшено: 84 | меньше лимита: 106 | больше лимита: 35
Время быстрой проверки 42736 мс | скорость 6 чисел/сек
time = 42,445 ms.
?

Лимит 10^9

? fact_vec("Y270.txt",10^9,2)
Загружаем вектор из файла Y270.txt
Загружено 270 чисел, начинаю проверку ECM. | Лимит: 10^9 | кривых: 2 | B1=910

Всего факторизовано: 131 из них | отброшено: 76 | меньше лимита: 42 | больше лимита: 89
Время быстрой проверки 15337 мс | скорость 17 чисел/сек
time = 15,280 ms.

То есть из 270 чисел удалось найти делитель у 131 числа. Из этих 131 числа, после деления числа на найденный делитель, составных остатков-частных оказалось 76 (отброшено). Всего же из 131 найденного делителя 42 оказались меньше 10^9 и 89 оказались больше 10^9

[Yadryara]

Спасибо. Похоже что оптимум лимита где-то в районе 10^9 — 10^10.

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

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

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

Если так, то нужно только именно вот это быстрое корректное нахождение одинокого фактора от 2^19 — 2^21 до 10^9 — 10^10. Если возможно, хочу попробовать сразу в программу внедрить и тестить.

И опять остаётся вопрос: а что делать со второй половиной чисел, откладывать на потом или вовсе выбрасывать. Если бы их было мало, не половина, а 20-30%, то можно было бы отложить на потом.

А вдруг лучше будет выбрасывать вовсе. Или промежуточный вариант — выбрасывать цепочки с частными определённого размера и/или вида.