Магические квадраты

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

svb в сообщении #565150 писал(а):

Для последовательных чисел нужно писать другую программу, либо скармливать программе наборы по 36 чисел.

А как вы представляете себе процесс скармливания программе наборов по 36 чисел?

Вот я сейчас как раз скармливаю... жутко интересное занятие! Представили, да? :-)

Постоянная болезнь программистов. Уж сколько раз я о ней писала!
Ни одна из двух программ не предусматривает автоматическую проверку массивов из 36 чисел. Вот у меня такимх массивов, скажем, 100 штук. И для каждого массива я должна записать его во входной файл inp.txt, затем запустить и выполнить программу.

Конечно, можно поизощряться и что-то придумать, например, написать пакетный файл что ли. И то вряд ли получится, потому что в программе svb надо каждый раз вводить параметры, она не запускается автоматом. Да и в программе alexBlack не вижу пока, как организовать конвейерную проверку n массивов по 36 чисел, потому что в ней тоже задаётся параметр (магическая константа квадрата), и массив считывается из входного файла только один и только из файла с именем a.txt.

А, нет, вроде для программы alexBlack можно написать пакетный файл. Надо подумать. Если подготовить все исходные массивы, записать их в текстовые файлы, потом из них на каждом шаге копировать массив в файл a.txt и запускать программу с этой магической константой.
Но! Программа каждый раз открывает для записи полученных результатов один и тот же выходной файл ms.txt. Кажется, опять не получится, результаты будут теряться при каждом новом выполнении программы. Уф :-(

А! Тогда после каждого выполнения программы копировать данные из файла ms.txt в другие файлы, потом в этих файлах смотреть все полученные результаты.
Так получится?

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Программа alexBlack проверяет составление из чисел Смита вида 4 (mod 9) пандиагональных квадратов 6-го порядка с магической константой 5964, начинающихся с числа 2911, ровно сутки.
Найдено три квадрата:

Код:

S = 5964
№ 1
2182 1255 319 1165 526
634 1858 265 346 1219
94 958 1507 2605 22
274 913 562 355 1282
2614 895 1678 382 4
166 85 1633 1111 2911

№ 2
1894 1642 94 454 22
166 778 562 2578 958
2362 706 1678 895 4
346 517 202 1282 1795
1111 1966 1507 121 274
85 355 1921 634 2911

№ 3
391 2362 274 4 895
85 1903 526 1111 1633
1921 346 1165 1795 202
1255 454 22 2326 265
2218 382 1822 562 58
94 517 2155 166 2911

В этой программе проверяемое число помещается в правый нижний угол квадрата (фиксированный элемент). Подробное описание алгоритма alexBlack приведено по указанной чуть выше ссылке.

Не знаю, удастся ли довести до конца этот эксперимент, вдруг опять отключат электричество :-)

У нас это частое явление.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

svb в сообщении #565465 писал(а):

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

svb
подробнее этот момент можете осветить?

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

Моё примитивное представление о распараллеливании в этой программе такое (может, совсем неверное :?:

):
у нас есть вложенные циклы, их несколько (скажем 11 вложенных циклов). Есть внешний цикл, например, переменная этого цикла изменяется от 1 до 64. Тогда мы заставляем переменную внешнего цикла изменяться от 1 до 16 в работе первого ядра процессора, от 17 до 32 в работе второго ядра и т. д. (если четырёхядерный процессор). Все остальные вложенные циклы работают одинаково во всех 4 ветках.

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

Открыла тему "Распараллеливание для многоядерных процессоров" в форуме "Программирование".

svb · 20/01/10 766 Нижний Новгород

Попробовал запустить неполный поиск при CP=4

(Оффтоп)

Для N=62(2785) найдено 5 квадратов, т.е. 1 квадрат потерян, т.к. ранее было найдено 6 квадратов при полном поиске (CP=1)

(Оффтоп)

Цитата:

А как вы представляете себе процесс скармливания программе наборов по 36 чисел?

Вот я сейчас как раз скармливаю... жутко интересное занятие! Представили, да? :-)

Постоянная болезнь программистов. Уж сколько раз я о ней писала!

Для каждого вновь поставленного вопроса необходимо писать новую программу. Ну, проверили на тестовых примерах, что программа работает неудовлетворительно, прежде всего очень медленно. Зачем же ее дальше мучить? Сейчас самая главная задача это ускорение работы программы хотя бы на порядок. Но тут нужны новые идеи.

Цитата:

svb
подробнее этот момент можете осветить?

