В этой статье я расскажу про то, что я очень давно намеревался сделать в D, но никак не получалось и постоянно вылезали разные непреодолимые (на тот момент) ошибки. Разумеется, будет описан весь эксперимент с очень простым и легко читаемым кодом, и вы легко сможете его повторить, используя текущую версию dlib.
Эксперимент будет, как обычно, с математической графикой, и на этот раз познакомлю вас с самореферентной формулой, которая называется формулой Таппера.
Формула Таппера — это необычное неравенство, открытое Джеффом Таппером, которое при определенных условиях является самореферентным (т.е ссылается на само себя). В контексте неравенства, самореферентность означает то, что при некоторых параметрах, подставляемых в саму формулу, его графический образ будет представлять собой изображение самого неравенства. Если говорить проще, то получается так, что неравенство начертит на плоскости само (!) себя.
Сама формула выглядит следующим образом:
Знак «половинных квадратных скобок» обозначает взятие целой части числа, а mod — остаток от деления.
В качестве параметров в формуле фигурируют x и y, которые в данном случае следует рассматривать как координаты точек, которые удовлетворяют неравенству (т.е делают его истинным при подстановке указанных параметров). Также, формула Таппера ограничивает набор значений, которые могут принимать переменные: для x диапазон значений простирается от 0 до 106 (включая границы интервала), а для y диапазон простирается от k до k + 17 (также включая границы интервала).
А что такое k ?
Это очень большое целое число, которое содержит очень много цифр и которое при этом создает проблемы, поскольку не помещается ни в один из элементарных типов D (в дробные, конечно, поместится, но потеряем некоторые цифры, а они тут все без исключения являются значащими).
Выглядит k довольно внушительно (544 цифры !):
Если использовать это число в неравенстве и применять при этом указанные диапазоны для точек, то на плоскости отобразится маленькое чудо — скромное графическое изображение формулы Таппера (естественно, без диапазонов для x и y):
Именно это мы попытаемся повторить, для чего создадим пустой проект в dub и добавим в него в качестве зависимости библиотеку dlib. Эту библиотеку мы будем использовать для того, чтобы получить оригинальную картинку. Также, dlib — это единственная сторонняя зависимость в нашем проекте.
Первое, что после создания проекта необходимо сделать — это создать реализацию вычисления формулы Таппера для произвольных x и y. На самом деле, при такой казалось бы тривиальной задаче нас ждут проблемы: как в программе представить число k и каким образом над ним выполнять все те операции, которые представлены формулой Таппера ?
Решение проблемы предоставляет сам D: в его стандартной библиотеке есть модуль std.bigint, котрые позволяет создавать большие целые числа и оперировать ими. Т.е по сути D предоставляет нам средство работы с арифметикой произвольной точности или длинной арифметикой. Также, нам по сути дела не нужно делать ничего лишнего, так как практически вся необходимая арифметика определена в std.bigint.
Формула Таппера тогда будет выглядеть следующим образом:
import std.bigint;
import dlib.image;
auto tupper(BigInt k, int x, int y)
{
auto ny = y + k;
auto a = ny / 17;
auto b = ny % 17;
auto c = 17 * x + b;
BigInt d = BigInt("2") ^^ c;
return ((a / d) % 2) > 0.5;
}
Как видите, ничего необычного: для работы с длинными числами нужно просто создать структуру BigInt и передать ей в качестве параметра строковое представление числа (т.е просто записать все цифры длинного числа в одну строку). Данная структура поддерживает базовые математические операции, что значительно упрощает дело. Но, как вы видите реализация формулы не сделана прямо «в лоб» и вот почему:
- сама формула очень длинная и в ней легко ошибиться при наборе, поэтому я ее разбил на элементарные операции;
- я изменил ход операций в формуле. Дело в том, что возведение двух в отрицательную степень с указанными в неравенстве значениями приведет к двум очень нехорошим вещам: смещению результата в область нуля (поскольку все вычисления проводятся в области целых чисел) и возникновению floating point exception, т.е к возникновению аппаратной ошибки деления на ноль. Для того, чтобы этого не произошло, я заменил возведение в отрицательную степень на возведение в положительную с последующим делением на полученный результат (тривиальное представление отрицательных степеней);
- не стал реализовывать взятие целое части, поскольку сама реализация длинной арифметики решает этот вопрос: результат деления будет в любом случае длинным целым числом;
- сделал так, что функция стала принимать три параметра, т.е помимо упоминавшихся x и y, она стала принимать число k в качестве параметра (почему, объясню чуть позже).
После того, как определена функция, показывающая удовлетворяет ли некий набор параметров (x, y) неравенству, стоит определить два цвета: белый цвет для тех точек, координаты которых удовлетворяют неравенству; и черный — для тех точек, координаты которых не являются решениями неравенства:
private
{
enum WHITE = Color4f(1.0f, 1.0f, 1.0f);
enum BLACK = Color4f(0.0f, 0.0f, 0.0f);
}
Имея обозначения точек для графического образа неравенства, можно получить его в виде простой картинки в формате PNG. Для этого, необходимо пройти в цикле по диапазонам параметров x и y, вызывая функцию tupper, которая подскажет нам, как именно нужно раскрасить точку (x,y) черным или белым:
void main(string[] args)
{
auto img = image(108, 40);
BigInt k = BigInt("4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300");
foreach(x; 0..107)
{
foreach(y; 0..18)
{
img[x, img.height / 2 - y] = tupper(k, x, y) ? WHITE : BLACK;
}
}
img.savePNG("tupper.png");
}
Полученное изображение на скриншоте (сильно увеличено):
Как это работает ?
Все дело в числе k, ведь именно оно содержит в себе изображение, которое получается из формулы Таппера. Это число является простейшим монохромным растром, и в двоичном виде представляет собой набор битов, которые если их раскладывать построчно (вертикальная строка длиной 17 бит) и составляют полученную картинку. Следовательно, само неравенство представляет собой набор операций для пошагового извлечения битов из некоего растра k (который представлен обычным десятичным числом длиной 106 * 17 битов) и отображения их на плоскость. Также, число k не обязано быть именно таким, каким оно было показано в начале статьи, что приводит к еще одному выводу: выбрав произвольное k можно получить единственное ему одному соответствующее изображение (можете убедиться в этом здесь) — и поэтому функция tupper принимает в качестве одного из параметров k !
Конечно, это не все нюансы данного алгоритма: например, я не упомянул о том, что при отрисовке было применено смещение по оси Y, поскольку без этого картинка получается зеркальной, а также, без указания смещения картинка из растра k может выйти за пределы изображения (точнее, часть картинки окажется внизу от нижней границы изображения), но это на мой взгляд, делает алгоритм интересным для изучения. Особенно, интересно будет в том случае, если вы рискнете побаловаться с константой k, либо пройдя по упоминавшейся ссылке, либо собственоручно написав перекодировщик монохромного изображения размером 106х17 в растр k…
Но это уже совсем иная история…
P.S: Полный код примера (включая константу k):
import std.bigint;
import dlib.image;
auto tupper(BigInt k, int x, int y)
{
auto ny = y + k;
auto a = ny / 17;
auto b = ny % 17;
auto c = 17 * x + b;
BigInt d = BigInt("2") ^^ c;
return ((a / d) % 2) > 0.5;
}
private
{
enum WHITE = Color4f(1.0f, 1.0f, 1.0f);
enum BLACK = Color4f(0.0f, 0.0f, 0.0f);
}
void main(string[] args)
{
auto img = image(108, 40);
BigInt k = BigInt("4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300");
foreach(x; 0..107)
{
foreach(y; 0..18)
{
img[x, img.height / 2 - y] = tupper(k, x, y) ? WHITE : BLACK;
}
}
img.savePNG("tupper.png");
}