Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

41 Страницы«<3738394041>
Опции
К последнему сообщению К первому непрочитанному
Offline whitefox  
#761 Оставлено : 13 декабря 2018 г. 16:43:55(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 252

Сказал(а) «Спасибо»: 80 раз
Поблагодарили: 191 раз в 123 постах
Программа find_symm_2.00 аналогична программе find_symm, но теперь можно вместо кода симметрии указать слово all.

Файл readme.txt

Вложение(я):
find_symm_2.00.zip (52kb) загружен 32 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 13.12.2018(UTC)
Offline citerra  
#762 Оставлено : 14 декабря 2018 г. 8:06:10(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
результаты
Вложение(я):
prot.rar (2kb) загружен 25 раз(а).
stat.rar (239kb) загружен 26 раз(а).
thanks 1 пользователь поблагодарил citerra за этот пост.
whitefox оставлено 14.12.2018(UTC)
Offline citerra  
#763 Оставлено : 14 декабря 2018 г. 8:22:16(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
Симметрии среди всех 2 043 646 решений герасима
Квадратов с симметрией (1,31,31) найдено: 948 они записаны в файл symm_1_31_31.txt
Квадратов с симметрией (2,31,31) найдено: 1008 они записаны в файл symm_2_31_31.txt
Квадратов с симметрией (4,31,31) найдено: 19589 они записаны в файл symm_4_31_31.txt
Квадратов с симметрией (8,8,8) найдено: 16 они записаны в файл symm_8_8_8.txt
Квадратов с симметрией (8,31,31) найдено: 3784 они записаны в файл symm_8_31_31.txt
Квадратов с симметрией (16,16,16) найдено: 143 они записаны в файл symm_16_16_16.txt
Квадратов с симметрией (16,31,31) найдено: 2358 они записаны в файл symm_16_31_31.txt
Квадратов с симметрией (21,21,21) найдено: 1 они записаны в файл symm_21_21_21.txt
Квадратов с симметрией (21,36,36) найдено: 1 они записаны в файл symm_21_36_36.txt
Квадратов с симметрией (27,27,27) найдено: 28 они записаны в файл symm_27_27_27.txt
Квадратов с симметрией (41,41,41) найдено: 1 они записаны в файл symm_41_41_41.txt
Квадратов с симметрией (41,42,42) найдено: 1 они записаны в файл symm_41_42_42.txt
Всего 27 878 симметрией

Upd
Пара сравнений:

a)симметрия (16,31,31)

Введено ЛК: 5412

Найдено марьяжных КФ:
count[1] = 4339
count[2] = 1630
count[3] = 1
count[4] = 57
count[6] = 2
Всего: 6029
Найдено соквадратов: 7842
КФ соквадратов: 6029

у деда макара
Введено ЛК : 432
Найдено КФ ЛК: 400
Время работы : 0.218 сек

Поиск всех КФ марьяжных ДЛК для ЛК

Введено ЛК: 400
Найдено марьяжных КФ:
count[1] = 330
count[2] = 102

б) по четверкам
Введено ЛК: 578

Квадратов с симметрией (1,31,31) найдено: 75 они записаны в файл symm_1_31_31.txt
Квадратов с симметрией (4,31,31) найдено: 230 они записаны в файл symm_4_31_31.txt
Квадратов с симметрией (16,16,16) найдено: 5 они записаны в файл symm_16_16_16.txt
Квадратов с симметрией (16,31,31) найдено: 18 они записаны в файл symm_16_31_31.txt
Квадратов с симметрией (41,41,41) найдено: 1 они записаны в файл symm_41_41_41.txt
Квадратов с симметрией (41,42,42) найдено: 1 они записаны в файл symm_41_42_42.txt


у ДМ
Введено ЛК: 442

Квадратов с симметрией (1,31,31) найдено: 75 они записаны в файл symm_1_31_31.txt
Квадратов с симметрией (4,31,31) найдено: 157 они записаны в файл symm_4_31_31.txt
Квадратов с симметрией (16,16,16) найдено: 5 они записаны в файл symm_16_16_16.txt
Квадратов с симметрией (16,31,31) найдено: 5 они записаны в файл symm_16_31_31.txt
Квадратов с симметрией (41,41,41) найдено: 1 они записаны в файл symm_41_41_41.txt
Квадратов с симметрией (41,42,42) найдено: 1 они записаны в файл symm_41_42_42.txt

Отредактировано пользователем 14 декабря 2018 г. 15:06:04(UTC)  | Причина: Не указана

thanks 1 пользователь поблагодарил citerra за этот пост.
evatutin оставлено 14.12.2018(UTC)
Offline citerra  
#764 Оставлено : 15 декабря 2018 г. 8:27:03(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
Найдено в Герасиме
Квадратов с симметрией (16,31,31) найдено: 2358 они записаны в файл symm_16_31_31.txt
Найдено у Макаровой и в боик-проектах
Квадратов с симметрией (16,31,31) найдено: 197 они записаны в файл symm_16_31_31.txt
Вывод Макаровой
совсем незначительная разница
Хотя касалось многих симметрий, симметрия входила в это множество.
Хотя перед этим упрекала меня в некорректном сравнении, но говорить про 2358 и 197 - совсем незначительная разница,
вполне корректно?
Offline whitefox  
#765 Оставлено : 15 декабря 2018 г. 15:29:40(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 252