"Программа не использует многоядерность"... А можете сделать так, чтобы использовала?

Пока не пробовал, хотя запуск 4-х программ вполне эквивалентная замена, которую можно наблюдать в диспетчере задач. На мой некомпетентный взгляд запуск независимых процедур в том же Delphi должен дать такой же эффект - это легко проверить, но я пока еще не установил на свою машину компилятор.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

svb в сообщении #569324 писал(а):

Для каждого вновь поставленного вопроса необходимо писать новую программу. Ну, проверили на тестовых примерах, что программа работает неудовлетворительно, прежде всего очень медленно. Зачем же ее дальше мучить? Сейчас самая главная задача это ускорение работы программы хотя бы на порядок. Но тут нужны новые идеи.

Вы не поняли меня. Речь идёт о проверке тех массивов из 36 чисел, для которых проверка выполняется быстро. Я проверила уже много таких массивов (это массивы из 36 последовательных простых), проверка одного массива выполняется всего несколько минут.

Для ускорения работы программы я предлгаю задействовать многоядерность процессора.

Цитата:

На мой некомпетентный взгляд запуск независимых процедур в том же Delphi должен дать такой же эффект - это легко проверить, но я пока еще не установил на свою машину компилятор.

Не понимаю:что значит "запуск независимых процедур"?
Я написала своё представление о распараллеливании всего процесса вычислений.
Запуск 4 отдельных программа (при количестве ядер 4) не даёт никакого убыстрения выполнения каждой отдельно взятой программы!

Да, можно запустить на моём компьютере сразу две программы (у меня двухядерный процессор), это я и делаю, иногда даже сразу три программы запускаю. Ну и что? Каждая программа проверяет одно число (или один массив из 36 чисел), никакого убыстрения в этой программе не происходит, так как в ней нет никакого распараллеливания.

Вот сейчас, например, у меня работает программа alexBlack (вторые сутки), запустила массив из 64 чисел, она сама выбрала для проверки число 2911, и молотит эту проверку. И всё! И никакого убыстрения, и никакого обращения ко второму ядру процессора в этой программе не происходит. Работает одно ядро, как я понимаю.

svb · 20/01/10 766 Нижний Новгород

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

Не понимаю:что значит "запуск независимых процедур"?
Я написала своё представление о распараллеливании всего процесса вычислений.
Запуск 4 отдельных программа (при количестве ядер 4) не даёт никакого убыстрения выполнения каждой отдельно взятой программы!

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

). При процедурном подходе к программированию, когда запуск очередной процедуры требовал окончания работы предыдущей процедуры, это было невозможно. Но современные компиляторы устроены чуть умнее. Находясь в среде windows мы постоянно наблюдаем параллельную работу множества процедур и нас мало интересует, реальное это распараллеливание или обман с помощью операционной системы. Специально изучать особенности этой работы нужды нет, достаточно иметь возможность запуска нескольких независимых программ (процедур). Сравните с DOS - там не было возможности запуска нескольких программ (но некоторые элементы этого были и там - мышь, клава, резиденты и т.п.)

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

В моём представлении о распараллеливании цикла меня ничего не смущает (хотя не вполне уверена, что у меня правильное представление).

Я не понимаю, о чём пишете вы. "Будет тот же эффект при запуске 4-х независимых процедур..." - так примерно я поняла ваше высказывание. Вот и непонятно, какой "тот же эффект" :-)

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

Мне известно, что alexBlack писал программы для двухядерных процессоров, у меня даже была одна такая программа. Но вот в программе для построения пандиагональных квадратов 6-го порядка он не задействовал использование нескольких ядер. По крайней мере, нигде нет указания на это.

-- Чт май 10, 2012 17:27:42 --

Программа работает 1,5 суток, найдено ещё три квадрата:

Код:

S = 5964
Квадрат № 4
166 1642 1282 94 1822
706 2218 121 562 391
778 526 895 2839 4
1678 58 517 2038 454
2362 985 1255 346 382
274 535 1894 85 2911

Квадрат № 5
382 2785 958 706 355
22 1858 274 1822 346
1165 4 121 1966 526
1903 517 2155 985 319
2038 265 1894 94 1507
454 535 562 391 2911

Квадрат № 6
2038 1255 94 454 958
913 1507 121 2182 319
1219 85 1678 2326 274
1282 778 355 202 985
346 1633 1822 535 517
166 706 1894 265 2911

До вечера программа не отработает до конца. Не буду оставлять компьютер работающим на вторую ночь, ещё часа 4 поработает программа и прерву.

