База золотого сечения

База золотого сечения — это нецелая позиционная система счисления , в которой используется золотое сечение (иррациональное число). ⁠ 1 + √ 5/2 , ≈ 1,61803399 ⁠ обозначенное греческой буквой φ ) в качестве основания . Его иногда называют основанием-φ , основанием золотого сечения , фи-основанием или, в просторечии, финарием . Любое неотрицательное действительное число может быть представлено в виде числа с основанием φ, используя только цифры 0 и 1 и избегая последовательности цифр «11» — это называется стандартной формой . Числа с основанием φ, включающие в себя последовательность цифр «11», всегда можно переписать в стандартной форме, используя алгебраические свойства основания φ — в частности, то, что φ ¹ + ж ⁰ = е ². Например, 11 _φ = 100 _φ .

Несмотря на использование иррациональной системы счисления, при использовании стандартной формы все неотрицательные целые числа имеют уникальное представление в виде конечного (конечного) разложения по основанию φ. Множество чисел, обладающих конечным представлением по базе φ, представляет собой кольцо Z [ ⁠ + √ 5/2 ⁠ ] ; 1 в этой системе счисления он играет ту же роль, что и двоичные рациональные числа в двоичных числах , обеспечивая возможность умножения .

Другие числа имеют стандартные представления в базе φ, при этом рациональные числа имеют повторяющиеся представления. Эти представления уникальны, за исключением того, что числа с завершающим расширением также имеют неконечное расширение. Например, 1 = 0,1010101… в базе φ, точно так же, как 1 = 0,99999… в базе 10 .

Примеры

Десятичный	Степени φ	База f
1	ж ⁰	1
2	ж ¹ + ж ⁻²	10.01
3	ж ² + ж ⁻²	100.01
4	ж ² + ж ⁰ + ж ⁻²	101.01
5	ж ³ + ж ⁻¹ + ж ⁻⁴	1000.1001
6	ж ³ + ж ¹ + ж ⁻⁴	1010.0001
7	ж ⁴ + ж ⁻⁴	10000.0001
8	ж ⁴ + ж ⁰ + ж ⁻⁴	10001.0001
9	ж ⁴ + ж ¹ + ж ⁻² + ж ⁻⁴	10010.0101
10	ж ⁴ + ж ² + ж ⁻² + ж ⁻⁴	10100.0101

Запись базовых чисел золотого сечения в стандартной форме

В следующем примере преобразования из нестандартной формы в стандартную обозначение 1 используется для обозначения цифры -1.

211.0 1 _φ не является стандартным числом с основанием φ, поскольку оно содержит «11», а также «2» и « 1 » = −1, которые не являются «0» или «1».

Чтобы привести числительное в стандартную форму, мы можем использовать следующие замены: $0{\underline {1}}0_{\phi }={\underline {1}}01_{\phi }$ , $1{\underline {1}}0_{\phi }=001_{\phi }$ , $200_{\phi }=1001_{\phi }$ , $011_{\phi }=100_{\phi }$ . Замены можно применять в любом порядке, поскольку результат будет тот же. Ниже справа — замены, примененные к числу в предыдущей строке, слева — полученное число.

${\begin{aligned}211.0{\underline {1}}0_{\phi }=211&.{\underline {1}}01_{\phi }&0{\underline {1}}0\rightarrow {\underline {1}}01\\=210&.011_{\phi }&1{\underline {1}}0\rightarrow 001\\=1011&.011_{\phi }&200\rightarrow 1001\\=1100&.100_{\phi }&011\rightarrow 100\\=10000&.1_{\phi }&011\rightarrow 100\\\end{aligned}}$

стандартизировать любое положительное число с нестандартным завершающим представлением по основанию φ можно однозначно Таким способом . Если мы дойдем до точки, где все цифры равны «0» или «1», за исключением первой цифры, которая будет отрицательной , тогда число станет отрицательным. (Исключением является случай, когда первая цифра равна отрицательной единице, а следующие две цифры равны единице, например 1 111,001 = 1,001.) Это можно преобразовать в отрицательное представление по основанию φ, отрицая каждую цифру, стандартизируя результат, а затем пометить его как отрицательный. Например, используйте знак минус или какое-либо другое значение для обозначения отрицательных чисел.

Представление целых чисел в виде базовых чисел золотого сечения

Мы можем либо считать наше целое число (единственной) цифрой нестандартного числа с основанием φ и стандартизировать его, либо сделать следующее:

1 × 1 = 1, φ × φ = 1 + φ и ⁠ 1 / φ ⁠ = −1 + φ. Следовательно, мы можем вычислить

( a + b φ) + ( c + d φ) = (( a + c ) + ( b + d )φ),

( а + б φ) - ( c + d φ) знак равно (( а - c ) + ( b - d )φ)

и

( a + b φ) × ( c + d φ) = (( ac + bd ) + ( ad + bc + bd )φ).

Таким образом, используя только целые значения, мы можем складывать, вычитать и умножать числа вида ( a + b φ) и даже представлять положительные и отрицательные целые степени φ.

