2014 dxdy logo

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

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




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


22/03/08

7154
Саратов
Работает программа whitefox

Изображение

Генерация простых в интервале длины 2 млрд не более 4 сек, проверка построения квадрата - минута с хвостиком.

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


11/01/06
5660
Nataly-Mak в сообщении #905731 писал(а):
Генерация простых в интервале длины 2 млрд не более 4 сек, проверка построения квадрата - минута с хвостиком.

Что и требовалось доказать: при нормальном генераторе (будь то primesieve или что-то еще) основная вычислительная нагрузка ложиться на построение квадрата.

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


24/05/09

2054
2 млрд за 4 секунды на обычном компьютере (у меня шустрый ноутбук) - это реально? Пустой цикл из 2-х миллиардов, который ничего не делает - дольше выполняться будет...

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


22/03/08

7154
Саратов
maxal в сообщении #905739 писал(а):
Nataly-Mak в сообщении #905731 писал(а):
Генерация простых в интервале длины 2 млрд не более 4 сек, проверка построения квадрата - минута с хвостиком.

Что и требовалось доказать: при нормальном генераторе (будь то primesieve или что-то еще) основная вычислительная нагрузка ложиться на построение квадрата.

Дуб да мочало - начинай сначала :lol:

Вы сначала докажите, что у вас нормальный генератор.
В чём я очень сильно сомневаюсь, судя по времени, которое вы затратили на поиск ассоциативного квадрата Стенли 4-го порядка. Что у вас в этом поиске с алгоритмом построения квадрата было не так, как у Progger, например?? Или у whitefox.

Вы уже оттестировали свой генератор? Результаты теста в студию! :wink:

И вы не ответили на мой вопрос: какая из двух программ - с генератором svb или с генератором primesieve при одинаковой процедуре проверки построения квадрата - будет работать быстрее :?:

-- Вт сен 09, 2014 08:51:27 --

Alexu007 в сообщении #905748 писал(а):
2 млрд за 4 секунды на обычном компьютере (у меня шустрый ноутбук) - это реально? Пустой цикл из 2-х миллиардов, который ничего не делает - дольше выполняться будет...

Alexu007
вы тему читаете?

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 сек.

Прочитайте, цитату, пожалуйста.
Вам подчеркнуть "генерация простых чисел в диапазоне $0..10^{10}$ занимает 5.82 сек" или сами найдёте?

У меня компьютер не шустрый, даже тихоход.
Программа whitefox, как я уже писала, выводит на экран время каждые две секунды. Так вот, генерация длится два таких вывода времени - раз: 2 секунды, два - ещё 2 секунды. И сразу же начинается процедура проверки построения квадрата, пишется слово "Проверено". При генерации простых чисел на экране пишется слово "Просеяно".

Цитата:
Видно, что большую часть времени занимает процедура проверки, что позволяет надеяться на значительное ускорение работы за счёт улучшения алгоритма проверки.

maxal
ещё раз не пишите "что и требовалось доказать", ладно? :D
Вот именно: это и доказывает, что генератор primesieve сверхскоростной, что я и пытаюсь всем здесь доказать.

Теперь перед всеми стоит задача оптимизации процедуры проверки построения квадрата Стенли 5-го порядка.
Так давайте, вместо пустых споров, займёмся решением этой задачи.

-- Вт сен 09, 2014 09:08:49 --

Alexu007
вы видите на экране в окне программы запись "Скорость 109"?
Это скорость проверки в млрд/час (натуральных чисел) для текущего интервала. Уже объясняла для Dmitry40 (что вы, похоже, тоже не читали).
Если арифметические вычисления умеете выполнять, посчитайте, сколько секунд в среднем потребуется для обработки 2 млрд натуральных чисел (сюда войдёт и генерация простых чисел и процедура проверки построения квадрата).

-- Вт сен 09, 2014 09:26:37 --

