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

[Dmitriy40]

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

I may be misunderstanding the phrase "maximum degree", is that intended to be the same as "maximum power"? Because the maximum power would be $p^{11}$ here, so I don't understand what you mean by "for prime in the maximum degree searched". (The variables in your formula are also not clear to me, but I'm confident I can work out what is needed there.)

It's an auto-translation mistake. I meant that for 12 divisors it would be the 5th degree (power), $p^5$, because that's the only one that goes into pcoul, or $p^{11}$ too (and up to?)?!
The variables -p and -x are just numbers in these keys, positive of course. LCM is the lcm() of the whole pattern before the substitution of primes in squares (or fifth powers). n is the power (fifth for 12 divisors). I was trying to figure out how much to limit the of $p^5$ from above.

[Huz]

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

I meant that for 12 divisors it would be the 5th degree (power), $p^5$, because that's the only one that goes into pcoul, or $p^{11}$ too (and up to?)?!

For the example pattern b198, we have $3^1$ allocated in the first position; at that location with 6 divisors still to find, pcoul will try $p^2$ and $p^5$. In the eleventh position nothing is allocated; at that location with 12 divisors still to find, it will try $p^2, p^5$ and $p^{11}$.

For the new feature we are talking about, I imagine that it would have a separate check for the cases $3p^5$ in the first position and for $p^11$ in the eleventh position, and similarly for each other position that still requires a number of divisors that is not a power of 2. The existing code paths would then need to avoid redoing those cases.

Cases where the number of divisors is divisible by two or more odd primes need additional care: since we are doing this at the pattern level (where only the forced primes have been allocated), the existing code paths should not skip anything for a position that has had an unforced prime allocated. Where the number of divisors is divisible by only a single odd prime that is not a problem, since there can only be one allocation per position.

[Dmitriy40]

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

For the example pattern b198, we have $3^1$ allocated in the first position; at that location with 6 divisors still to find, pcoul will try $p^2$ and $p^5$. In the eleventh position nothing is allocated; at that location with 12 divisors still to find, it will try $p^2, p^5$ and $p^{11}$.

I see, it was my inattention: never noticed in the logs $p^{11}$, apparently they were too fast, so I did not think about them.
But you shouldn't think about them: both $p^{11}$ and $Ap^5$ (with prime $A$) are searched once and you don't have to do that for every prime you set, you just do it once at startup. But I'm talking about what is done many-many times when you try primes in squares.

[Huz]

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

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

Make the -PXXX switch to limit primes to degrees greater than the second (i.e. the fifth), or just remove the fifth degree enumeration, run it and compare time. Maybe not twice, but there should be a speed gain. Especially for fairly small -P/-W's, like the ones I have above.

You're right, the difference is bigger than I expected if I hack the code to return immediately when asked to consider working on a prime power that would leave the remaining tau equal to 1:

# without hack
001 pcoul(12 13) -p200000 -f13 -g10 -x60000000000000000000000000 -b198
367 coul(12, 13): recurse 44878407, walk 71984211, walkc 56675032 (117.99s)
# with hack
001 pcoul(12 13) -p200000 -f13 -g10 -x60000000000000000000000000 -b198
367 coul(12, 13): recurse 44878407, walk 44889726, walkc 56675032 (78.53s)

I added a function to loop over the $p^e$ assignments with less overhead when the number of remaining divisors is $e+1$, and found that this gives almost all the savings immediately:

001 pcoul(12 13) -p200000 -f13 -g10 -x60000000000000000000000000 -b198
367 coul(12, 13): recurse 44878407, walk 71988014, walkc 56675032 (81.46s)

I will run this for a bit in case I screwed something up, then aim to release it so you can get the benefit.

[Huz]

New version of pcoul is now available at https://github.com/hvds/divrep/releases/tag/20230208, please see the release notes for details.

[Dmitriy40]

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

I added a function to loop over the $p^e$ assignments with less overhead when the number of remaining divisors is $e+1$, and found that this gives almost all the savings immediately:

In my opinion, these are independent things and even in the new version of the enumeration of the fifth powers still goes to 2e5 for each square substituted, although enough to search only up to 520 (and all large check exactly once), it should still give 1.5-2-fold increase in speed.
-j3 has not tried, I don't understand.

[Huz]

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

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

I added a function to loop over the $p^e$ assignments with less overhead when the number of remaining divisors is $e+1$, and found that this gives almost all the savings immediately:

In my opinion, these are independent things and even in the new version of the enumeration of the fifth powers still goes to 2e5 for each square substituted, although enough to search only up to 520 (and all large check exactly once), it should still give 1.5-2-fold increase in speed.

When I removed the checking of those cases entirely, the test case took 78 seconds; the latest code took 82 seconds. So the possible saving is at most 4 seconds out of 82.

Цитата:

-j3 has not tried, I don't understand.

-j3 is relevant only for n (the number of divisors) divisible by a composite square, such as n=36, n=72 or n=100.

[Dmitriy40]

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

When I removed the checking of those cases entirely, the test case took 78 seconds; the latest code took 82 seconds. So the possible saving is at most 4 seconds out of 82.

No, if they are independent things as I suspect, then the gain will add up, i.e. the time will become less than 78s. Try it!

[Huz]

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

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

When I removed the checking of those cases entirely, the test case took 78 seconds; the latest code took 82 seconds. So the possible saving is at most 4 seconds out of 82.

No, if they are independent things as I suspect, then the gain will add up, i.e. the time will become less than 78s. Try it!

I don't understand why you think that: with the latest code, the same hack involves simply not calling the newly added function:

001 pcoul(12 13) -p200000 -f13 -g10 -x60000000000000000000000000 -b198
367 coul(12, 13): recurse 44878407, walk 44889726, walkc 56675032 (78.39s)

[Dmitriy40]

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

I don't understand why you think that: with the latest code, the same hack involves simply not calling the newly added function:

Not the added function not to call, but to remove the enumeration of $p^5$! And call the function.
If both $p^2$ and $p^5$ are searched up to 2e5 and both CRT and chain check are performed for each of them, then it is obvious that by removing one of the searches (specifically $p^5$) the speed should increase. What is unclear about it? And your new function has nothing to do with it, it gives acceleration elsewhere. At least I see it that way, but tests will tell more precisely.

[Huz]

Dmitriy40 I think I must be misunderstanding what you are talking about.

We are looking for numbers with $n$ divisors. For a given value $v_i$, with a current allocation $a_i: n = t_i \cdot \tau(a_i)$, I'm talking about the handling of the cases where pcoul will try to allocate prime powers $p^{t_i - 1}$. Since for any given $p$, $a_i \cdot p^{t_i-1}$ is an absolute value, doing that repeatedly is potentially wasted effort.

The hack I used to test the potential saving here involved modifying the code to avoid testing those cases at all. For the original code, that hack showed the time reduced from 118s to 78s; the new code does the same work in 82s, and as expected the hack again showed the time reduced to 78s.

You suggest to "remove the enumeration of $p^5$". The hack removes that enumeration for those cases where $\tau(a_i) = 2$, are you suggesting to remove it also for cases where $\tau(a_i) = 1$? (If the answer is "yes", then I will comment further on that suggestion.)

[Dmitriy40]

Huz
A, i.e., the elimination of repeated searches $Ap^5, A>1$ and gave a decrease in time to 82s? And accordingly it is possible to remove $Ap^5,a=1$, which will reduce time to 78s, right? Then I understand, that's really what I was talking about.

But then it doesn't work for you:

T:\M12minimal\Hugo\20230208>pcoul -f13 -x6e24 -p2e4 -g10 -b198 -d 12 13
001 pcoul(12 13) -p20000 -f13 -g10 -x6000000000000000000000000 -b198
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.23^2 2.5^2 7^2 2^2.3 17^2 2.29^2 3^2.5: 0 / 3
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.23^2 2.5^2 7^2 2^2.3 17^2 2.19997^2 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.23^2 2.5^2 7^2 2^2.3 17^2 2.17^5 3^2.5 - FIRST, OK
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.23^2 2.5^2 7^2 2^2.3 17^2 2.19997^5 3^2.5 - FIRST, OK
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2.23^2 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2.23^2 3^2.5: 0 / 3
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2.19997^2 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2.17^5 3^2.5 -- REPEAT!
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2.19997^5 3^2.5 -- REPEAT!
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.31^2 2.5^2 7^2 2^2.3 17^2 2 3^2.5: 0 / 1887
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^2 2.5^2 7^2 2^2.3 17^2 2 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.17^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5 - FIRST, OK
...
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5 - FIRST, OK
...
3.23^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2 3^2.5: 0 / 1471
...
3.23^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^2 2.5^2 7^2 2^2.3 17^2 2 3^2.5
3.23^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.17^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5 -- REPEAT!
...
3.23^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5 - REPEAT!

