Модифицировать программу (практическая помощь)

[Nataly-Mak]

Progger в сообщении #901856 писал(а):

Для квадрата maxal:

progger@progger-laptop:/tmp/build-primesquare-Desktop-Release$ ./primesquare 170693000000000 170694000000000
170693941183817 170693941183847 170693941183861 170693941183891 
170693941183859 170693941183889 170693941183903 170693941183933 
170693941183907 170693941183937 170693941183951 170693941183981 
170693941183949 170693941183979 170693941183993 170693941184023 

170693941183817 170693941183847 170693941183907 170693941183937 
170693941183859 170693941183889 170693941183949 170693941183979 
170693941183861 170693941183891 170693941183951 170693941183981 
170693941183903 170693941183933 170693941183993 170693941184023 

170693941183817 170693941183847 170693941183859 170693941183889 
170693941183861 170693941183891 170693941183903 170693941183933 
170693941183907 170693941183937 170693941183949 170693941183979 
170693941183951 170693941183981 170693941183993 170693941184023 

Time: 5.24848, primes: 30520112

whitefox в сообщении #892128 писал(а):

maxal в сообщении #892112 писал(а):

[ 0 42 90 132]
[30 72 120 162]
[44 86 134 176]
[74 116 164 206]

Nataly-Mak в сообщении #891897 писал(а):

0 30 44 74 
42 72 86 116 
90 120 134 164 
132 162 176 206

Два варианта одного и того же квадрата.
Его "каноническая форма" следующая:

[ 0 30 42 72]
[44 74 86 116]
[90 120 132 162]
[134 164 176 206]

Условие "каноничности" : $a_{12}<a_{13}<a_{21}<a_{31}$

[Nataly-Mak]

Это набор из 25 последовательных простых чисел, выложенный maxal в теме «Магические квадраты»:

293452155919921 
0 6 12 18 36 48 66 70 78 82 88 96 102 108 120 126 138 148 150 168 180 216 246 250 258

Это набор, прошедший предпроверку, описанную maxal в той же теме.

Из чисел этого набора моей программе удалось построить такой квадрат Стенли 5-го порядка:

0  6  36  66  70 
12  18  48  78  82 
102  108  138  168  172* 
120  126  156*  186*  190* 
150  156*  186*  216  220*

Звёздочкой помечены элементы квадрата, не вошедшие в заданный набор.
Решение с 7 "дырками" ("дырки" - это неправильные элементы квадрата, то есть недопустимые по принадлежности заданному набору чисел; есть тут и два одинаковых элемента, что тоже недопустимо).

[Alexu007]

Nataly-Mak в сообщении #902753 писал(а):

"Прикрутить" генератор primesieve к нашей задаче whitefox смог. Теперь надо оптимизировать процедуру проверки построения квадрата Стенли, чтобы она так сильно не тормозила весь процесс.

Nataly, держитесь крепче за стул. Многие из тех, кто читают вашу тему, не слишком отчётливо представляют, что такое "генератор primesieve" и "квадрат Стенли". Поэтому, если хотите, чтобы вам помогли - формулируйте задачу так, чтобы было понятно всем, а не только посвящённым.


Если я не прав, поправьте. Задача, в которой просит помощи Nataly-Mak, делится на две подзадачи:

1. Найти все простые числа в заданном диапазоне.
2. В массиве найденных простых чисел произвести поиск по некоторому алгоритму, с целью найти (либо не найти) последовательность чисел, из которых затем построится квадрат Стэнли.

О размере и количестве требуемых простых чисел можно догадаться из предыдущих сообщений:

Цитата:

Понятно, что проверять придётся огромные массивы.
maxal сообщил в теме, что он уже дошёл до $4 \cdot 10^{14}$, решение пока не найдено. Это поразительно! Столько наборов проверено и ни одного квадрата.

Так же можно сделать вывод, что проблема генерации простых чисел всё-же решена:

Цитата:

Прикрутить" генератор primesieve к нашей задаче whitefox смог.

В таком случае, очевидно, не нужно тратить усилия на дублирование написания программы генерации. Однако непонятно, как она решена, где и в каком виде хранятся эти найденные простые числа - в оперативной памяти, в файле? Где именно осуществлять поиск?

Ну и сам алгоритм поиска. Напишите как можно проще и понятнее, что вам нужно найти в массиве простых чисел?

[Nataly-Mak]

Alexu007 в сообщении #902810 писал(а):