Приводила и отчёт о работе программы svb, да, видно, это вообще никто не читал.
Приведу ещё раз (интервал тот же самый, для которого у меня сейчас работает программа whitefox ):

Код:
5: 673401999227921..673402499227920
Sieve time: 28.83 sec
si=0,0,0
Searching time: 4.69 sec
number=14646392
Time: 33.53 sec

Как я понимаю: время генерации простых - 28.83 сек. (это на полмиллиарда!); время проверки построения квадрата 4.69 сек. Общее время за цикл - 33.53 сек.

Сравнивайте!

Похоже, svb хорошо справился с процедурой проверки построения квадрата - она у него выполняется в несколько раз быстрее генерации простых.

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


22/03/08

7154
Саратов
Кстати, ссылка на тему "Программа генерации КПППЧ" на форуме ПЕН:
http://e-science.ru/?q=node/145280

В теме довольно подробно написано о КПППЧ (Комплементарные Пары Последовательных Простых Чисел).
Можно найти там, что попутно надо искать.

Dmitry40 нашёл первую 22-ку (набор из 11 комплементарных пар последовательных простых чисел). Это решение внесено в OEIS - A055381. Теперь можно искать 24-ку.
Пока никто не нашёл первую 15-ку (это набор из 7 комплементарных пар последовательных простых чисел с центральным числом, которое равно половине константы комплементарности набора). Это для A055380.

Ну, и не надо забывать о наборах из 8 комплементарных пар последовательных простых, среди которых может оказаться второй ассоциативный квадрат Стенли 4-го порядка.

Написала об этой проблеме на форуме сайта своего коллеги Stefano Tognon (ice00):
http://primesmagicgames.altervista.org/ ... /#post-222
Знаю, что этот форум просматривает Jarek; хотелось бы привлечь его внимание к этой проблеме.
Ещё собираюсь написать Jens K Andersen; может быть, он захочет поучаствовать в решении этой задачи, хотя знаю, что он очень пессимистически оценил возможность её решения.

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


22/03/08

7154
Саратов
Ещё интересная задача

Цитата:
For d=5 the square with minimal index has difference 222.
Here is a square with the smaller difference 180:

Код:
13 19 43 109 139
31 37 61 127 157
41 47 71 137 167
53 59 83 149 179
67 73 97 163 193

However, the minimal difference for an admissible pattern is 156, for example for this pattern:

Код:
0 10 24 40 54
12 22 36 52 66
60 70 84 100 114
96 106 120 136 150
102 112 126 142 156

The k-tuple conjecture predicts infinitely many occurrences but finding one is infeasible

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

Как я поняла, Jens K Andersen не нашёл решение для приведённого паттерна даже в случае не последовательных простых чисел.
Это один из паттернов для квадрата Стенли 5-го порядка из различных простых чисел с минимально возможной разностью между наибольшим и наименьшим числами набора (она равна 156). Выше приведено решение с разностью 180.

P.S. Кстати, на сайте в фрагментах строк
70 84 100 114
112 126 142 156
я вижу наличие ссылок, но у меня эти ссылки не работают. Интересно, что там?

-- Вт сен 09, 2014 12:33:22 --

По поводу последней задачи привожу результаты Pavlovsky:

Pavlovsky в сообщении #343577 писал(а):
Ниже представлены пандиагональные МК 5х5 с магической суммой в диапозоне [395,481]. Для всех нечетных магических сумм больше 481 можно построить пандиагональные МК 5х5. Правда это строго не доказано.

(Оффтоп)

