Сбалансированная тройная система - это нестандартная позиционная система счисления (сбалансированная форма ), который использовался в некоторых ранних компьютерах и был полезен при решении головоломок с балансом. Это троичная система счисления (с основанием 3), в которой цифры имеют значения –1, 0 и 1, в отличие от стандартной (несбалансированной) троичной системы, в которой цифры имеют значения 0, 1. и 2. Сбалансированная троичная система может представлять все целые числа без использования отдельного знака минус ; значение первой ненулевой цифры числа имеет знак самого числа. В то время как двоичные числа с цифрами 0 и 1 обеспечивают простейшую позиционную систему счисления для натуральных чисел (или для положительных целых чисел, если в качестве цифр используются 1 и 2), сбалансированная троичная система обеспечивает простейшую автономную позиционную систему счисления для целые числа.
В разных источниках используются разные глифы для представления трех цифр в сбалансированной троичной системе. В этой статье T (который напоминает лигатуру знака минус и 1) представляет -1, а 0 и 1 представляют сами себя. Другие соглашения включают использование '-' и '+' для обозначения -1 и 1 соответственно или использование греческой буквы тета (Θ), которая напоминает знак минус в круге, чтобы представляют -1. В публикациях о компьютере Сетунь, −1 представлен перевернутым 1: «1».
Сбалансированная троичная система впервые появляется в книге Майкла Стифеля «Арифметика». Интегра (1544 г.). Это также встречается в работах Иоганна Кеплера и Леона Лаланна. Связанные схемы подписанных цифр в других базах обсуждались Джоном Колсоном, Джоном Лесли, Огюстен-Луи Коши и, возможно, даже древним индийцем Веды.
На заре вычислительной техники было построено несколько экспериментальных советских компьютеров с сбалансированная троичная система вместо двоичной, наиболее известной из которых является Сетунь, построенная Николаем Брусенцовым и Сергеем Соболевым. Обозначение имеет ряд вычислительных преимуществ перед традиционными двоичными и троичными. В частности, согласованность «плюс-минус» снижает скорость переноса при многозначном умножении, а эквивалентность округления-усечения снижает скорость переноса при округлении дробей. Однозначная таблица умножения не имеет сбалансированных троичных переносов, а таблица сложения имеет только два симметричных переноса вместо трех.
Поскольку сбалансированная троичная система обеспечивает единообразное самодостаточное представление для целых чисел, больше нет необходимости проводить различие между числами со знаком и без знака; тем самым устраняя необходимость дублировать наборы операторов в знаковые и беззнаковые варианты, как это делают в настоящее время большинство архитектур ЦП и многие языки программирования.
В сбалансированной троичной системе значение цифры n разрядов слева от точки счисления - это произведение цифры и 3. Это полезно при преобразовании между десятичной и сбалансированной троичной. Далее в строках, обозначающих сбалансированную троичную систему, присутствует суффикс bal3. Например,
Аналогично первое место справа от точки счисления соответствует 3 = 1/3, второе место занимает 3 = 1/9 и так далее. Например,
Dec | Bal3 | Расширение | Dec | Bal3 | Расширение | |
---|---|---|---|---|---|---|
0 | 0 | 0 | ||||
1 | 1 | +1 | −1 | ᴛ | −1 | |
2 | 1ᴛ | + 3−1 | −2 | ᴛ1 | −3 + 1 | |
3 | 10 | +3 | −3 | ᴛ0 | - 3 | |
4 | 11 | + 3 + 1 | −4 | ᴛᴛ | −3−1 | |
5 | 1ᴛᴛ | +9−3−1 | −5 | ᴛ11 | −9 + 3 + 1 | |
6 | 1ᴛ0 | + 9−3 | −6 | ᴛ10 | −9 + 3 | |
7 | 1ᴛ1 | + 9−3 + 1 | −7 | ᴛ1ᴛ | −9 + 3−1 | |
8 | 10ᴛ | +9−1 | −8 | ᴛ01 | −9 + 1 | |
9 | 100 | +9 | −9 | ᴛ00 | - 9 | |
10 | 101 | +9+1 | −10 | ᴛ0ᴛ | −9-1 | |
11 | 11ᴛ | +9+ 3−1 | −11 | ᴛᴛ1 | −9−3 + 1 | |
12 | 110 | + 9 + 3 | −12 | ᴛᴛ0 | −9−3 | |
13 | 111 | +9+3+1 | −13 | ᴛᴛᴛ | −9− 3−1 |
Целое число делится на три тогда и только тогда, когда цифра в разряде единиц равна нулю.
Мы можем проверить четность сбалансированного троичного целого числа, проверив четность суммы всех тритов. Эта сумма имеет ту же четность, что и само целое число.
Сбалансированная троичная система также может быть расширена до дробных чисел аналогично тому, как десятичные числа записываются справа от точки счисления.
Decimal | -0.9 | -0,8 | -0,7 | -0,6 | -0,5 | -0,4 | -0,3 | -0,2 | −0,1 | 0 |
---|---|---|---|---|---|---|---|---|---|---|
Сбалансированный тройной | ᴛ.010ᴛ | ᴛ.1ᴛᴛ1 | ᴛ.10ᴛ0 | ᴛ.11ᴛᴛ | 0.ᴛ или ᴛ.1 | 0.ᴛᴛ11 | 0.ᴛ010 | 0.ᴛ11ᴛ | 0,0ᴛ01 | 0 |
Десятичный | 0,9 | 0,8 | 0,7 | 0,6 | 0,5 | 0,4 | 0,3 | 0.2 | 0,1 | 0 |
Сбалансированный тройной | 1.0ᴛ01 | 1.ᴛ11ᴛ | 1.ᴛ010 | 1.ᴛᴛ11 | 0,1 или 1.ᴛ | 0,11ᴛᴛ | 0,10ᴛ0 | 0,1ᴛᴛ1 | 0,010ᴛ | 0 |
В десятичном или двоичном формате целочисленные значения и завершающие дроби имеют несколько представлений. Например, 1/10 = 0,1 = 0,10 = 0,09. И 1/2 = 0,1 2 = 0,10 2 = 0,01 2. Некоторые сбалансированные троичные дроби также имеют несколько представлений. Например, 1/6 = 0,1ᴛ bal3 = 0,01 bal3. Конечно, в десятичном и двоичном формате мы можем опустить крайние правые конечные бесконечные нули после точки счисления и получить представление целого числа или конечной дроби. Но в сбалансированной троичной системе мы не можем опустить крайнее правое конечное число –1 после точки счисления, чтобы получить представление целого числа или конечной дроби.
Дональд Кнут указал, что усечение и округление - это одна и та же операция в сбалансированной троичной системе - они дают точно такой же результат (свойство, разделяемое с другими сбалансированными системами счисления). Число 1/2 не является исключением; он имеет два равнозначных представления и два одинаково допустимых усечения: 0,1 (округление до 0 и усечение до 0) и 1.ᴛ (округление до 1 и усечение до 1). При нечетной системе счисления , двойное округление также эквивалентно прямому округлению до конечной точности, в отличие от четной системы счисления.
Основные операции - сложение, вычитание, умножение и деление - выполняются как в обычной троичной системе. Умножение на два может быть выполнено путем прибавления числа к самому себе или вычитания самого себя после сдвига влево.
Арифметический сдвиг влево сбалансированного троичного числа эквивалентен умножению на (положительную, целую) степень 3; а арифметический сдвиг вправо сбалансированного троичного числа эквивалентен делению на (положительную, целую) степень 3.
Дробь | Сбалансированная троичная | Фракция | Сбалансированная тройная | |||
---|---|---|---|---|---|---|
1 | 1 | 1/11 | 0,01ᴛ11 | |||
1/2 | 0,1 | 1.ᴛ | 1/12 | 0,01ᴛ | ||
1/3 | 0,1 | 1/13 | 0,01ᴛ | |||
1/4 | 0,1ᴛ | 1/14 | 0,01ᴛ0ᴛ1 | |||
1/5 | 0,1ᴛᴛ1 | 1/15 | 0,01ᴛᴛ1 | |||
1 / 6 | 0,01 | 0,1ᴛ | 1/16 | 0,01ᴛᴛ | ||
1/7 | 0,0110ᴛᴛ | 1/17 | 0,01ᴛᴛᴛ10ᴛ0ᴛ111ᴛ01 | |||
1/8 | 0.01 | 1/18 | 0.001 | 0,01ᴛ | ||
1/9 | 0,01 | 1/19 | 0,00111ᴛ10100ᴛᴛᴛ1ᴛ0ᴛ | |||
1/10 | 0,010ᴛ | 1/20 | 0,0011 |
Преобразование повторяющегося сбалансированного троичного числа в дробь аналогично преобразованию повторяющегося десятичного числа. Например (из-за 111111 bal3 = (3 - 1/3 - 1) 10):
Как и в любой другой базе целых чисел, алгебраические иррациональные и трансцендентные числа не заканчиваются и не повторяются. Например:
Сбалансированное троичное расширение представлен в OEIS как A331313, в в A331990.
U Сбалансированную троичную систему можно преобразовать в сбалансированную троичную нотацию двумя способами:
Сбалансированный | Логика | Без знака |
---|---|---|
1 | Истина | 2 |
0 | Неизвестно | 1 |
T | Ложь | 0 |
Если три значения троичной логики являются ложными, неизвестными и истинными, и они отображаются в сбалансированную троичную систему как T, 0 и 1 и в обычные тернарные значения без знака как 0, 1 и 2, тогда сбалансированная троичная система может рассматриваться как смещенная система счисления, аналогичная смещение двоичной системы. Если троичное число имеет n тритов, то смещение b равно
который представлен как все единицы в традиционной или смещенной форме.
В результате, если эти два представления используются для сбалансированных и беззнаковых троичных чисел, положительное тройное значение n-trit без знака может быть преобразованный в сбалансированную форму путем добавления смещения b, а положительное сбалансированное число можно преобразовать в беззнаковую форму путем вычитания смещения b. Кроме того, если x и y являются сбалансированными числами, их сбалансированная сумма равна x + y - b при вычислении с использованием традиционной тернарной арифметики без знака. Точно так же, если x и y являются обычными тернарными числами без знака, их сумма равна x + y + b при вычислении с использованием сбалансированной троичной арифметики.
Мы можем преобразовать в сбалансированную тройную систему по следующей формуле:
где,
Например,
−25,4 10 = - (1T × 101 + 1TT × 101 + 11 × 101) = - (1T × 101 + 1TT + 11 ÷ 101) = −10T1.11TT = T01T.TT11
1010.1 2 = 1T + 1T + 1T = 10T + 1T + 0,1 = 101,1
Сложение, вычитание, умножение по одному элементу и таблицы деления показаны ниже. Для вычитания и деления, которые не являются коммутативными, первый операнд указывается слева от таблицы, а второй - вверху. Например, ответ на 1 - T = 1T находится в нижнем левом углу таблицы вычитания.
|
|
|
|
Сложение и вычитание многотритов аналогично сложению и вычитанию двоичные и десятичные. Добавляйте и вычитайте трение за трением и соответствующим образом прибавляйте переносимость. Например:
1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1 + 11T1.T - 11T1.T - 11T1.T → + TT1T.1 ______________ ______________ _______________ 1T0T10.1100TT1T1T1 + 1T + T T1 + TT ______________ ________________ ________________ 1T1110.0TT1 1110TT.TTT1 1110TT.TTT1 + T + T 1 + T 1 ______________ ________________ ________________ 1T0110.0TT1 1100T.TTT1 1100T.TTT1
Многоточечное умножение аналогично двоичному и десятичному умножению.
1TT1.TT × T11T.1 _____________ 1TT.1TT умножить 1 T11T.11 умножить T 1TT1T.T умножить 1 1TT1TT умножить 1 T11T11 умножить T _____________ 0T0000T.10T
Сбалансированное троичное деление аналогично двоичному и десятичному делению.
Однако 0,5 10 = 0,1111... bal3 или 1.TTTT... bal3. Если дивиденд превышает делитель плюс или минус половины, дробь частного должна быть 1 или T. Если дивиденд находится между плюсом и минусом половины делителя, дробь частного равна 0. Величина делимого должна быть сравнивать с половиной делителя перед установкой частного trit. Например,
1TT1.TT частное 0,5 × делитель T01.0 _____________ делитель T11T.1) T0000T.10T делимое T11T1 T000 < T010, set 1 _______ 1T1T0 1TT1T 1T1T0>10T0, установите T _______ 111T 1TT1T 111T>10T0, установите T _______ T00. 1 T11T.1 T001 < T010, set 1 ________ 1T1.00 1TT.1T 1T100>10T0, установить T ________ 1T.T1T 1T.T1T 1TT1T>10T0, установить T ________ 0
Другой пример,
1TTT 0,5 × делитель 1T _______ Divisor 11) 1T01T 1T = 1T, но 1T.01>1T, установить 1 11 _____ T10 T10 < T1, set T TT ______ T11 T11 < T1, set T TT ______ TT TT < T1, set T TT ____ 0
Другой пример,
101.TTTTTTTT… или 100.111111111… 0,5 × делитель 1T _________________ делитель 11) 111T 11>1T, установить 1 11 _____ 1 T1 < 1 < 1T, set 0 ___ 1T 1T = 1T, trits end, set 1.TTTTTTTTT… or 0.111111111…
Процесс извлечения квадратного корня в сбалансированной троичной системе аналогичен процессу в десятичной или двоичный.
Как и в случае деления, сначала мы должны проверить значение половины делителя. Например,
1. 1 1 T 1 TT 0 0... _________________________ √ 1T 1 <1T<11, set 1 − 1 _____ 1×10=10 1.0T 1.0T>0,10, установить 1 1T0 −1.T0 ________ 11 × 10 = 110 1T0T 1T0T>110, установить 1 10T0 −10T0 ________ 111 × 10 = 1110 T1T0T T1T0T111T0, набор 1 10T110 −10T110 __________ 111T1 × 10 = 111T10 TT1TT0T TT1TT0T Извлечение кубического корня в сбалансированной троичной системе аналогично извлечению в десятичной или двоичной системе:
Как и при делении, мы должны сначала проверить значение половины делителя. Например:
1. 1 T 1 0... _____________________ ³√ 1T - 1 1 <1T<10T,set 1 _______ 1.000 1×100=100 −0.100 borrow 100×, do division _______ 1TT 1.T00 1T00>1TT, установить 1 1 × 1 × 1000 + 1 = 1001 −1,001 __________ T0T000 11 × 100 - 1100 заимствовать 100 ×, сделать деление _________ 10T000 TT1T00 TT1T001T1T01TT, установить 1 11T × 11T × 1000 + 1 = 11111001 - 11111001 ______________ 1T10T000 11T1 × 100 - 11T100 заимствовать 100 ×, сделать деление __________ 10T0T01TT 1T0T0T00 T01010T11 <1T0T0T00<10T0T01TT, set 0 11T1×11T1×1000+1=1TT1T11001 − TT1T00 return 100× _____________ 1T10T000000... Следовательно √2 = 1,259921 89>= 1.1T1 000 111 001 T01 00T 1T1 T10 111 bal3.
Другие приложенияТеорема о том, что каждое целое число имеет уникальное представление в сбалансированной троичной системе, была использована Леонардом Эйлером для подтверждения тождества формального степенного ряда
У сбалансированной троичной системы есть и другие приложения помимо вычислений. Например, классические весы с двумя чашами , с одним грузом для каждой степени 3, могут точно взвешивать относительно тяжелые предметы с небольшим количеством гирь, перемещая гири между двумя весами и столом. Например, с гирями для каждой степени от 3 до 81 60-граммовый объект (60 10 = 1T1T0 bal3) будет идеально сбалансирован с 81-граммовым грузом на другой чаше., гиря 27 грамм в отдельной кастрюле, гиря 9 грамм в другую кастрюлю, гиря 3 грамма в собственной кастрюле и 1 грамм отложенный.
Аналогичным образом рассмотрим валютную систему с монетами достоинством 1¤, 3¤, 9¤, 27¤, 81¤. Если у покупателя и продавца есть только по одной монете каждого вида, возможна любая транзакция до 121¤. Например, если цена составляет 7 центов (7 10 = 1T1 bal3), покупатель платит 1¤ + 9¤ и получает 3¤ сдачей.
Они также могут обеспечить более естественное представление для Qutrit и систем, которые его используют.
См. Также
- Сетун, троичный компьютер
- троичная логика
- Система счисления
- Методы вычисления квадратных корней
- Табличка Саламина
- Кутрит
ИсточникиВнешние ссылки
Викискладе есть материалы, связанные с Сбалансированной троичной системой.
- Разработкой троичных компьютеров в МГУ
- Представление дробных чисел в сбалансированной троичной системе
- «Третье основание», троичная и сбалансированная троичная системы счисления
- Сбалансированная троичная система счисления (включает десятичное целое в сбалансированный троичный преобразователь)
- OEIS последовательность A182929 ( биномиальный треугольник, приведенный к сбалансированным троичным спискам)
- Сбалансированная (подписанная) троичная запись Брайан Дж. Шелберн (файл PDF)
- Троичная вычислительная машина Томаса Фаулера Марка Гласкера