2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9, 10 ... 12  След.
 
 Re: Al Zimmermann: Primorial Soup
Сообщение20.11.2017, 13:53 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение20.11.2017, 18:02 


02/11/12
141
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.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение20.11.2017, 21:56 


04/10/17

153
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 с. Имеет ли смысл с таким результатом двигаться дальше?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение20.11.2017, 22:21 


20/01/13
62
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...

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение21.11.2017, 09:45 


04/10/17

153
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 с., но вопрос остается актуальным.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение21.11.2017, 13:00 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
as73251 в сообщении #1267463 писал(а):
Улучшил результат до 39 с., но вопрос остается актуальным.

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение21.11.2017, 19:45 
Аватара пользователя


25/08/12
171
Germany
as73251 в сообщении #1267463 писал(а):
Улучшил результат до 39 с., но вопрос остается актуальным.
My program is slower for N=10. You definitely should proceed!

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение21.11.2017, 23:07 


04/10/17

153
dimkadimon, Herbert Kociemba

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.11.2017, 03:17 


04/10/17

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.11.2017, 10:01 


04/10/17

153
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: в результате увидите больше точных знаков.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.11.2017, 10:33 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.11.2017, 11:22 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.11.2017, 12:00 


04/10/17

153
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?

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.11.2017, 12:37 
Аватара пользователя


25/08/12
171
Germany
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?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.11.2017, 14:09 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
as73251 found 14 optimal solutions for N=11.

-- 22.11.2017, 20:20 --

as73251 в сообщении #1267872 писал(а):
Не стоит искать черную кошку в темной комнате.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 177 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9, 10 ... 12  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group