Напишите как можно проще и понятнее, что вам нужно найти в массиве простых чисел?

А не прочитать ли вам эту тему с первого поста?
Всё ведь написано и описано, и расписано
Вот в этом посте, например, описан алгоритм поиска квадрата Стенли 5-го порядка.

Что ещё вам нужно написать "проще и понятнее"?

-- Вт сен 02, 2014 01:41:43 --

Alexu007 в сообщении #902810 писал(а):

Так же можно сделать вывод, что проблема генерации простых чисел всё-же решена:

Цитата:

Прикрутить" генератор primesieve к нашей задаче whitefox смог.

В таком случае, очевидно, не нужно тратить усилия на дублирование написания программы генерации. Однако непонятно, как она решена, где и в каком виде хранятся эти найденные простые числа - в оперативной памяти, в файле? Где именно осуществлять поиск?

Программа whitefox пока не обсуждается. Он над ней работает.
Если автор сочтёт нужным, выложит её для обсуждения.

В этом посте выложена программа Progger.
Если вам интересно, как "прикручен" генератор primesieve к поставленной здесь задаче, смотрите эту программу.

[Nataly-Mak]

Пока у меня крутится программа whitefox, экспериментирую вручную (ну, конечно, квадрат Стенли составляю по своей программке).

Это ещё один набор maxal, выложенный в теме "Магические квадраты" как прошедший предпроверку:

maxal в сообщении #896257 писал(а):

Эти проверки настолько "убийственные", что в интервале $[47\cdot 10^{12},235\cdot 10^{12}]$ им не удовлетворяет ни один набор из 25 последовательных простых чисел (при уменьшение на минимальных элемент, так как мы требуем $x_0=0$). А последний из прошедших проверку был такой:

46335098240069 0 18 30 42 60 78 104 122 168 182 198 200 210 212 224 228 240 272 288 290 302 332 380 410 500

Попробовала из чисел этого набора построить квадрат Стенли:

0  60  104  182  272 
18  78  122  200  290 
228  288  332  410  500 
302  362*  406*  484*  574* 
-148* -88* -44*  34*  124*
S=1018

Как всегда, неправильные элементы квадрата помечены звёздочкой.
9 "дырок" в этом решении (кстати, в квадрате есть отрицательные числа, чего не было в предыдущих примерах).
Обратите внимание: полностью правильно составились три строки квадрата (это напомнило мне "с тремя правильными рядами" из описания предпроверки svb).
Насколько я поняла, у svb это были бы такие правильные ряды:

46335098240069:
0  60  104  182  272 
18  78  122  200  290 
x   x   x   x   x 
x   x   x   x   x
228  288  332  410  500
S=1018

Квадрат с четырьмя правильными рядами мне пока получить не удалось; хоть бы посмотреть на такой

[Nataly-Mak]

Вот здесь есть почти четыре правильных ряда:

13: 0, 4, 6, 10, 16, 18, 24, 28, 30, 34, 40, 46, 48, 54, 58, 60, 66, 70, 76, 84, 88, 90, 94, 96, 100

0  4  16  60  70
6  10  22*  66  76  
24  28  40  84  94 
x   x   x   x   x
30  34  46  90  100
S=248 

Если кто найдёт лучшее приближение к искомому решению, покажите, пожалуйста.
Важно знать, насколько близко мы можем приблизиться к решению.
Например, очень хорошо было бы увидеть решение с одной "дыркой".

[Nataly-Mak]

Пока все потенциальные помощники думают и решают
покажу работу программы whitefox (надеюсь, он не будет в претензии):



В программе работает генератор primesieve. Как это реализовано - вопросы к whitefox.
Я знаю следующее: в интервале длины $2 \cdot 10^9$, начиная с заданной начальной точки, которая задаётся произвольно и вводится в программу из файла start.txt, генерируются все простые числа. Затем выполняется процедура проверки построения квадрата Стенли 5-го порядка из сгенерированных простых. Далее снова генерация простых - в следующем интервале такой же длины. И всё повторяется.

В окне программы вы видите рабочий момент, выводится текущий интервал, в котором выполняется генерация и проверка построения квадрата. Ещё выводится количество всех массивов из 25 последовательных чисел в текущем интервале и количество подходящих массивов. Интересная закономерность наблюдается: отношение вторых к первым примерно 1:5.
Ну, и время работы программы видим на экране.
Ах да, скорость проверки в миллиардах/час.

