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

[wrest]

В общем, проход по большой таблице, типа 21x10^5 себя не оправдывает.
Скорость прохода  включая создание таблицы, заполнение, и определение отбрасываемых цепочек, составила ~336 тыс/сек, что близко к интегральной скорости при последовательной проверке каждой цепочки (с терапевтикой, табличным отсевом и финальными numdiv-ами) . При этом отсев только 62% (т.е. в 38% переполнения не случилось - это при простых до 2^20) и дальше копать смысла нет. Главная проблема - векторы векторов и матрицы это длинные числа, их нельзя или я не понял как, объявить как small в gp2c.
Сам проход по ткблице при этом около ~1млн/сек, но её подготовка и главное последующий анализ, портят скорость. Я делал вычитание единицы для каждого простого на которое разделилось, из предзаполненного ожидаемого количества множителей, раньше называлось nu, например тут: post1711535.html#p1711535
nu=[3, 2, 3, 3, 3, 3, 3, 2, 4, 3, 4, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3];
\\Сколько разных простых делителей должно быть в каждой позиции
Так что после окончания прохода по таблице смотрел чтобы vecmin по цепочке был неотрицательный (такие фильтр прошли и надо крякать их ispseudoprime-ом и далее по списку).
Можно ещё заранее думать что если множителей набралось сколько надо, то ос этавшееся частное точно составное, но цепочка D(48,21) таких чисел, где частное простое, имеет более одного.

-- 30.03.2026, 21:05 --

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

Значит есть разница в типах между PARI/GP и gp2c и тогда говорите точнее про что имеете в виду.

Ну так мы ж тут на скорость пишем :)
Поэтому после proof of cocept, в итоге всё заканчивается трансляцией в gp2c
Жаль конечно что в pari/gp не завезли Сишные массивы двумерные.

[Yadryara]

Привет. А что без меня тут всё заглохло...

Я из обоймы вроде не выпал — много всего посчитал. Ну вот, например, такие скорости:

2^   Остаток   Старт      Комплектов       Счёт     Найдено      Время       Скорость
      по 729  полосы       посчитано        e25     D(96,6)     секунд    D(96,6)/час

13       243      11     3!*4!*1! 24      0 — 1         292         63          16686 
14       243      11     3!*4!*1! 24      0 — 1         292         58          18124 
15       243      11     3!*4!*1! 24      0 — 1         292         57          18442 best
16       243      11     3!*4!*1! 24      0 — 1         292         59          17817

Паттерн пока не привожу, сравнительный анализ по разным сериям паттернов попробую показать позже.

[wrest]

Yadryara
У меня проверяет 200 тыс цепочек в секунду на планшете, а у вас 16 тыс в час на компе?

-- 04.04.2026, 20:51 --

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

Привет. А что без меня тут всё заглохло...

Достигли максимальной скорости, нечего ускорять...

[Dmitriy40]

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

Достигли максимальной скорости, нечего ускорять...

Мне подкинуть другую задачку? Их есть у меня.
Правда я их почти все и сам уже решил, но вдруг можно и ещё быстрее ...
Например преобразование длинного числа (40+ цифр) в десятичный вид для вычисления суммы десятичных цифр числа (sumdigits в PARI). Сейчас у меня оно занимает порядка 120 тактов для чисел до 57 знаков, вот бы ускорить на порядок ... Я что уж только не придумывал, ничего не помогает. В PARI sumdigits работает за ~1800 тактов для тех же чисел.

[Yadryara]

wrest
Вот не знаю, как вы так ухитряетесь не понимать что я пишу.

Написано же: "Найдено D(96,6) 292".

То есть за 57 секунд найдены 292 цепочки. И это даёт среднюю скорость свыше 18 тысяч в час.

Надо ли все 292 приводить? Могу. Ну вот пока три из них:

7407058747876149529448475
7445314543171512778251675
7589229201663593571368475

[wrest]

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

Например преобразование длинного числа (40+ цифр) в десятичный вид для вычисления суммы десятичных цифр числа (sumdigits в PARI). Сейчас у меня оно занимает порядка 120 тактов для чисел до 57 знаков, вот бы ускорить на порядок ...

Не, я в такты не умею. У меня же в основном arm64 и изредка amd64 и я к ассемблеру не касаюсь вовсе, полагаясь на pari, которая полагается на libgmp

-- 04.04.2026, 23:55 --

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

То есть за 57 секунд найдены 292 цепочки. И это даёт среднюю скорость свыше 18 тысяч в час.

