RakeSearch - ОДЛК, порождаемые перестановкой строк
Немного про заполнения и интересную ортогональную пару!
(копию/оригинал новости в VK вы можете найти здесь)
Ранее мы рассказавали о новом поиске R10 в рамках проекта RakeSearch, последовавшего за поиском "перестановочных" диагональных латинских квадратов 9 ранга (он же - поиск R9). Сейчас появился повод рассказать о некоторых его деталях!
На изображении ниже - матрица квадрата 10 ранга, клетки которой раскрашены в несколько цветов:
- серым цветом отмечена верхняя строка с зафиксированными значениями клеток - {0, 1, 2, ..., 9} (выходить за рамки квадратов с такой строкой (они же - нормализованные квадраты) - нет смысла, т.к. ненормализованных квадрат может быть сведён к нормализованному);
- красным цветом обозначены клетки главной и побочной диагоналей, не относящиеся к первой строке;
- оранжевым цветом обозначены клетки первой и второй строки которые вместе с диагоналями и первой (фиксированной) строкой заполняются ещё на этапе генерации workunit-а;
- зелёным цветом обозначаются клетки, заполняемые во время обработки задания на компьютере участника - вычислительный модуль, заполняя матрицу до конца, формирует всё новые и новые диагональные латинские квадраты и переставляя в них строки, пробует получить ортогональную пару из исходного (только что сформированного) ДЛК перестановкой его строк.
Как вы также можете видеть, все красные и оранжевые клетки пронумерованы в определённом порядке. Это порядок по которому они заполняются, при формировании комбинации для очередного workunit-а. При этом, клетки самой верхней, фиксированной строки - не пронумерованы потому, что они не меняются и какая бы не получилась комбинация в других клетаках - они в ней всегда присутствуют в одном и том же виде.
Интереса ради, мы можем посчитать - сколько же возможно комбинаций, которыми можно заполнить самую первую пронумерованную клетку, или первые две, или три... и так далее. Если получившиеся числа выписать в табличку вида {Число клеток, Число заполнений} то мы получим ряд, возрастающий почти всё время (но не всё время) и с темпом, менающимся от клетки к клетке. Для первых 28 клеток, пронумерованных на изображении он получается таким:
1 - 8
2 - 57
3 - 356
4 - 1909
5 - 8544
6 - 30637
7 - 82508
8 - 148329
9 - 133496
10 - 934472
11 - 5356527
12 - 26980186
13 - 117013695
14 - 424874652
15 - 1210593966
16 - 2603495520
17 - 3755155200
18 - 2723433984
19 - 17021462400
20 - 82230388428
21 - 341712006852
22 - 1187460703344
23 - 3329849282564
24 - 7024312609228
25 - 9908083279232
26 - 7996577754080
27 - 43965973715660
28 - 212963246290200
Первые ~18 строк этой таблицы (или членов ряда - кому как больше нравится) вычисляются очень быстро - на отдельно взятое число уходят доли секунды, секунды или минуты в один поток, на уже давно выпущенном процессоре Intel Core i5-3570K. Чтобы пойти дальше, надо произвести намного больше вычислений - к примеру, для получения 28 члена ряда потребовалось ~50 суток процессорного времени CPU с архитектурой Haswell.
Но это число - 212963246290200 - интересно и другим. Как говорилось в самом начале, на первом изображении показано заполнение матрицы квадрата при генерации workunit-ов. А это значит, что каждая коминация заполнения этих клеток - это отдельный workunit. А число комбинаций, которыми мы можем заполнить эти клетки, соответственно, это и есть число workunit-ов, которые мы могли бы сгенерировать, если бы решили выполнить поиск по всему пространству ДЛК 10 ранга! Или, 212 триллионов 963 миллиарда 246 миллионов 290 тысяч 200 workunit-ов! Конечно - это слишком много и поиск будет только частичным, по небольшой части от возможно пространства.
Но даже в рамках частичного поиска, можно наткнуться на что-нибудь интересное. И об этом - новость № 2!
В каждом результате, приходящем с компьютера участника проекта, записываются пары со степенью (или "характеристикой") ортогональности более 80. И в каждом результате таких находится как минимум несколько штук. По мере обработки результатов - накапливается статистика о том, сколько пар с той или иной степенью ортогональности было обнаружено. По итогам сентября (то есть, за июль, август и сентябрь вместе взятые) она выглядела следующим образом:
Degree 81: 3887427
Degree 82: 899172
Degree 83: 181014
Degree 84: 33997
Degree 85: 5254
Degree 86: 900
Degree 87: 94
Degree 88: 16
Degree 89: 0
Degree 90: 0
...
Degree 100: 0
Хорошо видно, что переходе к следующей степени ортогональности число найденных пар уменьшается где-то в 4-6 раз. Но при переходе от степени 86 к 87 - разница уже почти в 10 раз (возможно - это временное явление и при дальнейшем накоплении статистики - мы увидим что-то иное), а после степени 88 - уже нет ничего, хотя если бы тенденция соблюдалась, мы должны были бы увидеть от 1 до 3 пар со степенью ортогональности 89!
И вот прошла первая половина октября. Что мы видим в результатах за эти две недели? А вот что:
Degree 81: 1329684
Degree 82: 330656
Degree 83: 74528
Degree 84: 14608
Degree 85: 2624
Degree 86: 400
Degree 87: 47
Degree 88: 6
Degree 89: 0
Degree 90: 1
Degree 91: 0
...
Degree 100: 0
- всё почти тоже самое - даже разрыв между степенями 86 и 87 до карикатурности похож на общую статистику, также нет ни одной пары со степенью 89... но есть 1 пара с 90! К тому же, если мы прибавим число пар с ХО = 88 (ХО - это "характеристика ортогональности", она же - "степень") найденных в первой половине октября к общей статистики, то получим 6 + 16 = 22! А ведь примерно таким (т.е. где-то 25 к 1) и должно быть, судя по статистике, соотношение числа пар на двух ступенях, отстоящих друг от друга на 2 уровня - как в случае с ХО = 88 и ХО = 90! Вот только промежуточное звено с ХО = 89 "куда-то пропало"!
Что это? Какая-то закономерность? Случайность? Что-то ещё? Увидим!
Ну, а саму пару с ХО = 90 - вы можете увидеть на втором изображении. Вот она:
Нашли её - josef j из команды Russia Team и Thyler Durden@P3D из команды Planet 3DNow!, однако вычисления каждого участника приближали эту находку. А может быть, (кто знает?) - и чего-то ещё!
Спасибо за участие и поддержку!