Код:
395 = 5 7 11 13 17 23 31 37 41 43 53 67 71 73 83 97 101 103 113 127 131 137 167 197 227
403 = 7 13 17 19 23 29 31 37 41 43 47 53 61 67 73 103 113 127 137 139 149 157 163 173 193
409 = 5 7 11 13 29 31 41 43 47 53 59 61 71 73 79 83 97 101 109 127 157 163 181 193 211
413 = 5 11 23 29 31 37 41 47 53 59 67 71 73 79 83 89 97 109 113 131 139 149 157 173 199
419 = 5 13 19 23 29 31 37 47 53 59 67 71 73 83 89 97 103 107 113 137 149 157 163 173 197
425 = 5 7 11 13 17 23 41 43 53 61 67 71 73 83 97 101 103 113 127 131 137 157 167 197 227
431 = 5 7 11 13 17 19 31 37 41 43 47 53 71 73 97 101 103 107 127 137 167 173 179 233 263
433 = 11 13 17 19 31 37 41 43 53 59 61 67 73 83 97 107 109 127 137 139 149 157 163 179 193
437 = 7 11 13 17 23 29 37 41 43 47 53 59 67 73 97 101 103 107 131 137 163 167 179 223 257
441 = 5 11 23 29 31 37 41 47 53 59 67 71 83 89 97 101 107 113 131 137 149 157 167 173 227
443 = 11 17 23 29 31 41 43 47 53 59 61 67 71 73 79 83 97 101 109 113 173 179 193 229 233
447 = 5 11 23 29 37 41 43 47 53 59 71 73 83 89 101 103 107 113 131 137 149 163 167 173 227
449 = 5 13 23 29 31 37 43 61 67 71 79 83 89 97 101 107 109 113 127 131 137 149 167 179 197
451 = 7 13 17 31 37 41 43 47 61 71 73 79 83 97 103 107 109 113 127 137 157 163 167 181 191
457 = 7 13 17 19 23 29 31 37 41 43 47 53 61 67 73 139 149 157 163 167 173 181 191 193 211
461 = 5 11 17 23 29 37 41 43 47 59 61 71 79 83 103 107 113 131 149 157 163 173 181 199 223
463 = 13 19 31 37 41 43 47 53 59 61 67 71 73 83 97 109 127 137 139 149 157 163 167 179 193
467 = 13 23 31 37 41 43 47 53 61 71 79 83 97 101 103 107 109 113 127 131 149 167 173 179 197
469 = 7 11 13 17 23 29 37 41 43 47 53 59 73 79 97 101 103 109 113 163 193 199 223 229 283
473 = 5 11 17 23 31 41 43 47 53 59 61 67 73 79 97 101 109 113 137 149 173 179 199 229 269
475 = 11 23 31 41 43 53 59 61 67 71 73 79 83 89 97 101 103 109 131 139 151 163 181 193 223
479 = 11 17 23 29 31 37 41 47 53 59 61 67 73 79 101 103 107 109 131 137 179 191 199 241 269
481 = 11 17 23 29 31 41 43 47 53 59 61 67 73 79 83 89 97 103 109 139 199 211 229 241 271
483 = 5 11 23 29 41 47 53 59 71 73 79 83 89 101 107 109 113 131 137 139 149 167 173 199 227
485 = 5 19 31 41 47 53 59 61 67 73 79 83 89 101 107 113 127 137 139 149 151 163 167 173 191
487 = 11 17 23 29 31 41 43 47 53 59 61 67 73 79 97 107 109 113 127 163 181 193 211 223 277
491 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 97 101 109 113 127 139 191 197 211 251 277
493 = 13 19 23 29 31 37 41 43 47 53 61 71 73 79 103 139 149 157 163 167 173 181 191 199 223
497 = 11 17 23 29 31 41 43 47 61 67 71 79 83 97 101 107 113 127 163 167 173 179 193 229 233
499 = 7 17 29 31 37 41 43 47 53 59 67 73 79 103 109 127 137 149 157 163 167 179 193 199 229
503 = 11 17 23 29 31 41 43 47 61 67 79 83 89 97 103 107 113 127 139 163 167 179 197 239 263
505 = 5 11 13 19 29 37 47 53 59 67 71 73 79 97 101 127 131 139 157 163 173 181 199 211 283
509 = 11 13 17 19 23 29 31 37 41 43 53 61 101 107 131 137 139 149 157 179 181 191 199 227 269
511 = 13 19 31 37 41 43 47 61 67 71 73 97 101 107 109 127 131 137 139 157 163 167 193 197 227
515 = 5 7 11 13 17 19 31 37 41 43 47 53 71 73 97 101 103 107 127 137 251 257 263 317 347
517 = 11 13 17 19 23 29 37 43 71 73 83 97 101 103 113 127 137 139 149 151 157 163 211 241 277
521 = 11 13 17 19 29 31 53 59 61 67 71 79 83 89 101 107 109 149 157 179 191 193 233 241 263
523 = 11 23 31 41 43 53 59 61 67 71 73 79 83 89 97 101 103 109 131 139 199 211 229 241 271
527 = 11 17 23 29 31 41 43 47 53 59 61 67 71 73 79 83 97 101 109 113 257 263 277 313 317
529 = 11 13 17 19 23 29 31 37 59 61 71 79 103 109 137 139 149 151 157 179 181 191 199 229 271
531 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 101 113 137 149 167 179 191 197 211 251 317
533 = 11 13 17 19 23 29 37 43 71 73 83 97 101 103 113 127 137 139 149 163 167 173 227 257 293
535 = 5 7 11 13 17 19 31 37 41 43 47 53 61 67 73 101 103 127 137 157 281 283 307 317 337
537 = 5 11 23 29 37 41 43 47 53 59 71 73 83 89 103 113 131 149 163 173 191 197 227 257 317
539 = 23 29 31 37 47 53 59 67 73 79 83 89 97 109 113 131 137 139 149 157 167 173 197 199 257
541 = 11 13 23 37 41 43 53 67 71 73 83 97 101 103 113 127 137 139 149 151 163 181 211 241 277
545 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 101 113 151 163 181 191 193 197 211 251 331
547 = 11 13 17 19 31 37 41 43 53 59 61 83 97 103 127 137 139 157 179 191 193 211 223 233 277
549 = 11 13 17 19 23 29 41 47 53 59 71 73 83 101 113 137 139 149 167 179 227 229 239 257 269
551 = 11 13 17 19 23 29 41 43 53 71 73 83 101 103 113 151 157 167 173 181 197 211 227 241 257
553 = 11 17 23 29 31 41 43 47 61 67 79 83 89 97 103 139 151 163 173 179 181 193 223 229 313
555 = 5 11 13 17 19 23 29 37 41 59 67 71 83 89 101 107 109 113 137 179 257 263 281 311 353
557 = 11 13 17 19 23 29 37 43 47 53 71 73 83 97 101 103 107 113 127 137 281 283 293 307 317
559 = 13 19 23 29 31 37 43 53 61 73 79 103 107 113 137 139 149 157 163 173 181 199 223 233 257
561 = 11 13 17 19 23 29 41 47 53 59 71 73 83 101 113 137 139 149 167 179 239 241 251 269 281
563 = 11 13 17 19 41 43 53 59 71 73 83 97 103 113 127 137 139 157 167 173 179 197 223 227 293
565 = 11 17 23 29 31 41 43 47 53 59 61 73 83 89 103 151 163 181 193 199 211 223 229 241 271
567 = 5 11 17 23 37 41 43 47 53 59 71 73 79 83 103 131 137 167 173 197 227 233 263 269 293
569 = 11 13 17 19 41 43 53 59 67 73 83 97 107 109 137 139 149 163 167 173 179 193 197 263 293
571 = 11 13 19 29 31 37 59 61 67 71 73 79 89 101 103 107 109 137 149 179 223 241 271 283 313
573 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 101 113 131 137 151 191 239 251 269 281 359
575 = 11 17 23 29 31 41 43 47 61 67 71 79 83 97 101 107 113 127 163 167 251 257 271 307 311
577 = 11 17 23 29 37 41 43 53 67 73 79 101 103 113 127 151 157 163 167 179 181 193 229 241 307
581 = 11 13 17 19 23 29 41 47 59 61 71 89 101 103 113 131 137 139 149 167 223 229 271 313 349