Цитата:

Реализация этого алгоритма проверена на константе 5964 для чисел Смита = 4 (mod 9). Время работы на массиве из 36-ти чисел менее 10-ти секунд. Для константы 3912 полная проверка 39-ти чисел заняла 10 минут. К сожалению время проверки очень быстро растет с увеличением количества чисел в массиве. На полном массиве могу пока дать только грубую оценку времени выполнения - 40-50 часов для константы 5964.

Это пишет alexBlack на своём сайте. Думаю, что на полном массиве для константы 5964 программа будет выполняться гораздо больше 40-50 часов, даже с поправкой на мощность моего компьютера.

svb · 20/01/10 766 Нижний Новгород

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

В моём представлении о распараллеливании цикла меня ничего не смущает (хотя не вполне уверена, что у меня правильное представление).

Я не понимаю, о чём пишете вы. "Будет тот же эффект при запуске 4-х независимых процедур..." - так примерно я поняла ваше высказывание. Вот и непонятно, какой "тот же эффект" :-)

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

Когда вы запускаете 2 программы, то какой эффект вы наблюдаете? Ответ: одновременно работают 2 программы. Каждая требует некоторого времени работы. Если бы у вас было 1 ядро, то для исполнения этих 2-х программ потребовалось бы в 2 раза больше времени, сначала первая программа, потом вторая.
Тут уже я вас не понимаю, какой эффект вы наблюдаете на 2-х ядрах, разве не ускорение суммарной работы?

Вам не нравится, что сейчас при запуске одной программы не задействованы 2 ядра? Так вы же сами и написали, что нужно сделать - слегка изменить программу именно так, как вы написали. В чем сомнения? Но сейчас я это проверить не могу (хотя и не сомневаюсь), т.к. не установлен компилятор :-)

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

svb в сообщении #569470 писал(а):

Когда вы запускаете 2 программы, то какой эффект вы наблюдаете? Ответ: одновременно работают 2 программы. Каждая требует некоторого времени работы. Если бы у вас было 1 ядро, то для исполнения этих 2-х программ потребовалось бы в 2 раза больше времени, сначала первая программа, потом вторая.

Наверное, не всё так просто :-)

вот такая прямо-пропорциональная зависимость.
У меня был процессор с одним ядром, и я выполняла на нём одновременно сразу две программы. Мне кажется, что выполнение идёт не так, как вы пишете: "сначала первая программа, потом вторая" (выполнение идёт всё-таки параллельно, а не последовательно), и времени требуется не в 2 раза больше.
Почему я так думаю? Объясню.
Сейчас у меня двухядерный процессор, я запускала сразу не 2, а 3-4 программы! При запуске 4-х программ (одновременно) время работы не уменьшалось в 2 раза. Оно уменьшалось, но совсем немного.
При этом, когда у меня работают 3 программы, я свободно брожу по Интернету, а вот при работе 4-х программ это уже сильно тормозится.

(Недавно крутила программы решения конкурсной задачи, тоже всё время по 4 программы одновременно работали.)

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

Ну, и если вы не сомневаетесь в том, что в данной программе можно задействовать многоядерность процессора, это замечательно. Осталось проверить это на практике.
Я просто вообще не представляю, как это делать. Можно ли это делать на QBASIC?

-- Чт май 10, 2012 23:11:12 --

Последний найденный квадратик

Код:

S = 5964
Квадрат № 7
517 2902 319 58 202
22 1219 121 2578 1633
2461 85 1903 346 274
1507 94 526 1894 778
922 958 2182 454 166
535 706 913 634 2911

Программу прервала, до конца ещё очень много (судя по нарисованным точкам).

svb · 20/01/10 766 Нижний Новгород

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

Наверное, не всё так просто :-)

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

Именно просто. Дополнительные ресурсы кушают другие уже запущенные процессы. Вы запустите диспетчер задач, в нем все видно.

Цитата:

У меня был процессор с одним ядром, и я выполняла на нём одновременно сразу две программы. Мне кажется, что выполнение идёт не так, как вы пишете: "сначала первая программа, потом вторая" (выполнение идёт всё-таки параллельно, а не последовательно), и времени требуется не в 2 раза больше.

Это операционка создает иллюзию параллельной работы, т.е. по очереди запускает разные процессы. Но на одном ядре реально не может быть параллельной работы.

Цитата:

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

Диспетчер задач вам покажет как распределяется время процессора. Какой-нибудь Касперский или Fox может очень сильно повлиять на время исполнения вашей самой обычной программы.