Сказал(а) «Спасибо»: 80 раз
Поблагодарили: 191 раз в 123 постах
Обобщённая статистика по ЛК_16_31_31

Код:
Семейств ЛК_16_31_31           : 81669
Собственных семейств           : 81665
Всего КФ ЛК_16_31_31           : 324212524
Из них
ЛК_1_31_31                     : 43483
ЛК_2_31_31                     : 0
ЛК_4_31_31                     : 131006
ЛК_8_31_31                     : 0
Всего ранее проверенных        : 157183
С кратной симметрией (16,31,31): 49339
Средняя мощность семейства     : 3970
Максимальная мощность семейства: 8192


Симметрия (16,31,31) несовместна с симметриями (2,31,31) и (8,31,31).

2 марьяжных ДЛК одновременно обладают симметриями (16,31,31) и (4,31,31):

Код:
0 2 4 6 5 3 7 8 9 1
6 1 8 7 3 4 9 5 0 2
8 7 2 9 1 0 5 3 6 4
5 8 6 3 0 9 4 2 1 7
9 0 1 5 4 2 8 6 7 3
1 9 7 2 6 5 3 0 4 8
2 4 3 8 7 1 6 9 5 0
4 3 9 0 8 6 1 7 2 5
3 5 0 1 9 7 2 4 8 6
7 6 5 4 2 8 0 1 3 9

0 4 8 9 6 2 7 5 3 1
3 1 5 2 7 6 8 9 0 4
9 6 2 4 8 1 5 3 7 0
5 7 1 3 2 0 4 8 9 6
1 9 0 6 4 8 3 2 5 7
8 0 4 7 9 5 1 6 2 3
2 3 7 5 1 9 6 0 4 8
4 8 6 0 5 3 9 7 1 2
6 2 9 1 3 7 0 4 8 5
7 5 3 8 0 4 2 1 6 9


Оба двойки. Ещё 553 марьяжных ДЛК одновременно обладают симметриями (16,31,31) и (1,31,31). Их распределение по степеням ортогональности:

Код:
count[1] = 142
count[2] = 364
count[3] = 1
count[4] = 44
count[6] = 2
Всего: 553


Эти 553 ДЛК получаются однократным применение Канонизатора ЛК по ДЛК (скрипт kanon_new.bat) к следующим 8 ЛК:



Им соответствуют 13752 "тяжёлых" ДЛК с большим числом д-трансверсалей, так что программа klpmd, используемая скриптом kanon_new.bat, вместо обычных 4000 - 8000 ДЛК/сек показывает 25 - 130 ДЛК/сек, из-за чего прогресс выводится на консоль не каждые пять секунд, а примерно раз в полминуты.
Offline evatutin  
#766 Оставлено : 16 декабря 2018 г. 20:00:49(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,700
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1893 раз в 917 постах
Автор: whitefox Перейти к цитате
Им соответствуют 13752 "тяжёлых" ДЛК с большим числом д-трансверсалей, так что программа klpmd, используемая скриптом kanon_new.bat, вместо обычных 4000 - 8000 ДЛК/сек показывает 25 - 130 ДЛК/сек, из-за чего прогресс выводится на консоль не каждые пять секунд, а примерно раз в полминуты.


Там есть некоторое количество тяжелых Браунов. Поскольку мы их давно все нашли, я у себя в коде поставил проверку: если попадается Браун, он игнорится, чтобы сильно не снижалась скорость обработки

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline citerra  
#767 Оставлено : 16 декабря 2018 г. 21:37:53(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
Симметрии кончились. Осталось хвосты подсчитать.
Offline whitefox  
#768 Оставлено : 17 декабря 2018 г. 13:59:35(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 252

Сказал(а) «Спасибо»: 80 раз
Поблагодарили: 191 раз в 123 постах
Докажем справедливость следующего утверждения.

Утверждение. Симметрия (31,31,31) не существует.

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

Код:
** 9876543210 9876543210 9876543210


Тогда всякий ЛК со стандартным представлением симметрии (31,31,31) будет "центрально симметричным" ЛК со следующим соответствием элементов:

Код:
0 <-> 9
1 <-> 8
2 <-> 7
3 <-> 6
4 <-> 5


Отождествив пары соответствующих друг другу элементов (заменив в ЛК старшие члены пар соответствующими им младшими членами), получим блочную структуру соответствующую стандартному представлению симметрии (31,31,31). Эта БС будет центрально симметричным квази-ЛК с мультимножеством значений {0,0,1,1,2,2,3,3,4,4}.

Не всякий такой квази-ЛК является БС. Как уже было показано, для этого необходимо и достаточно, чтобы были выполнены следующие условия:
1) всякий цикл позиций является самосогласованным;
2) все смежные циклы позиций согласованы;
3) все замкнутые контуры циклов позиций согласованы;
4) все замкнутые контуры циклов позиций согласованы в совокупности.

Первое условие было использовано в качестве необходимого при определении списка 46 возможных кодов чистых симметрий. Легко показать, что для симметрий (x,31,31) x in {1,2,4,8,16,31} второе и четвёртое условия также выполнены.