Ну окей, вы своих попугаях, я в своих. Обычная история. Мне "за 57 секунд найдены 292 цепочки" ни о чём, с точки зрения быстро это или нет, не говорит. Не ну позравляю канеш. 292! Круто наверное.

[Dmitriy40]

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

Не, я в такты не умею.

Для сравнения:

? for(n=10^14,10^14+10^6-1, sumdigits(n^4))
time = 594 ms.

При частоте 3.5ГГц получается 0.6/1e6*3.5e9=2100 тактов, из которых 1/8 занимает n^4:

? for(n=10^14,10^14+10^6-1, n^4)
time = 75 ms.

[wrest]

Dmitriy40
В исходниках там есть лукап-таблица по суммам цифр чисел от 0 до 999, а подсчёт ведется последовательным вычислением остатка по модулю 1000 и делением на 1000 пока число не закончится.

[Dmitriy40]

wrest
Это первая из 4 или 5 (смотря как считать) оптимизаций что я у себя применил ...

[Yadryara]

wrest
Тут вопрос в том, чьи попугаи лучше подходят для оценки эффективности решения исходной задачи.

Вот же был вопрос:

EUgeneUS в сообщении #1715588 писал(а):

Если мы говорим про эффективность использования ресурсов, то в знаменателе - затраты, собственно, потраченные ресурсы.
А в числителе что?

В знаменателе единицы времени, как это традиционно принято для скорости. Например, часы.

А в числителе, очевидно, количество найденных искомых цепочек.

А если ни одной не найдено? Тогда мат. ожидание количества искомых цепочек.

А как убедиться что это мат. ожидание посчитано правильно? Вопрос непростой и решать его надо не торопясь.

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

Вот этим я пока и занимался, спустился не только до D(96, 13), но и до D(96, 6). Вроде более короткие смотреть уже не надо. Затем предлагаю постепенно подниматься — считать D(96, 7), D(96, 8) и так далее, смотреть на различные параметры, коих набралось уже немало. Я далеко не все указал.

Вот здесь показано как ставятся подпорки, то бишь простые в первой степени:

0-0-2-1-3-2!    0-0-2-1-3-2!    0-0-2-1-3-2!    0-0-2-1-3-2!    0-0-2-1-3-2!    0-0-2-1-3-2!
     +3-3            +3-3            +3-3            +3-3            +3-3            +3-3
   +1-1            +2-2            +3-3            +4-4            +4-4            +4-4
                                                                 +1-1            +1-1
                                                                               +1-1
____________    ____________    ____________    ____________    ____________    ____________
0-0-3-3-0-2!    0-0-4-2-0-2!    0-0-5-1-0-2!    0-0-6-0-0-2!    0-1-5-0-0-2!    1-0-5-0-0-2!

Как видно, исходная серия в данных случах одна и та же. Квадраты простых тоже расставляются и, чтобы не забывать об этом, справа указано количество их расстановок — 2!

А вот сводная статистика по эффективности для этих 6 серий:

Серия            2^     Комплектов       Счёт     Найдено      Время       Скорость
                         посчитано    от 0 до     D(96,6)     секунд    D(96,6)/час

0-0-3-3-0-2!     12     3! * 1!  6       1e21         662       1002           2378
0-0-3-3-0-2!     13     3! * 1!  6       1e21         662        946           2519 best
0-0-3-3-0-2!     14     3! * 1!  6       1e21         662        984           2422

0-0-4-2-0-2!     13     3! * 2! 12       1e22        1084        887           4400
0-0-4-2-0-2!     14     3! * 2! 12       1e22        1084        871           4480 best
0-0-4-2-0-2!     15     3! * 2! 12       1e22        1084        945           4130

0-0-5-1-0-2!     13     3! * 3!  6       1e23         407        188           7794
0-0-5-1-0-2!     14     3! * 3!  6       1e23         407        175           8373 best
0-0-5-1-0-2!     15     3! * 3!  6       1e23         407        183           8007

0-0-6-0-0-2!     14     3! * 3! 12       1e24         473        134          12707
0-0-6-0-0-2!     15     3! * 3! 12       1e24         473        122          13957 best
0-0-6-0-0-2!     16     3! * 3! 12       1e24         473        134          12707

0-1-5-0-0-2!     14     3!*4!*1 24       1e25         292         58          18124 
0-1-5-0-0-2!     15     3!*4!*1 24       1e25         292         57          18442 best
0-1-5-0-0-2!     16     3!*4!*1 24       1e25         292         59          17817

