2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 47  След.
 
 Re: Модифицировать программу (практическая помощь)
Сообщение07.09.2014, 18:01 
Заслуженный участник


20/08/14
8576
Россия, Москва
Nataly-Mak в сообщении #905133 писал(а):
Dmitriy40 в сообщении #905128 писал(а):
Nataly-Mak в сообщении #903782 писал(а):
Генерация простых в интервалах указанной длины в текущем моменте выполняется примерно 2 секунды, а вот проверка построения квадрата примерно 1 мин 22 сек. Вот такое соотношение явно не в пользу проверки построения квадрата; очень тормозится весь процесс этой проверкой.
Что-то времена не совпадают, в окне указана скорость 85млрд/ч, это вовсе не 1м22с, это 42с.
Dmitriy40
вы, как всегда, с ходу, не разобравшись :D
Да, тут я промахнулся, не заметил что 1м22с для двух миллиардов, а 85млрд/ч для одного, тогда вопрос снимается, всё понятно.

Nataly-Mak в сообщении #905133 писал(а):
Вы сколько шли до первого ассоциативного квадрата Стенли 4-го порядка (ну, когда искали КПППЧ)? Несколько дней. Так?
А посмотрите, за сколько его нашёл Progger. Меньше 12 часов!
С тех пор программа была заметно ускорена, текущая скорость приведена мной выше. Сейчас до 240трлн мне идти дней 5. Но и потоков у меня не 22, а 5 (о чём Вы совершенно позабыли!), и все компы явно сильно постарее чем у него. На кластере из тысяч машин можно и за минуты дойти, у кого только он есть такой ...
Ну я и не отказывался что мой генератор в несколько раз тормознее primeseive.

Nataly-Mak в сообщении #905133 писал(а):
Так что, не надо говорить, что скорость генератора тут не играет никакой роли. Ещё как играет!
Играет. По Вашим же словам - не более 5% (или не более 20% для моего генератора). Вот и всё на что играет его фантастическая скорость в данной задаче. Вовсе не несколько дней против 12ч, как Вы тут намекаете. Вот в задаче поиска КПППЧ выигрыш от него действительно будет поразительным.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение07.09.2014, 18:12 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Dmitriy40 в сообщении #905141 писал(а):
Играет. По Вашим же словам - не более 5% (или не более 20% для моего генератора). Вот и всё на что играет его фантастическая скорость в данной задаче. Вовсе не несколько дней против 12ч, как Вы тут намекаете. Вот в задаче поиска КПППЧ выигрыш от него действительно будет поразительным.

Я не намекаю :lol: У меня конкретные данные, которые я сравниваю. Никаких намёков!

Именно "несколько дней" у вас и у maxal против "менее 12 часов" у Progger.
Факты - упрямая вещь. Вы что-то имеете против этих фактов?

Для квадратов 5-го порядка ещё никто не привёл никаких экспериментальных данных, кроме тех, что я получила, работая по программе whitefox.
Давайте ваши данные, будем сравнивать. А пока беспредметный разговор.

При этом замечу: никто не заставляет вас пользоваться именно генератором primesieve. Пользуйтесь своим, если считаете, что он лучше (например, допускает многопоточность).
И процедуру проверки построения квадрата Стенли 5-го порядка напишите свою, чтобы не винить никого в том, что вот проверка написана отвратительно. Кто как умеет, так и пишет. Мы стремимся найти оптимальную программу с тем, чтобы сообща найти решение поставленной задачи.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение07.09.2014, 18:22 
Заслуженный участник