Решение с разность между минимальным и максимальным числом равной 180 здесь есть:

Код:
463 = 13 19 31 37 41 43 47 53 59 61 67 71 73 83 97 109 127 137 139 149 157 163 167 179 193

С разностью 156 я не нашла.
Но пандиагональных квадратов 5-го порядка из не последовательных простых чисел море. И строить их просто. А каждому такому квадрату соответствует свой квадрат Стенли (один и только один).

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


22/03/08

7154
Саратов
Нашла в старых файлах свои пандиагональные квадраты 5-го порядка из простых чисел. Добавлю их к результатам Pavlovsky, хотя разности 156 у меня тоже нет, все разности больши-и-и-е:

(Оффтоп)

Код:
3  271  193  31  109
157  13  107  233  97
337  59  61  139  11
43  137  241  163  23
67  127  5  41  367
S= 607

5  131  379  23  73
359  13  71  107  61
173  37  41  349  11
31  347  113  103  17
43  83  7  29  449
S= 611

3  373  163  31  43
127  13  41  359  73
397  59  37  109  11
19  107  367  97  23
67  61  5  17  463
S= 613

3  103  337  37  139
307  13  137  89  73
223  59  43  283  11
19  281  97  193  29
67  163  5  17  367
S= 619

3  127  337  31  139
331  13  137  89  67
223  29  61  313  11
43  311  97  163  23
37  157  5  41  397
S= 637

