Пентадекатлон мечты

[wrest]

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

Поэтому после реализации в pcoul расчета по явно заданному паттерну\батчу у меня пропал интерес к компиляции скриптов PARI\GP в исполняемый код.

В pari/gp что-то сделано довольно неплохо в алгоритмическом плане (та же факторизация).
Там уже системно вшита длинная арифметика, так что об этом не надо беспокоиться.
И сам по себе pari/gp это всё-в-одном.
Когда заходит речь о скорости на длинных дистанциях, преимущества pari/gp становятся недостатками, например использование длинной арифметики там, где заведомо нужна короткая, постоянное копирование больших тяжелых данных туда-сюда вместо передачи по ссылке и тому подобное. При компиляции через gp2c не очень хорошо сделан сбор мусора (garbage collection), что или приводит к замедлению на чрезмерный сбор мусора или к утечкам. К параллеллизму тоже есть вопросы по эффективности.

В итоге, pari/gp хорошо подходит для проверки концепции ну и для не очень длинных вычислений. Для многодневных вычислений, быстрее будет потратить день на оптимизацию, возможно рефакторинг алгоритма в Си/Асм и т.п. Но при рефакторинге придётся решать уже решённые в pari/gp задачи: та же длинная арифметика.

Преимущества, которые становятся недостатками проектов типа yafu, primesieve (ну и pcoul) тоже очевидны: заточенность на конкретную функцию, невозможность самостоятельно менять/подстраивать алгоритмы или форматы обмена, необходимость погружаться в детали по многим проектам вместо одного.

В целом, если в этом новом предприятии на boinc скрипт pari/gp хорошо подготовлен к компиляции аккуратной типизацией, сделано какое-то профилирование например по потреблению памяти и т.п. и поправлены мелкие косячки, то скорость будет вполне приемлемая в смысле отношения трудозатрат на программирование к скорости вычислений.

[Yadryara]

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

В целом, если в этом новом предприятии на boinc скрипт pari/gp хорошо подготовлен к компиляции аккуратной типизацией, сделано какое-то профилирование например по потреблению памяти и т.п. и поправлены мелкие косячки,

Я написал 26 версий программы, но в работу пошла довольно ранняя, 4-я.

В числе прочих версий были и бинарники, то есть программы для которых (по заявлению ИИ) вообще не нужен PARI, а достаточно голого Линукса, правда, такой бинарник весил 12 Мегов.

Экзешник под Винду тоже делали.

[wrest]

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

достаточно голого Линукса, правда, такой бинарник весил 12 Мегов.

Да, это примерно размер libpari

[EUgeneUS]

Huz в сообщении #1735656 писал(а):

It will vary greatly by target:

Thanks for the answer.
It would be interesting to know whether the calculation acceleration improvements that have proven effective in implementing PARI/GP scripts have already been or will be implemented. Specifically:

1. After substituting primes into powers greater than one, the check should first be performed at those positions where a prime is expected (if such positions exist, of course). This is because primes are less common, and the check is much faster than factorization.

2. "Filtering by forbidden iterator remainders."
That is, eliminating variants that lead to an increase in the degree of the primes placed. At least for the numbers forced into the batch.
This can lead to lost solutions in some cases. Therefore, it's not suitable for working on chain minimality proofs. However, it greatly streamlines the search for chains.

3. After substituting primes to powers greater than one, check positions where a product of primes is expected (pq, pqr, prqs, etc.) and check the remainder for primality before factoring. This will quickly weed out obviously unsuitable chains.

4. After substituting prime numbers to powers greater than one, checking positions where the presence of a product of prime numbers is expected (pq, pqr, prqs ...), after checking the remainder for primality, do not perform a complete factorization, but rather a search for relatively small divisors (for example, up to $10^{20}$) with a check of the remaining remainder for primality.
For example.
a. We expect a number with 16 factors (pqrs). We found two small factors. We checked the remainder for primality – it is prime. We can immediately "reject" it without performing a full factorization.
b. We expect a number with 8 factors (pqr). We found two small factors. We checked the remainder for primality – it is prime. Factorization is complete.

This method is also not suitable for working on chain minimality proofs. However, it significantly speeds up chain searches.

[Yadryara]

Написал я на форуме BOINC Central. Посещаемость там конечно дай боже: за 5 часов 6 просмотров
Вот такую картинку хотел там запостить, но вроде у них TikZ не работает, путь пока будет здесь. Здесь все обладатели находок нынешнего поиска с valids не меньше 23:

\begin{tikzpicture}[scale=1.0] \node[anchor=west] at (0, 1.5) {\large\textbf{thec0mpler}}; \node[blue] (num1) at (5.2, 1.5) {$23$}; \draw[blue, thick] (num1) circle (0.29); \filldraw[draw=green!70!black, fill=white, thick] (6.1, 1.5) circle (0.29); \node[text=green!60!black] at (6.1, 1.5) {$\mathbf{24}$}; \node[anchor=west] at (0, 0.8) {\large\textbf{Egon Olsen}}; \filldraw[draw=blue, fill=orange!35!yellow!20, thick] (5.2, 0.8) circle (0.29); \node[blue] at (5.2, 0.8) {$\mathbf{23}$}; \node[anchor=west] at (0, 0.1) {\large\textbf{RinYuhki}}; \node[blue] (num3) at (5.2, 0.1) {$23$}; \draw[blue, thick] (num3) circle (0.29); \node[anchor=west] at (0, -0.6) {\large\textbf{Mark Andrew Herbst}}; \node[blue] (num4) at (5.2, -0.6) {$23$}; \draw[blue, thick] (num4) circle (0.29); \node[anchor=west] at (0, -1.3) {\large\textbf{Nichan}}; \node[blue] (num5) at (5.2, -1.3) {$23$}; \draw[blue, thick] (num5) circle (0.29); \node[anchor=west] at (0, -2.0) {\large\textbf{Hanjo}}; \node[blue] (num6) at (5.2, -2.0) {$23$}; \draw[blue, thick] (num6) circle (0.29); \node[anchor=west] at (0, -2.7) {\large\textbf{Haegar}}; \node[blue] (num7) at (5.2, -2.7) {$23$}; \draw[blue, thick] (num7) circle (0.29); \node[anchor=west] at (0, -3.4) {\large\textbf{atfogarasi}}; \node[blue] (num8) at (5.2, -3.4) {$23$}; \draw[blue, thick] (num8) circle (0.29); \node[anchor=west] at (0, -4.1) {\large\textbf{69Camaro}}; \node[blue] (num9) at (5.2, -4.1) {$23$}; \draw[blue, thick] (num9) circle (0.29); \node[anchor=west] at (0, -4.8) {\large\text{Аноним}}; \node[blue] (num10) at (5.2, -4.8) {$23$}; \draw[blue, thick] (num10) circle (0.29); \node[anchor=west] at (0, -5.5) {\large\textbf{LouBricant}}; \node[blue] (num11) at (5.2, -5.5) {$23$}; \draw[blue, thick] (num11) circle (0.29); \node[anchor=west] at (0, -6.2) {\large\textbf{ZJDon}}; \node[blue] (num12) at (5.2, -6.2) {$23$}; \draw[blue, thick] (num12) circle (0.29); \node[anchor=west] at (0, -6.9) {\large\textbf{MikeyG\_U2}}; \node[blue] (num13) at (5.2, -6.9) {$23$}; \draw[blue, thick] (num13) circle (0.29); \node[anchor=west] at (0, -7.6) {\large\textbf{TheBlackDream}}; \node[blue] (num14) at (5.2, -7.6) {$23$}; \draw[blue, thick] (num14) circle (0.29); \end{tikzpicture}

[EUgeneUS]

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

Specifically:

This, of course, implies that quick checks of all positions in the chain are performed first, until the first one fails.
Only if the quicker checks of all positions in the chain are successful does the transition to longer checks occur.

[Huz]

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

It would be interesting to know whether the calculation acceleration improvements that have proven effective in implementing PARI/GP scripts have already been or will be implemented.

Yes, pcoul has always done all of 1, 3, 4 and more; it has also been discussed in this forum before - Dmitry may remember when that was.
I'm not sure what you mean by (2), it seems to have two parts in it: the '-px' option you already use lets you control the degree of the primes placed; and where any position leaves a square remaining we track the quadratic residues modulo the LCM of all placed prime powers, and avoid any further placement that would contradict that.

If it is not clear, I can ask Claude to write an explanation for the wiki in both English and Russian, it is possible he can do a better job than the free translators.

[EUgeneUS]

Huz в сообщении #1735698 писал(а):

Yes, pcoul has always done all of 1, 3, 4 and more;

Wonderful

Huz в сообщении #1735698 писал(а):

I'm not sure what you mean by (2), it seems to have two parts in it: the '-px' option you already use lets you control the degree of the primes placed;

Apparently I didn't explain it clearly (even in Russian)
This is the same effect that causes you to use the "double step", but when applied to prime numbers other than 2.
Below I will try to explain with an example.

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

Example 1.
Suppose the maximum power of $3$ in a batch is $3^5$, and it appears only in one position.
The Chinese Remainder Theorem guarantees that the number in the candidate chain is divisible by $3^5$. However, there is no guarantee that this number is divisible by exactly $3^5$, or even a higher power of $3$.
And if the number in this position is divisible by $3^6$ or a greater power, then
a) either it won't work at all, since there won't be the required number of divisors
b) or the remainder will require some unlikely combination of divisors

