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
10142
Россия, Москва
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
10142
Россия, Москва
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
206
Обновил решения для квадратов 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
10142
Россия, Москва
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
Саратов
Запустила снова свою программу, пытаюсь найти решение с четырьмя правильными рядами.
Почти получается - один элемент в последнем ряду неправильный:

Код:
* Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  * Potential scam. Censored *  63905273

* Potential scam. Censored *  63905021  x  63905081
* Potential scam. Censored *  63905077  x  63905137
* Potential scam. Censored *  63905059  x  63905119
* Potential scam. Censored *  63905161  x  63905221
* Potential scam. Censored *  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
206
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 "дырками" (показан был выше):

Код:
* Potential scam. Censored *  63905021  x  63905081
* Potential scam. Censored *  63905077  x  63905137
* Potential scam. Censored *  63905059  x  63905119
* Potential scam. Censored *  63905161  x  63905221
* Potential scam. Censored *  63905239  x  x
S =  319525643

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

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

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

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


11/01/06
5605
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  След.

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



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

Сейчас этот форум просматривают: TheRuinedMap


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

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