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

[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%, то можно было бы отложить на потом.

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

[wrest]

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

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

Ну там надо смотреть на B1; привязка лимита к B1 весьма условная.

-- добавлено через 40 секунд --

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

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

Без единицы.

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

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

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

Так для этого и нужно ТЗ и эталонная функция. Понимаете, может оказаться, что встроенная факторизация работает так же быстро в итоге, потому что там в одном флаконе сразу всё, включая проверку на простоту.
Попробуйте не numdiv(n), а factorint(n,4) Количество простых множителей там же просто считается
nfac=factorint(n,4);
if(#nfac[,1]>2,print("это отбросить"),print("это прошло"));

Более того, numdiv() нативно принимает в качестве аргумента результат факторизации, то есть будет работать конструкция
if(numdiv(factorint(n,4))!=4,print("это отбросить"),print("это прошло"))

Вот вам кастомный ECM (вызов встроенного):

install(Z_ECM,GLLU);
isnl(x=0)=x;
my_ecm(n,rounds,seed,b1)=isnl(Z_ECM(n,rounds,seed,b1));

Эта my_ecm() возвращает множитель или нуль если множитель не найден.
rounds - количество попыток (кривых), чем их больше чем будет дольше работать на "трудных" числах. Я поставил 2, если больше то и находит больше но намного дольше.
seed - "зерно", можно просто ноль
B1 - тайный параметр, вот с ним надо эксперементировать, чем он больше тем дольше будет работать, больше находить но медленнее. Для ваших 270 чисел я бы ставил 800..1600

[Yadryara]

Спасибо.

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

потому что там в одном флаконе сразу всё,

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

Не нужно в одном флаконе сразу всё, потому что задача специально, ради скорости, разбита на несколько подзадач. И вот надо решить маленькую подзадачу — найти фактор, который по величине от сих и примерно до сих. Маленькие простые уже не надо ведь проверять, они проверены ранее.

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

Без единицы.

А мы вроде выяснили что с 1-цей быстрее, а надёжность такая же: если число составное, то оно составное.

[wrest]

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

И вот надо решить маленькую подзадачу — найти фактор, который по величине от сих и примерно до сих.

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

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

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

А мы вроде выяснили что с 1-цей быстрее, а надёжность такая же: если число составное, то оно составное.

А если функция вернула что псевдопростое, то надо ещё проверять.

[Dmitriy40]

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

А мы вроде выяснили что с 1-цей быстрее, а надёжность такая же: если число составное, то оно составное.

Нет, наоборот: если вернула что составное, то число точно составное, но вот если вернула что простое, то число может быть и составным.
Потому проверять на составное можно, это гарантированно (на простое никогда не скажет что оно составное). Но не про все составные числа скажет что они составные.