( a + b φ) > ( c + d φ) тогда и только тогда, когда 2( a - c ) - ( d - b ) > ( d - b ) × √ 5 . Если одна сторона отрицательна, а другая положительна, сравнение тривиально. В противном случае возведите обе стороны в квадрат, чтобы получить целочисленное сравнение, изменив направление сравнения на противоположное, если обе стороны отрицательны. При возведении в квадрат обеих частей √ 5 заменяется целым числом 5.

Таким образом, используя только целые значения, мы также можем сравнивать числа вида ( a + b φ).

Чтобы преобразовать целое число x в число по основанию φ, обратите внимание, что x = ( x + 0φ).
Вычтите высшую степень φ, которая все еще меньше, чем имеющееся у нас число, чтобы получить наше новое число, и запишите «1» в соответствующем месте полученного числа по основанию φ.
Если наше число не равно 0, переходим к шагу 2.
Законченный.

Вышеописанная процедура никогда не приведет к получению последовательности «11», поскольку 11 _φ = 100 _φ , поэтому получение «11» будет означать, что мы пропустили «1» перед последовательностью «11».

Начните, например, с целого числа = 5, пока результат будет ...00000.00000... _φ

Наивысшая степень φ ≤ 5 равна φ ³ = 1 + 2φ ≈ 4,236067977

Вычитая это из 5, мы имеем 5 - (1 + 2φ) = 4 - 2φ ≈ 0,763932023..., результат на данный момент составляет 1000,00000... _φ.

Наивысшая степень φ ≤ 4 − 2φ ≈ 0,763932023... равна φ. ⁻¹ = −1 + 1φ ≈ 0,618033989...

Вычитая это из 4 - 2φ ≈ 0,763932023..., мы имеем 4 - 2φ - (-1 + 1φ) = 5 - 3φ ≈ 0,145898034..., результат на данный момент составляет 1000,10000... _φ.

Наивысшая степень φ ≤ 5 − 3φ ≈ 0,145898034... равна φ. ⁻⁴ = 5 − 3φ ≈ 0,145898034...

Вычитая это из 5 - 3φ ≈ 0,145898034..., мы имеем 5 - 3φ - (5 - 3φ) = 0 + 0φ = 0, с конечным результатом 1000,1001 _φ .

Неуникальность

Как и в любой системе счисления с основанием n, числа с завершающим представлением имеют альтернативное повторяющееся представление. В системе счисления с основанием 10 это основано на наблюдении, что 0,999...=1 . В базе φ цифру 0,1010101... можно считать равной 1 несколькими способами:

Преобразование к нестандартной форме: 1 = 0,11 _φ = 0,1011 _φ = 0,101011 _φ = ... = 0,10101010.... _φ
Геометрический ряд : 1,0101010... _φ равен

\sum _{k=0}^{\infty }\varphi ^{-2k}={\frac {1}{1-\varphi ^{-2}}}=\varphi

Разница между «сдвигами»: φ ² x - x = 10,101010... _φ - 0,101010... _φ = 10 _φ = φ, так что x = ⁠ ж / ж ² − 1 ⁠ = 1

Эта неединственность является особенностью системы счисления, поскольку и 1,0000, и 0,101010... имеют стандартную форму.

В общем, последнюю 1 любого числа в базе φ можно заменить повторяющимся 01 без изменения значения этого числа.

Представление рациональных чисел в виде базовых чисел золотого сечения

Каждое неотрицательное рациональное число может быть представлено как повторяющееся разложение по основанию φ, как и любой неотрицательный элемент поля Q [ √ 5 ] = Q + √ 5 Q , поля, порожденного рациональными числами и √ 5 . И наоборот, любое повторяющееся (или завершающее) расширение по основанию φ является неотрицательным элементом Q [ √ 5 ]. Для повторяющихся десятичных дробей повторяющаяся часть зачеркнута:

⁠ 1 / 2 ⁠ ≈ 0,010 _ф
⁠ 1 / 3 ⁠ ≈ 0,00101000 _ф
√ 5 = 10,1 _ф
2 + ⁠ √ 5 / 13 ⁠ ≈ 10,01 0100010001010100010001000000 _φ

Обоснование того, что рациональное выражение дает повторяющееся разложение, аналогично эквивалентному доказательству для системы счисления с основанием n ( n = 2,3,4,...). по основанию φ По сути, при длинном делении существует только конечное число возможных остатков, и поэтому однажды должен существовать повторяющийся шаблон. Например, с ⁠ 1 / 2 ⁠ = ⁠ 1 / 10.01 _φ⁠ = ⁠ 100 _φ / 1001 _φ ⁠ длинное деление выглядит следующим образом (обратите внимание, что вычитание по основанию φ поначалу может быть затруднено):

                .0 1 0 0 1
         ________________________
 1 0 0 1 ) 1 0 0.0 0 0 0 0 0 0 0
             1 0 0 1                        trade: 10000 = 1100 = 1011
             -------                            so 10000 − 1001 = 1011 − 1001 = 10
                 1 0 0 0 0
                   1 0 0 1
                   -------
                       etc.

