Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Вчерашний короткий эксперимент по расширению спектра трансверсалей в ДЛК порядка 11 оперативно завершен (практически за сутки с учетом досчета хвостов). В результате, как и ожидалось, спектр числа трансверсалей расширился с 3561 до 5068 значений. Манипуляция с КФами от известных на данный момент спектров при постобработке результатов позволила немного расширить как спектр числа трансверсалей, так и спектр числа диагональных трансверсалей:
* трансверсали: Min value = 1721, max value = 37851, width = 36131, cardinality = 5070 (!!!)
* диагональные трансверсали: Min value = 194 (!!!), max value = 4828, width = 4635 (!!!), cardinality = 927 (!!!)
Для минимального числа трансверсалей в ДЛК порядка 11 можно сказать, что a(11) <= 1721 (до этого было a(11) <= 2091). Аналогично, для диагональных трансверсалей: a(11) <= 199 -> a(11) <= 194. Оба ограничения усилены благодаря нахождению квадрата
0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 6 9 10 8 7 0 5
3 10 8 7 0 4 1 9 5 2 6
8 5 9 10 2 1 3 4 6 7 0
5 3 4 6 9 7 8 1 0 10 2
2 6 10 8 7 3 0 5 9 1 4
4 8 7 0 1 6 5 10 2 3 9
7 9 5 2 3 0 4 6 10 8 1
10 4 6 9 8 2 7 0 1 5 3
6 7 0 1 5 10 9 2 3 4 8
9 0 1 5 10 8 2 3 4 6 7
Спектры числа трансверсалей и диагональных трансверсалей скорее всего допускают расширение...
Цитата: Yura12 от 13.12.2021, 05:25А тогда можно вопрос, а почему бы, раз не хватает времени, не дать эту работу в качестве курсовых или дипломных работ?
То есть одному студенту дать курсовую / дипломную работу по портированию кода на Linux.
А другому студенту (а лучше нескольким) дать работу по оптимизации программного кода, чтобы посмотрели код, может какие участки можно оптимизировать, может что-то даже на ассемблер переписать.
Я бы с радостью так сделал, но...
Что но...? Неужели сейчас нет ни одного студента, который бы увлекался программированием, оптимизацией кода? Я вот помню когда мы были студентами в конце 90-х так всё свободное время были заняты компьютерные классы, там все добровольно и увлечённо занимались программированием, оптимизировали код на Паскале и Ассемблере. Я даже статью в 2000 делал: http://jkfs.petrsu.ru/~yura/pyldin/opt6800.htm
Неужели современная молодёжь, студенты уже совсем стали от этого далеки?
ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 9 8 11 5 10 0 6 7
5 8 10 6 11 4 1 3 9 7 0 2
11 7 5 8 10 2 9 1 3 6 4 0
7 5 8 10 6 3 0 2 4 11 9 1
9 0 1 2 3 7 10 11 5 4 8 6
6 11 7 5 8 1 4 0 2 10 3 9
10 6 11 7 5 0 3 9 1 8 2 4
3 4 9 0 1 6 5 10 11 2 7 8
2 3 4 9 0 10 7 8 6 1 11 5
4 9 0 1 2 11 8 6 7 3 5 10
8 10 6 11 7 9 2 4 0 5 1 3
с рекордным на данный момент числом диагональных трансверсалей (30192) и ОДЛК (3855983322) перепроверен еще раз: число ОДЛК в точности совпало с найденным и опубликованным ранее (на тот момент из-за аппаратных ошибок на сервере были определенные сомнения, теперь все точки на ё расставлены окончательно). Текущий расчет выполнен совместно в проектах Gerasim@Home (http://gerasim.boinc.ru) и RakeSearch (https://rake.boincfast.ru/rakesearch/).
PS. Некоторые кранчеры (например, CoolAtchOk) поучаствовали почти на всех стадиях проверки данного квадрата в разных проектах, за что им отдельное спасибо! 
Возьмем выборку из 200 тыс. случайных ДЛК порядка 13 и построим по ним спектр числа диагональных трансверсалей. На этот расчет ушло в общей сложности около 10 часов работы процессора Core i7 4770 в 1 поток, в результате чего, как и ожидалось, получен спектр мощностью 766, состоящий из узкой полоски значений. Спектр допускает существенное расширение как вверх, так и вниз, чем можно будет заняться в перспективе... Фрагмент спектра показан ниже.
...
9980 0123456789ABC18B593027AC64C4A1B92560738A3CB6784510927C642B18A590397821CB3465A0305786912CB4A5B3C72A608419867A04C91325B6A98C05B3412729465A70CB3814509A13CB2876B210384A976C5
9981 0123456789ABC7A8B910425C63AC5287410693B12A6397B540C88534BA9C127066B712C854039A47986230BC1A53065CBA871429C6B074539A81254CA162937B80B907A316C8254981C50B2A3647234908CA6B571
9982 0123456789ABC16B978A30C254A84291563B7C08975632AC410B7C81B0926A435C5A61748B2093BA5C043928671530A821C76B4927C4A60B95318629B3C704158A3410C9B5A782640682BC1539A79B375A8410C62
9983 0123456789ABC38A714962CB502710ABC548369C03A985B714267C563928A014BB3896CA417502A29403B156C878A65B042C3791140B2739658CA59B8721C046A36572C180BA93446C15A039B2789B4C867A32015
9984 0123456789ABCA8B03C219675434C7BA92586105209C3B4718A6651872A04C93B7A5B1609C23488C41273A60B95173498C5BA062B365041CA7289C98A50462B17390726B58134CA4B96A18305C2726AC897B34501
9985 0123456789ABC5A9703CB2168484C6AB920537146592013CB8A77B3869AC40152C91AB8367254037BC1A2054968B86537419C02A2CA49605B8713908154BA372C663027C581A49B1570C284A6B39A24B817963C05
9986 0123456789ABC3649ABC258710A4BC218073695C8A263B1970545910C67A3284B17C4980B6532AB23679584AC017B5A82190C46323810C94AB5769C08573614BA26597B4A3201C88A7B1045C623940653A2CB1987
9987 0123456789ABC94582A713CB606C94B0A318275CB6A3920514872A35741C0B89670B9C85A6431286C29735BA041A2018B9673C54137652B4C09A8B8170349256CA358BA6C24710959401C8BA672347AC61089253B
9988 0123456789ABCA469870C3B51243C75129608AB1085CA3B2679486B1A45092C37273C69B4A8105C8421B760A9536A18B2C34507992A40815B73C6597A3642C1B80BC5690A8732417B9023815C46A350B7C9A14628
9989 0123456789ABC3A5079C862B14C0478356AB291B71C3A29504861BA890324C567A5B1064398C7223C6B471059A89C8A2B15367407605A89B241C384796CA0B1325426BC70A13859689251B4C703A5934128C7A60B
9990 0123456789ABC4A6BC12037859C21890B57364AA409827B61C35253169CA04B8710CA3782B549658B2043C967A189752A14C036B634C7B582A9107C94A8065B123B6801C93A25743BA75649180C29756B3A14C208
9991 0123456789ABC4957BC836120A8AB4375C20961C5082AB634197B290C8A1576435C36012BA847990CBA23546718AB72569413C8064198BC07A3527681934AB20C513AC69780B524376514029C8AB284A7019C5B36
9992 0123456789ABC6A04BC91238578052CBA364179C3AB812907465467C18B2A5390A24739861C50B1B9A574036C8274C163085B92AB8190675CA2439568743AB20C13CB62A54907185980A2CB716342735901C48BA6
9993 0123456789ABC5B0A812C964377492CA3058B164368901AC527B98C6AB514270367513C820B9A4A01B2478635C9128906B57C34ABA47129630C85C67058A3B41922CA4B3091765839B567C4A1820853C794B2A061
9994 0123456789ABC3A14C2805B9679C35870412BA643B1A0C278659C57896BA2340172461B950C83AAB620C739451827C0B4A865193508C39164A27BB85A2149367C064095A31B7C8289A7635BC1024169B782CA0345
9995 0123456789ABCA4C1265B07938CA6203159874B63B789201AC5438A512C640B79B549AC01368271C36BA827459072143BA95C086807A914CB23659B80C7342561A495B6078A32C156087493CB1A2279C58BA61403
9996 0123456789ABC587290A13C46BC74B382A9150626091A5BC87434B965783A2C10105A8C79B3624B368C4105A97235A7029614BC88C15B642703A9A9C021346B8579A347BC5062816481A9BC2703572BC63084519A
9997 0123456789ABC92567BC30A814A01C36B4785293A69BC81274057592610B4C38A59BA8416320C78407293CA615B187B0A9563C4263A59028C4B714730C85A1B296BC81A24950763CB481372956A026C457A0B1938
9998 0123456789ABCC43B581A72609B5AC0491287632C4681350B97A806219BC5A4371B5467293C8A06A097C8B413257285C6A3B019438C02A749651B97BA3046C52815917A2C063B48A3789B52140C64691B308A7C52
9999 0123456789ABC4BC5A10637298C71439285B06A32489C50B16A7A9B158C26470365901234CA87B208B6A794C3519A67CB43185205C39278BA0416B80A749C261357652B0A193C84137C86BA0594284A6031572BC9
10000 0123456789ABCCB576103A824937962C480A15B93CAB4856702148BC72569031AA04518B2C397684A9C73B21605B28456913C7A0267180A954BC3756B3AC0124986902A314B5C871A38097C4B5625C109B2A76834
10001 0123456789ABC4C62A95B738108475C2BA9603160AB3C2415789981A2340B75C61307B8962C4A5B65490A2C817329C014836AB57CAB68701543925B496A7C31208A73156C80294B32987B1540C6A758C0139AB624
10002 0123456789ABC95B81AC473602A4720B81963C5BA91603C258478915C40267BA350A7364BC812927C6B3A051498C65427983B01A3C0B89254A7614839ACB6125707B405213AC986628A7159B0C34136C987A0425B
10003 0123456789ABC78C0963A52B141A948B03C56272C6A107B348953247B9A608C5159BC0142A37689731CA582B046B602A7841C539407B3C156A982A519682C4730BC3A854B1962706B852390714CA845672C9B01A3
10004 0123456789ABC974C325861BA040B72189AC6531B38062547C9AA29018C6B453759C673A10B84228A56B9C73401637BC04A5812976098AB4C2315CA62B40315978BC5497103A286841A5C329076B3581A97B260C4
10005 0123456789ABC5308ACB216947A254970C6831B176C58932B0A44690B1A852C73B08A7436C5291C9B236804715A8415207A9CB366CAB194573802354962CBA17809B7183240A6C57AC60B19345282837CA51B0469
10006 0123456789ABC7685CB2A319402A9CB38140567A40289C567B13C058A7B2164394B715C962A30859472138BC0A617B90854A36C263CB94105827A8C3062A97B15498A61043C572B321A760B94C85B5643A7C02891
10007 0123456789ABCB3A1C60548297C96B2078A41357AC26914B38504579B1A620C838B4C1A906537250978243C6BA1671438C90B52A980A73B2516C41485972A3C06B2CB854319A7063650AB8C72419A2360C5B17948
10008 0123456789ABC875B0A4163C2964BC82037A1959238C710A645B504791C6B83A21B702CA8945362C6AB9341508735A16092CB874C912748A50B63B385A679412C0A8945B2C376017AC6135B02948460938B52C71A
10009 0123456789ABC9C0586A137B424B6C0A8395721A372509C1B68478B61249A30C53710B9C2645A88247AC350196B56C9382B4A107B584930A7C216C4A12B76583901A5867B0C2439209A7418B6C53693BC1542087A
10010 0123456789ABC6248A1903CB75C09276B3A4158B78502314AC961B36C854927A0596C3B127840A4A702986B35C19814B02AC56372C096A751B84383AB5C4967012765194AC2038BA4C7830B5126935BA17C806924
10011 0123456789ABC58BA9C14276308471B3206C59AA9C572360B4817C3960521AB483A542198B0C76109BC4A3728652510897BC63A4B68C0A4935127CB02A68194753936758CA4120B67481B05A39C242A637BC58019
10012 0123456789ABCC5381B096A274731A0C459B8624C7B593A0612816C9278BA430587A53410B29C6B241809C5763A2A0791C645B83A964B2783C5106B9273A4C80519056A82371C4B5480C6B1237A938BC6A5210497
10013 0123456789ABC2BC6798A035411067C49BA28359CB450A6312785A483B2C70196B4A09C1268753683107549CB2A798B26C1543A0369CBA7825014457982031AC6B870A1345B69C2C352A1B047689A2156839CB407
10014 0123456789ABC1C8B627A340599B563A240C817B37A8C052149685B1709C462A3A93C1456B87025A94C6B2701386402A789135CB271809A36BC4570C95318A2B6446A7B8C195320C240913B5768A38652B40CA971
10015 0123456789ABC8A9261CB734053C10964A27B5873CB02A61458958B47903A1C26B635A481C2790AB461798052C31068532CBA974C7A120395684B2457CB109863A4289BC75603A1950A38B24C167697C8A543B012
10016 0123456789ABC76C4A35B902818A4761952B3C0C8657AB03491237029846B1C5A539C8BA167024948B5C2A136074C30B718A2569A51809C27643B12BA30895C746B059263C4A17829761403C8BA56BA1C27405893
10017 0123456789ABC63841A5B9C027C0B693A5127484A6C7820B3159A97B61C248305BC42890A5167324A5BC130798637CA2B48605919B0154367A8C27230A689C541B5897C0B13426A165837942BCA08519027CA6B34
10018 0123456789ABC4B6A9710C52387591C042A3B86C2368AB190457530C7428169ABB4592CA63187096B413850A7C2387B620A5C14987A0519C4B6231C870634B259A2A45B8C96730169C2AB5378014A018397B24C65
10019 0123456789ABC52B786C4931A0AB920C7516348371CB4280569A853B6A1C479029401A3B2587C64C6579832A01B7658209AB1C346A891B507C423C8A6910B34275237A5841C0B691940C236AB857B0C437A962581
10020 0123456789ABC1308C25B4A679B0A27915C6843791653AC0B482356AB87092C142B9C048A7315687513B246C9A06CB4A10958327C28B60431579AA8402C9137B654A3796C82150B94758A36B02C156C917B2A4038
...
Возьмем имеющийся в распоряжении спектр числа диагональных трансверсалей в ДЛК порядка 13 и применим к нему преобразование его расширения путем построения окрестностей в ходе вращения 1 интеркалята. На данное преобразование потребовалось чуть более 1 часа вычислительного времени одного ядра Core i7 4770, в результате получен спектр из 1284 элементов, представленный в графическом виде ниже. Его беглый анализ показывает, что сделанное преобразование слегка увеличило ширину сплошной полоски в составе исходного спектра в обе стороны.
Возьмем имеющийся в наличии спектр числа диагональных трансверсалей в ДЛК порядка 13 и добавим к нему элементы, получающиеся от циклических ДЛК. После этого применим к полученному спектру преобразование, основанное на анализе окрестностей, получаемых поворотом 1 цикла (для спектра целиком). В результате за 3 часа работы Core i7 4770 в 1 поток получен спектр, включающий в своем составе 1348 элементов. Его анализ показывает, что появились новые точки, расположенные в трех местах:
* самый низ картинки (там где много трансверсалей: 127339, 127830, 128489, 128519, 128533, 128608, 128751, 128818, 128861, 129046, 129059, 129171, 129243, 129286, 129353, 129474, 129641, 129657, 130323 и 131106 диагональных трансверсали);
* чуть ниже основной группы точке в спектре (10650, 10652, 10660, 10673, 10675, 10679, 10682, 10691, 10719, 10731, 10738, 10770, 10952, 10994, 11061, 11172, 11353, 11386, 11477, 11484, 11806, 11853, 12628, 12924, 13000, 14135 и 14162 диагональных трансверасали);
* чуть выше основной группы точек в спектре (9119, 9140, 9147, 9163, 9177..9178, 9185, 9225, 9239, 9247, 9253..9254, 9258, 9266, 9287, 9298, 9300..9301, 9305, 9307..9308, 9310..9315, 9318, 9320..9322, 9324, 9326..9330, 9333..9340, 9342..9344, 9346..9348, 9350..9358, 9360..9362, 9364..9369, 9372..10525, ...).
Совместив ряд преобразований пандиагональных ДЛК (повороты на 45 градусов, перестановка строк, M-преобразования) с исследованием окрестностей путем вращения 1 интеркалята за ~5,5 ч расчета на Core i7 4770 в 1 поток спектр числа диагональных трансверсалей в ДЛК порядка 13 удалось расширить до 3761 значений. Расширение произошло от имевшейся ранее сполшной полоски в сторону большего значения диагональных трансверсалей в ДЛК.
Выполним расширение спектра, изначально полученного от циклических ДЛК в сочетании с рядом эквивалентных преобразований, путем анализа окрестностей, получаемых вращением 1 цикла в ДЛК. В результате за почти 10 ч расчета в 1 поток на Core i7 4770 получен спектр, включающий в своем составе 4098 элементов. Анализ спектра показывает, что его расширение в основном произошло чуть выше сплошной полосы в его составе. Глазом видно, что полученный спектр скорее всего допускает расширение, т.к. глазом видны "битые пиксели" в его составе.
Цитата: Yura12 от 14.12.2021, 06:26
Что но...? Неужели сейчас нет ни одного студента, который бы увлекался программированием, оптимизацией кода? Я вот помню когда мы были студентами в конце 90-х так всё свободное время были заняты компьютерные классы, там все добровольно и увлечённо занимались программированием, оптимизировали код на Паскале и Ассемблере. Я даже статью в 2000 делал: http://jkfs.petrsu.ru/~yura/pyldin/opt6800.htm
Неужели современная молодёжь, студенты уже совсем стали от этого далеки?
Увлекаться - одно дело, другое дело что-то реально в этой области уметь делать, а для этого уже опыт нужен. Сейчас времена другие, плюсами никто не интересуется, сейчас JS, "хуяк-хуяк и в продакшн". За оптимизацию сейчас даже никто по сути не платит, потому что это дорого и не нужно: всегда можно купить на один инстанс Амазона больше.
Посмотрите как-то на досуге рейтинг ЯП и поймёте, что то, что было 10 лет назад и более, давно уже не актуально.