И еще немного о двоичной системе
Немного с алиасингом поиграемся. Без предисловия. Под кат.
В предыдущей записи разобрались с делением. А как у нас обстоят дела с умножением?
Двоичные числа по порядку:
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, таких последовательностей существует больше миллиарда.
Думается мне, для перебора всех возможных последовательностей, сюда отлично впишется генетический алгоритм. Но это как-то в другой раз.
В предыдущей записи разобрались с делением. А как у нас обстоят дела с умножением?
Двоичные числа по порядку:
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, таких последовательностей существует больше миллиарда.
Думается мне, для перебора всех возможных последовательностей, сюда отлично впишется генетический алгоритм. Но это как-то в другой раз.