Генерация простых в интервалах указанной длины в текущем моменте выполняется примерно 2 секунды, а вот проверка построения квадрата примерно 1 мин 22 сек. Вот такое соотношение явно не в пользу проверки построения квадрата; очень тормозится весь процесс этой проверкой.

[Progger]

Сделал возможность распределённого поиска и запустил поиск квадратов Стенли $4 \times 4$ на 22 ядрах (клиент однопоточный, я запустил 22 экземпляра). За ~12 часов удалось проверить до $2.4 \cdot 10^{14}$. Первые числа найденных квадратов можно посмотреть тут.
Если там ничего не пропущено, то можно запустить для поиска квадратов $5 \times 5$, но я могу искать на таком количестве компов разве что по выходным. Может у кого если лишний суперкомпьютер или кластер?

[Alexu007]

Nataly-Mak в сообщении #903782 писал(а):

Пока все
Генерация простых в интервалах указанной длины в текущем моменте выполняется примерно 2 секунды, а вот проверка построения квадрата примерно 1 мин 22 сек. Вот такое соотношение явно не в пользу проверки построения квадрата; очень тормозится весь процесс этой проверкой.

Максимум, что я смог выжать из решета Эрастофена - это построение до 1 миллиарда (50 млн простых чисел) за 6 минут. Если ваш товарищ написал программу, которая может генерировать простые числа с произвольной точки, и перебирает миллиард значений за 2 секунды - это результат!!! Вряд ли он налажал что-либо в процедурах построения квадрата, чтобы можно было улучшить.

[Nataly-Mak]

Progger в сообщении #904931 писал(а):

Сделал возможность распределённого поиска и запустил поиск квадратов Стенли $4 \times 4$ на 22 ядрах (клиент однопоточный, я запустил 22 экземпляра). За ~12 часов удалось проверить до $2.4 \cdot 10^{14}$. Первые числа найденных квадратов можно посмотреть тут.

Progger
Посмотрела ваши решения. Отличный результат!
Проанализировала. Из решений Jens K Andersen ничего не пропущено:

Цитата:

The first squares for n=4 start at 136367186951, 399926078933, 501929799281,
809511139667, 1038209011757, 1502332658587, 2351122716457, 2401736073493.

http://www.primepuzzles.net/puzzles/puzz_731.htm

У вас есть все эти решения:

136367186951
399926078933
501929799281
809511139667
1038209011757
1502332658587
2351122716457
2401736073493

Далее:

2746843352863 … 99867388471619 

В этой группе решений проверено Dmitry40 на ассоциативные квадраты Стенли. Таких не найдено.

В следующей группе maxal нашёл наименьший ассоциативный квадрат Стенли, он у вас тоже есть.

100457181427909 … 170693941183817

В этой группе также была выполнена проверка Dmitry40 на ассоциативный квадрат Стенли. Нашёлся тот же самый, что и у maxal.

Наконец, последняя группа решений:

173406001149833 … 237336951057847

Эту группу проверю на ассоциативный квадрат Стенли. Вдруг здесь есть второй квадрат, следующий за квадратом maxal.

Если говорить о скорости...
maxal писал мне, что у него программа работала в 40 потоков круглосуточно.
При этом он искал наименьший ассоциативный квадрат Стенли 4-го порядка несколько дней. Вы же нашли его за 12 часов. К тому же, вы искали не только ассоциативные квадраты, а все. Если бы искали только ассоциативные квадраты, нашли бы первое решение менее чем за 12 часов.
Это очень сильно говорит в пользу генератора primesieve

Можете запускать поиск квадрата Стенли 5-го порядка.
Учтите, что запускать надо как минимум с $10^{12}$, так как в этом интервале решений точно нет, проверно maxal и мной.
Если же не дублировать то, что уже проверено maxal, то запускать надо с последнего выложенного им в теме "Магические квадраты" набора, прошедшего предпроверку его программой:

531511414105079: 0 18 30 42 48 90 102 132 144 150 182 200 212 272 282 290 302 314 332 338 422 440 464 470 524

Однако окончательную проверку этот набор не прошёл, то есть квадрат Стенли 5-го порядка из чисел этого набора не составился.

P.S. Вы можете отправить ваши решения в головоломку, в дополнение к решениям Jens K Andersen.

[Nataly-Mak]

Nataly-Mak в сообщении #904977 писал(а):

Наконец, последняя группа решений:

173406001149833 … 237336951057847

Эту группу проверю на ассоциативный квадрат Стенли. Вдруг здесь есть второй квадрат, следующий за квадратом maxal.