20/08/14
8576
Россия, Москва
Nataly-Mak в сообщении #905144 писал(а):
Вы что-то имеете против этих фактов?
Против этих фактов - нет. Против Вашей интерпретации их - да.
Собственно я с Вами и не спорю, делайте для себя выводы какие угодно.
Я лишь высказываю свою точку зрения, что судя по приведенным Вами цифрам, скорость самого генератора простых чисел В ДАННОЙ ЗАДАЧЕ и для данной программы от whitefox - дело второе, важнее оптимизация проверки чисел на квадрат.
Что разумеется не отвергает прямой зависимости скорости от числа задействованных потоков (ядер, процессоров). Для любого генератора.
Сравнивать времена счёта для разных задач и на разном железе в абсолютных единицах (секунды, часы, дни) - ну, можно конечно, но практической пользы мало.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение07.09.2014, 18:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Dmitriy40 в сообщении #905148 писал(а):
Nataly-Mak в сообщении #905144 писал(а):
Вы что-то имеете против этих фактов?
Против этих фактов - нет. Против Вашей интерпретации их - да.

И чем же не такая у меня интерпретация?
У maxal была круглосуточная работа в 40 потоков и несколько дней поиска.
У Progger были 22 запущенных экземпляра программы на 22-ядерном процессоре. И менее 12 часов поиска.
Вас уже не привожу :lol:
Так в чём ущербность моей интерпретации?

Цитата:
Я лишь высказываю свою точку зрения, что судя по приведенным Вами цифрам, скорость самого генератора простых чисел В ДАННОЙ ЗАДАЧЕ и для данной программы от whitefox - дело второе, важнее оптимизация проверки чисел на квадрат.

Нет, не второе, а первое!
У меня есть аналогичная программа whitefox для поиска ассоциативных квадратов Стенли 4-го порядка. Так вот, в этой программе тормозом является, в первую очередь, генератор простых. Он работает раз в 30 медленнее генератора primesieve. В интервале такой же длины 2 млрд он генерирует простые числа примерно 90 сек. (конечно, это для очень больших простых чисел, а не с самого начала натурального ряда).
Вот и сравнивайте! Пока ещё до проверки построения квадрата не дошли, застряли на генерации простых.

Цитата:
Сравнивать времена счёта для разных задач и на разном железе в абсолютных единицах (секунды, часы, дни) - ну, можно конечно, но практической пользы мало.

А вот этого никто и не делает. Сравниваются данные для одной задачи (поиск ассоциативного квадрата Стенли 4-го порядка), а не для разных!

Всё, я прекращаю беспредметный разговор.

-- Вс сен 07, 2014 19:55:44 --

Кстати, в теме "Магические квадраты"
svb выложил свою программу поиска.
Было бы неполохо, если бы он привёл пример поиска квадрата 5-го порядка в некотором интервале.
Или кто-то из форумчан опробовал бы его программу.

У меня процессор полностью загружен (два ядра), работает программа whitefox и моя программа (поиск ассоциативного куба 4-го порядка). Больше пока ничего не могу выполнять.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение07.09.2014, 19:20 


27/08/14
181
Обновил решения для квадратов 4-го порядка до $4.6 \cdot 10^{14}$
Для квадратов 5-го порядка добрался до $1.2 \cdot 10^{13}$, решений пока нет.
По поводу скорости работы. Для сборки использовался компилятор gcc-4.9 с опцией -O3. Измерялось на ноуте с поцессором Intel(R) Core(TM)2 Duo CPU T6600 @ 2.20GHz. Генерация простых чисел в диапазоне $0..10^{10}$ занимает 5.82 сек. Вместе с поиском квадрата 4-го порядка - 45.23 сек, 5-го порядка - 154.08 сек. Видно, что большую часть времени занимает процедура проверки, что позволяет надеяться на значительное ускорение работы за счёт улучшения алгоритма проверки.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение07.09.2014, 19:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Progger в сообщении #905172 писал(а):
Обновил решения для квадратов 4-го порядка до $4.6 \cdot 10^{14}$

Пока не посмотрела новые решения. Сразу вопрос: вы ассоциативный квадрат Стенли не ищете? Попробуйте! Обычные уже не представляют интереса. А вот ассоциативные интересны! Интересно найти второй квадрат, следующий за наименьшим, найденным maxal. Будет ли вторым квадрат Jarek, или между этими двумя решениями всё же существует ещё один квадрат :?:

Цитата:
Для квадратов 5-го порядка добрался до $1.2 \cdot 10^{13}$, решений пока нет.

Здесь очень хотелось бы видеть решения с "дырками".
maxal такие не выводит. А зря!
Вот представьте, что в том огромном интервале, который он проверил, нет ни одного решения с 1-2 "дырками". Это очень печально. Означает только то, что последовательные простые очень плохо складываются в квадрат Стенли 5-го порядка. Ну, разумеется, нельзя из этого сделать вывод, что решения вообще не существует. Просто вероятность его нахождения очень мала.

Ещё раз покажу лучшее приближение к решению, которое мне удалось найти по своей программе (5 "дырок", помечены звёздочкой):

Код:
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
30 34 46 90 100
38* 42* 54 98* 108*
S=248

Решение с 4 "дырками" я не видела, не говоря уже об 1-2 "дырках".

-- Вс сен 07, 2014 21:12:56 --

Progger
для поиска ассоциативного квадрата Стенли 4-го порядка вам можно просто вставить в программу проверку каждого найденного решения на симметричность набора.
Например, вот ваше решение (обычный квадрат Стенли 4-го порядка):

Код:
173422250429287
{0, 54, 60, 82, 112, 132, 136, 142, 144, 166, 172, 186, 192, 226, 256, 276}

Так вот, для ассоциативного квадрата нужно, чтобы набор был симметричным, то есть состоял из комплементарных пар чисел (это и есть термин КПППЧ - Комплементарные Пары Последовательных Простых Чисел, введённый мной в теме на форуме ПЕН).
Очевидно, что в приведённом решении набор не состоит из комплементарных пар.

-- Вс сен 07, 2014 21:19:20 --

А это набор в решении, найденном maxal (ассоциативный квадрат Стенли из этого набора составлен):

Код:
170693941183817: 0, 30, 42, 44, 72, 74, 86, 90, 116, 120, 132, 134, 162, 164, 176, 206

Комплементарные пары:

Код:
(0, 206), (30, 176), (42, 164), ..., (90, 116)

Сумма чисел в каждой комплементарной паре равна одному и тому же значению - 206, называемому константой комплементарности набора.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 08:22 
Заслуженный участник


20/08/14
8576
Россия, Москва
Nataly-Mak в сообщении #905156 писал(а):
Кстати, в теме "Магические квадраты" svb выложил свою программу поиска.
Смотрел я эту его программу. В плане генерации простых чисел там простейшее решето Эрастофена, вообще без оптимизаций - работать будет медленно. Тестовый запуск с рекомендованными параметрами (4-й порядок, Nmin=2746843300000) это подтверждает: 56с на генерацию чисел в полумиллиарде.
Проверку чисел на квадрат не изучал. По отчёту программы она заняла 8с.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 08:52 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Dmitriy40 в сообщении #905366 писал(а):
Проверку чисел на квадрат не изучал. По отчёту программы она заняла 8с.

Получается, что у него проверка длится гораздо меньше генерации. Так? Вот вам и конкретный пример, когда торомозом является именно генератор простых, а не проверка построения квадрата Стенли.
А неполные решения (с "дырками") выводятся? Можно на них глянуть? Ну, хотя бы 4 правильных ряда (строки) квадрата Стенли 5-го порядка. Я такого ещё не видела.

P.S. Хотя... тестовый пример для квадратов Стенли 4-го порядка. Мало интересно.
Надо протестировать программу для квадратов Стенли 5-го порядка. Понятно, что проверка построения квадрата 4-го порядка выполняется намного быстрее, нежели 5-го порядка.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 11:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Progger
не поленилась проверить ваши новые решения для квадратов Стенли 4-го порядка на ассоциативность.
Проверяла с помощью WolframAlpha, вот такой код:

Код:
Select[Range[0,550],PrimeQ[239673033479947+#]&]

Очень нудно, конечно.
Вот несколько первых решений, первые 16 чисел набора отделены точкой с запятой:

(Оффтоп)

Код:
239673033479947
{0, 60, 70, 106, 130, 156, 166, 216, 306, 376, 390, 412, 460, 462, 496, 546}

239963642254279
{0, 40, 58, 84, 100, 114, 124, 142, 154, 172, 180, 184, 214, 220, 238, 280, 292;   294, 334, 340, 342, 364, 370, 402, 448, 454, 520, 522, 528}

240595049548039
{0, 18, 30, 40, 42, 58, 60, 70, 72, 112, 130, 132, 142, 172, 174, 244;   270, 352, 378, 394, 442, 454, 480, 550}

240811483752157
{0, 6, 24, 30, 42, 66, 70, 76, 112, 114, 120, 156, 216, 240, 286, 330;   352, 372, 390, 412, 432, 454, 486, 526}

240836730935299
{0, 22, 28, 42, 72, 94, 100, 114, 132, 154, 160, 174, 192, 214, 220, 234;   244, 270, 288, 352, 382, 400, 430, 472, 538}

243193769376941
{0, 6, 12, 18, 42, 48, 96, 108, 110, 116, 120, 132, 138, 162, 206, 230;   258, 276, 300, 336, 372, 390, 416, 432, 446, 456, 458,
468, 476, 482}

248297207412103
{0, 10, 66, 76, 90, 100, 150, 160, 168, 220, 234, 258, 286, 310, 318, 370;   436, 454, 460, 498, 510}

249135459607637
{0, 36, 114, 120, 126, 144, 150, 162, 180, 234, 236, 246, 264, 350, 362, 380;   422, 462, 474, 516, 536}

250464450343213
{0, 54, 64, 100, 156, 210, 220, 256, 276, 294, 330, 340, 348, 358, 376, 394;   430, 486, 504, 514, 546}

251173542166871
{0, 8, 48, 62, 78, 86, 126, 140, 198, 206, 210, 218, 246, 258, 260, 272; 366, 396, 408, 462, 500}

251830168030433
{0, 6, 14, 24, 84, 90, 98, 108, 144, 150, 158, 168, 174, 180, 188, 198;   236, 240, 278, 444, 458}

252168965459623
{0, 18, 108, 114, 130, 148, 238, 244, 300, 318, 370, 388, 408, 414, 478, 484;   496, 510, 534, 550}

252875434344133
{0, 54, 154, 160, 174, 186, 208, 210, 214, 228, 340, 346, 360, 364, 370, 384;   396, 420, 430, 454, 514}

256235040648781
{0, 6, 36, 60, 90, 96, 126, 132, 138, 150, 168, 192, 280, 286, 316, 340;   376, 438, 480, 490, 528, 550}

256565661204763
{0, 4, 18, 58, 66, 70, 84, 96, 100, 114, 124, 126, 130, 144, 154, 184;   210, 330, 358, 378, 390, 430, 460, 484, 516, 520, 550}

Уже в самом конце интересное решение попалось, думала, что даст ассоциативный квадрат, но увы...

Код:
435559187294989
{0, 18, 24, 42, 70, 88, 90, 94, 108, 112, 114, 132, 220, 238, 244, 262;   322, 354, 358, 378, 400, 420, 442, 448, 454, 480, 492, 552}

Начала проверять:

$0+262=18+244=24+238=42+220=262$

А дальше уже не такая сумма в парах, хотя тоже одинаковая:

$70+132=88+114=90+112=94+108=202$

Вот такой квазиассоциативный квадрат Стенли обнаружился. Интересное решение.
Я сейчас построю этот квадрат.

Проверяла на комплементарность визуально, могла что-то проглядеть.

-- Пн сен 08, 2014 12:52:56 --

Вот квадратик почти ассоциативный:

Код:
435559187294989+
0  18  24  42 
70  88  94  112
90  108  114  132 
220  238  244  262 
S=464

И достроила его до квадрата Стенли 5-го порядка:

Код:
0  18  24  42  378
70  88  94  112  448
90  108  114  132  468*
220  238  244  262  598*
244*  262*  268*  286*  622*
S=1086

7 "дырок".

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 14:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Запустила снова свою программу, пытаюсь найти решение с четырьмя правильными рядами.
Почти получается - один элемент в последнем ряду неправильный:

Код:
63904991  63905021  63905029  63905033  63905047  63905059  63905071  63905077  63905081  63905087  63905089  63905119  63905129  63905131  63905137  63905147  63905161  63905173  63905197  63905209  63905221  63905239  63905243  63905251  63905273

63904991  63905033  63905021  x  63905081
63905047  63905089  63905077  x  63905137
63905029  63905071  63905059  x  63905119
63905131  63905173  63905161  x  63905221
63905209  63905251  63905239  x  x
S =  319525643

Это пока максимум, что удаётся получить. Ещё покручу программу. У меня программа не нормализует наборы. Надо вставить нормализацию, удобнее будет смотреть решения.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 17:01 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Добралась всё же до программы svb. Решила опопробовать.
Начала с $135 \cdot 10^6$, по своей программе в этом интервале (начиная с 3) не нашла ни одного решения с 4 правильными рядами.
Вот отчёт программы svb, начало и конец, я чуть-чуть покрутила:

Код:
5: 135000000..634999999
Sieve time: 5.72 sec
si=23,0,0
Searching time: 7.70 sec
number=25408347
. . . . . . . . . . .
5: 13635000000..14134999999
Sieve time: 6.76 sec
si=218,0,0
Searching time: 6.57 sec
number=625570628
Time: 374.96 sec

Насколько понимаю, здесь тоже не найдено ни одного решения с 4 правильными рядами.

Чем больше числа, тем ещё хуже:

Код:
5: 673401999227921..673402499227920
Sieve time: 28.83 sec
si=0,0,0
Searching time: 4.69 sec
number=14646392
Time: 33.53 sec
. . . . . . . . . . .
5: 673405999227921..673406499227920
Sieve time: 31.66 sec
si=3,0,0
Searching time: 4.67 sec
number=131791473
Time: 315.41 sec

Программа работает медленно по сравнению с программой whitefox.
Продолжу крутить программу whitefox.

Начинаю заражаться пессимизмом Jens K Andersen и Jarek.
Пока всё очень плохо складывается. И с ростом чисел всё ухудшается, как показывает программа svb.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 18:40 


27/08/14
181
Progger в сообщении #905172 писал(а):
По поводу скорости работы. Для сборки использовался компилятор gcc-4.9 с опцией -O3. Измерялось на ноуте с поцессором Intel(R) Core(TM)2 Duo CPU T6600 @ 2.20GHz. Генерация простых чисел в диапазоне $0..10^{10}$ занимает 5.82 сек. Вместе с поиском квадрата 4-го порядка - 45.23 сек, 5-го порядка - 154.08 сек. Видно, что большую часть времени занимает процедура проверки, что позволяет надеяться на значительное ускорение работы за счёт улучшения алгоритма проверки.

Пробовал ускорить проверку и заметил замечательную вещь. Тут я подготавливаю массив для дальнейшей работы, заодно считая сумму и проверяя, что она кратна размеру квадрата:
Код:
bool prepare()
{
  first = primes[0];
  uint64_t sum = 0;
  for (size_t i = 0; i < NN; ++i)
  {
    uint64_t p = primes[i];
    arr[i] = p - first;
    sum += p;
  }
  return sum % N == 0;
}

А дальше результат этой функции никак не использую :facepalm: :
Код:
void work()
{
  prepare();
  a[1] = arr[1];
  try_b<1>();
}

Вообще сумму не надо каждый раз считать - её легко получить из предыдущей суммы. В новой версии получилось следующее время: для квадратов 4-го порядка - 31.16 сек, для квадратов 5-го порядка - 40.24 сек. Другие попытки оптимизации приводили только к увеличению времени. Последняя версия тут.
Nataly-Mak в сообщении #905179 писал(а):
Сразу вопрос: вы ассоциативный квадрат Стенли не ищете? Попробуйте! Обычные уже не представляют интереса. А вот ассоциативные интересны! Интересно найти второй квадрат, следующий за наименьшим, найденным maxal. Будет ли вторым квадрат Jarek, или между этими двумя решениями всё же существует ещё один квадрат :?:

Все решения хранятся в БД, чуть позже добавлю проверку их на ассоциативность.
Nataly-Mak в сообщении #905179 писал(а):
Здесь очень хотелось бы видеть решения с "дырками".
maxal такие не выводит. А зря!
Вот представьте, что в том огромном интервале, который он проверил, нет ни одного решения с 1-2 "дырками". Это очень печально. Означает только то, что последовательные простые очень плохо складываются в квадрат Стенли 5-го порядка. Ну, разумеется, нельзя из этого сделать вывод, что решения вообще не существует. Просто вероятность его нахождения очень мала.

Чтобы искать решения с "дырками", необходимо отключить проверку суммы на кратность и перебирать значительно больше вариантов, что сильно снизит скорость поиска.

P.S. А кто-нибудь пробовал оценить вероятность найти квадрат 5-го порядка?

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 18:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Progger в сообщении #905599 писал(а):
Чтобы искать решения с "дырками", необходимо отключить проверку суммы на кратность и перебирать значительно больше вариантов, что сильно снизит скорость поиска.

Не поняла. Зачем отключать проверку на кратность?
Вы проверяете только подходящие наборы и никакие больше!
Но вот есть момент, когда программа нашла очередной элемент (правильный!) и всё - дальше уже нет и не будет правильных элементов. Вот это решение и надо вывести.
В нём будут только найденные правильные элементы, а вместо тех, что вообще и не искались, пусть стоит любой символ (у меня программа обычно выводит нули).
Ну, понятно, что если найдено совсем мало элементов, а "дырок" много, такое решение не имеет смысла выводить. Начать надо с 5 "дырок" (что может соответствовать 4 правильным рядам в квадрате) и выводить все с 5-4-3-2-1 "дырками".

Вот пример решения с 6 "дырками" (показан был выше):

Код:
63904991  63905033  63905021  x  63905081
63905047  63905089  63905077  x  63905137
63905029  63905071  63905059  x  63905119
63905131  63905173  63905161  x  63905221
63905209  63905251  63905239  x  x
S =  319525643

Нули, выведенные программой вместо элементов, которые и не искались, я заменила на символ x.
Набор из 25 последовательных чисел здесь хороший, сумма чисел в нём кратна 5.

Цитата:
P.S. А кто-нибудь пробовал оценить вероятность найти квадрат 5-го порядка?

Хороший вопрос :-)
Я таких попыток не знаю. Вот именно для такой оценки я и хочу видеть приближения к решению, то есть решения с "дырками".
Если бы maxal искал решения с 1-2 "дырками", мы сейчас уже имели бы какую-то информацию о частоте появления таких решений (он ведь проверил уже очень большой интервал).
Пока я могу сказать только, что мои многочисленные попытки найти решение с 4 правильными рядами не увенчались успехом.
Возможно, есть другие критерии для оценки вероятности найти решение, но я таких не знаю.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение08.09.2014, 23:42 
Модератор
Аватара пользователя


11/01/06
5532
Progger в сообщении #905137 писал(а):
40 потоков - это было 40 реальных ядер? На чём это поиск выполнялся?


На Dell Precision T7610. Но, похоже, моя проверка хоть и круто выглядит в теории, на практике проигрывает вашему поиску с возвратом (если я правильно понял). Как бы там Nataly-Mak не катила бочку на генератор простых, его вклад здесь минимален по сравнению с затратами на проверку/построение квадрата.
Впрочем, генераторы вчистую можно оттестировать, например, на вычислении членов A046731.

-- Mon Sep 08, 2014 15:46:12 --

Dmitriy40 в сообщении #905148 писал(а):
Я лишь высказываю свою точку зрения, что судя по приведенным Вами цифрам, скорость самого генератора простых чисел В ДАННОЙ ЗАДАЧЕ и для данной программы от whitefox - дело второе, важнее оптимизация проверки чисел на квадрат.

Поддерживаю :-)

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение09.09.2014, 00:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
maxal в сообщении #905712 писал(а):
Впрочем, генераторы вчистую можно оттестировать, например, на вычислении членов A046731.