Покажу на примере как проверять третье условие для симметрии (31,31,31). Для этого рассмотрим квази-ЛК:

Код:
0 1 2 3 4 0 1 3 2 4
1 4 4 3 1 0 2 3 2 0
2 1 0 0 2 3 4 1 4 3
3 0 1 0 1 2 4 2 3 4
1 0 0 1 3 4 2 4 3 2
2 3 4 2 4 3 1 0 0 1
4 3 2 4 2 1 0 1 0 3
3 4 1 4 3 2 0 0 1 2
0 2 3 2 0 1 3 4 4 1
4 2 3 1 0 4 3 2 1 0


Для стандартного представления симметрии (31,31,31) каждый цикл позиций состоит из двух ячеек ЛК с координатами {(i,j),(9-i,9-j)}. Ячейку с меньшими координатами будем считать начальной позицией соответствующего цикла, а сами циклы будем идентифицировать координатами их начальной позиции (то есть присвоим циклу позиций номер n=i*10+j, где i,j координаты начальной позиции). Два однотипных (с одинаковым значением) цикла позиций будем считать смежными если найдётся строка и/или столбец пересекающая(ий) одновременно оба цикла позиций. Ребро, соединяющее смежные циклы позиций, будет иметь длину 1 если их начальные позиции принадлежат одной строке или одному столбцу, в противном случае ребро имеет длину 0.

Данному квази-ЛК поставим в соответствие граф G вершины которого соответствую циклам позиций (и помечены соответствующими номерами). Если два цикла позиций смежны, то соответствующие им вершины графа соединим ребром. Очевидно, что все вершины графа G имеют степень 2, поэтому все его компоненты связности суть замкнутые контуры. То есть задача разыскания замкнутых контуров циклов позиций сводится к разысканию компонент связности графа G.

Для нашего примера находим следующие замкнутые контуры:

Код:
0-(1)-5-(1)-15-(1)-19-(0)-*
22-(1)-23-(1)-33-(1)-31-(1)-41-(1)-42-(1)-*
1-(1)-6-(0)-43-(1)-40-(1)-10-(1)-14-(1)-34-(1)-32-(0)-27-(1)-21-(1)-*
8-(1)-2-(0)-37-(1)-35-(0)-24-(1)-20-(0)-49-(1)-46-(1)-16-(1)-18-(1)-*
7-(1)-3-(1)-13-(1)-17-(1)-*
29-(1)-25-(0)-44-(1)-48-(1)-38-(1)-30-(0)-*
9-(1)-4-(0)-45-(1)-47-(0)-12-(1)-11-(0)-28-(1)-26-(1)-36-(1)-39-(1)-*

Здесь -(1)- означает ребро и его длину, а * — первую вершину контура.

Для симметрии (31,31,31) замкнутый контур циклов позиций будет согласованным если он имеет чётную длину. В примере замкнутые контуры имеют длины: 3, 6, 8, 7, 4, 4, 7. Следовательно данный квази-ЛК не является блочной структурой соответствующей стандартному представлению симметрии (31,31,31).

Сделаем пару наблюдений.
1) М-перестановки строк и/или столбцов, транспонирование и переименование элементов центрально симметричного квази-ЛК переводят его в центрально симметричный квази-ЛК. При этом БС переходит в БС, а не-БС в не-БС.

2) Центрально симметричный квази-ЛК однозначно определяется своей левой половиной, которую будем называть шаблоном. Если шаблон определяет БС, то будем называть его собственным шаблоном.

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

Объем работы можно сократить ещё в 65536 раз если перечислять нормализованные супершаблоны. Супершаблон будем называть собственным если ему соответствует хотя бы один собственный шаблон. Для проверки последнего факта, сопоставим каждому замкнутому контуру супершаблона линейное уравнение над полем F2. Имеет место следующая лемма.

Лемма. Супершаблон является собственным тогда и только тогда, когда соответствующая ему система уравнений над полем F2 является совместной.

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

Код:
Поиск собственных супершаблонов БС_31_31_31

Паттерн_0: 0
Паттерн_1: 0
Паттерн_2: 0
Паттерн_3: 0
Паттерн_4: 0
Паттерн_5: 0

Время работы: 8.533 сек


За деталями построения системы уравнений и проверки её совместности отсылаю к исходнику в прилагаемом архиве.

Вложение(я):
proverka_31_31_31.zip (11kb) загружен 28 раз(а).
Offline whitefox  
#769 Оставлено : 18 декабря 2018 г. 13:08:31(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 252

Сказал(а) «Спасибо»: 80 раз
Поблагодарили: 191 раз в 123 постах
В boinc проекте было найдено 2429 марьяжных ДЛК с симметрией (16,31,31). Ещё 555 были найдены раньше. Всего марьяжных ДЛК с симметрией (16,31,31) существует 2984. Их распределение по степеням ортогональности

Код:
count[1] = 1303
count[2] = 1621
count[3] = 1
count[4] = 57
count[6] = 2
Всего: 2984


Им соответствуют 2436 д-марьяжных ЛК с симметрией (16,31,31). А в их замыкание входят 6185 ОДЛК со следующим распределением по степеням ортогональности