Обратное также верно: число с повторяющейся базой φ; представление является элементом поля Q [ √ 5 ]. Это следует из наблюдения, что повторяющееся представление с периодом k включает в себя геометрическую прогрессию с отношением φ ^-к, что в сумме будет давать элемент Q [ √ 5 ].

Представление иррациональных чисел в виде базовых чисел золотого сечения

Представления некоторых интересных чисел по основанию φ:

$π$ ≈ 100,0100 1010 1001 0001 0101 0100 0001 0100 ... _φ (последовательность A102243 в OEIS )
$e$ ≈ 100,0000 1000 0100 1000 0000 0100 ... _φ (последовательность A105165 в OEIS )
√ 2 ≈ 1,0100 0001 0100 1010 0100 0000 0101 0000 0000 0101 ... _φ
√ 5 = 10,1 _ф

Сложение, вычитание и умножение

Можно адаптировать все стандартные алгоритмы арифметики с основанием 10 к арифметике с основанием φ. Есть два подхода к этому:

Рассчитайте, затем преобразуйте в стандартную форму

Для сложения двух чисел по основанию φ сложите каждую пару цифр без переноса, а затем преобразуйте число в стандартную форму. Для вычитания вычтите каждую пару цифр без заимствования (заимствование — это отрицательная сумма переноса), а затем преобразуйте число к стандартной форме. Для умножения умножьте обычным способом по основанию 10, без переноса, а затем преобразуйте число в стандартную форму.

Например,

2 + 3 = 10.01 + 100.01 = 110.02 = 110.1001 = 1000.1001
2 × 3 = 10.01 × 100.01 = 1000.1 + 1.0001 = 1001.1001 = 1010.0001
7 − 2 = 10000.0001 − 10.01 = 100 1 0.0 1 01 = 11 1 0.0 1 01 = 1001.0 1 01 = 1000.1001

Избегайте цифр, отличных от 0 и 1.

Более «родной» подход состоит в том, чтобы избежать необходимости складывать цифры 1+1 или вычитать 0 – 1. Это делается путем реорганизации операндов в нестандартную форму, чтобы эти комбинации не возникали. Например,

2 + 3 = 10.01 + 100.01 = 10.01 + 100.0011 = 110.0111 = 1000.1001
7 − 2 = 10000.0001 − 10.01 = 1100.0001 − 10.01 = 1011.0001 − 10.01 = 1010.1101 − 10.01 = 1000.1001

Представленное здесь вычитание использует модифицированную форму стандартного «торгового» алгоритма вычитания.

Разделение

Никакое нецелое рациональное число не может быть представлено как конечное число по основанию φ. Другими словами, все конечно представимые числа по основанию φ являются либо целыми числами, либо (что более вероятно) иррациональными в квадратичном поле Q [ √ 5 ]. Из-за того, что при длинном делении имеется только конечное число возможных остатков, деление двух целых чисел (или других чисел с конечным представлением по основанию φ) будет иметь повторяющееся расширение, как показано выше.

Связь с кодированием Фибоначчи

Кодирование Фибоначчи — это тесно связанная система счисления, используемая для целых чисел. В этой системе используются только цифры 0 и 1, а разрядные значения цифр являются числами Фибоначчи . Как и в случае с основанием-φ, последовательность цифр «11» можно избежать путем перестановки в стандартную форму с использованием рекуррентного соотношения Фибоначчи F _{k +1} = F _k + F _{k -1} . Например,

30 = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1 = 10100010 _фиб .

Практическое использование

Можно смешивать арифметику по основанию φ с целочисленными последовательностями Фибоначчи . Сумма чисел в общей целочисленной последовательности Фибоначчи, которые соответствуют ненулевым цифрам числа по основанию φ, представляет собой умножение числа по основанию φ и элемента в нулевой позиции в последовательности. Например:

произведение 10 (10100,0101 основание-φ) и 25 (нулевое положение) = 5 + 10 + 65 + 170 = 250
база-φ: 1 0 1 0 0. 0 1 0 1

частичная последовательность: ... 5 5 10 15 25 40 65 105 170 275 445 720 1165 ...
произведение 10 (10100,0101 основание-φ) и 65 (нулевое положение) = 10 + 25 + 170 + 445 = 650
база-φ: 1 0 1 0 0. 0 1 0 1

частичная последовательность: ... 5 5 10 15 25 40 65 105 170 275 445 720 1165 ...

См. также

Бета-кодер – первоначально использовалась база золотого сечения.
Нумерация Островского

Примечания

Ссылки

Бергман, Джордж (1957). «Система счисления с иррациональной основой». Журнал «Математика» . 31 (2): 98–110. дои : 10.2307/3029218 . JSTOR 3029218 .
Эгган, ЖК; Ванден Эйнден, CL (1966). «Десятичные разложения по нецелым основаниям». амер. Математика. Ежемесячно . 73 (73): 576–582. дои : 10.2307/2314786 . JSTOR 2314786 .
Плохар, Йозеф (1971). «Добродушный кроликовод». Многообразие . 11 :26–30.

Внешние ссылки

Использование степеней Фи для представления целых чисел (основание Фи)