1-0-5-0-0-2!     14   3!*4!*1*1 48       1e27         496        128          13950
1-0-5-0-0-2!     15   3!*4!*1*1 48       1e27         496        124          14400 best
1-0-5-0-0-2!     16   3!*4!*1*1 48       1e27         496        133          13426

96 делителей очень интересны. Здесь хорошо видно, что при переходе от одной серии к другой приходится увеличивать интервал поиска. Но, не смотря на это, скорость всё равно росла. За исключением последнего перехода. Обычно увеличивал на порядок, но вот в самом конце, для надёжности результатов измерения скорости, пока увеличил на два порядка.

Возможно, самый последний вариант стоит ещё покопать. Подъём на один порядок внимательнее посмотреть. На всякий случай. Это та самая, так называемая серия с одним простым. Уже писал что для нахождения цепочек по ней надо изменять программу, добавляя почти в самое начало ещё две фильтрации.

Да, не упомянул. Это всё был счёт именно в одном потоке.

wrest, у вас другое мнение о том как надо считать эффективность? Как понимаю, Вы считаете количество проверенных цепочек, причём по одному единтсвенному паттерну. Но что это говорит об успехе в исходном поиске? Вот я пока нашёл 292 цепочки за 57 секунд. Сколько цепочек и за какое время найдёте вы?

[wrest]

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

у вас другое мнение о том как надо считать эффективность?

Вы в этой теме, как и в "той", ищетете цепочки. Но предполагалось искать другое - способы ускорения программ.

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

Вы считаете количество проверенных цепочек, причём по одному единтсвенному паттерну.

Да, какой есть, по тому и считаю. В моих целях, как я понимаю суть этой темы, нет результата в виде найденных цепочек. Цель - уменьшение времени (=увеличение скорости) обработки какого-то "эталонного" набора данных. Чтобы можно было видеть "ускорительные" эффекты.

-- 05.04.2026, 10:34 --

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

Это первая из 4 или 5 (смотря как считать) оптимизаций что я у себя применил ...

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

-- 05.04.2026, 11:04 --

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

Для сравнения:

Ну тут немножко такое сравнение... не вполне как мне кажется верное.
Посмотрим так:

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

sdg(k_start,k_len)={
  my(n0=0):int;
  my(sd=0):small;
  my(t0=getwalltime());\\Замер времени  начала
  for(n=k_start,k_start+k_len-1, n);
  print("Только цикл: ",strtime(getwalltime()-t0));
  t0=getwalltime();
  for(n=k_start,k_start+k_len-1, n^4);
  print("Без присваивания: ",strtime(getwalltime()-t0));
  t0=getwalltime();
  for(n=k_start,k_start+k_len-1, n0=n^4);
  print("С присваиванием, без суммы: ",strtime(getwalltime()-t0));
  t0=getwalltime();
  for(n=k_start,k_start+k_len-1, sumdigits(n^4));
  print("Без присваивания, с суммой: ",strtime(getwalltime()-t0));
  t0=getwalltime();
  for(n=k_start,k_start+k_len-1, sd=sumdigits(n^4));
  print("С присваиванием, с суммой: ",strtime(getwalltime()-t0));
}

В интерпретаторе имеем:

? sdg(10^14,10^6)
Только цикл: 64 ms
Без присваивания: 145 ms
С присваиванием, без суммы: 271 ms
Без присваивания, с суммой: 394 ms
С присваиванием, с суммой: 524 ms
time = 1,394 ms.
?

Компилируем в gp2c. Имеем:

? sdg(10^14,10^6)
Только цикл: 24 ms
Без присваивания: 97 ms
С присваиванием, без суммы: 97 ms
Без присваивания, с суммой: 340 ms
С присваиванием, с суммой: 341 ms
time = 896 ms.
?

Ну, не особо помогло. Компиляция ускорила присваивание (и сопутсвующие конвертации), но не вычисления.
Итого. На возведение в четвёртую степень 73 наносекунды, на подсчёт суммы цифр 244 наносекунд.

А вот приколы нашего городка. Увеличиваем количество циклов до 10^7, интерпретатор:

? sdg(10^14,10^7)
Только цикл: 600 ms
Без присваивания: 1,415 ms
С присваиванием, без суммы: 2,571 ms
Без присваивания, с суммой: 3,853 ms
С присваиванием, с суммой: 5,008 ms
time = 13,393 ms.
?

Те же 10^7 компиляция:
? sdg(10^14,10^7)
Только цикл: 194 ms
Без присваивания: 986 ms
С присваиванием, без суммы: 957 ms
*** sdg: Warning: increasing stack size to 800000000.
Без присваивания, с суммой: 3,397 ms
С присваиванием, с суммой: 3,320 ms
time = 8,714 ms.
?