Код:
count[1] = 4495
count[2] = 1630
count[3] = 1
count[4] = 57
count[6] = 2
Всего: 6185
Вложение(я):
mar_dlk_16_31_31_2984.zip (314kb) загружен 27 раз(а).
zamyk_16_31_31.zip (678kb) загружен 27 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 18.12.2018(UTC)
Offline Demis  
#770 Оставлено : 18 декабря 2018 г. 13:10:21(UTC)
Demis


Статус: Я тут не впервой

Группы: Member
Зарегистрирован: 29.05.2017(UTC)
Сообщений: 42

Сказал(а) «Спасибо»: 9 раз
Поблагодарили: 10 раз в 8 постах
Пример использования некоторых функций.

в программе kanonizator_lk (и некоторых других) использованы функции которые,
при первом рассмотрении, могут поставить в ступор.
Особенно тех кто хочет получить работающее приложение под юникс-совместимыми системами.

Речь пойдет об этом:
Код:
_BitScanForward
_BitScanReverse
_BitTest
_BitTestAndReset
_BitTestAndSet

Родное описание по ним лежит здесь:
https://docs.microsoft.com/en-us...sics/x86-intrinsics-list
https://docs.microsoft.com/en-us...64-amd64-intrinsics-list
В юникс системах функции выполняющие аналогичные действия появились на BSD4.3 в 1986 году в виде библиотеки.
https://en.wikipedia.org/wiki/Find_first_set
Первая-же строка в таблице "Tool and library support" показывает нам "4.3BSD".
Там-же по ссылке на "4.3BSD" можно увидеть :
https://en.wikipedia.org/wiki/Hi...ware_Distribution#4.3BSD
такой текст "4.3BSD was released in June 1986".

У MS, если верить таблице, появилось в Visual Studio 2005 спустя 19 лет.
К таблице есть некоторые "вопросы", т.к. clang указан как 5.х
Хотя реально пробовал на 3.6.1 и 3.8.0 и все собралось, но clang молодой компилятор, поэтому не удивительно, что в нем учтены эффективные функции.

А через некоторое время оные (FFS) вообще вошли в код системы, т.е. стали нативными (native).
Разные вариации на эту тему, но не все, собраны Sean Eron Anderson в одну кучку:
http://graphics.stanford.edu/~seander/bithacks.html
Есть очень интересное обсуждение с примерами (публиковал ранее):
https://stackoverflow.com/questi...nificant-bit-that-is-set
Не суть.

Рассмотрим пример работы программы под Windows 7 x64 RAM 16Гб, проц Intel i7
Во всех описанных экспериментах программа запускалась
на одном и том-же наборе данных пять раз,
чтобы видеть стороннюю нагрузку и кеширование.

Есть определенная НЕ корректность в том,
что при измерениях были разные процессоры и объем памяти.
Корректность работы программы сравнивалась по полученным output.txt
с того-же блока входных данных на виндовс машине.
Конечно они (процессоры) должны быть одинаковы для разных систем.

Смотрим, внимательно, на "время работы":
Разница времени выполнения на юникс x64 и процессор i7 :
22.8047 - 18.9141 = 3.8906

Разница времени выполнения на Win7 x64 и процессор i7 :
24.414 - 18.9141 = 5.4999

У меня был прогноз, что можно выиграть от 3-ех до 6-ти секунд если перейти на нативный режим, получилось 5.5сек, то есть прогноз сбылся. По аналогии код можно применить в других программах. Только будьте внимательны к коду.
thanks 3 пользователей поблагодарили Demis за этот пост.
citerra оставлено 18.12.2018(UTC), whitefox оставлено 18.12.2018(UTC), Disel оставлено 18.12.2018(UTC)
Offline Disel  
#771 Оставлено : 18 декабря 2018 г. 14:22:30(UTC)
Disel


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch! Донор: За финансовую помощь сайту

Группы: Member, Russia Team Group
Зарегистрирован: 08.07.2013(UTC)
Сообщений: 3,459
Мужчина
Российская Федерация

Сказал «Спасибо»: 523 раз
Поблагодарили: 428 раз в 328 постах
Demis, а в G++ собирать не пробовали? Если нет могу попробовать, но какой именно код компилировать?
Ubuntu Linux 18.04 LTS - 64 bit / Boinc 7.9.3(х64) / Core 2 DUO E6300 1.8 Ггц / GeForce GT-630
Offline Demis  
#772 Оставлено : 18 декабря 2018 г. 17:09:50(UTC)
Demis


Статус: Я тут не впервой

Группы: Member
Зарегистрирован: 29.05.2017(UTC)
Сообщений: 42

Сказал(а) «Спасибо»: 9 раз
Поблагодарили: 10 раз в 8 постах
Автор: Disel Перейти к цитате
Demis, а в G++ собирать не пробовали?
Честно говоря - не пробовал.

Автор: Disel Перейти к цитате
Demis, какой именно код компилировать?

Как и написано выше:
Автор: Demis Перейти к цитате

"Применим паллиатив для файла kanon.cpp (не забываем выкинуть #include <intrin.h> из файла main.h)."

И, в примере (в тексте эксперимента) видно, что это программа kanonizator_lk. Соответственно для показанного примера находим и скачиваем программу kanonizator_lk с исходниками.

