Нерегулярное множество Мандельброта

Фрагмент нерегулярного множества Мандельброта.

На этот необычный фрактал я наткнулся некоторое время назад, перебирая различные вариации множества Мандельброта. Оригинальное множество Мандельброта строится путём итерации по формуле \(z_{n+1}=z_n^2+c\) с начальным условием \(z_0=0\). нерегулярное множество Мандельброта получится, если поочерёдно подвергать комплексное число \(z\) двум немного различным преобразованиям, причём делать это по неповторяющейся схеме, например, так:

$$z_{n+1} = \begin{cases}z_n^2+kc & \text{if }n=1,3,6,...,(m^2+m)/2,... \\z_n^2+c & \text{otherwise}\end{cases}$$

где \(k\approx1.001\) - коэффициент, незначительно отличающийся от единицы. Здесь предлагается применять первое преобразование для тех итераций, которые являются треугольными числами. Этот выбор достаточно произволен, другие апериодические схемы дают сходные результаты.

Несмотря на то, что формулы отличаются всего на 0.1%, отсутствие периодичности оказывает огромное влияние на вид фрактала. Это очень хорошо заметно на спиральных участках, таких как на верхней картинке. В обычном множестве Мандельброта подобные спиральные фрагменты образованы масштабированным повторением практически одинакового узора, в то время как в нерегулярном варианте узор постоянно изменяется, спиральные ветви хаотично изменяют свою ширину, между ними образуются спайки и разрывы.

Пример регулярного варианта того же фрактала, где две формулы применяются поочерёдно. Спираль образована повторением практически одинаковых элементов.

Можно предположить, что причина такого эффекта в том, что апериодическая итерация не позволяет возникать устойчивым периодическим аттракторам.

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

Монохромня раскраска, чёрный - область устойчивости. Для просмотра рекомендуется пройти по ссылке и открыть исходное изображение 1600x1600.

Остальные изображения этого фрактала есть в галерее, вот ещё одно.

Горящий корабль

Горящий корабль: общий вид.

Фрактал с образным названием "Горящий Корабль" (английская вики) это одна из многих модификаций множества Мандельброта, с формулой итерации: $$Z_{n+1} = \left(|\Im(Z_n)| + i|\Re(Z_n)|\right)^2+C.$$ и начальным значением \(Z_0=0\). Отличие от обычной формулы для множества Мандельброта: \(Z_{n+1}=Z_n^2+X\) в том, что перед возведением в квадрат действительная и мнимая части числа лишаются знака. Так как такое отображение неголофморфно, фрактал приобретает более хаотичный вид, чем привычное множество Мандельброта. Тем не менее, он также проявляет те же признаки самоподобия и содержит в себе бесконечное разнообразие форм. Вот несколько примеров (ссылка ведёт на исходное изображение размером 2400x2400, трафик!).

"Архиватор" Бабушкина

Ставший недавно интернет-знаменитостью барнаульский студент Алексей Бабушкин, среди прочих изобретений предложил идею новаторского алгоритма сжатия данных.  Мне этот алгоритм показался хоть и бесперспективным с точки зрения сжатия, но достаточно любопытным, чтобы попробовать его реализовать.

Работающий код можно скачать с Github: babushkin_arch.

Примеры использования программы

Кодирование (сжатие)

$ python babushkin_arch.py original.txt encoded.dat

Декодирование:

$ python babushkin_arch.py -d encoded.dat decoded.txt

Сложность алгоритма достаточно быстро растёт по мере роста объёма файла, практический верхний предел размера - около 100Кб, при этом требуется порядка 10-20 минут времени. Файлы размером несколько килобайт преобразуются за секунды.

Алгоритм

Рассмотрим работу алгоритма на примере сжатия строки с текстом “hello world”

1. Байты исходного сообщения записываются в 16-ричной системе счисления:
   “68 65 6c 6c 6f 20 77 6f 72 6c 64”.
