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

[wrest]

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

Ваша таблица? А в каком смысле негодная? В неё ошибка какая-то вкралась? Какая?

Трудно сказать, просто игнорьте её, вы же готовите такую же, по большему количеству цепочек/чисел?
"270 чисел" неактуальны давно...

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

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

Но, если угодно, могу сделать.

Это будет полезно [вам] для того, чтобы попробовать понять, на какую величину делителей настраивать первый проход ECM.

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

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

Кстати, всё забываю спросить: теперь-то вы понимаете что мы считали, начиная с 14-й страницы?

Мне "считали, начиная с 14-й страницы" ни о чём конкретном не говорит. Так что не знаю, может понимаю может нет.

[Yadryara]

wrest, начиная вот с этого поста.

[wrest]

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

начиная вот с этого поста.

Ну я и тогда и в некоторой части сейчас:

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

мало что понимаю в том что вы говорите, поэтому и помалкиваю.

[Yadryara]

Хорошие новости. Начал постепенно заменять алгоритм Полларда на ECM. Менял пока только параметр B1.

При B1=4000 ECM проигрывал 30000 Pol. Но при 3000 уже выигрывал. Так что в этом я пока правильно сделал, что не послушался wresta. При 2-х и при одной тысяче выигрыш только усиливался.

Тогда решил снова вернуться к весьма коротким цепочкам длиной 7, чтобы посмотреть не теряются ли находки. Сначала вообще не терялись, потом терялись чуток. Результаты:

6-поточный счёт, серия 1-0-6-0.

Фактор          Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
изация          простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут

Pol 1, 30000   3!3!5!5!**    360   17   1e43       1464       522      1449     242526

ECM 1,1, 100   3!3!5!5!**    360   17   1e43       1449       376      1043     333359
ECM 1,1, 200   3!3!5!5!**    360   17   1e43       1453       382      1060     329109
ECM 1,1, 500   3!3!5!5!**    360   17   1e43       1464       423      1173     299508
ECM 1,1,1000   3!3!5!5!**    360   17   1e43       1464       483      1341     262069

Ну, ниже 100 уже не пойду. Надо не только в 8-й, но ещё и в 9-й фильтрации попробовать заменить и посмотреть. Затем всё равно надо будет возвращаться к более длинным цепочкам.

[wrest]

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

Так что в этом я пока правильно сделал, что не послушался wresta.

В чём в этом?

[Yadryara]

wrest, сейчас пока по памяти, если надо цитату поищу. Помнится, вы говорили, что если я взял параметры (cha,1,1,1000) для my_ecm(cha,rounds,seed,b1), то это слишком маленькая настройка. А сейчас я взял даже не 1000, а ещё в 10 раз меньше, то есть 100 и это самый лучший результат по скорости. Кстати, схожу всё-таки ниже 100, интересно сколько решений потеряется. Пока что жалкий 1%.

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

Вообще выбор B1 - довольно мутное дело.

А вот и нет. Сейчас как раз видна ясная закономерность. Надо просто не торопиться и, чтобы не запутаться, зафиксировать параметры и менять пока только один. Менять и смотреть, смотреть и менять...

wrest, ещё помнится, вы спрашивали какого чуда я жду. Да вроде никакого не жду. Просто надеялся, что сложная рабочая программа не оптимальна и её можно и нужно ускорить. Что, собственно, шаг за шагом и делается.

И я не обо всех ускорениях сообщаю. Есть ускорения по мелочи, есть из-за исправления ошибок.

[wrest]

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

А сейчас я взял даже не 1000, а ещё в 10 раз меньше, то есть 100 и это самый лучший результат по скорости.

Это для маленьких чисел, чем меньше делитель тем меньше нужно B1.
Я вам писал так:

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

Брать надо не так :)
Надо брать возрастающие B1, из этой последовательности:
[500,520,560,620,700,800,900,1000,1150,1300,1450,1600,1800,2000,2200,2450,2700,2950,3250,3600,4000,4400,4850,5300,5800,6400]
Если мало, могу добавить. И делать по 1..3 заходам (rounds). Так мне думается будет оптимальнее.
Для тех 270 которые вы уже вычеркнули как ненужные, я бы начинал с B1=800.

И это было в контексте факторизации "270 чисел".
Для справки, вот вам две таблицы из исходного кода pari/gp

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