Решил попробовать g++:
Код:
-rwxr-xr-x 1 root demis 110520 Aug 28 17:20 kanonizator-lk
-rwxr-xr-x 1 root wheel 110272 Aug 22 17:03 kanonizator-lk-222
-rwxr-xr-x 1 root wheel 110664 Aug 22 17:05 kanonizator-lk-2224
-rwxr-xr-x 1 root wheel 125966 Aug 22 17:06 kanonizator-lk-2225
-rwxr-xr-x 1 root wheel 110608 Dec 18 15:44 kanonizator-lk-8888

Собралось строкой:
Код:
g++ -std=c++11 -O3 -s -Wall -Wno-missing-braces main.cpp kanon.cpp -o kanonizator-lk-8888

Версия g++ -v:
Код:
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/local/libexec/gcc6/gcc/x86_64-portbld-freebsd11.1/6.4.0/lto-wrapper
Target: x86_64-portbld-freebsd11.1
Configured with: /usr/ports/lang/gcc6/work/gcc-6.4.0/configure --with-build-config=bootstrap-debug --disable-nls --enable-gnu-indirect-function --libdir=/usr/local/lib/gcc6 --libexecdir=/usr/local/libexec/gcc6 --program-suffix=6 --with-as=/usr/local/bin/as --with-gmp=/usr/local --with-gxx-include-dir=/usr/local/lib/gcc6/include/c++/ --with-ld=/usr/local/bin/ld --with-pkgversion='FreeBSD Ports Collection' --with-system-zlib --with-ecj-jar=/usr/local/share/java/ecj-4.5.jar --enable-languages=c,c++,objc,fortran,java --prefix=/usr/local --localstatedir=/var --mandir=/usr/local/man --infodir=/usr/local/info/gcc6 --build=x86_64-portbld-freebsd11.1
Thread model: posix
gcc version 6.4.0 (FreeBSD Ports Collection)

На скорость и точность вычисления собранным через g++ не проверял (в clang'e тогда допустил опечатку, неделю искал).
Хотя, на вскидку (с тестовыми данными), выходной результат правильный, но глубоко не проверял. Давно делал, мог и забыть что-то.

Offline citerra  
#773 Оставлено : 18 декабря 2018 г. 17:46:31(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
jozef j
В подпроекте, который запустила Макарова, проверяются ЛК, которые уже проверены в Герасиме. К тому же самым неэффективным методом. Мощная техника, говоришь. А будешь использовать на уровне дектопа?
Offline hoarfrost  
#774 Оставлено : 23 декабря 2018 г. 19:17:36(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,482
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1296 раз
Поблагодарили: 1772 раз в 1110 постах
Автор: Disel Перейти к цитате
Demis, а в G++ собирать не пробовали? Если нет могу попробовать, но какой именно код компилировать?

На g++ можно сделать. Там есть похожая по смыслу, но не идентичная по возвращаемому значению функция __builtin_ffs. В RakeSearch cначала Daniel-ем, а потом и нами было сделано примерно так:
Код:

...
# ifdef _MSC_VER
    isRowFree = _BitScanForward(&bitIndex, freeRowsMask);
# else
    bitIndex = __builtin_ffs(freeRowsMask);
    if (bitIndex > 0)
    {
        isRowFree = 1;
        bitIndex--;
    }
    else
    {
        isRowFree = 0;
    }
# endif
...


Но надо упомянуть, что битовую логику такого же смысла, насколько я понимаю, первым реализовал Степан Кочемазов в одном из приложений для Gerasim@Home. Именно поэтому начиная RakeSearch расчитывали на то, что приложение можно будет оптимизировать. (С самим решением Степана в деталях тогда знакомы не были, да и сейчас руки не дошли посмотреть, но область использования конкретно этой функци - ну очень прозрачна).
smile
UserPostedImage
Offline whitefox  
#775 Оставлено : 24 декабря 2018 г. 12:11:06(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 252

Сказал(а) «Спасибо»: 80 раз
Поблагодарили: 191 раз в 123 постах
Теория перечисления всех существенно различных ЛК10, обладающих симметрией (27,27,27).

В качестве стандартного представителя симметрии (27,27,27) возьмём автоморфизм

Код:
** 0231564897 0231564897 0312645978

Всякий ЛК со стандартным представлением симметрии (27,27,27), например ЛК

Код:
0 1 2 3 4 5 6 7 8 9
8 2 4 7 3 6 0 9 1 5
9 8 3 5 0 1 4 6 7 2
7 6 9 1 5 0 2 3 4 8
6 4 1 9 2 8 7 0 5 3
4 7 5 2 8 3 9 1 0 6
5 3 8 6 7 9 1 4 2 0
2 9 6 0 1 4 8 5 3 7
3 0 7 4 9 2 5 8 6 1
1 5 0 8 6 7 3 2 9 4


имеет следующую структуру

Код:
0  1 2 3  4 5 6  7 8 9

8  2 4 7  3 6 0  9 1 5
9  8 3 5  0 1 4  6 7 2
7  6 9 1  5 0 2  3 4 8

6  4 1 9  2 8 7  0 5 3
4  7 5 2  8 3 9  1 0 6
5  3 8 6  7 9 1  4 2 0

2  9 6 0  1 4 8  5 3 7
3  0 7 4  9 2 5  8 6 1
1  5 0 8  6 7 3  2 9 4

Автор: whitefox Перейти к цитате

1) в левом верхнем углу стоит 0;
2) оставшиеся девять элементов первой строки составляют три секции по три элемента, одна из них является некоторым циклическим сдвигом строки 123, вторая — циклическим сдвигом строки 456, а третья — строки 789;
3) для первого столбце аналогично первой строке;
4) оставшиеся 81 элемент составляют 9 блоков 3x3:

Код:
2 4 7  3 6 0  9 1 5
8 3 5  0 1 4  6 7 2
6 9 1  5 0 2  3 4 8

4 1 9  2 8 7  0 5 3
7 5 2  8 3 9  1 0 6
3 8 6  7 9 1  4 2 0

9 6 0  1 4 8  5 3 7
0 7 4  9 2 5  8 6 1
5 0 8  6 7 3  2 9 4


прямые ломанные диагонали каждого блока могут иметь только один из следующих четырёх видов:
а) 000
б) циклический сдвиг строки 123
в) циклический сдвиг строки 456
г) циклический сдвиг строки 789

Рассмотрим совокупность строк которые могут быть первой строкой ЛК со стандартным представлением симметрии (27,27,27). Всего таких строк (3!)*(3^3)=162. Соответствующие им перестановки составляют группу, которую будем называть (27,27,27)-группой.

Следующие эквивалентные преобразования переводят ЛК со стандартным представлением симметрии (27,27,27) в такой же ЛК:
1) произвольная (27,27,27)-перестановка строк;
2) произвольная (27,27,27)-перестановка столбцов;
3) переименование элементов ЛК в соответствии с произвольной (27,27,27)-перестановкой;
4) произвольная парастрофия;
Всего таких преобразований 6*(162^3)=25509168.

Сделаем следующую замену элементов:

Код:
{1,2,3} -> 1
{4,5,6} -> 2
{7,8,9} -> 3


получим квази-ЛК с мультимножеством значений {0,1,1,1,2,2,2,3,3,3}. Например, наш ЛК перейдёт в квази-ЛК

Код:
0  1 1 1  2 2 2  3 3 3

3  1 2 3  1 2 0  3 1 2
3  3 1 2  0 1 2  2 3 1
3  2 3 1  2 0 1  1 2 3

2  2 1 3  1 3 3  0 2 1
2  3 2 1  3 1 3  1 0 2
2  1 3 2  3 3 1  2 1 0

1  3 2 0  1 2 3  2 1 3
1  0 3 2  3 1 2  3 2 1
1  2 0 3  2 3 1  1 3 2


который является блочной структурой вида (27,27,27). Любая такая БС однозначно определяется строками 0, 1, 4 и 7. Будем их называть шаблоном данной БС. Для нашего примера получим шаблон

Код:
0  1 1 1  2 2 2  3 3 3
3  1 2 3  1 2 0  3 1 2
2  2 1 3  1 3 3  0 2 1
1  3 2 0  1 2 3  2 1 3


К шаблону применимы следующие эквивалентные преобразования:
1) произвольная (27,27,27)-перестановка столбцов;
2) произвольная перестановка строк {1,2,3};
3) одинаковый циклический сдвиг каждого сегмента одной строки;
4) переименование элементов шаблона в соответствии с произвольной переставкой {1,2,3}.

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

Код:
3 2 0  1 2 3  2 1 3
2 1 3  1 3 3  0 2 1
1 2 3  1 2 0  3 1 2

К нормализованым шаблонам применимы следующие эквивалентные преобразования:
1) произвольная перестановка 3x3-блоков с точно такой же перестановкой строк и с переименование элементов шаблона в соответствии с обратной перестановкой;
2) одинаковый циклический сдвиг всех сегментов одной строки;
3) одинаковый циклический сдвиг всех сегментов одного 3x3-блока.

Возможно шесть преобразовани типа 1:

Код:
012 012 0123
021 021 0132
201 201 0231
210 210 0321
120 120 0312
102 102 0213


Сегменты, содержащие ноль, будем называть нулевыми. Составим 3x3 (0,1)-матрицу показывающую расположение нулевых сегментов. Для нашего примера получим

Код:
1 0 0
0 0 1
0 1 0

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

Код:
3 цикла -> паттерн 0
2 цикла -> паттерн 1
1 цикл  -> паттерн 2

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

Код:
1 0 0
0 1 0
0 0 1

1 0 0
0 0 1
0 1 0

0 1 0
0 0 1
1 0 0

для паттернов 0, 1 и 2 соответствено.

Нормализованый шаблон будем называть сильно нормализованным если:
1) нулевые сегменты расположены нормально;
2) во всех нулевых сегментах ноль стоит на первом месте;
3) во всех сегментах первой строки на первом месте стоит наименьший элемент.

Для нашего примера получим

Код:
0 3 2  1 2 3  1 3 2
1 3 2  3 1 3  0 2 1
2 3 1  0 1 2  3 1 2


Определим супершаблон как 3x3 матрицу в ячейках которой находятся мультимножества элементов соответствующих сегментов шаблона. В нашем примере получим

Код:
{0,2,3} {1,2,3} {1,2,3}
{1,2,3} {1,3,3} {0,1,2}
{1,2,3} {0,1,2} {1,2,3}

