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

[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$

[EUgeneUS]

Huz
I encountered strange behavior in pcoul when generating batches, which I can’t explain.
I generate batches for D(36,14). Startline:

pcoul -r"36_14-1.log" -f13 -p72 -x5e80 -fr -a2 36 14 > 36-14-4.txt

I check which powers were included in the batches in the output file:

$2^3$ - exists
$3^3$ - don't exists
$5^3$ - don't exists
$7^3$ - don't exists
$11^3$ - don't exists
$13^3$ - don't exists

$2^5$ - exists
$3^5$ - exists
$5^5$ - don't exists
$7^5$ - exists
$11^5$ - exists
$13^5$ - exists

$2^8$ - exists
$3^8$ - exists
$5^8$ - exists
$7^8$ - exists
$11^8$ - exists
$13^8$ - exists

$2^{11}$ - exists
$3^{11}$ - don't exists
$5^{11}$ - don't exists
$7^{11}$ - don't exists
$11^{11}$ - exists
$13^{11}$ - exists

$2^{17}$ - exists
$3^{17}$ - exists
$5^{17}$ - don't exists
$7^{17}$ - exists
$11^{17}$ - exists
$13^{17}$ - exists

Why were some seemingly valid options not included in any batches?

[Huz]

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

Huz
I encountered strange behavior in pcoul when generating batches, which I can’t explain.
I generate batches for D(36,14). Startline:

pcoul -r"36_14-1.log" -f13 -p72 -x5e80 -fr -a2 36 14 > 36-14-4.txt

There are 4.5 simple explanations:

1) $3^{11}$ is impossible: $v_i = 3^{11} \cdot q^2$, each value of $q$ leads to a contradiction for some value that has to be in the chain.

2) $3^3, 5^3, 5^{11}, 5^{17}$ each appear only in cases where some value has remaining $t = 1$. Those cases are handled immediately and the batch is never printed unless you run with '-a6'.

2.5) You can't run with '-a6', because it crashes. I can fix the crash, but see additional discussion below.

3) $5^5, 7^3, 7^{11}$ each appear also in cases where two values are forced square. Those cases are handled immediately by the Pell solver and the batch is never printed unless you run with '-a6' or '-jp'.

4) $2^3, 7^1, 11^1, 11^3, 13^1, 13^3$ do not appear as the highest power of a batch due to a bug with the handling of $p^{2^x - 1}$, I have a fix coming for that.

I believe (or Claude believes, and I believe Claude) the correct counts should be:
- 459,233 normal batches (you see 311,396 of them due to the bug (4))
- 142,691 Pell batches
- 11,223,481 fixed values (t=1)

That is assuming '-a4' should print every batch that includes a fixed value: for example, when $v_0 = 2^8 \cdot 3^3$ there are 1003 ways to assign the remaining primes to make a batch. I don't know how valuable it is to you to have all 1003 of those printed. There are two ways I could make it behave differently:
1) print a short batch as soon as we see a fixed value, so you'd see one batch starting $2^8 \cdot 3^3$ with only powers of 2 and 3 allocated. This is easy, and would show 380,810 cases of which about 22,700 are short batches. I recommend this.
2) make complete batches for those cases, but do all the usual checks that the additional primes represent valid assignments. That would need another 40-50 lines of code to handle this specific case - it would do a lot more work, and eventually print nothing since none of those 11,223,481 batches are valid. I will implement this only if you tell me this is what you want.

[EUgeneUS]

Thank you for the detailed answer and comprehensive analysis!

Indeed, 311,396 batches were formed. This means the analysis was completed fully.

I'm not interested in “quickly solved” batches at all. Therefore, no special modifications that you didn't plan for are required to output them.
BTW, I noticed the lack of batches with $t_1 >0$. But I immediately forgot about it because I'm not interested in them at all.

After your answer, I checked that $5^8$ appears only as $2 \cdot 5^8$ or $3 \cdot 5^8$.
It is clear that in such positions replacing $5^8$ with $5^3$ is impossible, and replacing it with $5^5$ leads to a “quickly solved” batch.

[Yadryara]

8 дней со старта D48-24 Starday Dime прошло. Приложение в последнее время наконец-то работает бесперебойно. ("Стучу по деревянной комментаторской голове" )

Скорость счёта даже чуть возросла и перевалила-таки за 50 тысяч заданий в день. Посчитано 420 тысяч заданий и по 380 тысячам у меня есть стата по находкам.

В вычислениях приняли участие 302 кранчера и 418 компов. Из моих знакомых здорово помогают Демис и Наталия Макарова, видимо, подключившая 48 ядер, которые позволили меньше чем за сутки посчитать около 4-х тысяч заданий.

Демисом было замечено, что некоторые задания, в том числе из первого сорта, не были полностью посчитаны. Вчера досчитали и их, так что статистика подкорректирована.

Валидс                  от 0 до 1е58
по полю         1-й сорт            2-й сорт

     24                                    1
     23                2                  13   13.0
     22               26   13.0           44    3.4
     21              126    4.8          226    5.1
     20              402    3.2          853    3.8
____________________________________________
                     556                1137

В первом сорте, похоже, был недобор 23-к, а во втором всё ещё перебор.