Вот и оттестируйте! И увидите, что ваш генератор тоже проигрывает генератору primesieve в разы.

whitefox, к примеру, уже оттестировал. И написал мне, что только генерация (без проверки построения квадрата) показывает на его компьютере скорость 1,5 трлн в час.

[Разумеется, при такой скорости генератора становится тормозом проверка построения квадрата.]

Dmitriy40 в сообщении #905141 писал(а):
Ну я и не отказывался что мой генератор в несколько раз тормознее primeseive.

Я опробовала генераторы ещё двоих коллег: svb и whitefox. Оба они медленнее primeseive в несколько раз.

Очень здорово сомневаюсь, что вся разница в поиске ассоциативного квадрата Стенли 4-го порядка ложится только на проверку построения квадрата, а работа генератора простых тут ни при чём.
Все трое, искавшие этот квадрат, наверняка имели идентичный алгоритм проверки построения этого квадрата (правда, Dmitry40 его вообще никак не искал, а искал только потенциальные наборы из 16 последовательных простых, а проверку выполняла я).
Есть ещё и четвёртый - whitefox, по программе которого я тоже искала этот квадрат. И он сам признал в личной переписке, что в этой программе тормозом был генератор, а не проверка построения квадрата.

А разница во времени поиска поразительная.

Dmitry40 тоже опробовал программу svb и написал же (!), что генератор в программе работает очень медленно. Так разве это не будет тормозить весь процесс (не говоря пока о проверке построения квадрата)??

