Al Zimmermann: Primorial Soup

[dimkadimon]

dobrichev в сообщении #1266592 писал(а):

With realistic assumption that the current best results are obtained using less than several thousands CPU cores, the right approach is different.

I believe the "brute-force" method can only work for $N \leq 13$. For higher $N$ there must be a clever approach that approximates good solutions, but not optimal ones. I tried simulated annealing, but it gives very bad solutions. Perhaps there is some hybrid algorithm that combines the brute-force method with simulated annealing? For example you can find some (maybe half) of the nodes using the brute-force method and after that run simulated annealing to find a good combination of weights for the remaining nodes.

[mertz]

I tried annealing by randomly choosing 2 nodes, looking at all 1024 (N=12) combinations of swapped values, then picking the one with the least amount of change to the score. It is not very dynamic and gets stuck in a local minimum easily. It might be improved by randomly selecting a small number of possibilities instead of just the best. I am not an experienced annealer.

For N=13, it is not hard to find nine nodes, it is the tenth that is hard. You only need to find ten, then build the last two nodes from the 2048 possibilities of the remaining primes to find the best score. To build the last three nodes would require searching 362 million possibilities.

N=12 solution is still hiding from me.

[as73251]

Herbert Kociemba в сообщении #1265742 писал(а):

as73251 в сообщении #1265683 писал(а):

Это полный поиск?

Yes, 1 hour for the complete search space. The optimal solution already appears after 4 minutes with my order of computation.

For N=13 I use a list of about 200000 vertices. But within 12 hours I did not find even 8 vertices that "fit together". So I need a different approach for N>=13.

У меня сейчас на одном ядре полный поиск для n=10 занимает 130 с. Имеет ли смысл с таким результатом двигаться дальше?

[jcmeyrignac]

dimkadimon в сообщении #1267250 писал(а):

dobrichev в сообщении #1266592 писал(а):

With realistic assumption that the current best results are obtained using less than several thousands CPU cores, the right approach is different.

For higher $N$ there must be a clever approach that approximates good solutions, but not optimal ones. I tried simulated annealing, but it gives very bad solutions. Perhaps there is some hybrid algorithm that combines the brute-force method with simulated annealing? For example you can find some (maybe half) of the nodes using the brute-force method and after that run simulated annealing to find a good combination of weights for the remaining nodes.

Another idea is to remove all unpromising vertices, and combine the good ones by using brute-force.
Some patterns seem to exist...

[as73251]

as73251 в сообщении #1267379 писал(а):

Herbert Kociemba в сообщении #1265742 писал(а):

as73251 в сообщении #1265683 писал(а):

Это полный поиск?

Yes, 1 hour for the complete search space. The optimal solution already appears after 4 minutes with my order of computation.

For N=13 I use a list of about 200000 vertices. But within 12 hours I did not find even 8 vertices that "fit together". So I need a different approach for N>=13.

У меня сейчас на одном ядре полный поиск для n=10 занимает 130 с. Имеет ли смысл с таким результатом двигаться дальше?

Улучшил результат до 39 с., но вопрос остается актуальным.

[dimkadimon]

as73251 в сообщении #1267463 писал(а):

Улучшил результат до 39 с., но вопрос остается актуальным.

Хороший результат, продолжайте дальше!

[Herbert Kociemba]

as73251 в сообщении #1267463 писал(а):

Улучшил результат до 39 с., но вопрос остается актуальным.

My program is slower for N=10. You definitely should proceed!

[as73251]

dimkadimon, Herbert Kociemba

Спасибо. Herbert Kociemba, почему Ваша программа медленней: ведь алгоритм, который я использую, должен быть виден невооруженным глазом.

[as73251]

Полный расчет на одном ядре для n=11 занял 32.5 мин.

[as73251]

dimkadimon в сообщении #1264047 писал(а):

Geen в сообщении #1264003 писал(а):

Кстати, при $n=12$ перестаёт хватать int64

А я просто double использую. Да неточно, но работает.

Тогда советую для лучшей точности использовать long double - интеловский транслятор поддерживает эту точность. Опции при трансляции: -Qlong-double -Qpc80. Т.к. для печати printf использует мелкософтовскую библиотеку, не поддерживающую long double, то советую соответствующим образом преобразовать long double, чтобы long double влезал в границы unsigned __int64 (разделить, например, на 10 в соответствующей степени), а потом привести его к unsigned __int64: в результате увидите больше точных знаков.

[Dmitriy40]

as73251 в сообщении #1267821 писал(а):

Тогда советую для лучшей точности использовать long double

Только это убъёт возможность векторизации SSE/AVX и заставит использовать FPU, что может существенно (до 5 раз) замедлить программу. Потому возможно стоит внимательно проанализировать где именно нужна такая точность, а где можно обойтись и чуть меньшей (double или даже single) - ради скорости вычислений. Впрочем надо потестировать реальную программу, может падение скорости будет и небольшим.

[dimkadimon]

as73251 в сообщении #1267821 писал(а):

Тогда советую для лучшей точности использовать long double

Друзья, я использую Java и у меня нет long double и SSE/AVX etc. В моем случае точность особо не нужна и double хватает. Double во много раз быстрее точного варианта (BigDecimal).

Кстати, кто нибудь считал сколько разных оптимальных решений для каждого N?

-- 22.11.2017, 17:15 --

Observation: often optimal solutions contain a node, which is adjacent to 2 and the largest prime p.

I have verified that this holds for N<=10, but fails for my N=11. Although N=11 has the largest prime adjacent to 3. Can anyone explain this phenomenon? Can we derive other similar patterns?

[as73251]

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

as73251 в сообщении #1267821 писал(а):

Тогда советую для лучшей точности использовать long double

Только это убъёт возможность векторизации SSE/AVX и заставит использовать FPU, что может существенно (до 5 раз) замедлить программу. Потому возможно стоит внимательно проанализировать где именно нужна такая точность, а где можно обойтись и чуть меньшей (double или даже single) - ради скорости вычислений. Впрочем надо потестировать реальную программу, может падение скорости будет и небольшим.

При нормальном алгоритме скорость не изменится.

-- 22.11.2017, 12:20 --

dimkadimon в сообщении #1267852 писал(а):

Кстати, кто нибудь считал сколько разных оптимальных решений для каждого N?

Для n=11 у меня получилось 14 оптимальных решений вместо 15-ти, как у jcmeyrignac. Это связано с тем, что в силу специфики моего алгоритма получения vertices их количество (штук на 20) немного отличаются.

-- 22.11.2017, 12:25 --

dimkadimon в сообщении #1267852 писал(а):

Can anyone explain this phenomenon?

Не стоит искать черную кошку в темной комнате.

[Herbert Kociemba]

dimkadimon в сообщении #1267852 писал(а):

Кстати, кто нибудь считал сколько разных оптимальных решений для каждого N?

I think it is very probable that the optimal solutions are unique. I think it is even hard to find two arbitrary solutions with the same rawscore. Does anybody know such a pair?

[dimkadimon]

as73251 found 14 optimal solutions for N=11.

-- 22.11.2017, 20:20 --

as73251 в сообщении #1267872 писал(а):

Не стоит искать черную кошку в темной комнате.

Я думаю тут могут быть полезные узоры...