static const ulong TB1[] = {
  142,172,208,252,305,370,450,545,661,801,972,1180,1430,
  1735,2100,2550,3090,3745,4540,5505,6675,8090,9810,11900,
  14420,17490,21200,25700,31160,37780UL,45810UL,55550UL,67350UL,
  81660UL,99010UL,120050UL,145550UL,176475UL,213970UL,259430UL,
  314550UL,381380UL,462415UL,560660UL,679780UL,824220UL,999340UL,
  1211670UL,1469110UL,1781250UL,2159700UL,2618600UL,3175000UL,
  3849600UL,4667500UL,5659200UL,6861600UL,8319500UL,10087100UL,
  12230300UL,14828900UL,17979600UL,21799700UL,26431500UL,
  32047300UL,38856400UL, /* 110 times that still fits into 32bits */
#ifdef LONG_IS_64BIT
  47112200UL,57122100UL,69258800UL,83974200UL,101816200UL,
  123449000UL,149678200UL,181480300UL,220039400UL,266791100UL,
  323476100UL,392204900UL,475536500UL,576573500UL,699077800UL,
  847610500UL,1027701900UL,1246057200UL,1510806400UL,1831806700UL,
  2221009800UL,2692906700UL,3265067200UL,3958794400UL,4799917500UL
#endif
};
static const ulong TB1_for_stage[] = {
 /* Start below the optimal B1 for finding factors which would just have been
  * missed by pollardbrent(), and escalate, changing curves to give good
  * coverage of the small factor ranges. Entries grow faster than what would
  * be optimal but a table instead of a 2D array keeps the code simple */
  500,520,560,620,700,800,900,1000,1150,1300,1450,1600,1800,2000,
  2200,2450,2700,2950,3250,3600,4000,4400,4850,5300,5800,6400,
  7100,7850,8700,9600,10600,11700,12900,14200,15700,17300,
  19000,21000,23200,25500,28000,31000,34500UL,38500UL,43000UL,
  48000UL,53800UL,60400UL,67750UL,76000UL,85300UL,95700UL,
  107400UL,120500UL,135400UL,152000UL,170800UL,191800UL,215400UL,
  241800UL,271400UL,304500UL,341500UL,383100UL,429700UL,481900UL,
  540400UL,606000UL,679500UL,761800UL,854100UL,957500UL,1073500UL
};

Первая, TB1, используется для "обычного" ECM. Вторая, TB1_for_stage используется для "предварительного" ECM, а там он запускается если не справился Поллард-Брент. Это возрастающий ряд, и в коде определяется с какого B1 начать. Но в коде pari/gp B1 определяется не по величине ожидаемого делителя, а по величине факторизуемого числа.

Если вы заменяете Полларда (в версии авторства Квена) на ECM, то надо тестировать, конечно, какие пары rounds и B1 подойдут лучше всего. Этотбудет зависеть и от условий: если вы постепенно повышаете B1, то начинать с небольших. Если запускаете ECM только один раз, то B1 брать |несколько больше, чтобы захватить и множители подбольше.

[Yadryara]

Спасибо. Ваши идеи работают. Никакого чуда, просто кайф Пока получается, что фильтровать надо не сильнее, а слабее — больше цепочек проходят через все фильтрации кроме последней.

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

Если запускаете ECM только один раз,

Вот этого не понял. Что значит один раз??

[Dmitriy40]

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

Вот этого не понял. Что значит один раз??

rounds=1 в параметрах ECM.
На мой взгляд лучше чуть увеличить rounds (с уменьшением B1 для сохранения времени работы если надо) - в алгоритме ECM есть момент когда кривая не даёт решений из-за неудачного выбора (то ли самой кривой, то ли начальной точки, то ли seed, не понял), потому думается запускать проверку только по одной кривой не самый лучший вариант.

[Yadryara]

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

потому думается запускать проверку только по одной кривой не самый лучший вариант.

Ну да, разумеется, это тоже будет тестироваться. Я уже раньше писал что мне помогло увеличение 2-го параметра (rounds) c уменьшением 4-го (B1). Сейчас, когда поймаю минимум, пока сделаю чтобы B1 стоял на месте, а rounds буду менять. Ну и так далее, не вникая особо в суть, опытным путём попытаюсь нащупать тенденции чтобы в будущем их экстраполировать.

Ну вот, в принципе оптимум по B1 я уже вроде поймал:

6-поточный счёт, серия 1-0-6-0.

Фактор          Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
изация          простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут

Pol 1, 30000   3!3!5!5!**    360   17   1e43       1464       522      1449     242526

ECM 1,1,  10   3!3!5!5!**    360   17   1e43       1464       514      1427     246157
ECM 1,1,  20   3!3!5!5!**    360   17   1e43       1464       454      1259     279047
ECM 1,1,  30   3!3!5!5!**    360   17   1e43       1464       448      1243     282706
ECM 1,1,  40   3!3!5!5!**    360   17   1e43       1464       445      1235     284575
ECM 1,1,  60   3!3!5!5!**    360   17   1e43       1464       431      1196     293719
ECM 1,1,  70   3!3!5!5!**    360   17   1e43       1476       382      1058     334704
ECM 1,1,  80   3!3!5!5!**    360   17   1e43       1464       370      1027     342079
ECM 1,1,  90   3!3!5!5!**    360   17   1e43       1464       380      1054     333213
ECM 1,1, 100   3!3!5!5!**    360   17   1e43       1449       376      1043     333359
ECM 1,1, 200   3!3!5!5!**    360   17   1e43       1453       382      1060     329109
ECM 1,1, 500   3!3!5!5!**    360   17   1e43       1464       423      1173     299508
ECM 1,1,1000   3!3!5!5!**    360   17   1e43       1464       483      1341     262069