3  103  397  31  109
367  13  107  89  67
193  53  37  349  11
19  347  97  157  23
61  127  5  17  433
S= 643

5  181  379  23  73
359  13  71  157  61
223  37  41  349  11
31  347  163  103  17
43  83  7  29  499
S= 661

5  191  379  23  73
359  13  71  167  61
233  37  41  349  11
31  347  173  103  17
43  83  7  29  509
S= 671

5  331  271  23  73
251  13  71  307  61
373  37  41  241  11
31  239  313  103  17
43  83  7  29  541
S= 703

5  397  211  23  73
191  13  71  373  61
439  37  41  181  11
31  179  379  103  17
43  83  7  29  547
S= 709

5  191  463  23  73
443  13  71  167  61
233  37  41  433  11
31  431  173  103  17
43  83  7  29  593
S= 755

5  197  463  23  73
443  13  71  173  61
239  37  41  433  11
31  431  179  103  17
43  83  7  29  599
S= 761

5  107  463  23  181
443  13  179  83  61
257  37  41  433  11
31  431  89  211  17
43  191  7  29  509
S= 779

5  251  463  23  73
443  13  71  227  61
293  37  41  433  11
31  431  233  103  17
43  83  7  29  653
S= 815

3  103  571  31  109
541  13  107  89  67
193  53  37  523  11
19  521  97  157  23
61  127  5  17  607
S= 817

3  283  397  31  109
367  13  107  269  67
373  53  37  349  11
19  347  277  157  23
61  127  5  17  613
S= 823

5  97  463  23  241
443  13  239  73  61
307  37  41  433  11
31  431  79  271  17
43  251  7  29  499
S= 829

5  107  463  23  241
443  13  239  83  61
317  37  41  433  11
31  431  89  271  17
43  251  7  29  509
S= 839

5  191  389  23  241
359  13  239  167  71
401  47  41  349  11
31  347  173  281  17
53  251  7  29  509
S= 849

5  263  379  23  181
293  13  179  227  139
401  103  53  283  11
43  281  233  277  17
109  191  7  41  503
S= 851