Чудес не бывает и все достаточно просто - если на исполнение программы требуются некоторые ресурсы, то вы их можете дать, либо оттяпать с помощью дополнительного запуска других процессов. Но требуемый суммарный объем ресурсов останется постоянным.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Я не знаю, как запускать Диспетчер задач.

Но... тогда почему при работе 4-х программ у меня время не уменьшается в 2 раза? Оно уменьшается, но совсем чуть-чуть. А ведь в процессоре всего 2 ядра.

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

Может быть, это иллюзия параллельной работы... но уж очень хорошая иллюзия :-)

Я прямо очень чётко видела, как в одной из программ выводятся результаты как бы "впрыгивая" в некий промежуток, интервал времени, "украденного" у другой программы.
Кто это пробовал, тот согласится, что иллюзия очень классная и ... вполне правдоподобная (для параллельной работы).

Вот результат эксперимента (стр. 156):

Цитата:

То, что не работали другие программы, дало очень незначительное убыстрение; раньше было 2,85 ч., сейчас 2,81 ч., это всего около 2,5 мин.

Ещё раз: это была проверка работы программы alexBlack для константы 3774 (массив из 36 чисел). Сначала эта программа работала при ещё двух работающих программах (ваших), а потом я прогнала эту программу одну, больше ничего не работало. Время уменьшилось всего на 2,5 минуты!
Я понимаю так: одновременная работа сразу двух программ вообще не должна у меня повлиять на время выполнения каждой программы. Но в данном случае работали сразу три программы. Где процессор брал ресурсы для выполнения 3-ей программы?

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Среди квадратов, выложенных svb вчера (неполный поиск) нашла два новых квадрата, начинающихся с числа 3046 (в дополнение к найденным мной 7 квадратам, которые выложены выше):

Код:

S = 5964
Квадрат № 8
22 778 94 913 1111
706 1633 2434 535 391
1903 1219 454 85 1921
526 121 202 2515 1966
2461 1894 922 274 58
346 319 1858 1642 517
Квадрат № 9
202 94 121 1219 1282
706 2515 1678 526 454
895 265 958 1822 166
1633 634 274 922 1966
2182 22 2155 562 985
346 2434 778 913 1111

Имеем уже 9 различных квадратов. Так совместными усилиями и все найдём :-)

Сейчас ещё сравню квадраты, начинающиеся с числа 2911. У меня таких квадратов 7 штук, и у svb тоже 7 штук, есть ли различные...

Выбросила из массива число 2911 и снова запустила программу alexBlack. Теперь она начала проверку числа 2974. В массиве осталось 63 числа.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Нашла среди квадратов svb два новых квадрата, начинающихся с числа 2911:

Код:

S = 5964
Квадрат № 8
4 895 22 1219 913
1822 1795 985 382 922
634 274 2614 85 1903
1642 202 526 1111 1966
1507 1165 1255 265 94
355 1633 562 2902 166

Квадрат № 9
1111 517 85 634 706
778 2515 1678 526 202
274 166 382 2362 2326
2173 1858 22 58 895
1507 346 1642 1165 913
121 562 2155 1219 922

svb · 20/01/10 766 Нижний Новгород

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

Я не знаю, как запускать Диспетчер задач.

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

Можно нажать F1 на пустом поле, появится Центр справки и поддержки. В окне поиска наберите Диспетчер задач. Там тоже появится инструкция.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Спасибо.
Я попробовала, запустила Диспетчер задач. Сейчас у меня работает одна программа - alexBlack. Диспетчер показал, что загрузка ЦП составляет 49-50 %, память 30 %.

-- Пт май 11, 2012 21:28:18 --

Прервала программу проверки числа 2974, 16 часов работала программа, найдено 3 квадрата:

Код:

S = 5964

Квадрат № 1
913 2362 202 274 958
895 1642 454 526 1165
346 265 1822 2614 355
1678 535 58 1111 121
2038 778 1921 517 391
94 382 1507 922 2974
Квадрат № 2
2038 1894 85 922 706
913 355 634 1678 166
1219 526 1282 2578 94
562 985 958 454 391
1111 1822 778 274 1633
121 382 2227 58 2974
Квадрат № 3
2605 706 22 958 391
535 1795 4 2839 265
1633 454 1111 1822 166
355 985 634 58 1894
517 1642 2227 85 274
319 382 1966 202 2974

Завтра выброшу из массива число 2974, в массиве останется 62 числа, запущу программу, будет проверяться следующее число, какое - пока не знаю.

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

Магические квадраты

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