Где-то в районе 80-ти, а точнее знать и не надо. На то, что в районах 70 и 100 гуляет количество найденных цепочек, пока не обращаю внимания, хотя при подсчёте скорости это учитывается автоматом.

[wrest]

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

Вот этого не понял. Что значит один раз??

Вместо того чтобы один раз запустить ECM на 10 попыток с конкретным с B1, например rounds=10, B1=150 Можно 10 раз запустить ECM с rounds=1 и возрастающим B1. Встроенная факторизация в pari/gp примерно так и делает. Вот коротенький цчасток кода у меня

  for(ecm_i=ecm_start,ecm_finish,
    nfac=my_ecm(vquot[num_i],ecm_rounds,random(100),TB1[ecm_i]);
    if(nfac!=[],print1(num_i," ecm found factor with ",TB1[ecm_i]," ",nfac));
    if(nfac!=[],
      if(ispseudoprime(nfac),
        vtau[num_i]*=2;
        vquot[num_i]\=nfac;
        if(ispseudoprime(vquot[num_i]),
          vquot[num_i]=1;
          vtau[num_i]*=2;
          print(" .. finished");
          next(2)
          ,
          print();
          );
        ,
        print("for",num_i," number: ",vquot[num_i]," ECM returned composite factor ",nfac);return();
        );
    );
  );

Там B1 перебираются по таблице в некоторых пределах.

[Yadryara]

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

Можно 10 раз запустить ECM с rounds=1 и возрастающим B1.

Имеете в виду что если my_ecm вернёт 0, то нужно будет увеличить b1 и вызвать my_ecm ещё раз?

Кстати, похоже, что и здесь надо брать rounds = 1. Это стало понятно уже по rounds=2. Для очистки совести проверил и rounds=3.

6-поточный счёт, серия 1-0-6-0.

Фактор          Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
изация          простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут

Pol 1, 30000   3!3!5!5!**    360   17   1e43       1464       522      1449     242526

ECM 1,1,  80   3!3!5!5!**    360   17   1e43       1464       370      1027     342079

ECM 2,1,  60   3!3!5!5!**    360   17   1e43       1467       430      1193     295143
ECM 2,1,  70   3!3!5!5!**    360   17   1e43       1464       391      1084     324171
ECM 2,1,  80   3!3!5!5!**    360   17   1e43       1464       400      1108     317007

ECM 3,1,  60   3!3!5!5!**    360   17   1e43       1457       453      1257     278244
ECM 3,1,  70   3!3!5!5!**    360   17   1e43       1452       404      1122     310647
ECM 3,1,  80   3!3!5!5!**    360   17   1e43       1474       403      1118     316498

[Dmitriy40]

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

Вместо того чтобы один раз запустить ECM на 10 попцток с конкретным с B1, например rounds=10, B1=150 Можно 10 раз запустить ECM с rounds=1 и возрастающим B1.

А мне кажется это совсем не эквивалентно.
И какой вариант лучше - ещё вопрос. По идее кажется второй, но надо бы поточнее проверить. И второй можно и ещё улучшить запуская каждый раз с разными seed.

И даже с одинаковым B1 эти запуски не эквивалентны:

? for(i=1,100, print1(isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,8,1,40))>0))
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
time = 14,071 ms.
? for(i=1,100, print1(isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,7,1,40))>0))
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
time = 13,088 ms.
? for(i=1,100, print1(isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,1,40))>0))
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
time = 1,873 ms.
? for(i=1,100, print1(isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,7,1,63))>0))
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
time = 18,814 ms.
? for(i=1,100, print1(isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,7,1,64))>0))
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
time = 1,998 ms.
? for(i=1,100, print1(isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,1,64))>0))
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
time = 1,998 ms.

Видите, даже 100 повторений с меньшим rounds не даёт эффекта от большего rounds (делитель не находится).
А B1 пришлось увеличить в полтора раза чтобы компенсировать снижение rounds, хотя при таком B1 работает даже rounds=1. Т.е. изменения rounds и B1 очень плохо/нетривиально компенсируют друг друга.


Yadryara
А Вы уверены что при таких малых B1 у Вас ECM вообще находит делители?
И я не понимаю почему у Вас опять флуктуации количества цепочек (найденных ECM делителей) при изменении B1, у меня их нет как выше видно, т.е. Вы измеряете что-то малопонятное, а не скорость ECM.

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