5  379  359  37  73
163  13  71  367  239
433  227  43  139  11
19  137  373  293  31
233  97  7  17  499
S= 853

3  103  577  31  139
541  13  137  89  73
223  59  37  523  11
19  521  97  193  23
67  157  5  17  607
S= 853

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


20/08/14
11070
Россия, Москва
Alexu007 в сообщении #905748 писал(а):
2 млрд за 4 секунды на обычном компьютере (у меня шустрый ноутбук) - это реально? Пустой цикл из 2-х миллиардов, который ничего не делает - дольше выполняться будет...
Я Вам уже отвечал ведь - post905128.html#p905128
И цикл разумеется выполняется не 2млрд, а (для 387-го миллиарда) примерно 50 тысяч раз (обрабатывая при этом все числа в диапазоне 2млрд) плюс 75млн чисел находит (т.е. второй цикл копирования 75млн чисел). И вот это выполнить за 4с вполне реально как показывает практика.

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


22/03/08

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

Код:
a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
a51 a52 a53 a54 a55

Набор из 25 чисел я выбрала такой, из чисел которого квадрат составляется:

Код:
0, 2, 6, 8, 12, 18, 26, 32, 36, 38, 48, 62, 66, 68, 78, 92, 96, 98, 108, 122, 126, 132, 162, 192, 222

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

Итак, начинаем: сразу же выполняем следующие присвоения:
Код:
a11=0, a55=222

Далее начинаем перебор 4-х элементов квадрата: a12, a13, a14, a15, при этом перебирать их надо так: $a_{12}<a_{13}<a_{14}<a_{15}$ (основываясь на свойствах квадрата Стенли).
Первая подходящая комбинация будет такой, при которой сложится последняя строка квадрата, так как все элементы этой строки сразу же вычисляются при задании элементов a12, a13, a14, a15.
Вот, например, такая подходящая комбинация для этих четырёх перебираемых элементов:

Код:
a11=6
a12=36
a13=66
a14=96

Тогда квадрат принимает вид (с полными первой и пятой строками):

Код:
0 6 36 66 96
x x x x x
x x x x x
x x x x x
126 132 162 192 222

Теперь выбрасываем из набора использованные элементы, оставшийся набор:

Код:
2, 8, 12, 18, 26, 32, 38, 48, 62, 68, 78, 92, 98, 108, 122

Опять же основываясь на свойствах квадрата Стенли, элементу a21 мы даём только одно значение - минимальное в оставшемся наборе. То есть этот элемент (как и следующие - a31 и a41) уже и не перебирается.
Итак, присваиваем: $a_{12}=2$.
Сразу вычисляем элементы второй строки. Если каждый из них принадлежит оставшемуся набору, всё хорошо - можно идти дальше. В противном случае - возврат на поиск другой подходящей комбинации элементов a12, a13, a14, a15.
[Внимание! Вот здесь и видим действие "перебора с возвратом".]

В данном примере имеем полностью хорошую вторую строку:

Код:
0 6 36 66 96
2 8 38 68 98
x x x x x
x x x x x
126 132 162 192 222

Ну, и думаю, не надо показывать, как проверить построение оставшихся двух строк квадрата - надо повторить все действия, которые выполнялись при заполнении второй строки.
Окончательное решение:

Код:
0 6 36 66 96
2 8 38 68 98
12 18 48 78 108
26 32 62 92 122
126 132 162 192 222
S=370

Таким образом, в алгоритме whitefox фактически 4 свободных переменных!
Если есть вопросы по описанию алгоритма, пожалуйста, задавайте. На что смогу, отвечу.

В примере использован наименьший квадрат Стенли 5-го порядка из не последовательных простых чисел Pavlovsky.

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #906206 писал(а):
Итак, присваиваем: $a_{12}=2$.

Прошу прощения, здесь, конечно, опечатка. Должно быть:
Итак, присваиваем: $a_{21}=2$.

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


22/03/08