2. К получившемуся длинному 16-ричному числу спереди дописывается десятичная точка, тем самым получается конечная 16-ричная дробь, значение которой лежит в полуинтервале [0;1):
   X = 0.68656c6c6f20776f726c64₁₆ = 0.4077976...₁₀
3. Подбирается (способ описан ниже) простейшее рациональное число P/Q, которое с достаточной точностью приближает X. В данном случае минимальной дробью будет число:
   X^* = 9a808e9d263₁₆ / 17adea823736₁₆ 
4. Числитель и знаменатель найденной дроби, а также длина исходного сообщения и являются результатом "сжатия".

Несложно заметить, что качество "сжатия" невелико: исходная последовательность из 22 шестнадцатеричных цифр заменяется двумя последовательностями из 11 и 12 цифр соответственно.

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

Реализация

Автор полагал, что поиск подходящей дроби P/Q≈X может занять огромное время, однако это не так. Используя подходящие алгоритмы и современные компьютеры, несложно найти простейшие рациональные представления дроби для чисел с сотнями тысяч 16-ричных знаков после запятой.

Математика

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

Любое число можно единственным образом представить в виде подобной "многоэтажной" дроби с натуральными коэффициентами. При этом для рациональных чисел “лестница” всегда будет конечной и наоборот.

Замечательным свойством цепных дробей является то, что, отбрасывание нижних “этажей” даёт наилучшие рациональные аппроксимации для числа x. Тем самым, задача построения рациональной аппроксимации может быть решена так:

1. Записать для исходного числа цепную дробь.

2. Отбрасывать у цепной дроби нижние этажи, пока сохраняется достаточная точность.

3. Свернуть последнюю цепную дробь в обычную – это и есть наилучшая аппроксимация.

Например, для числа x=0.2941=2941/10000 цепная дробь запишется так:

Оставив в этой дроби 4 верхних этажа, получим аппроксимацию:

Таким образом, нужные 4 десятичные цифры числа x можно получить, вычислив гораздо более простую дробь: 5/17.

Нужное количество этажей определить несложно. Достаточно рассмотреть цепные дроби для двух чисел: нижней (0.2941) и верхней (0.294199999...=0.2942) границ подходящих чисел. Первый различающийся коэффициент двух разложений покажет место отсечения. (Последним коэффициентом в сокращённой цепочке будет меньший из двух различающихся коэффициентов, увеличенный на 1)

Анализ алгоритма

Первый приведённый пример показывает, что на небольших объёмах данных сжатия не наблюдается. Увы, как несложно убедиться, для большинства файлов более солидного объёма результат тот же самый: результат "сжатия" на несколько байт больше исходного файла. Впрочем, для некоторых файлов "архиватор" всё-же работает.

Например, рассмотрим файл helloworlds.txt размером 126 байт со следующим текстом (без переноса строки в конце!):

Hello world world world world world world world world world world world world world world world world world world world world

Сжатый файл имеет размер 30 байт, налицо сжатие в 4 раза! Однако даже единственный перенос строки, добавленный в конце файла, разрушает эффект.

Причины такого поведения понять несложно, если знать свойства n-ичных представлений рациональных чисел. Известно, что десятичная запись любого рационального числа после некоторого момента начинает повторяться. Например:

$$\frac 5 {14} = 0.357142857142857142857... = 0.3(571428)$$

То же самое верно и для любой другой системы счисления. Верно и обратное: десятичная дробь, которая с некоторого момента содержит повторяющуюся последовательность - рациональна. Как правило, чем короче период и непериодическая часть, тем меньше числитель и знаменатель рационального числа. Таким образом, файлам, которые заканчиваются многократным повтором одной последовательности символов, соответствуют простые рациональные дроби, и наблюдается хорошее сжатие. Алгоритм Бабушкина действительно способен уменьшить размер файла, но обнаруживает только очень специфичные закономерности, сильно уступая более "всеядным" традиционным алгоритмам сжатия.