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

[wrest]

Yadryara
То, что можно посчитать какие числа в нашем массиве скажем в миллион строк (цепочек) и 20 столбцов (чисел в строке-цепочке), делятся на табличное простое, это понятно.
Вопрос тут -- как вести учёт.
В случае прохода по строкам (цепочкам) мы просто переходим к следующей строке (цепочке) и про предыдущую полностью забываем.
А в случае прохода по столбцам, нам надо вести учёт отбросили ли мы уже ту строку (цепочку), в которой нашлось кратное очередному табличному простому число. По мере продвижения по таблице простых, мы в основном будем натыкаться на уже отброшенные строки (цепочки).

[Yadryara]

wrest, пока об этом не думал. Мне пришла в голову идея ускорения. Её и отрабатываю.

Ведь для каждой строки, для каждого нового i, мы вычисляем остаток по модулю предпростого. А нафига делать это миллион раз???

Для предпростого 79 можно и так по формуле найти все места для лишь 79 строк, а затем строки, содержащие последовательность мест будут повторяться.

Вот, смотрите на первые два столбца:

PredPrime    79, 83,  89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151
i
0.          -25 -10  -59 -14    1  -25  -31  -25  -38   -3  -48  -33  -84  -54    0
1.            5   6   16   8  -14    7  -86   12  -28  -92  -62   11  -93  -41   -1
2.          -44 -61    2 -67  -29  -64  -34  -60  -18  -54  -76  -82 -102  -28   -2
3.          -14 -45  -12 -45  -44  -32   18  -23   -8  -16  -90  -38 -111  -15   -3
4.           16 -29  -26 -23  -59    0  -37   14    2 -105 -104    6   19   -2   -4
5.          -33 -13  -40  -1  -74  -71   15  -58   12  -67   13  -87   10   11   -5
...
77.          -6 -23   20  -66  -43  -33  14  -10  -59  2  -78  -70  -82  -96  -77
78.         -55  -7    6  -44  -58  -1  -41  -82  -49  -87  -92  -26  -91  -83  -78
79.         -25   9   -8  -22  -73  -72  11  -45  -39  -49  -106  18  -100  -70  -79
80.           5 -58  -22   0  13  -40  -44  -8  -29  -11  11  -75  -109  -57  -80
81.         -44 -42  -36  -75  -2  -8  8  -80  -19  -100  -3  -31  -118  -44  -81
82.         -14 -26  -50  -53  -17  -79  -47  -43  -9  -62  -17  13  12  -31  -82
83.          16 -10  -64  -31  -32  -47  5  -6  1  -24  -31  -80  3  -18  -83
84.         -33   6   11  -9  -47  -15  -50  -78  11  14  -45  -36  -6  -5  -84
85.          -3 -61   -3  13  -62  17  2  -41  -92  -75  -59  8  -15  8  -85

Они начинают повторяться с i=79 и i=83 соответственно. То есть период равен самому предпростому.

Ну и первый столбец я уже вычислил, аналогично можно вычислить и остальные.

Здесь первый столбец показан в строку:

[-25, 5, -44, -14, 16, -33, -3, -52, -22, 8, -41, -11, 19, -30, 0, -49, -19, 11, -38, -8, -57, -27, 3, -46, -16, 14, -35, -5, -54, -24, 6, -43, -13, 17, -32, -2, -51, -21, 9, -40, -10, 20, -29, 1, -48, -18, 12, -37, -7, -56, -26, 4, -45, -15, 15, -34, -4, -53, -23, 7, -42, -12, 18, -31, -1, -50, -20, 10, -39, -9, -58, -28, 2, -47, -17, 13, -36, -6, -55, -25, 5, -44, -14, 16]~

[wrest]