Проверила, второй ассоциативный квадрат Стенли 4-го порядка в этой группе решений не нашёлся.

Ещё проверила один набор, просто эксперимент.

176773622692567: 0, 4, 36, 40, 70, 90, 94, 96, 106, 120, 124, 132, 160, 186, 190, 216

Добавляю в набор следующие 9 последовательных простых чисел:

176773622692567: 0, 4, 36, 40, 70, 90, 94, 96, 106, 120, 124, 132, 160, 186, 190, 216, 234, 246, 252, 274, 286, 354, 372, 406, 424

Сразу замечу, что этот набор не удовлетворяет необходимому условию: сумма чисел набора кратна 5. Я "обманула" свою программу, заменив последнее число на 422. Иначе она просто выдаёт сообщение об ошибке: сумма чисел набора не кратна 5 и ничего не составляет.

Составляю по своей программе из чисел этого набора квадрат Стенли 5-го порядка, разумеется, с "дырками":

0 36 90 120 252
4 40 94 124 256*
70 106 160 190 322*
96 132 186 216 348*
234 270* 324* 354 486*

S=902

Неправильные элементы ("дырки") помечены звёздочкой.
В этом решении очень хорошо видно подквадрат 4х4, являющийся квадратом Стенли 4-го порядка, составленным из чисел исходного набора, взятого в решениях Progger.

[Dmitriy40]

Nataly-Mak в сообщении #903782 писал(а):

Генерация простых в интервалах указанной длины в текущем моменте выполняется примерно 2 секунды, а вот проверка построения квадрата примерно 1 мин 22 сек. Вот такое соотношение явно не в пользу проверки построения квадрата; очень тормозится весь процесс этой проверкой.

Что-то времена не совпадают, в окне указана скорость 85млрд/ч, это вовсе не 1м22с, это 42с.
Если предположить что время в 2с указано верно, а проверка квадрата (или общее время) 42с, то генерация простых чисел занимает менее 5% времени. И даже если бы генерация простых чисел была бесконечно быстрой, то скорость увеличилась бы не более чем на 5%, с 85 до 89 млрд/ч. А с моим генератором простых, скорость была бы около 6с на простые и 42с на квадрат, итого 75млрд/ч.
Вот не вижу я принципиальной разницы между 75 и 89, меньше 20%. Так что ИМХО скорость генератора тут пока что вторична, ускорять/оптимизировать надо проверку на квадрат.

Alexu007 в сообщении #904965 писал(а):

Максимум, что я смог выжать из решета Эрастофена - это построение до 1 миллиарда (50 млн простых чисел) за 6 минут.

Вероятно Вы не учли следующие вещи: 1) не нужно (да и невозможно для больших интервалов) вычислять и хранить весь массив проверяемых чисел, надо поделить его на кусочки и обрабатывать их последовательно; 2) кусочки очень желательно брать размером не более размера кэша каждого ядра процессора (32кБ L1 или 256кБ L2); 3) не нужно делать взятие остатков для каждого кусочка, достаточно лишь один раз; 4) очевидное, но иногда не учитывают для простоты программы - не нужно проверять чётные числа, да и делящиеся на 3 (и на 5, 7, 11, 13, ...) тоже.
П.1 ускорения вычислений не даёт, только уменьшает требования к памяти и позволяет начать вычисления с произвольного числа; п.2 ускоряет в три-пять раз; п.3 ускоряет раз в 7; п.4 ускоряет в два раза (при исключении проверок чётных), при исключении и 3 - в три раза, при исключении и 5 - в 3.7 раза, при исключении и 7 - в 4.4 раза, дальнейшие исключения ускоряют уже не сильно и всё меньше и меньше, а сложность программы и требования к памяти быстро растут. Вот в сумме они и дадут скорость не 6 минут, а секунд 5-10. За 2с (точнее первый миллиард вообще меньше секунды, 2с это для 387-го миллиарда) primeseive вычисляет т.к. кроме указанных оптимизаций там сделано и ещё много других.
Чисто для сравнения, мой генератор (дельфи плюс асм) обрабатывает первый миллиард за 6с (primeseive за 0.9с), 2 миллиарда начиная с 387-го за 13с (primeseive за 3c). Асм даёт выигрыш всего процентов 15.