This is not difficult to control using the "iterator" remainders modulo 3. Every third one will lead to this collision, and such remainders are called "forbidden" or "bad".

And further verification of such a chain is unnecessary. The chain will either be inherently invalid, or the probability of obtaining a valid number at that position will be greatly reduced.
Of course, this is if we're searching for a chain, not proving the minimality of a known one.

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

Example 2.
Let's say the maximum power of 3 in a batch is $3^2$, and it appears in two positions.

By similar reasoning, we find that there are two "bad remainders" modulo 3. Only one "good" remainder remains. This leaves us with the need to conduct further checks on the candidate chain.

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

Efficiency.
The proportion of "good" remainder depending on the number of primes used is calculated as follows (assuming each prime yields one "bad" remainder):

$$GR = \prod\limits_{p_i=3}^{p_{\text{max}}} (1 - \frac{1}{p_i})$$

If $p_{\text{max}}=23$, then $GR \approx 0.327$
Only a third of the chains need to be checked. If the iterator range is large and upfront overhead is irrelevant, the speedup will be three times greater.

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

If, however, some prime numbers yield more "bad" remainders, the filtering is even better.
For the case in Example 2, the GR is halved.

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

Of course, this method must be enabled with a special key, as it can skip solutions and is not suitable for proving the minimality of a chain.

[EUgeneUS]

Apparently I was wrong at this point:

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

Of course, this method must be enabled with a special key, as it can skip solutions and is not suitable for proving the minimality of a chain.

This method does not skip solutions when proving minimization, but eliminates the need to double-check some chains.

Let's consider batches, for example, for D(48,24), which differ only in the maximum power of 3. And this maximum power can be: $3^2$, $3^5$, $3^{11}$, $3^{23}$ (we don't count $3^{47}$, there is only one candidate).
So, if we don't check for "bad" iterator remainders, as described above, then when we check chains for batches with a maximum degree of three $3^2$, all other batches with a higher degree of three will also be checked.
In addition, checks will be performed on chains with clearly unsuitable powers such as $3^3$, $3^4$, $3^6$, $3^7$, etc.

And checking for batches with powers of three greater than $3^2$ will simply repeat the check that has already been performed.

[Huz]

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

Example 1.
Suppose the maximum power of $3$ in a batch is $3^5$, and it appears only in one position.
The Chinese Remainder Theorem guarantees that the number in the candidate chain is divisible by $3^5$. However, there is no guarantee that this number is divisible by exactly $3^5$, or even a higher power of $3$.

Within the walk we check this: for each value we are about to walk, we check that it would not repeat a prime at any place where that prime is already allocated. (We prepare the modular inverse in advance, so this is a quick check for each individual prime that has been allocated, but it might be faster to combine them all so that it becomes a single gcd() check.)

Цитата:

Example 2.
Let's say the maximum power of 3 in a batch is $3^2$, and it appears in two positions.

We have discussed this before: pcoul does not currently detect that case in advance, so the bad cases here will only be filtered during the walk by the inverse check described above. Detecting and recording this case at the point we build the batch is possible, but there was always a high risk of introducing new bugs. Now that I am working with AI, it should be possible to achieve it. I would expect a big saving for cases where a square is fixed, since this will give us new cases we can reject much earlier due to quadratic residues - but those cases are already fast. The saving for other cases will be smaller.

A new optimization due to be added soon will increase the savings - it finds additional early rejections based on the fixed modulus, which is usually 2 times the LCM of the allocations. This case would multiply the fixed modulus by 3, which would increase the early rejection rate.

[EUgeneUS]

Huz в сообщении #1735729 писал(а):

Within the walk we check this: for each value we are about to walk, we check that it would not repeat a prime at any place where that prime is already allocated.

Well, so this check is already implemented. And all we can talk about is optimizing its execution speed.
I will only note that there is no need to check in all the places where this simple is located.

It is enough to check the places where the prime is located in the maximum power for a given arrangement.

For example, here is one of the batches for D(48,24)

Batch id   v_0   v_1   v_2   v_3   v_4   v_5   v_6   v_7   v_8   v_9   v_10   v_11   v_12   v_13   v_14   v_15   v_16   v_17   v_18   v_19   v_20   v_21   v_22   v_23
279981496   2^3.5^2   3.11^2   2.19^2   7.23^2   2^2.3   5   2   3^2   2^5   13.17^2   2.3.5.7^2   1   2^2.11   3   2   5   2^3.3^2   7   2   3   2^2.5   19   2.3.13^2   11

There is no need to check if an "extra 3" has fallen in all positions where a 3 is located.
It is enough to check the positions v_7 and v_16 where the 3 is located in the maximum power for a given batch - $3^2$