maxal
о том, что в алгоритме "перебор с возвратом" не нужны никакие предпроверки, я писала с самого начала в теме "Магические квадраты". Потом повторила ещё раз, когда вы написали, что ищете квадрат Стенли (а не сразу пандиагональный квадрат).

-- Вт сен 09, 2014 01:26:18 --

Не понимаю, как можно отрицать очевидный факт (и называть это "катить бочку").

Возьмите два генератора:
1. генератор svb
2. генератор primesieve

При этом процедуру проверки построения квадрата в обе программы вставьте от Progger.

maxal
ответьте, пожалуйста, на вопрос: какая из этих двух программ будет работать быстрее на одном и том же компьютере :?:

И при чём тут "бочка"?
Я вам давно предлагала использовать генератор primesieve, как очень быстрый. Вы ответили, что вас вполне устраивает ваш генератор. Ну, устраивает и чудесно.

-- Вт сен 09, 2014 01:38:59 --

maxal в сообщении #905712 писал(а):
Dmitriy40 в сообщении #905148 писал(а):
Я лишь высказываю свою точку зрения, что судя по приведенным Вами цифрам, скорость самого генератора простых чисел В ДАННОЙ ЗАДАЧЕ и для данной программы от whitefox - дело второе, важнее оптимизация проверки чисел на квадрат.

Поддерживаю :-)

Что же именно вы поддерживаете?
Здесь сказано, что "судя по приведённым Вами цифрам" для программы от whitefox ...
Ну, да, в этой программе уже используется генератор primesieve.
И именно ПОЭТОМУ "скорость самого генератора" уже не является тормозом! И теперь уже "важнее оптимизация проверки чисел на квадрат".

Какая же именно точка зрения тут высказывается, которую вы ещё и поддерживаете? :lol:

P.S. Вот вам и ещё цифры: в программе от whitefox для поиска ассоциативного квадрата Стенли 4-го порядка работал его собственный генератор. В том же самом интервале длины 2 млрд его генератор генерировал простые примерно 90 сек (для больших чисел). Генератор primesieve это делает в таком же интервале примерно 3 сек.
Сравнивать умеете? :wink:
(всё это на одном и том же компьютере - на моём)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 695 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 47  След.

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



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

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


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

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