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

Huz · 05/06/22 293

Regarding the chance that $D(12,11) < 9887353188984012120346$ .

I had forgotten that before now I had done additional tests that made me believe we were unlikely to find a smaller solution for $D(12,11)$ .

I also run pcoul with the '-p' flag to limit the maximum prime that it will try to allocate. I have done complete runs in the past with '-p100', so there should be no possible smaller result unless it includes a square (or higher power) of a prime $p > 100$ .

I had also attempted complete runs up to -p1000, but there was an error in my logic (see below). So I have tested some but not all possible cases with combinations of squares of primes $p \le 1000$ .

This additional information underlies my "gut feeling" that the probability of finding a smaller minimum is very low.

(Оффтоп)

The -p option supports both a minimum and a maximum prime. So after a full run with -p100, a second run with -p100:200 is intended to check all possibilities with allocated primes $< 200$ that were not checked by the first run.

So with -p100:200, the set of allocations we consider require that a) all primes allocated are $\le 200$ ; b) at least one of the primes allocated must be $> 100$ .

However there is a flaw in the logic: the heuristics used by the program decide at each stage whether to recurse further (to allocate another prime) or switch to linear evaluation. Since it may make those decisions differently between the two runs, they are not guaranteed to consider the same sets of possibilities. As a result, a combination of the two runs are not sufficient to check all possibilities that would be checked by -p200.