I hope you also see these repeated $Ap^5$ searches in positions with $3p^5$ and $2p^5$? Because I see them, that's how many there are on a 100MB log (received in a few seconds!):

3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.23^2 2.5^2 7^2 2^2.3 17^2 2.19997^5 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 17^2 2.19997^5 3^2.5
3.23^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19^2 2.5^2 7^2 2^2.3 17^2 2.19997^5 3^2.5
3.29^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19^2 2.5^2 7^2 2^2.3 17^2 2.19997^5 3^2.5
3.17^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.23^2 2.5^2 7^2 2^2.3 19^2 2.19997^5 3^2.5
3.17^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.29^2 2.5^2 7^2 2^2.3 19^2 2.19997^5 3^2.5
3.23^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.17^2 2.5^2 7^2 2^2.3 19^2 2.19997^5 3^2.5
3.29^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.17^2 2.5^2 7^2 2^2.3 19^2 2.19997^5 3^2.5
3.17^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19^2 2.5^2 7^2 2^2.3 23^2 2.19997^5 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.17^2 2.5^2 7^2 2^2.3 23^2 2.19997^5 3^2.5
3.17^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19^2 2.5^2 7^2 2^2.3 29^2 2.19997^5 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.17^2 2.5^2 7^2 2^2.3 29^2 2.19997^5 3^2.5
3.19^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5
3.23^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5
3.29^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5
3.31^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5
3.37^2 2^2.7 5.11^2 2.3^2 13^5 2^5 3.19997^5 2.5^2 7^2 2^2.3 17^2 2 3^2.5

And another 300pcs of the $3.19997^5$ string.

And the string "3.19997^5" in total occurred in the log 2483 times (with the specified parameters of the launch, the time at the same time only 15s), instead of exactly two times!

[Huz]

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

Huz
A, i.e., the elimination of repeated searches $Ap^5, A>1$ and gave a decrease in time to 82s? And accordingly it is possible to remove $Ap^5,a=1$, which will reduce time to 78s, right? Then I understand, that's really what I was talking about.

I am talking only about the case of $Ap^5, A>1$. The recent improvement does not eliminate the repetition, it only makes that repeated work faster. The original code took 118s; the improvement gets that to 82s; removing the $Ap^5, A>1$ work entirely takes it to 78s. So eliminating the repetition will save at most another 4s.

I will still look for a way to remove the repetition. But it is not my highest priority, since the maximum possible saving (for this example test case) is fairly small and the work will involve a lot more complexity.

Independent of that, the limits specified by -p and -W are limits on primes $p$, ignoring the power. I am also considering a variation that would allow them to be expressed as limits on $p^e$. For example I might support the option "-p100^2" to mean "allocate only prime powers $p^e: p^e \le 100^2$ so that the range we consider for $p^5$ would automatically be smaller than the range for $p^2$. I need to work out how all the interactions would play out, but if I can make it work it might be a more useful way of constraining things. This is the only change that I am currently considering that would affect the $Ap^5,A=1$ case.

[Dmitriy40]

Huz
OK, I agree, the new version is indeed faster than the previous one, thank you and Demis for it. And fighting for the extra 5% (4s out of 82s) speed makes no sense. Separate -p limitation by powers would be nice, though.

[EUgeneUS]

По поиску более меньшей 12-14.

Наименование групп паттернов как в этом посте.

"Группа А" досчиталась до 21e31 (-p500)
"Группа B" досчиталась до 21e31 (-p500)
"Группа Ж" считается в диапазоне 7-14e31 (-p500)

цепочек не найдено.

В работе:
1. У DemIS'а началась считаться "Группа Б" (цель такая же - досчитать до 21e31 с ключом -p500)
2. У меня началась считаться "Группа Г" (цель досчитать до 21e31, но с ключом -p300, чтобы время расчета было более вменяемым)

Также провел эксперимент по расчету паттерна из "Группы А" с ключом -p100 от 21e31 до 200e31. Время расчета получилось вполне вменяемым - около 400 тысяч секунд.

Dmitriy40
Huz
Как по вашему мнению, насколько перспективно посчитать паттерны из "Группы А" до 200e31 (то есть до минимальной известной цепочки) с ключом -p100?
В частности, если уже такой расчет кем-то проводился, то повторно считать, нет смысла. Также приветствуются любые другие соображения.