В общем, на пока что очередная версия закончена.
Публикую текст функции em4()
Поскольку паттернов мне не дали (кроме тех что Антон дал в личку, но их я не пробовал по этическим причинам), то проверялось на паттерне с 24 страницы, котором находится $D(48,21)$ в первом миллионе.
В этой версии em(4) довольно большие изменения по сравнению с em3() с 29 страницы.
1. Добавлена "терапевтика". Сомнительно что тут правильный выбор точность против скорости, но пусть будет.
2. В ходе проверки по таблице простых чисел, проверяются и делимость на их высшие степени.
3. Честно считается $\sigma _0 (n_d)$ где $n_d$ текущее число в цепочке. Если $\sigma _0 (n_d)$ не кратна нужному количеству делителей, цепочка отбрасывается.
4. Накапливается факторизованная часть по каждому числу цепочки.
5. После проверки по таблице простых, вычисляется нефакторизованный остаток (частное).
6. Добавлена проверка на "недобор": если остаток (частное) простое число, то факторизация закончена и если делителей меньше, цепочка отбрасывается.
7. Добавлена дофакторизация алгоритмом Полларда-Брента ро, с количеством итераций как во встроенной факторизации, одна попытка.
8. Добавлена дофакторизация методом mpqs (встроенным) если поллардом не получилось.
9. Добавлены разные счётчики, значение которых печатается в конце.

Текст готов к трансляции-компиляции в gp2c - произведена типизация всех коротких переменных.

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

/*
GP;default(threadsize,32M);
GP;default(debugmem,0);
GP;default(factor_add_primes,1);
*/
install(Z_pollardbrent,GLL);
install(Z_ECM,GLLU);
isnull(x:vec=[])=x; \\ функция нужна для корректной обработки NULL
                    \\ который может вернуть Z_pollardbrent
my_pollard(n:int)={
my(
v:vec,
size:small=logint(n,2)+1,
tune:small=14,
\\ количество итераций вычисляется так же, как в исходном коде pari/gp
c0:small = if(size>301,
                       49152
                      ,
                       tune + size-60 + ((size-73)>>1)*((size-70)>>3)*((size-56)>>4)
              )
  );
v=(isnull(Z_pollardbrent(n,c0,0)));
if(v!=[],return(v));
\\ Если хочется чтобы поллард пытался/не пытался зайти несколько раз, 
\\ надо раскомментировать/закомментировать следующий for
/*
for(i:small=1,4,
    v=isnull(Z_pollardbrent(n,c0,i));
    if(v!=[],return(v));
 );
*/
return([]);
}
install(mpqs,G);
\\ mpqs возвращает вектор с какой-то дичью
\\ но первый компонент это один из найденных множителей
\\ второй компонент это вероятно степень (например квадрат)
\\ но это не проверяется тут в надежде что возвращается
\\ всегда первая степень
my_mpqs(n:int)=my(divisor=component(mpqs(n),1));return([divisor,n/divisor]);

\\ заготтвка на будущее, если разобраться какие
\\ параметры rounds и b1 оптимальны
my_ecm(n,rounds,seed,b1)=isnull(Z_ECM(n,rounds,seed,b1));

