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

[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-цей быстрее, а надёжность такая же: если число составное, то оно составное.

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

[Yadryara]

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

Нет, наоборот: если вернула что составное, то число точно составное

А почему "наоборот"? Я ровно это и сказал:

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

если число составное, то оно составное.

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

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

Алгоритм Полларда, насколько я понимаю, по-другому работает.

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

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

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

seed - "зерно", можно просто ноль

Пока проверяю в интерпретаторе. Не, нельзя ноль, ругается. А вот так получается:

? my_ecm(507402582355514267845633283581441744161387429508744204861,1,1,1)
%29 = 163

? my_ecm(2274633165407473584539333838684760203042562977884469509221,1,1,64)
%30 = 9979273

? my_ecm(11793505344104936975044392557241108958304762813475679759,1,1,68)
%27 = 680742149

[wrest]

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

Алгоритм Полларда, насколько я понимаю, по-другому работает.

Поллард тут, видимо, бесполезен по скорости.
Вот кстати статистика

Используется синтаксис Text

Статистика по наименьшим простым множителям
10^6:1
10^7:10
10^8:14
10^9:17
10^10:25
10^11:23
10^12:23
10^13:19
10^14:23
10^15:19
10^16:11
10^17:6
10^18:10
10^19:11
10^20:2
10^21:8
10^22:16
10^23:4
10^24:3
10^25:6
10^26:9
10^27:5
10^28:4
10^29:1

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

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

Не, нельзя ноль, ругается.

Странно.
Третье число в вашем списке

? my_ecm(856627785511734165079590481074009130364404427984961283,5,0,1600)
time = 197 ms. 
%1 = 930294735031
? factor(856627785511734165079590481074009130364404427984961283)
time = 2 ms.
%2 =
[            930294735031 1]
[     4368989040712696079 1]
[210761188351863545459867 1]
?

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

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

Пока проверяю в интерпретаторе.

Проверяйте на ваших 270 числах, а не случайных.

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

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

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

И из 270 чисел одно составное, после деления на найденный множитель, таки показывается как простое.

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

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

Не, нельзя ноль, ругается.

А ну да, в исходном коде так:

Используется синтаксис C

/* assume rounds >= 1, seed >= 1, B1 <= ULONG_MAX / 110 */
GEN
Z_ECM(GEN N, long rounds, long seed, ulong B1)
{

Но дальше оно всегда больше единицы т.к. к его вычислениям единица прибавляется
Вы берёте слишком мaленькие B1. В исходном коде они начинаются с 142 и 500 (для разных фаз).
Там их две таблицы, и индекс в таблице вычисляется сложным образом, но первые вот эти.
Так что меньше 142 я бы B1 не брал.

[Dmitriy40]

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

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

Нет, наоборот: если вернула что составное, то число точно составное

А почему "наоборот"? Я ровно это и сказал:

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

если число составное, то оно составное.

Потому что я в словах "если число составное, то оно составное" вижу такой логический вывод: если число составное, то вернёт составное. Т.е. условие на само число, а не на результат функции. А это неправильно. Условие должно быть на результат функции: если вернула составное, то число составное. Слово "число" должно стоять в другом месте, не в условии, а в выводе/результате. Не для всех составных вернётся результат составное. Потому и наоборот.
Либо Вы выразились недостаточно для меня понятно.

[Yadryara]

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

Либо Вы выразились недостаточно для меня понятно.

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

Если (функция сказала что) число составное, то оно составное.

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

Проверяйте на ваших 270 числах, а не случайных.

Правда думаете что на случайных проверяю? У меня их гораздо больше нежели 270.

[wrest]

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

Правда, думаете что на случайных проверяю? У меня их гораздо больше нежели 270.

У вас получилось что число делится на 163

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

? my_ecm(507402582355514267845633283581441744161387429508744204861,1,1,1)
%29 = 163

Но вы писали, что никакие не делятся до 2^19-2
Значит это число не из тех, что требуют "тяжелой" проверки.
Если вы будете смотреть в свои числа, а я в свои, у нас будут разные результаты, которые будет трудно сравнивать.

(Оффтоп)

Впрочем, проверяйте как хотите, дело ваше. Пока фронта для сотрудничества по ускорению не вижу.