[wrest]

Что-то не так со сбором мусора в коде который производит gp2c.

-- 05.04.2026, 11:54 --

Надо заглянуть в код на Си и разобраться, но похоже на то, что на стеке откладываются все результаты прошедших итераций цикла. Если цикл длинный, стек вырастает пропорционально и очищается по выходу из цикла. Для скорости это хорошо. Но как-то всё-таки недодумано. Вместо увеличения стека можно было бы его дропнуть.

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

[Dmitriy40]

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

А в числителе, очевидно, количество найденных искомых цепочек.

Мне не очевидно!
Я всегда использовал количество проверенных кандидатов в цепочки.
Потому что найденных может и не быть (и мат.ожидание не посчитать), а проверенные есть всегда.
И ещё потому что именно за эту скорость и борюсь. А уж сколько из них дадут решения - зависит от множества причин начиная с конкретного паттерна (скорость же проверки от него зависит гораздо слабее). И мне скорость важна для редких паттернов, если решений много, то ускорять надо другие места программы или вообще менять алгоритм (например на вариант решета Эратосфена), это не интересно.

-- 05.04.2026, 14:58 --

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

Я всегда использовал количество проверенных кандидатов в цепочки.
Потому что найденных может и не быть (и мат.ожидание не посчитать), а проверенные есть всегда.
И ещё потому что именно за эту скорость и борюсь.

К тому же имея мат.ожидание легко пересчитать эту скорость в скорость нахождения решений или требуемое время до нахождения n решений.

К тому же под скоростью работы программы все обычно подразумевают именно скорость выполнения вычислительных операций и скорость обработки входных данных, а не скорость получения выходных данных (результатов).

Вообще задача ускорения выходного потока при том же входном (скорости получения результатов с того же набора кандидатов), тем более когда выходной поток далеко не нулевой - это другая задача оптимизации! Например тут придётся ускорять финальные проверки, до которых дело обычно (при нулевом выхлопе) вовсе не доходит и их скорость никак не влияет.

-- 05.04.2026, 15:03 --

wrest
Из деления числа на цифры (или группы цифр) я уже выжал всё что можно, теперь бы найти алгоритм подсчёта суммы десятичных цифр без получения этих самых цифр ...
Или побыстрее вычислять sumdigits((n+1)^4) зная n^4 и sumdigits(n^4) (и даже пусть деление n^4 на группы цифр). Этого никак не получается.

[Yadryara]

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

Вы в этой теме, как и в "той", ищетете цепочки. Но предполагалось искать другое - способы ускорения программ.

Это не другое. Как искать цепочки давным-давно понятно. А вот как их искать быстро — это как раз центральный вопрос. На месяц растянется поиск или на сотни лет?

То как я указал скорость счёта, позволяет ответить на этот вопрос для некторых цепочек. Как на этот вопрос помогает ответить ваша скорость проверки цепочек? Человеку, прежде чем подключаться к поиску, неплохо бы знать сколько времени в среднем займёт нахождение той или иной цепочки. Сколько при этом отброшено — вопрос уже более второстепенный. С этим согласны?

Кстати, вы же именно про непреывные цепочки говорили, дырявые вас не интересовали. Ведь именно они, непрерывные, лучше подтверждают правильность работы программы. Ну вот сейчас как раз они и ищутся. Кстати, попутно уже нашлись и подлиннее: из 2653-х две оказались не только D(96, 6), но и D(96, 7).

Да, проблемы с памятью сохраняются. Именно такие. Идёт какое-то странное её потребление в зависимости от количества циклов и операций в них. В том числе при нынешнем счёте — порой тратятся гигабайты. И это тоже влияет на скорость, порой весьма сильно. Вот свежий пример:

Серия            2^     Комплектов       Счёт     Найдено      Время       Скорость
                         посчитано    от 0 до     D(96,6)     секунд    D(96,6)/час
0-1-5-0-0-2!     13     3!*4!*1 24       1e26        2653        746          12803
0-1-5-0-0-2!     14     3!*4!*1 24       1e26        2653        686          13923 best
0-1-5-0-0-2!     15     3!*4!*1 24       1e26        2653        835          11438
0-1-5-0-0-2!     16     3!*4!*1 24       1e26        2653       1157           8255

Теперь получается что поиск в серии с одним простым всё же чуть побыстрее.

[Dmitriy40]

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

С этим согласны?

Я не согласен. Тут смешали несколько вопросов. С частью согласен, с частью нет.