When I first tried runs like -p100:200 I was happy that they ran so fast. But I eventually realised that they were too fast, and that there must be a problem. It took me some time to understand what the underlying error was. :(

EUgeneUS · 11/12/16 13850 уездный город Н

Кстати, если кто не видел.
Черепашка уделала меня больше чем в $2.5$ раза (по паттерну b1863)

Цитата:

Код:

001 pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1863 *RT*
...
367 coul(12, 11): recurse 568817485, walk 568821556, walkc 5621052956 (8475.14s)

Насколько понимаю, там считалось новой версией pcoul. Либо это следствие усилий по ускорению pcoul, либо Черепашка не такая уж и черепашка.
Хорошо, если первое.

Dmitriy40 · 20/08/14 11766 Россия, Москва

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

@EUgeneUS, @Dmitriy40 I noticed today that with the prime iterators change, the recommended "gain" parameter for running pcoul should change from -g3 to -g16.

OK, I runned it with b1850 for compare speed.

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

возможно, но затратно.

Ой, а я сначала прочитал как "азартно", думаю нифига себе народ вовлёкся-то! :mrgreen:

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

Прошу Дмитрия прокомментировать.

Чего тут комментировать, я ж даже не вижу по какому паттерну и кто её запускал. Скорее всего речь о выложенных SSE версиях (или даже AVX2, которые я запускал лишь очень выборочно), но тогда всё просто: они выполняют только линейный перебор, если он превышает несколько часов (я пока могу оценить только нижнюю и верхнюю границы, да и то с большим допуском, но они очень сильно различаются и потому смысла мало), то очевидно выгодно запустить перебор по квадрату простого. И если так не делать, то очевидно программа будет проигрывать. Именно поэтому я и советовал бросить перебор этими программами и сосредоточиться на программе Hugo (по крайней мере пока у меня нет версии с хотя бы одним перебором, на многих паттернах хватит и его).

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

самое большое это паттерн с $n=4$ .

Есть 32 паттерна и с n=3, это ещё медленнее. Кстати чуть выше показывал как увеличение n с 6 до 7 ускорило программу втрое на том же паттерне.
И даже с одинаковыми n и шагом есть паттерны которые перебираются вдвое дольше - компилятор ускорителей не может разрешить лишь один остаток по модулю три, я до сих пор не знаю почему и ошибка ли это или так и должно быть. И таких паттернов (вдвое дольших) около 930 из 1044 (я где-то выше говорил точную цифру), т.е. практически все, фактически тогда есть лишь несколько десятков которые перебираются вдвое быстрее большинства остальных.

Дополню свой ответ выше.

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

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

Сейчас уже завершено? Сколько времени заняло?

На данный момент ещё нет, но теперь уже близка к завершению, верхний перебор перешёл к простым 950+, ещё час-два и всё (но я пока убегаю). Уже считает 197500с.

Она днём завершилась:

Код:

367 coul(12, 11): recurse 13885499262, walk 13885504131, walkc 129303981142 (210738.91s)

Версия 20221109 пока ещё считает, но думаю часа за два справится, тоже уже пришла к числам 950+:

Код:

305 3^2.5 2 953^2 2^2.3 7^2 2.5^2 3.11^2 2^5 . 2.3^2 5: 75582353 / 127511777 (91164.77s)

Dmitriy40 · 20/08/14 11766 Россия, Москва

Huz
Finished calculation by version 20221109 for b1850:

Код:

001 pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1850 *RT*
367 coul(12, 11): recurse 13885499262, walk 13885504131, walkc 129303981142 (100465.27s)

It's double speed of version 20221107 with 210738.91s, for this particular pattern.

Testing version 20221109 with -g16 is continued, at the current moment, its speed is lower than the version -g3:

Код:

pcoul(12 11) -f11 -g16 -x9887353188984012120346 -b1850 *RT*
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 17^2 2.3^2 5.5580724703^2 (590.49s)
...
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 4174927243^2 2.3^2 5 (8166.37s)
3^2.5 2 17^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5.4248167513^2 (8757.80s)
vs
pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1850 *RT*
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 17^2 2.3^2 5: 1040514640 / 2371109213 (565.42s)
...
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 1196227259^2 2.3^2 5 (6422.65s)
3^2.5 2 17^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5: 309950771 / 2371109214 (7011.89s)

It looks like -g16 is somewhat large ...

Yadryara · 29/04/13 8111 Богородский

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

Она днём завершилась:Код:

367 coul(12, 11): recurse 13885499262, walk 13885504131, walkc 129303981142 (210738.91s)

Ну то есть прогноз Hugo не сбылся. Даже на Вашем быстром 64 AVX2 компе и то не удалось уложиться в 50 часов. 58,5 часов.

И действительно двойное ускорение в новой версии Hugo: 27,9 часа для этого же паттерна.

Но время Дмитрия(1,4 часа) всё равно в 19 раз меньше. Сравнение производилось на одном и том же компе.

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

Чего тут комментировать, я ж даже не вижу по какому паттерну и кто её запускал.

Так я же внятно сказал:

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

Напомню, что Софокл считал и считает по старым 32 SSE-прогам Дмитрия.

Считал естественно Демис.

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

1. LCM14642258400-2697641145-8 b1863 — Софокл справился быстрее всех.
...
10. LCM14642258400-2321399641-8 b2113 — Софокл справился медленнее чем комп Евгения по старой проге Hugo.

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

И если так не делать, то очевидно программа будет проигрывать.

Очевидно как раз обратное: Ваша прога выиграла(причём часто в разы) в 9 из 10 конкретных случаях.

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

Именно поэтому я и советовал бросить перебор этими программами и сосредоточиться на программе Hugo (по крайней мере пока у меня нет версии с хотя бы одним перебором, на многих паттернах хватит и его).

Зачем же бросать в тех частых случаях, когда Ваши программы явно быстрее??

Логично перейти на прогу Hugo в тех редких случаях, когда они медленнее.

Ну а версия "с хотя бы одним перебором" ведь скоро появится. Причём Вы ведь свои новые версии тестите на 64 AVX2 компе. И Маруся как раз такой комп. И уже почти свободна. Занято только 3 потока. Ведь можно уже и на ней запускать те или иные тесты?

Huz · 05/06/22 293

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

Testing version 20221109 with -g16 is continued, at the current moment, its speed is lower than the version -g3:

Please could you email me the log file for one or both of these runs?

It may be that optimal -g varies for different patterns, but when I tested this for other cases in the past it seemed similar for most patterns. I found -g16 by testing with b1630.

EUgeneUS · 11/12/16 13850 уездный город Н

Код:

b1850: LCM=42688800, n=6
b1630: LCM=42688800, n=5

Разница в количестве проверяемых чисел (values fixed to be a prime). Возможно, с этим связано, что у ключа -g разные оптимальные значения.

Yadryara · 29/04/13 8111 Богородский

Сводка по данным на вчера.

Код:

         554400  —   66 штук
        3880800  —  142 штуки
        6098400  —  180 штук
       42688800  —  226 штук
     1331114400  —   66 штук; 2 done
     8116970400  —   58 штук
    14642258400  —  152 штуки; 66 done
    56818792800  —   96 штук ; done
19488845930400  —   58 штук ; done

Количество полностью обсчитанных паттернов за сутки увеличилось на 19.

EUgeneUS · 11/12/16 13850 уездный город Н

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

Но время Дмитрия(1,4 часа) всё равно в 19 раз меньше. Сравнение производилось на одном и том же компе.

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

Очевидно как раз обратное: Ваша прога выиграла(причём часто в разы) в 9 из 10 конкретных случаях.

Идентифицируя программы Дмитрия, как "программу Дмитрия", Вы всё время говорите о двух совершенно разных вещах, как-будто бы об одной

1. Есть код, реализующий "линейный перебор с ускорителями". Код доступен, можно считать (в каком-то виде), что код отлажен. Именно на нем производится расчет на Софокле, например.
2. А есть код, реализующий "рекурсивный перебор с ускорителями". Код находится у Дмитрия в разработке, другим не доступен, а Дмитрий сообщает о своих успехах.

Первый проиграет pcoul на паттернах с малыми LCM, в некоторых особо тяжелых случаях случаях - очень сильно, в 10-20 раз.
Есть ожидания (не безосновательные), что второй будет выигрывать в разы или на порядок.

Yadryara · 29/04/13 8111 Богородский

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

Идентифицируя программы Дмитрия, как "программу Дмитрия", Вы всё время говорите о двух совершенно разных вещах, как-будто бы об одной

Нет, Вы заблуждаетесь. Я не то что "всё время" не говорю, я вообще ни разу их не путал. Будьте добры предоставьте пруфы.

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

1. Есть код, реализующий "линейный перебор с ускорителями". Код доступен, можно считать (в каком-то виде), что код отлажен. Именно на нем производится расчет на Софокле, например.

Совершенно верно. И этот код в 9 случаях из 10 оказался существенно быстрее кода Hugo.

Кстати, просьба. Запустите этот старый код Дмитрия на своём компе, чтобы ещё надёжней сравнить скорость обсчёта этих 10 паттернов.

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

2. А есть код, реализующий "рекурсивный перебор с ускорителями". Код находится у Дмитрия в разработке, другим не доступен, а Дмитрий сообщает о своих успехах.

Совершенно верно. И этот код для паттерна b1850 в 19 раз быстрее нового кода Hugo и в 41 раз быстрее старого.

Никакой путаницы нет.

EUgeneUS · 11/12/16 13850 уездный город Н

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

Нет, Вы заблуждаетесь. Я не то что "всё время" не говорю, я вообще ни разу их не путал. Будьте добры предоставьте пруфы.

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

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

Кстати, просьба. Запустите этот старый код Дмитрия на своём компе, чтобы ещё надёжней сравнить скорость обсчёта этих 10 паттернов.

Вообще нет никакого смысла. Ибо нет никакого смысла ещё более точно уточнять скорость работы pcoul и "линейного перебора с ускорителями" на паттернах с $LCM \geqslant 14642258400$ . Так как известно, что скорость работы в обоих случаях достаточна, чтобы посчитать их за дни.
В частности, все паттерны с $LCM = 14642258400$ (152 штуки) могут быть посчитаны pcoul только на моей стороне за 7-8 дней, может быть быстрее.

Проблемы с паттернами с $LCM \leqslant 42688800$ . Вот для них прогнозируемое время счета очень большое.

Yadryara · 29/04/13 8111 Богородский