Перенос в обе стороны
В обычной системе счисления сложение устроено очень локально: если в некотором разряде получилось 10 единиц, перенос уходит на один разряд влево.
С основанием φ всё интереснее. Запись числа здесь вообще говоря не единственна: например, 2 = 1,11ᵩ = 10,01ᵩ.
Будем приводить результат к стандартной записи без соседних единиц.
Мы знаем, что
φ² = φ + 1,
поэтому соседние единицы можно объединять:
011ᵩ → 100ᵩ.
Но что делать, если при сложении в одном разряде появилась цифра 2?
Из равенства φ² = φ + 1
можно получить
2 = φ + φ⁻².
А значит, для любого n
2φⁿ = φⁿ⁺¹ + φⁿ⁻².
Иными словами, вместо двойки при весе φⁿ появляются две единицы при весах φⁿ⁺¹ и φⁿ⁻².
Посмотрим на сложение:
2 = 10,01ᵩ,
3 = 100,01ᵩ.
Складываем коэффициенты:
2 + 3 = 110,02ᵩ.
Но в стандартной записи разрешены только цифры 0 и 1, поэтому двойку нужно устранить. Используем правило
2φ⁻² = φ⁻¹ + φ⁻⁴.
Получаем
110,02ᵩ → 110,1001ᵩ.
Теперь в целой части стоят две соседние единицы:
110ᵩ → 1000ᵩ.
Поэтому
2 + 3 = 1000,1001ᵩ.
Проверим:
1000,1001ᵩ =
φ³ + φ⁻¹ + φ⁻⁴ = 5.
Получилась обычная пятёрка — но путь к ней совсем не похож на школьное сложение столбиком.
Здесь работают два правила нормализации:
соседние единицы объединяются благодаря
φⁿ + φⁿ⁻¹ = φⁿ⁺¹,
а появившаяся цифра 2 распадается по правилу
2φⁿ = φⁿ⁺¹ + φⁿ⁻².
Поэтому перенос уже не движется только справа налево. Он может одновременно породить разряды по обе стороны от исходного — и даже перескочить через запятую.
В системе с целым основанием правила переноса задаются самим основанием. Здесь их задаёт алгебраическое равенство φ²=φ+1.
Поэтому перенос здесь может идти не только влево: соотношение φ²=φ+1 заставляет его распространяться сразу по нескольким разрядам.
В обычной системе счисления сложение устроено очень локально: если в некотором разряде получилось 10 единиц, перенос уходит на один разряд влево.
С основанием φ всё интереснее. Запись числа здесь вообще говоря не единственна: например, 2 = 1,11ᵩ = 10,01ᵩ.
Будем приводить результат к стандартной записи без соседних единиц.
Мы знаем, что
φ² = φ + 1,
поэтому соседние единицы можно объединять:
011ᵩ → 100ᵩ.
Но что делать, если при сложении в одном разряде появилась цифра 2?
Из равенства φ² = φ + 1
можно получить
2 = φ + φ⁻².
А значит, для любого n
2φⁿ = φⁿ⁺¹ + φⁿ⁻².
Иными словами, вместо двойки при весе φⁿ появляются две единицы при весах φⁿ⁺¹ и φⁿ⁻².
Посмотрим на сложение:
2 = 10,01ᵩ,
3 = 100,01ᵩ.
Складываем коэффициенты:
2 + 3 = 110,02ᵩ.
Но в стандартной записи разрешены только цифры 0 и 1, поэтому двойку нужно устранить. Используем правило
2φ⁻² = φ⁻¹ + φ⁻⁴.
Получаем
110,02ᵩ → 110,1001ᵩ.
Теперь в целой части стоят две соседние единицы:
110ᵩ → 1000ᵩ.
Поэтому
2 + 3 = 1000,1001ᵩ.
Проверим:
1000,1001ᵩ =
φ³ + φ⁻¹ + φ⁻⁴ = 5.
Получилась обычная пятёрка — но путь к ней совсем не похож на школьное сложение столбиком.
Здесь работают два правила нормализации:
соседние единицы объединяются благодаря
φⁿ + φⁿ⁻¹ = φⁿ⁺¹,
а появившаяся цифра 2 распадается по правилу
2φⁿ = φⁿ⁺¹ + φⁿ⁻².
Поэтому перенос уже не движется только справа налево. Он может одновременно породить разряды по обе стороны от исходного — и даже перескочить через запятую.
В системе с целым основанием правила переноса задаются самим основанием. Здесь их задаёт алгебраическое равенство φ²=φ+1.
Поэтому перенос здесь может идти не только влево: соотношение φ²=φ+1 заставляет его распространяться сразу по нескольким разрядам.