И еще немного о двоичной системе

xcontcom — 03.05.2018 Немного с алиасингом поиграемся. Без предисловия. Под кат.




В предыдущей записи разобрались с делением. А как у нас обстоят дела с умножением?

Двоичные числа по порядку:
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
и т.д.

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



Пока ничего необычного. А что, если попробовать отобрать числа кратные некоторому Z. Для разных Z:



Тут хорошо видно, что для чисел кратных k*(2^n) получаем числа кратные k со сдвигом на n бит влево.

Для Z=(0, 416):



Попробовал уменьшить количество разрядов и увеличить количество чисел в каждом столбике:



Тут видно некий паттерн, который проходит через все столбики! Чтобы сделать этот паттерн более явным - запихнем наши числа в трехмерную матрицу, где Y - число кратное Z, а X - разряд в двоичной системе. Или, проще говоря, взяли эти столбики выше и сложили их один на другой. Теперь можно сделать срез по координате X.

Первые 8 разрядов (младший разряд будем считать нулевым):



Размер повторяющейся части паттерна равен 2^(n+1), где n-разряд. Картинка быстро выходит за область прорисовки, поэтому написал скрипт, позволяющий двигать паттерн.



Возьмем наш 7-й разряд и подвинем на 64 пикселя влево (z+64) и на 64 пикселя вверх (y+64):



8-й разряд (128+64 влево и вверх):



9-й разряд (256+128 влево и вверх):



11-й разряд, центр симметрии:



15-й разряд. Размер повторяющейся части = 65536. Центр симметрии:



Каждый паттерн в младшем разряде - уменьшенный паттерн (в два раза) из старшего разряда. Паттерн уменьшается и теряется детализация. Это очевидно. Если мы наш делитель Z умножим на два - получим сдвиг всей нашей матрицы по оси X. То есть, вся эта ахинея сдвинется на один разряд вверх. А что если мы наш делитель на 3 умножим? Поехали.

Z*3 (первые 8 разрядов):


Z*4 - матрица на 2 разряда сдвинется.

Z*5:


Z*6 - получим матрица умноженная на 3 со сдвигом на 1 разряд.

Z*7:


Z*8 - степень двойки. Сдвиг на три разряда.

Z*9:


Z*10 - Z*5 со сдвигом на 1 разряд.

Z*11:


Z*12 - сдвиг Z*3 на два разряда.

Z*13:


Z*15:

Вот тут, кстати, у нас в 7 разряде хорошо видно, что паттерны обладают самоподобием (привет, фракталы).

Z*17:


Z*19:


Z*21:


Первые 4 разряда далее можно не рассматривать - они повторяются.
Z*23 (4, 5, 6 и 7 разряды):


Далее от 25 до 55 все нечетные.
Для 4 разряда:


Для 5 разряда:


Для 6 разряда:


Для 7 разряда:


От 57 до 87, 7-й разряд:


Откуда берутся эти паттерны?

Вернемся к нашим столбикам.



Если не изменять Z, то есть оставить его постоянным (=1) для всей матрицы, эти столбики будут выглядеть вот так:



Дальше, если мы сделаем срез по X для матрицы, чтобы посмотреть, что находится в разных разрядах двоичного числа - увидим горизонтальные линии:



То есть, в нулевом разряде находится:



В первом разряде:



И т.д.

Теперь, если мы изменяем Z - мы берем в каждом столбике цифру, индекс которой кратен этому самому Z. В первом столбике - все цифры, во втором - 2, 4, 6. В третьем - 3, 6, 9. Вот так для нулевого разряда:

Остается выровнять по верхнему краю, убрав все не выбранные цифры. Получаем паттерны.

Проверяем.

Шаблон у нас одномерный - хватит одномерного массива.

Берем для каждого элемента массива остаток от деления индекса на 256. Если остаток меньше 128 - помещаем в массив 0. Если больше или равно - 1.

Проверяем шаблон:




Отлично. Применяем к шаблону наш алгоритм:



Паттерн совпал:



А вот тут самое интересно начинается. Наш начальный шаблон (массив) можно заполнить произвольной двоичной последовательность (повторяющейся)!

Не обязательно физически делать массив очень длинным и заполнять его повторяющейся последовательностью. Достаточно взять остаток от деления (x*y) на длину повторяющейся части и этот остаток использовать в качестве индекса (номера элемента в последовательности). Пример:

Есть у нас массив:
[0, 0, 0, 0, 1];
Длина массива = 5. Допустим, нам надо брать каждый 3-й элемент (нумерация элементов начинается с 0).

Берем
0*3 = 0. Остаток от деления 0 на 5 = 0.
[0, 0, 0, 0, 1];
1*3=3. Остаток от деления 3 на 5 = 3.
[0, 0, 0, 0, 1];
2*3 = 6. Остаток от деления 6 на 5 = 1.
[0, 0, 0, 0, 1];
3*3 = 9. Остаток от деления 9 на 5 = 4.
[0, 0, 0, 0, 1];
4*3 = 12. Остаток от деления 12 на 5 = 2.
[0, 0, 0, 0, 1];

Фактически:
[0, 0, 0, 0, 1]; - взяли первый элемент
[0, 0, 0, 0, 1]; - взяли элемент через два
[0, 0, 0, 0, 1]; - уперлись в конец последовательности, продолжили считать от начала
[0, 0, 0, 0, 1];
[0, 0, 0, 0, 1];

В качестве примера возьмем вот такой начальный шаблон (повторяющуюся часть последовательности):
[0, 1]; - для первой итерации
[0, 0, 1]; - для второй
[0, 0, 0, 1]; - третьей
[0, 0, 0, 0, 1]; - четвертой
и т.д.

Скрипт выглядит довольно просто:



Результат:



Шаблон [0, 1, 1]. На каждой следующей итерации добавляем к шаблону слева 0:



[0, 1, 1, 1]:



[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]; - начальная последовательность. На каждой итерации добавляем слева 0. В качестве индекса берем: [(y*x*z)%l]



Двоичных последовательностей длиной n существует 2^n штук. Просмотреть их все невозможно. К примеру, если длина последовательности = 30, таких последовательностей существует больше миллиарда.
Думается мне, для перебора всех возможных последовательностей, сюда отлично впишется генетический алгоритм. Но это как-то в другой раз.

Оставить комментарий

Популярные посты:

• Ранее
• Архив