7154
Саратов
Безобразие, ещё опечатка :?
Цитата:
Вот, например, такая подходящая комбинация для этих четырёх перебираемых элементов:

Код:
a11=6
a12=36
a13=66
a14=96

Правильно так:
Вот, например, такая подходящая комбинация для этих четырёх перебираемых элементов:

Код:
a12=6
a13=36
a14=66
a15=96

Ещё раз прошу прощения.

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


24/05/09

2054
Dmitriy40 в сообщении #905823 писал(а):
И цикл разумеется выполняется не 2млрд, а (для 387-го миллиарда) примерно 50 тысяч раз (обрабатывая при этом все числа в диапазоне 2млрд) плюс 75млн чисел находит (т.е. второй цикл копирования 75млн чисел). И вот это выполнить за 4с вполне реально как показывает практика.

За 10 сек выполняется поиск простых чисел до первого миллиарда (50 847 534 штук) у меня пока. Продолжаю работу по ускорению, но это имеет мало смысла, потому что:

А как вы всё таки ищете простые числа с произвольного числа? Вы объясняли, но я ничего не понял. Сам принцип решета Эрастофена в том, что его всегда с начала заполнять надо... или я чего то не понимаю.

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


20/08/14
11070
Россия, Москва
Alexu007 в сообщении #906560 писал(а):
А как вы всё таки ищете простые числа с произвольного числа? Вы объясняли, но я ничего не понял. Сам принцип решета Эрастофена в том, что его всегда с начала заполнять надо...
Я бы сказал не совсем в этом принцип, а скорее в вычёркивании всех чисел кратных известным простых числам из непрерывного массива всех чисел и в результате в массиве остаются лишь новые простые числа.
Начинать с произвольного числа можно вот почему: чтобы вычеркнуть из массива заданной длины, начинающегося с произвольного числа, все составные числа (кратные простым) достаточно иметь список всех простых чисел величиной до квадратного корня из точки конца массива. Поэтому решето модифицируем, вместо постепенного поиска простых и добавлении их к списку известных, сразу находим (ну или читаем из файла, уж как удобнее, вычислить раз в 10 быстрее) все простые числа не превосходящие \sqrt{N+size} (конец вычисляемого массива). Потом циклом по этому списку определяем смещение в массиве первого числа, кратного данному простому (остаток от деления величины начала массива на данное простое число) и начиная с него идём по массиву и вычёркиваем кратные ему числа, ну как обычно в решете. После обработки всего списка простых все составные числа в массиве вычеркнутся.
Сама идея - правильно найти это вот смещение первого кратного числа в массиве. Делается примерно так:
Используется синтаксис C
offset = N mod p[i];//N - начальное число, p[i] - простое, offset - смещение в массиве кратного ему
if (offset != 0) offset = p[i] - offset;
Вот начиная с найденного offset и вычеркиваем дальше кратные числа.

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


22/03/08

7154
Саратов
Наконец, все всё поняли :lol:
Итак, на чём мы остановились? По алгоритму поиска квадрата Стенли 5-го порядка вопросов, кажется, ни у кого нет. Это хорошо.

Вот Progger и whitefox пропали - это плохо :-(

Я пока занялась пандиагональными квадратами 8-го порядка из простых чисел (последовательных и не последовательных).

Крутить программу whitefox пока бросила. Мне нужен вывод решений с "дырками". Без этой информации крутить программу вслепую, не зная, что там вообще находится, как-то очень скучно.
А вывод решений с "дырками" сделать некому.

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


27/08/14
206
Я не совсем пропал :D . Для квадратов 4-го и 5-го порядка дошёл до $10^{15}$. Ни квадрата 5-го порядка, ни нового ассоциативного квадрата 4-го порядка там нет. Про пандиагональный квадрат 8-го порядка тему видел, но пока не придумал, как реализовать поиск с приемлемой скоростью.

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

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



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

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


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

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