Супершаблон будем называть нормализованным если его нулевые сегменты (то есть мультимножества содержащие нули) имеют нормальное расположение в соответствии с паттерном.

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

Наименьший в лексикографическом порядке нормализованный супершаблон из всех эквивалентных будем называть каноническим супершаблоном. Всего канонических супершаблонов_27_27_27 существует 93, каждый из них определяет семейство ЛК_27_27_27.

В приложенном архиве программа перечисления канонических супершаблонов.

Продолжение следует.
Вложение(я):
gen_sem_27_27_27.zip (19kb) загружен 26 раз(а).
thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 24.12.2018(UTC), hoarfrost оставлено 24.12.2018(UTC)
Offline citerra  
#776 Оставлено : 24 декабря 2018 г. 15:03:26(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
Цитата:
И при обработке следующей порции решений из БД ручного проекта поворотом блоков найден ещё один новый стандарт с симметрией (4,31,31)!
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
2 0 6 1 7 3 9 4 5 8
3 6 5 7 0 9 8 2 1 4
4 3 7 6 9 8 1 0 2 5
5 8 4 2 1 0 3 9 7 6
6 5 8 9 2 1 0 3 4 7
7 9 0 8 6 2 4 5 3 1
8 4 9 0 3 7 5 1 6 2
9 7 1 5 8 4 2 6 0 3
Цитата:
только 44 дали ОДЛК (это стандарты в моей терминологии

Если ОДЛК, то квадрат не может быть стандартом.
Без определения, а только имея описание( каждый раз новое), трудно понять о чем идет речь - что такое стандарт.
Ладушки, деду макару нравиться и ладно, у него склероз.
Offline whitefox  
#777 Оставлено : 25 декабря 2018 г. 14:08:22(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 252

Сказал(а) «Спасибо»: 80 раз
Поблагодарили: 191 раз в 123 постах
Итак, мы нашли 93 канонических супершаблона которые определяют 93 семейства ЛК_27_27_27. Строго говоря, семейства определяют только канонические супершаблоны которым соответствуют суперклассы БС_27_27_27. Такие семейства (и определяющие их канонические супершаблоны) будем называть собственными, а прочие семейства назовём псевдосемействами.

Каждый суперкласс БС_27_27_27 состоит из шести (по числу парастрофий) совокупностей классов эквивалентности БС_27_27_27 (некоторые из этих совокупностей могут совпадать). Каждой из этих совокупностей соответствует одно и тоже множество ЛК_27_27_27, поэтому будет достаточно для каждого суперкласа перечислить только одну совокупность классов БС. Сделаем это так:
1) найдём совокупность сильно нормализованных шаблонов при "суперизации" которых (то есть при упорядочении по неубыванию всех сегментов) получается выбранный супершаблон, например, для нашего супершаблона найдётся ((3!)^4)*((2!)^5)=41472 сильно нормализованных шаблонов;
2) канонизируем полученные сильно нормализованные шаблоны и устраним дубли (в качестве канонического шаблона возьмём наименьший в лексикографическом порядке сильно нормализованный шаблон из всех эквивалентных данному);
3) из полученного списка канонических шаблонов удалим несобственные шаблоны (то есть шаблоны которым не соответствует блочная структура).
Если получим пустой список, то данному супершаблону никакой суперкласс БС не соответствует.

Для выполнения пункта 3, нужно по шаблону восстановить квази-ЛК и проверить, упоминавшиеся ранее, необходимые и достаточные условия на соответствие БС. Фактически, из этих условий нужно проверить только третье и четвёртое. Для чего, в свою очередь, нужно по квази-ЛК построить граф G (по методу аналогичному ранее описанному), выделить в нём компоненты связности и проверить последние.

Алгоритм проверки компонент связности графа G покажу на примере. Пусть имеется компонента связности с вершинами A, B, C, D и рёбрами (AC), (AD), (BC), (BD), (CD).

Код:
A--C
| /|
|/ |
D--B


Рёбра направлены из лексикографически меньшей буквы в большую, и каждому ребру соответствует множество допустимых значений длин, например

Код:
(AC) -> {0,1}
(AD) -> {0,2}
(BC) -> {1,2}
(BD) -> {1,2}
(CD) -> {1}


1) Обозначим рёбра переменными X_1, X_2, X_3, X_4, X_5 соответственно.

2) Выберем остовное дерево, не обращая внимания на ориентацию рёбер. Переменные, соответствующие рёбрам остовного дерева, назовём свободными, а прочие — зависимыми. Например

Код:
A--C
  /
 / 
D--B

Свободные: X_1, X_4, X_5.
Зависимые: X_2, X_3.


3) Каждой зависимой переменной сопоставим путь в остовном дереве из первой вершины во вторую. Составим по этому пути уравнение, в левой части которого стоит зависимая переменная, а в правой — алгебраическая сумма (по модулю 3) свободных переменных соответствующих рёбрам пути, причём если ребро проходится против направления, то соответствующую переменную берём со знаком минус. Для нашего примера получим

Код:
X_2 = X_1 + X_5 (mod 3)
X_3 = X_4 - X_5 (mod 3)


