оглавление

3. Системы счисления, основанные на числах Фибоначчи и Золотой Пропорции.

В этом разделе речь пойдет о различных представлениях чисел, основанных на числах Фибоначчи и Золотой Пропорции.

Доказано, что любое целое число можно представить в виде:

N = a₁*F₁ + …………………… + a_n*F_n , (1)

где a_i € {0, 1} , i € {1, ……, n}

Основным свойством этого представления является избыточность:

5 = 1+1+3 , 5 = 2+3;

16 = 8+5+2+1 , 16 = 13+3 и т.д.

(здесь слагаемые - 1, 2, 3, 5, 8, 13 - являются числами Фибоначчи).

Для того, чтобы получить систему счисления без избыточности, достаточно наложить запрет на использование в представлении числа двух соседних чисел Фибоначчи. То есть правильным представлением, например, числа 16 будет следующее: 16 = 13 + 3.

Такая система именуются системой счисления Цекендорфа, в честь бельгийского исследователя Эдуард Цекендорфа, доказавшего, что любое положительное целое число можно выразить в виде суммы чисел Фибоначчи, исключая комбинации с соседними числами Фибоначчи, и что такое представление будет уникальным.

Система счисления, основанная на степенях З.С., называется системой счисления Бергмана:

A = ∑ a_i*τ ⁱ , (2)

где A – произвольное действительное число,

τ = (1+√ 5) / 2 (З.С.) ,

a_i € {0, 1} , i € {-∞ , ∞ } .

Доказано, что любое действительное число можно представить в виде (2) , а представление натуральных чисел в виде (2) всегда является конечным.

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

Упростим вид представления (2) : будем записывать его в виде:

a _i a _i-1 ……. a ₀ , a _-1 ……. a _-j

Например, 1 = 1,0 , 2 = 10,01 , 3 = 100,01 ,

4 = 101,01 ( т.е. 4 = τ ² + τ ⁰ + τ ^-2 ) и т.д.

Z – свойство натуральных чисел (от “zero” – “ноль”) :

Если некоторое натуральное число N представить в виде (2) , а затем заменить τ ⁱ на F*_i (числа из расширенного ряда Фибоначчи) ,

то полученная сумма ∑ a_i F*_i ( i € {-∞ , ∞ } , a_i взяты из представления (2) ) будет равна нулю для любого натурального числа N .

Например:

4 = τ ² + τ ⁰ + τ ^-2 => F*₂ + F*₀ + F*_-2 = 1 + 0 + (-1) = 0 .

Система счисления Бергмана, как и представление Цекендорфа, является избыточной, например:

3 = 11,01 = 100,01 .

Различные представления числа в системе Бергмана могут быть получены с помощью операций “свертки” ( 011 → 100 ) и “развертки” ( 100 → 011 ) . Если над кодовым представлением числа выполнить все возможные операции свертки, мы получим “минимальную форму”, в которой не встречается рядом 2-х единиц; если выполнить все операции развертки, мы придем к “максимальной форме”, в которой не встречается рядом 2-х нулей.

___________________________________________________________________

Однако наиболее интересным является представление, предложенное А.П.Стаховым. Оно напоминает представление Бергмана, но с 2-мя отличиями:

• Основанием является не τ , а τ ² ;
• Веса a_i данной системы не двоичны ( {0; 1} ), а троичны ( {-1; 0; 1} ) .

Представление Стахова ( “троичное представление” ):

A = ∑ a_i*τ ²ⁱ , (3)

где A – произвольное действительное число,

τ = (1+√ 5) / 2 (З.С.) ,

a_i € {1, 0, 1} , i € {-∞ , -∞ } , 1 = -1 .

Стаховым предложена следующая форма записи представления:

a _i a _i-1 ……. a ₀ , a _-1 ……. a _-j ,

где a_i € {1, 0, 1} , 1 = τ ⁰ - троичная единица, 1 - троичная минус единица.

Например: 2 = 11,1 = τ ² - τ ⁰ + τ ^-2 .

Порядок выполнения операций над числами в троичном представлении в основном определяется следующим соотношением:

τ ²ⁿ + τ ²ⁿ = τ ²⁽ⁿ⁺¹⁾ - τ ²ⁿ + τ ^2(n-1) (4)

Доказательство формулы (4) : Ранее было показано, что:

τ ⁿ⁺¹ = τ ⁿ + τ ^n-1 , т.е. τ ⁿ = τ ⁿ⁺¹ - τ ^n-1 ;

возведем это равенство в квадрат:

τ ²ⁿ = τ ²⁽ⁿ⁺¹⁾ - 2τ ²ⁿ + τ ^2(n-1) => (4)

Из равенства (4) вытекает следующее правило сложения троичных единиц:

1 + 1 = 111

и правило сложения троичных минус единиц

1 + 1 = 111

При этом имеются в виду 1-цы и 1-цы, находящиеся в любом разряде, т.е. a_i = 1 ( или a_i = 1 ) для некоторых i .

Остальные правила троичных арифметических действий - следующие:

0 + 0 = 0 , 1 + 0 = 1 , 1 + 0 = 1 , 1 + 1 = 0 .

Примеры записи натуральных чисел в троичной системе:

1 = 1,0 (=τ ⁰)

2 = 11,1 (=τ ² - τ ⁰ + τ ^-2)

3 = 11,1 + 1,0 = 10,1 (=τ ² + τ ^-2)

Каждый раз, желая получить большее на 1 натуральное число, мы прибавляем единицу к нулевому разряду предыдущего числа и попадаем в одну из трех ситуаций:

1. a₀ = 0 , тогда a₀ + 1 = 1 , т.е.:

a_n ….. a₁0 , a _-1 ….. a _-n + 1 = a_n ….. a₁1 , a _-1 ….. a _-n

2. a₀ = 1 , тогда a₀ + 1 = -1 + 1 = 0 , т.е.:

a_n ….. a₁1 , a _-1 ….. a _-n + 1 = a_n ….. a₁0 , a _-1 ….. a _-n

3. a₀ = 1 , тогда, используя правило сложения единиц, получаем:

a₀ + 1 = 1 + 1 = 11,1 , т.е. изменяется не только нулевой разряд, но и два соседних, причем изменяются они симметрично.

Заметим, что как первое из чисел натурального ряда, единица, обладает "зеркальной симметрией" относительно нулевого разряда ( 0001,000 ) , так и правило прибавления единицы обладает тем же свойством. Следовательно, при записи любого нат. числа в данном троичном представлении левая часть (без нулевого разряда) зеркально совпадает с правой.

Итак, после прибавления единицы к a₀ = 1 мы должны добавить единицу к следующим разрядам.

Если там стоит 0 или 1 , процесс останавливается, например:

111, 11 + 1 = 101,01 ( т.е. 5 + 1 = 6 ) ,

101,01 + 1 = 111,11 ( т.е. 8 + 1 = 9 ) .

Если же и в следующем разряде находится единица, то "ползем" дальше по разрядам до тех пор, пока не "натолкнемся" на 0 или 1.

Схематично можно изобразить этот процесс так:

+0	1	1	1	1	1	,	1	1	1	1	0
					1	,					0
0	1	1	1	(1+1)	1	,	(1+1)	1	1	1	0
0	1	1	(1+1)	1	1	,	1	(1+1)	1	1	0
0	1	(1+1)	1	0	1	,	0	1	(1+1)	1	0
0	(1+1)	1	0	0	1	,	0	0	1	(1+1)	0
1	1	0	0	0	1	,	0	0	0	1	1

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

Из данной естественной избыточности А.П.Стаховым делается вывод о целесообразности создания компьютера (процессора), основанного на троично-зеркальной симметрии, обеспечивающей универсальный способ контроля всех арифметических операций.

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

И последнее (глупое) замечание. Пусть некоторое положительное целое X представлено в виде (3) :

X = ∑ a_i*τ ²ⁱ

Умножим X на (-1) : все a_i инвертируются.

Пример: 9 = 111,11 , -9 = 111,11

Приложение: Таблица разложения натуральных чисел по t ² от 1 до 47:

N	t ^2
1	1,0
2	11,1
3	10,1
4	11,1
5	111,11
6	101,01
7	100,01
8	101,01
9	111,11
10	110,11
11	111,11
12	1101,011
13	1111,111
14	1110,111
15	1111,111
16	1011,101
17	1001,001
18	1000,001
19	1001,001
20	1011,101
21	1010,101
22	1011,101
23	1111,111
24	1101,011
25	1100,011
26	1101,011
27	1111,111
28	1110,111
29	1111,111
30	11001,0011
31	11011,1011
32	11010,1011
33	11011,1011
34	11111,1111
35	11101,0111
36	11100,0111
37	11101,0111
38	11111,1111
39	11110,1111
40	11111,1111
41	10101,0101
42	10111,1101
43	10110,1101
44	10111,1101
45	10011,1001
46	10001,0001
47	10000,0001

далее