PS. Кстати, чтение документации к primeseive выявило что она не поддерживает более двух ядер для вычислений и при использовании двух не гарантирует выдачу простых чисел последовательно! Т.е. в выдаче простые могут быть и перемешаны. А это сильно затруднит его использование для квадратов/кубов. Пробовал на нескольких интервалах получить такой перемешанный вывод - не удалось, то ли он сильно редко может быть, то ли я вообще неправильно понял документацию. Интересно, те кто использует primeseive озадачились проверкой на корректность выдачи primeseive? Или используют её исключительно в однопоточном режиме?

[Nataly-Mak]

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

Nataly-Mak в сообщении #903782 писал(а):

Генерация простых в интервалах указанной длины в текущем моменте выполняется примерно 2 секунды, а вот проверка построения квадрата примерно 1 мин 22 сек. Вот такое соотношение явно не в пользу проверки построения квадрата; очень тормозится весь процесс этой проверкой.

Что-то времена не совпадают, в окне указана скорость 85млрд/ч, это вовсе не 1м22с, это 42с.

Dmitriy40
вы, как всегда, с ходу, не разобравшись (не в первый раз с вами такое)

Что вы понимаете под скорость 85 млрд/час?
Это сколько всего натуральных чисел будет проверено за час. Эта скорость, понятно, будет плавать. Всё зависит от выбранного интервала (у меня она изменялась постоянно, то 85 млрд/час, то 90 млрд/час и т.п., то есть в каждом интервале длины 2 млрд. эта скорость разная).
А время 1 мин 22 секунды - это время, потраченное программой на проверку всех подходящих наборов из 25 последовательных простых в интервале длины 2 млрд. Я смотрела это время по выводу на экран; ну, могла ошибиться на 2 секунды (время выводится каждые 2 секунды).
Со временем генерации простых в одном интервале длины 2 млрд. тоже могла ошибиться на 1-2 секунды, но это никак не больше 4 секунд для примера, показанного в окне.
Так что, всё у меня со временем правильно, с учётом допустимой погрешности в 2 секунды.

Вы сколько шли до первого ассоциативного квадрата Стенли 4-го порядка (ну, когда искали КПППЧ)? Несколько дней. Так?
А посмотрите, за сколько его нашёл Progger. Меньше 12 часов!

Так что, не надо говорить, что скорость генератора тут не играет никакой роли. Ещё как играет!
maxal тоже искал квадрат 4-го порядка несколько дней. Это при 40 потоках и при круглосуточной работе.

При этом вряд ли у всех троих сильно отличается алгоритм проверки построения квадрата Стенли 4-го порядка. Кстати, вы проверку построения квадрата вообще не выполняли (это делала я), а просто искали подходящие наборы из 16 последовательных простых (КПППЧ).

Делайте правильный вывод. Я его уже сделала.

[Progger]

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

PS. Кстати, чтение документации к primeseive выявило что она не поддерживает более двух ядер для вычислений и при использовании двух не гарантирует выдачу простых чисел последовательно! Т.е. в выдаче простые могут быть и перемешаны. А это сильно затруднит его использование для квадратов/кубов. Пробовал на нескольких интервалах получить такой перемешанный вывод - не удалось, то ли он сильно редко может быть, то ли я вообще неправильно понял документацию. Интересно, те кто использует primeseive озадачились проверкой на корректность выдачи primeseive? Или используют её исключительно в однопоточном режиме?

Я тоже это прочитал и решил не рисковать с многопоточностью. Вместо этого сделал клиент-серверную систему, клиенты которой работают однопоточно, просто я их несколько штук запускаю.

-- 07.09.2014, 21:48 --

Nataly-Mak в сообщении #905133 писал(а):

Так что, не надо говорить, что скорость генератора тут не играет никакой роли. Ещё как играет!
maxal тоже искал квадрат 4-го порядка несколько дней. Это при 40 потоках и при круглосуточной работе.

40 потоков - это было 40 реальных ядер? На чём это поиск выполнялся?

[Nataly-Mak]

Ага, у whitefox тоже программа работает в один поток; он писал мне, что primesieve при генерации простых чисел (когда они генерируются, а не просто подсчитывается их количество) не допускает многопоточность.
Да и не надо! Скорость генерации у этого генератора и в один поток фантастическая!

-- Вс сен 07, 2014 18:52:01 --

Progger в сообщении #905137 писал(а):

40 потоков - это было 40 реальных ядер? На чём это поиск выполнялся?

Он писал мне в личной переписке, что поиск выполняет на современном железе в 40 потоков. Подробности я не знаю. Можно спросить у него.