Ещё инфа по скорости ECM, без нахождения делителя и с нахождением (время справа и внизу в мс, слева rounds):

? b1=[10,20,30,50,70,100,200,300,500,700,1000]; t=vector(1000); print1("B1:"); foreach(b1,b, print1("\t",b)); print; foreach([1,2,3,5,7,10],r, t0=getwalltime(); print1(r,":"); foreach(b1,b, t1=getwalltime(); print1("\t", isnull(Z_ECM(2247114998159571900659091456691540232212547327598270688266289093,r,1,b))>0); t[b]+=getwalltime()-t1); print("\t",getwalltime()-t0)); foreach(b1,b, print1("\t",t[b]))
B1:     10      20      30      50      70      100     200     300     500     700     1000
1:      0       0       0       0       0       0       0       0       0       0       0       610
2:      0       0       0       0       0       0       0       0       0       0       0       1218
3:      0       0       0       0       0       0       0       0       0       0       0       1837
5:      0       0       0       0       0       0       0       0       0       0       0       3051
7:      0       0       0       0       0       0       0       0       0       0       0       4266
10:     0       0       0       0       0       0       0       0       0       0       0       6098
        169     255     328     461     625     803     1349    1822    2750    3620    4897
time = 17,035 ms.
? b1=[10,20,30,50,70,100,200,300,500,700,1000]; t=vector(1000); print1("B1:"); foreach(b1,b, print1("\t",b)); print; foreach([1,2,3,5,7,10,15,20],r, t0=getwalltime(); print1(r,":"); foreach(b1,b, t1=getwalltime(); print1("\t", isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,r,1,b))>0); t[b]+=getwalltime()-t1); print("\t",getwalltime()-t0)); foreach(b1,b, print1("\t",t[b]))
B1:     10      20      30      50      70      100     200     300     500     700     1000
1:      0       0       0       0       1       1       1       1       1       1       1       290
2:      0       0       0       0       1       1       1       1       1       1       1       346
3:      0       0       0       0       1       1       1       1       1       1       1       406
5:      0       0       0       0       1       1       1       1       1       1       1       526
7:      0       0       0       0       1       1       1       1       1       1       1       645
10:     0       0       0       1       1       1       1       1       1       1       1       768
15:     0       0       1       1       1       1       1       1       1       1       1       933
20:     0       0       1       1       1       1       1       1       1       1       1       1042
        546     812     881     905     167     211     351     263     266     271     280
time = 4,962 ms.

[wrest]

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

Имеете в виду что если my_ecm вернёт 0, то нужно будет увеличить b1 и вызвать my_ecm ещё раз?

Да.

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

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

А мне кажется это совсем не эквивалентно.
И какой вариант лучше - ещё вопрос. По идее кажется второй, но надо бы поточнее проверить.

Оно неэквивалентно потому что B1 растут, а с ними и время на одну итерацию. Но вероятность растёт видимо быстрее, иначе в pari/gp бы так не делали.

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

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

Ещё инфа по скорости ECM, без нахождения делителя и с нахождением

Ессно, если вы задали rounds=10 и ECM нашла делитель на 2-м заходе, то ECM не делает оставшиеся 8 циклов.
Ну то есть грубо говоря, вызов

nfac=my_ecm(n,rounds,seed, B1)

это то почти то же, что и

for(i=1,rounds,
  nfac=my_ecm(n,1,seed,B1);
  if(nfac,break);
);

С точнгстью до нюансов по seed.

[Dmitriy40]

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

Ессно, если вы задали rounds=10 и ECM нашла делитель на 2-м заходе, то ECM не делает оставшиеся 8 циклов.

Это понятно, там интереснее точки перелома, сколько rounds нужно для указанных B1 и наоборот.
И что увеличение B1 не ухудшает результат (делитель всё равно находится, правда разумеется медленнее). У Yadryara вон беда с этим, увеличение B1 не приводит к стабильному увеличению количества цепочек.

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

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

Ну то есть грубо говоря, вызов

nfac=my_ecm(n,rounds,seed, B1)

это то почти то же, что и

for(i=1,rounds,
  nfac=my_ecm(n,1,seed,B1);
  if(nfac,break);
);

С точнгстью до нюансов по seed.

А вот это как раз и нет! Я же именно это и проверил 100-кратным запуском одинакового варианта - и нет, либо находит все 100 раз, либо все 100 раз не находит делителя, так что нет, rounds и повторные вызовы Z_ECM - это очень разные вещи.

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

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

это то почти то же, что и

Тогда бы в строке из 100 цифр при rounds=1 единицы начинались бы с 8-й позиции, чего не наблюдается. Так что нет, не тоже самое.