/* Основная функция */
em4(myname,k_start:small,k_len:small,lim:small)={
/* myname - будет печататься в отчёте
* k_start - начало диапазона
* k_len - количество цепочек для просчёта
* lim - порог для пробных простых, оптимальный будет 2^20
*
*/
my(t0=getwalltime());\\Замер времени подготовки

\\ переменные специфичные для паттерна
my(v=[63, 3610, 3179, 12, 17797, 3362, 75, 392, 841, 18, 2209, 20, 1587, 242, 6727, 96, 14045, 338, 243, 68, 35131]);
my(n0=283938699868309713921641266159023371777169):int; \\ база
my(m=229403502054304075118105309394590566946400*2):int; \\ шаг
my(len=21):small; \\ длина цепочки
my(DN=48):small; \\ нужное количество делителей N в D(N,l)
my(pat_prime_lim:small=nextprime(vecmax(factor(vecprod(v))[,1])+1)); \\ следующее простое за максимальным в паттерне

\\ вычисляем остатки по всем малым простым диапазона
my(pr:vecsmall=Vecsmall(primes([pat_prime_lim,lim]))); \\ вектор с простыми
my(pr_q=#pr):small; \\ и сколько их там оказалось
my(pmods_n0:vecsmall=vectorsmall(pr_q,i,n0%pr[i])); \\вектор с остатками по простым по n0
my(pmods_m:vecsmall=vectorsmall(pr_q,i,m%pr[i])); \\ вектор с остатками по простым по m

\\ вспомогательные переменные
my(q=0,q1=0,q2=0,q3=0, q4=0, q5=0, q6=0, q7=0, q8=0):small;\\Разные счетчики
my(qp=0, qp1=0, qp2=0, qp3=0, c=0):small; \\Разные счётчики
my(ai=0):small; \\ степень с которой i-е простое входит в разложение на множители
my(d):small; \\ индекс числа от начала цепочки
my(nsigma:vecsmall=vectorsmall(len,d,numdiv(v[d]))); \\ Стартовый вектор количества делителей (сигма-ноль)
my(ns:vecsmall=vectorsmall(len,d,numdiv(v[d]))); \\ Вектор накопления количества делителей (сигма-ноль)
my(need_f:vecsmall=vectorsmall(len,d,1)); \\ вектор с флагом необходимости дофакторизации
my(nf=need_f); \\ Вектор накопления флагов дофакторизации
my(nv=v); \\ Вектор накопления факторизованной части
my(nr=vector(len,d,1)); \\ Вектор накопления остаток-частное
my(n):int; \\ Проверяемое число
my(pv:vec); \\ вектор, который вернёт поллард

\\ TODO: представим паттерн для красивой печати

\\ Печать стартового сообщения
print("Воркер ",myname, ": ++++++ Начинаю подготовку ++++++");
print("Воркер ",myname, ": Поиск D(",DN,",",len,")");
print("Воркер ",myname, ": База n0=",n0," бит:",logint(n0,2)+1);
print("Воркер ",myname, ":   шаг m=",m, " бит:",logint(m,2)+1);
\\ TODO: придумать как красиво/полезно печатать паттерн
print("Воркер ",myname, ": Паттерн: секретный");
print("Воркер ",myname, ": Задание: Старт: ",k_start," шагов:",k_len," Таблица простых до:", lim);
print("Воркер ",myname, ": Подготовился за:",strtime(getwalltime()-t0));
print("Воркер ",myname, ": ++++++ Приступил к работе ++++++ ");


\\ +++++++++++++++++++ основной цикл
t0=getwalltime();\\Замер времени отсеивания
for(k:small=k_start,k_start+k_len-1, \\ идём по цепочкам
\\Здесь начинается проверка конкретной цепочки
\\ начинающейся с числа n0+k*m

\\ Фильтр "терапевтика" отбрасывает цепочки
\\ в которые попали множители 3^6 или кубы любых
\\ простых чисел от 5 до pat_prime_lim
n=n0+k*m+len-1; 
if(n%3^6<len, q++;next); 
forprime(p=5,pat_prime_lim-1, if(n%p^3<len, q++; next(2)));
   \\ здесь цикл идёт по табличным простым числам
   \\ инициализируем аккумуляторы для цепочки
   \\ nv - вектор, накопленная часть факторизации, произведение всех известных
   \\ на текущий момент простых множителей с учётом их степеней
   \\ ns - вектор, количество делителей (сигма-ноль, numdiv) числа в цепочке
   nv=v; ns=nsigma; 
   for(i=1,pr_q,\\ идём по простым для каждой цепочки
      \\ вычисляем положение числа которое делится на это простое относительно начала цепочки
      d=len-(pmods_n0[i]+k*pmods_m[i]+len-1)%pr[i];
      \\ если на i-е простое ни одно число цепочки не разделилось, выходим на проверку следующего
      if(d<1, next());
      \\ на i-е простое разделилось d-е число цепочки 
      \\ выясняем не входит ли i-е простое в более высокой степени чем 1
      ai=valuation(n0+k*m+d-1,pr[i]);
      \\ теперь ai равно степени в которой i-е простое вошло в разложение
      ns[d]*=ai+1; \\ накопили сигма-ноль
      \\ проверим является ли сигма-ноль делителем DN
      \\ если не является, отбрасываем всю цепочку
      if(DN%ns[d]>0,q1++;next(2));
      \\ проверим нет ли перебора делителей
      if(ns[d]>DN/2, q1++;next(2)); \\ явный перебор делителей - отбрасываем всю цепочку
      nv[d]*=(pr[i]^ai); \\ накопим по текущему числу в цепочке факторизованную часть
      \\ перебора делителей пока нет
      \\Если делителей уже набралась больше четверти 
      if(ns[d]>DN/4,
      \\ то проверим композитный ли остаток-частное
      \\ и если композитный, то будет перебор делителей
      \\ и тогда отбрасываем цепочку
        qp++;qp2++;
        if(!ispseudoprime((n0+k*m+d-1)/(nv[d]),1), q1++;next(2)));

   );
   \\Проверка на переполнение по таблице простых закончена.
   \\ next(); 
   
   \\ Теперь числа в цепочке точно не содержат простых множителей, больших чем lim
   n=n0+k*m; \\ начальное число цепочки
  
  \\ Посчитаем остаток-частное для каждого числа из цепочки
  for(d=1,len,nr[d]=(n+d-1)/(nv[d]));

   \\ Проверим нет ли в цепочке чисел, у которых делителей явно меньше чем DN
   for(d=1,len,
    \\ Берём такие числа, у которых делителей меньше половины DN
      if(ns[d]<(DN/2), 
      \\ накапливаем счетчик проверок на простоту
      \\ если остаток-частное простой, то делителей будет недостаточно
      \\ тогда отбрасываем эту и переходим к следующей цепочке
      qp++; qp1++;
      if(ispseudoprime(nr[d]),q2++;next(2));
      );
   );
   \\ Теперь проверяем переполнение множителями
   \\ большими чем lim и дофакторизованность
   \\ nf - вектор с флагами где необходима дофакторизация, 1 значит необходима
   \\ для начала, считаем что всем числам в цепочке необходима дофакторизация
   nf=need_f;
   for(d=1,len, 
        \\ если остаток-частное простой, то это число полностью дофакторизованно
        if(nr[d]>1,qp3++;
           if(ispseudoprime(nr[d]),
              nr[d]=1;ns[d]=ns[d]*2;nf[d]=0;next()
             );
          ); \\ его больше не трогаем
        \\ в q6 посчитаем сколько раз полларда вызвали
        q6++;
        pv=my_pollard(nr[d]);
        if(pv==[],pv=my_mpqs(nr[d])); \\ поллард не справился, ухнем mpqs-ом
        while(pv!=[],
         q7++; \\ сколько раз поллард/mpqs вернул непустой ответ
         \\ TODO: добавить проверку что поллард вернул простое число
         ns[d]*=(#pv-1)*2; \\ увеличиваем количество найденных делителей в 2 или 4 раза
         if(ns[d]>(DN/2), q3++; next(3)); \\ если переполнение делителями, отбрасываем цепочку 
         nr[d]=nr[d]/pv[1]; \\ найден один множитель, уменьшим на него остаток-частное
         if(#pv==3,nr[d]=nr[d]/pv[2]); \\ найден ещё один, уменьшим на него остаток-частное
         
         \\ поллард справился, но надо проверить составной ли остаток-частное
         qp++;qp3++;
         if(!ispseudoprime(nr[d]),
           if(ns[d]>(DN/4),q3++; next(3)) \\ остаток-частное составной - переполнение, 
                                          \\ отбрасываем всю цепочку
           ,
           nf[d]=0;nr[d]=1;ns[d]=ns[d]*2;next(2); \\ остаток-частное простой 
                                                  \\ помечаем что факторизация закончена
                                                  \\ и переходим к следующему d в цепочке
           );
          \\ TODO проверить а точно ли нужна ли дофакторизация
         \\ нужна дофакторизация, опять пробуем полларда
         pv=my_pollard(nr[d]);
         if(pv==[],pv=my_mpqs(nr[d])); \\ поллард не справился, ухнем mpqs-ом
         \\ если mpqs не справится, то будет прерывание всей программы с ошибкой
         \\ поскольку mpqs вернёт в my_mpqs NULL а мы там ожидаем вектор
         \\ TODO попробовать научиться обрабатывать любой выхлоп my_mpqs
         \\ как дикий вектор так и NULL
         );
       );

  \\ Включаем "тяжелую артиллерию"

  \\ прошедшие полностью факторизуем, не будем откладывать.
  \\ TODO: часть у нас уже полностью факторизована, учесть это
  \\ пока оставлена полная проверка на случай ошибок в программе
  q8++; \\ посчитаем сколько дошло до numdiv
  \\ print("Дошло до numdiv: ", n);
  c=0; for(i=1,len,if(numdiv(n+i-1)==DN,c++));if(c==len,q4++;print("Воркер ", myname,": Найдено D(",DN,",",len,"):",n),q5++,next());
);

\\ отчитаемся о работе
print("Воркер ", myname,": ++++++ Счёт закончен, доклад ниже ++++++"); 
print("Воркер ", myname,": Дошло до | numdiv: ",q8," | Найдено:",q4," | Отброшено:",q+q1+q2+q3+q5);
print("Воркер ", myname,": Отброшено по | терапевтика:",q," | таблица:",q1," | недобор:",q2," | Поллард/mpqs:",q3," | numdiv:",q5);
print("Воркер ", myname,": Проверок псевдопростых | всего:",qp," | из них в таблице:", qp2," | в недоборах:",qp1," | в полларде:",qp3);
print("Воркер ", myname,": Проверок поллардом/mpqs начато:", q6," Поллард/mpqs нашёл множитель:", q7);
print("Воркер ", myname,": Cкорость счета: ", 1000*k_len\(getwalltime()-t0)," цеп/сек. Время счёта:",strtime(getwalltime()-t0));
print("Воркер ", myname,": ++++++ Работа закончена ++++++");
return(q4);
}

-- 22.03.2026, 16:18 --

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

Ведь для каждой строки, для каждого нового i, мы вычисляем остаток по модулю предпростого. А нафига делать это миллион раз???

Странный вопрос. У меня это не делается миллион раз ещё в em3() на 29 сранице.
В em4() выше, остатки вычисляются (там длинные операции) на 67 и 68 строках один раз на каждое простое в таблице:

my(pmods_n0:vecsmall=vectorsmall(pr_q,i,n0%pr[i])); \\вектор с остатками по простым по n0
my(pmods_m:vecsmall=vectorsmall(pr_q,i,m%pr[i])); \\ вектор с остатками по простым по m

А затем, используются только короткие вычисления (миллион раз), строка 118:

      d=len-(pmods_n0[i]+k*pmods_m[i]+len-1)%pr[i];

Эта строчка транслируется в Си так:

          d = len - smodss(((pmods_n0[i] + (k*pmods_m[i])) + len) - 1, pr[i]);

Тут smodss() это функция которая вычисляет положительный остаток от деления двух коротких (<64 бит на 64-битных системах) чисел.
Текст smodss на Си.

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

smodss(long x, long y)
{
  long r = x%y;
  return (r >= 0)? r: labs(y) + r;
}

[Dmitriy40]

Разумеется все остатки (n0+m*i)%p будут повторяться каждые p раз (при взаимной простоте m и p), ровно в том же порядке и начиная с n0%p (если i начинается с 0).
И да, из всех p штук i начиная с любого на p будет делиться лишь 1 число, а остатков меньше 20 будет ровно 20.
Вот только и на p и на q будут делиться уже числа с периодом pq (при взаимной простоте p и q), это и есть КТО.
Вопрос лишь как перебирать только нужные цепочки.
Если "вычёркивать" из списка ненужные, то придём фактически к решету Эратосфена.
Если хранить остатки по каждому p и пересчитывать их для каждой цепочки, то придём к сложению по модулю и хранению вектора остатков, который придётся обновлять для каждой цепочки (что уже было сделано выше и у меня работает быстрее других вариантов).
Если пытаться выявить общую часть пар или троек множеств делимости на каждое простое, то упрёмся в перебор всех возможных комбинаций, что на порядки хуже длинных делений.

[wrest]

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

Если "вычёркивать" из списка ненужные, то придём фактически к решету Эратосфена.

Ну да, но это же как раз выглядит как обмен сложности на память, не?
Т.е. понижаем сложность за счёт увеличения памяти.
Таблицу первых простых, например, кроме как Эратосфеном и не сделаешь.
Ну у нас будет в памяти массив коротких чисел размером 20х1 000 000 и это не выглядит как уж очень много памяти. Что-то около 0,16ГБайт плюс по 8 МБайт на каждый флаг типа "вычеркнуто" или какие мы придумаем. В собственно массиве хранить например сигму-ноль (numdiv).
Останавливаемся или когда все строки-цепочки вычеркнуты или закончились простые в таблице.
По прошедшим (невычеркнутым), будем на следующую стадию иметь сигмы-ноль по всем числам прошедших цепочек.
Мне то кажется что тут не просматривается ускорения, ибо мы и когда идём по строкам-цепочкам а не по столбцам, делаем практически всё то же самое.

-- 22.03.2026, 17:04 --

Теперь буду сылаться на "функцию em4() c 63-й страницы"

[Dmitriy40]

Проблема в том что для вычёркивания из таблицы 20х1e6 всех простых до 2^18 надо 20 раз запустить проход по таблице для каждого простого до 2^18.
Ну или 1 раз, но вычёркивать не одно из p чисел, а 20 из p в некоем сложном порядке (который однозначно зависит от n0 и m и p).
Под вычёркиванием надо понимать накопление количества делителей и проверку (после вычёркивания всех) что не получилось перебора и недобора.
Фактически это замена выражения d = len - smodss(((pmods_n0[i] + (k*pmods_m[i])) + len) - 1, pr[i]) для каждого i на цикл по 20 элементам вектора xx[1..p][1..20] с индексами нужных цепочек среди всех 1e6/p индексов для каждого p. Да, это может быть быстрее короткого деления ...

[Yadryara]

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

остатки вычисляются (там длинные операции) на 67 и 68 строках один раз на каждое простое в таблице:
А затем, используются только короткие вычисления (миллион раз), строка 118:

      d=len-(pmods_n0[i]+k*pmods_m[i]+len-1)%pr[i];

Ну вот я про это и спрашиваю, зачем так много раз считать %pr[i], то есть остаток по предпростому?

Что делает эта строка? Она вычисляет номер места. Так? Зачем это делать каждый раз? После терапевтики от миллиона остаётся, грубо говоря 300 тысяч. То есть эта строчка обычно вычисляется по 300 тысяч раз для каждого из 84 тысяч предпростых?

[wrest]

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

То есть эта строчка обычно вычисляется по 300 тысяч раз для каждого из 84 тысяч предпростых?

Да. Но цепочки обычно выбывают задолго до того, как пройдут через все 84 тысячи.
Для таблицы до 2^20, в среднем вычисляется 85 раз на цепочку.

[Yadryara]

Ну вот, а я предлагаю пока вычислять места не сотни тысяч раз для каждого предпростого, а 79 раз для 79, 83 раза для 83 и так далее.

И да, нередко сильно дальше идти и не приходится. Я выше показал, что цепочки выбывают и на первых 15 предпростых.

[wrest]

Ну в общем у меня такая новость.
В связи с открывшимися обстоятельствами касательно mpqs(), описанных тут: post1720885.html#p1720885
я чёй-та неслабо так разочаровался, т.к. там дофига всего дописывать, повторяя фактически способ хранения частично факторизованных чисел как это уже сделано в libpari, лишние вызовы функций и т.п. и просто плюнул на это заменил блок с поллардом/mpqs на... numdiv. Но numdiv, конечно, только по уже известному остатку (частному), а не полному числу.
Одной вот такой строчкой:

     if(ns[d]*numdiv(nr[d])!=DN,q3++;next(2));next();

Там ns[d] это накопленный numdiv, a nr[d]-- нефакторизованный остаток (частное).
И теперь код в целом работает быстрее (по скорости цепочек/сек) на 10% примерно, чем мой код с поллардом/mpqs.

Ну я оставил и сквозную финальную проверку всей цепочки numdiv-ом тоже, и она теперь тоже работает мгновенно, т.к. всё что ей надо, уже сидит в addprimes()

Даже как-то неловко

Короче говоря, главный ускорительный продукт последних нескольких дней (помимо терапевтики но это не моё изобретерие), это проверка недобора.
Совершенно тривиальная.
Ну и ещё добавление честного счёта сигмы-ноль, накопления факторизованной части, и учёт высших степеней табличных простых. Но это скорее замедление, хотя эффект оценить трудно, ибо он слишком комплексный: в проверке недобора используется накопленная сигма, а если бы её не было, то это по сути факторизация заново. А в проверке перебора используется накопленная факторизованная часть, а без неё numdiv работал бы дольше.

[wrest]

Ранее в сериале:

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

В общем, результат теперь, после компиляции, в многопоточном режиме 230 тыс цепочек в секунду в сумме. 8 миллионов за 35 секунд.

Это было для em3() на ноутбуке.
Добрался я до ноутбука, для em4() с 63 страницы на ноутбуке результат в многопотоке (4 ядра 8 потоков) составил ~840 тыс/сек
Это 8 млн. цепочек за 9,528 с

А начиналось всё так:

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

Компиляция, 4 ядра/8 потоков ~95 тыс/сек

8,8 раз от начала работ по ускорению. Ну вот -- уже почти десятикратно.
Но всё за счёт "терапевтики", конечно.

В однопотоке даёт 307 тыс цепочек/сек, что примерно в 1,5 раза быстрее планшета.

Ну вот я хотел спросить. А какие сейчас скорости-то? Те что выше приведены, норм?

[Dmitriy40]

Т.е. 4 ядра и 8 потоков работают медленнее чем 3 ядра в однопоток (307*3=921>840) ...
Или в однопоточном режиме частоты сильно завышаются?

[wrest]

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

Или в однопоточном режиме частоты сильно завышаются?

Да, когда загружено одно ядро, частота держится в районе 4ГГц, когда все -- 2..2,2ГГц (смотрю в вендовый таск менеджер).
Я так думаю, это делается для соблюдения теплопакета (TDP) на процессор, и настольные компы не должны, по идее, быть подвержены таким флуктуациям, в связи с наличием питания из розетки и килограммовым кулером.
Ну троттлинг это реалии жизни, что ж поделать. И это в принципе правильно. Я не знаю как сейчас, но буквально несколько лет назад основная масса используемого софта была однопоточной, типа майкрософт ворда, аутлука и т.п. Браузеры кажется не так уж и давно научились отделять вкладки в потоки.
Мобильным девайсам важна пиковая производительность, а долговременная не очень нужна. Да и в принципе "персональным" девайсам долговременная не нужна. Это уже класс "рабочих станций" и далее -- стоечных серверов, с которыми рядом стоять невозможно из-за шума.

На батарейке однопоток даёт 75 тыс цепочек/сек. Против 307 если подключено внешнее питание

[Yadryara]

Пока до засекания новой скорости не дошёл, тестирую новые идеи.

Периодичность, разумеется, распространяется и на произведение предпростых. Это можно использовать.

Например, установлено для конкретного паттерна, что в цепочке под номером 199 число на 20-м месте делится и на 79 и на 83. Тогда можно делать шаги по $79\cdot83$ и проверять сразу 20-е место в цепочках под номерами $199 + 6557s$, где $s = 1, 2, 3, ...$

Перепроверил на всякий случай количество факторов и в других периодах:

i     mes kfa  nu   delta'                 79*83 
199    20   2   3        1        = 199  + 6557*0
1889    2   2   3        1        = 1889 + 6557*0
2242    6   2   3        1        = 2242 + 6557*0
2595   10   2   3        1
3301   18   2   3        1
3440    1   2   3        1
4499   13   2   3        1
5344    4   2   3        1
6050   12   2   3        1
6403   16   2   3        1

6756   20   2   3        1        = 199  + 6557*1
8446    2   2   3        1        = 1889 + 6557*1
8799    6   2   3        1        = 2242 + 6557*1
9152   10   2   3        1
9858   18   2   3        1
9997    1   2   3        1
11056  13   2   3        1
11901   4   2   3        1
12607  12   2   3        1
12960  16   2   3        1

13313  20   2   3        1        = 199  + 6557*2
15003   2   2   3        1        = 1889 + 6557*2
15356   6   2   3        1        = 2242 + 6557*2
15709  10   2   3        1

[Dmitriy40]

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

Например, установлено для конкретного паттерна, что в цепочке под номером 199 число на 20-м месте делится и на 79 и на 83. Тогда можно делать шаги по $79\cdot83$ и проверять сразу 20-е место в цепочках под номерами $199 + 6557s$, где $s = 1, 2, 3, ...$

Так они все по любому будут проверены с шагами 79 и 83, их же всё равно делать, так зачем ещё и общий шаг организовывать ...