"Деревянная" система счисления

[asbest]

Добрый день!
Возился с бинарными деревьями в программе и мне показалось, что будет больше понимания, если в качестве одного из представлений записывать пути в дереве в виде двоичных чисел $f_0 f_1 f_2 f_3 ...$, где $f_i$ равно 0 или 1, что соответствует ветке, идущей влево или вправо. Старший разряд $f_0$ соответствует ветке дерева, идущей от корня. Если сопоставить цифрам разряда $i$ "веса" $f_i 2^{-i-1} - 2^{-i-2}$, (или $2^{-i-1}$, но цифре 0 будет соответствовать вычитание веса, цифре 1 - прибавление), то такого рода строчки будут представлять числа от (-1 до 1), пустое дерево соответствует 0. Последовательность 0110 соответствует, к примеру, -1/2+1/4+1/8-1/16 = -3/16. Отношения больше/меньше между этими числами соответствуют отношению между элементами в упорядоченном двоичном дереве. Так вот, как это называется и где почитать можно? Что-нибудь только лёгенькое. Как, к примеру, сложение-умножение выглядит... Сравнение выглядит необычно. Я нашел только деревья Штерна-Броко (ДШБ), они не совсем такие, хотелось бы оставить отрицательные числа и пределы, т.к. есть даже мысли использовать это "в железе"... Но пусть хоть и ДШБ, про них я тоже ничего толкового не нашел кроме определения.

[mihaild]

asbest в сообщении #1340083 писал(а):

пустое дерево соответствует 0

Только всё-таки пустой путь.

asbest в сообщении #1340083 писал(а):

$f_i 2^{-i-1} - 2^{-i-2}$, (или $2^{-i-1}$, но цифре 0 будет соответствовать вычитание веса, цифре 1 - прибавление)

Эти варианты в 2 раза отличаются.

Пока что вы по сути сказали, что двоично-рациональные числа на интервале $(-1; 1)$ представимы в виде $\sum \alpha_i 2^{-i}$, где $\alpha_i = \pm 1$. Это правда, и несложно доказывается, но пока непонятно, что вы из этого хотите извлечь.
Сложение выводит за пределы интервала, умножение скорее всего выглядит как-то страшно.

[asbest]

mihaild в сообщении #1340148 писал(а):

Только всё-таки пустой путь.

Да.

mihaild в сообщении #1340148 писал(а):

Эти варианты в 2 раза отличаются.

Точно, спасибо. Я и думаю - с чего это -2 взялось. Наверное должно быть $f_i 2^{-i} - 2^{-i-1}$.

mihaild в сообщении #1340148 писал(а):

Пока что вы по сути сказали, что двоично-рациональные числа на интервале $(-1; 1)$ представимы в виде $\sum \alpha_i 2^{-i}$, где $\alpha_i = \pm 1$. Это правда, и несложно доказывается, но пока непонятно, что вы из этого хотите извлечь.

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

mihaild в сообщении #1340148 писал(а):

Сложение выводит за пределы интервала, умножение скорее всего выглядит как-то страшно.

Ну, первое м.б. и не такая большая проблема, т.к. умножение чисел фиксированной разрядности тоже выводит.

[mihaild]

asbest в сообщении #1340214 писал(а):

умножение чисел фиксированной разрядности тоже выводит

Произведение чисел из интервала $(-1; 1)$ принадлежит этому же интервалу, а вот сумма - нет.

[asbest]

mihaild в сообщении #1340215 писал(а):

asbest в сообщении #1340214 писал(а):

умножение чисел фиксированной разрядности тоже выводит

Произведение чисел из интервала $(-1; 1)$ принадлежит этому же интервалу, а вот сумма - нет.

Я о том, что для хранения результата произведения восьмибитных чисел нужно в общем случае 16 бит. Сложение тоже может не войти.
Повозился с сабжем еще. Литературу пока не искал.

Хотя технически такие числа легче хранить как биты, записывать лучше наверное какими-то буквами, т.к. иначе в арифметике дикость получается. Можно записывать буквами $\alpha$ (-1) и $\beta$ (+1) по аналогии с проекцией спина 1/2 в квантовой механике.

Умножение реализуется несложно - столбиком. Одно из чисел раскладываем по разрядам, умножение на $\beta$ какого-то разряда есть сдвиг, умножение на $\alpha$ - сдвиг и изменение знака, последнее достигается инверсией всех разрядов. При сдвиге в освободившиеся разряды помещается не "0", а пустота ($\emptyset$).

Со сложением немного сложнее, эта сложность сказывается и на умножении, т.к. для получения результата нужно сложить поразрядные произведения. Арифметика такая: $\alpha+\alpha = 2\alpha$ (т.е. $\alpha$ переносится в старший разряд, в этом остается $\emptyset$), $\beta+\beta = $ аналогично, $\alpha+\beta = \emptyset$, $\alpha+\emptyset = \alpha$, с $\beta$ аналогично. Если в разряде получается $\emptyset$, "занимаем" (!) (причем что мы занимаем? не числа, а возможность их записи.) в младшем разряде: если там $\beta$, пишем $\beta\alpha$ (т.е. в младший разряд пишем $\alpha$), если там $\alpha$ - пишем $\alpha\beta$.