4) Компонента связности соответствует блоку блочной структуры тогда и только тогда, когда полученная система уравнений имеет решение. А квази-ЛК является БС тогда и только тогда, когда всякой компоненте связности графа G соответствует блок БС. В нашем примере система имеет одно решение

Код:
X_1 = 1, X_2 = 2, X_3 = 1, X_4 = 2


С найденными собственными каноническими шаблонами поступаем как обычно:
1) по шаблону БС находим БС;
2) по БС строим базовый ЛК;
3) варьирую ориентацию блоков базового ЛК, находим все ЛК отвечающие данной БС;
4) канонизируем найденные ЛК и исключаем дубли;
5) исключаем ЛК которые одновременно удовлетворяют меньшему супершаблону.
Offline whitefox  
#778 Оставлено : 24 января 2019 г. 13:05:27(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 252

Сказал(а) «Спасибо»: 80 раз
Поблагодарили: 191 раз в 123 постах
Исходные коды boinc-проектов по поиску марьяжных ДЛК10 с симметрией (x,31,31) x in {2,4,8,16}.

Цитата:
Can you give source codes?


Почему нет? Любое использование разрешено, при условии упоминания, что впервые эти проекты были выполнены на Gerasim@home.
Вложение(я):
boinc_x_31_31.zip (98kb) загружен 10 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
evatutin оставлено 24.01.2019(UTC)
Offline citerra  
#779 Оставлено : 29 января 2019 г. 14:25:23(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
На конец 2018 распределение по линейкам

1034685972 574453
1034678952 558242
1034678925 529582
1034628975 523957
1032675894 523430
1230675948 455340


1037892645 6133
1204635978 10415
1037892654 12569

Offline citerra  
#780 Оставлено : 30 января 2019 г. 10:22:53(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 1,967

Сказал(а) «Спасибо»: 534 раз
Поблагодарили: 364 раз в 263 постах
В связи с линейками, попалось такое сообщение на форуме ODLK@Home
Цитата:
Сейчас линейка №58 проверяется в проекте ODLK; все линейки со стопроцентным содержанием КФ проверяются.
Интересно стало посмотреть, сколько КФ ОДЛК найдено в линейке №58.
Выбрала все КФ ОДЛК этой линейки из результатов проекта ODLK, их оказалось 157028 штук.
Интервалы стали поменьше, КФ стали поближе друг к дружке.
Вот начало массива КФ ОДЛК из этой линейки
. Смотрим №3 и №4
Код:
0 2 3 4 5 7 8 6 9 1
2 1 4 5 3 8 7 9 0 6
1 4 2 0*7 9 5 3 6 8
9 8 6 3 0 2 4 1 5 7
7 3 5 9 4 6 0 8 1 2
6 9 8 7 2 5 1 4 3 0
4 5 7 8 9 1 6 0 2 3
8 0 9 6 1 3 2 7 4 5
3 7 1 2 6 0 9 5 8 4
5 6 0 1 8 4 3 2 7 9

0 2 3 4 5 7 8 6 9 1
2 1 4 5 3 8 7 9 0 6
1 4 2 7*0 9 5 3 6 8
8 9 6 3 7 0 4 5 1 2
3 0 5 1 4 6 9 8 2 7
7 6 8 9 2 5 0 1 4 3
4 5 7 8 9 1 6 2 3 0
6 3 9 0 8 2 1 7 5 4
9 7 0 6 1 3 2 4 8 5
5 8 1 2 6 4 3 0 7 9

А где
Код:
0 2 3 4 5 7 8 6 9 1 
2 1 4 5 3 8 7 9 0 6 
1 4 2 0*8 9 5 3 6 7 
7 0 6 3 9 1 4 8 5 2 
3 5 7 2 4 6 9 0 1 8 
8 9 0 6 2 5 3 1 7 4 
9 3 1 8 7 2 6 5 4 0 
4 8 9 1 6 3 0 7 2 5 
6 7 5 9 1 0 2 4 8 3 
5 6 8 7 0 4 1 2 3 9 

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

Сейчас известно более полмиллиона квадратов из 58 линейки
1034628975 523957 ( чуть выше ).
Если в odlk1@home их целенаправленно не ищут, то получается попутно нашлось в два раза больше, то тогда зачем такой проект.

Как же ищут квадраты в этой линейке. Кажется естественно последовательно одним зза другим. Благо есть софт от Белышева. Доделай и в путь. Но затейникам показалось простой путь скучным. Они выдумали какой свой. По установившимся правилам, исходники скрыли, алгоритмы поиска не описали.Или они так покурочили исходники Белышева,что появились дыры.

И с такими погремушками молотят. Мука будет. Вот какая? Можно полагаться на результаты проекта? Или так сойдет?
Как всегда ответа не будет.

Это для раздумья тем, кто считает проект odlk@home

Upd
Такая же ситуация и с линейкой №2.
Из-за такой кривизны вытаскиваются из чуланов изначально мало эффективный метод интервалов. ( Даже взятый случайный интервал дает на два решения больше.)
А при правильной реализации софта вообще бесполезный.

Отредактировано пользователем 30 января 2019 г. 11:08:17(UTC)  | Причина: Не указана

Пользователи, просматривающие эту тему
Guest
41 Страницы«<3738394041>
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2019, Yet Another Forum.NET
Страница сгенерирована за 0.522 секунды.