Троичная арифметика

Рассматриваются троичная симметричная (уравновешенная) система счисления (ТСС) и базовые операции производимые в ней.

Введение

Троичная система — позиционная система счисления по целочисленному основанию 3. Мы будем рассматривать вариант симметричной системы, значения в которой могут быть отрицательными, нулевыми или положительными, другими словами -1, 0, 1. Далее под понятием троичная система, троичное число и т.п., будет пониматься троичная симметричная позиционная система счисления.

Все мы уже привыкли к десятичным числам (1; 3; 5), двоичным (101; 1011001) и даже к шестнадцатеричным (0xFF; 0xA5), а что из себя представляет троичное число? Это такая же последовательность знаков (+0+--+0), только в отличие от ранее приведенных систем вместо цифр символы +,0,-. Примеры троичных чисел и их десятичный эквивалент: ${-+}_{3} = - 2_{10}$ , ${-0}_{3} = - 3_{10}$ , ${--}_{3} = - 4_{10}$ , ${+-}_{3} = 2_{10}$ , ${+0}_{3} = 3_{10}$ , ${++}_{3} = 4_{10}$ .

Перевод чисел из троичной симметричной системы в десятичную

В общем виде число в троичной системе можно представить как сумму произведений значения разряда на соответствующую этому разряду степень числа 3 (в десятичном представлении).

Иными словами: $a_{n} \cdot 3^{n} + a_{n-1} \cdot 3^{n-1} + \dots + a_{2} \cdot 3^{2} + a_{1} \cdot 3 + a_{0} + a_{-1} \cdot 3^{-1} + a_{-2} \cdot 3^{-2} + \dots + a_{-m+1} \cdot 3^{-m+1} + a_{-m} \cdot 3^{-m}$ , где $a_{i} \in [- 1,0,1]$ , $n, m, i \in N$ . Причем $a_{n} \cdot 3^{n} + a_{n-1} \cdot 3^{n-1} + \dots + a_{2} \cdot 3^{2} + a_{1} \cdot 3 + a_{0}$ – целая часть числа, $a_{-1} \cdot 3^{-1} + a_{-2} \cdot 3^{-2} + \dots + a_{-m+1} \cdot 3^{-m+1} + a_{-m} \cdot 3^{-m}$ – дробная часть.

Рассмотрим троичное число +-0-0++. $+-0-0++ = 1 \cdot 3^{7-1} - 1 \cdot 3^{6-1} + 0 \cdot 3^{5-1} - 1 \cdot 3^{4-1} + 0 \cdot 3^{3-1} + 1 \cdot 3^{2-1} + 1 \cdot 3^{1-1} = 3^{6} - 3^{5} + 0 - 3^{3} + 0 + 3 + 1 = 463$

Подробнее:

Троичный разряд	+	-	0	-	0	+	+
Номер разряда	7	6	5	4	3	2	1
Степень	$3^{7-1} = 3^{6}$	$3^{6-1} = 3^{5}$	$3^{5-1} = 3^{4}$	$3^{4-1} = 3^{3}$	$3^{3-1} = 3^{2}$	$3^{2-1} = 3^{1}$	$3^{1-1} = 3^{0}$
Десятичное значение	729	243	81	27	9	3	1
Множитель	1	-1	0	-1	0	1	1
Итоговое десятичное значение	729	-243	0	-27	0	3	1

Перевод из десятичной системы в троичную симметричную (уравновешенную) систему

Для перевода из десятичной системы в троичную, можно воспользоваться следующим алгоритмом:

Исходное число (в десятичной системе) делим на 3.
Если остаток от деления равен 2, то к результату добавляем +1.
Если результат от деления больше 2, — выполняем его деление на 3.
Пункты 2, 3 выполняем до тех пор пока не получим результат от деления меньше 3 (см. п.3).
После выполнения процедур сначала выписываем результат от последнего деления, при этом если результат равен двум то его выписываем как +-, затем выписываем остатки от предыдущих операций, так что первый остаток от деления был выписан последним (то есть выписываем снизу вверх), при этом все остатки равные двум выписываются как значение - (см. п.2, мы делали заём из остатка в результат).
Значения равные 1 выписываются как +, 0 оставляем как есть (0 и в троичной системе 0).

Пример: Переведём число 19 из десятичной системы в троичную систему.
Разделим 19 на 3. Получим 6, а в остатке будет $19 - 6 \times 3 = 19 - 18 = 1$ . Так как результат больше 2 (6>2), необходимо продолжить выполнение операций деления. Теперь 6 делим на 3. Получаем 2, в остатке $6 - 2 \times 3 = 6 - 6 = 0$ . Результат меньше 3. Дальше делить результат не требуется. Выписываем: 2, 0, 1. Заменяем, получаем: +-0+ — 19 в троичной системы.

Пример: Переведём число 5 из десятичной системы в троичную систему.
Разделим 5 на 3. Получим 1, а в остатке будет $5 - 1 \times 3 = 5 - 3 = 2$ . Так как остаток равен 2, то делаем заём в результат добавляя к нему +1, то есть результат теперь равен 2. Результат меньше 3. Дальше делить результат не требуется. Выписываем: 2, 2, но так как 2 из результата выписывается как +-, а из остатка как +, получаем +--.

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

Отрицательные числа

Ключевая особенность троичной системы — наличие знака числа в самом алфавите, т.е. однозначно определяется знак числа по самому числу. Если ведущий ненулевой разряд отрицателен, то и само число является отрицательным. Изменение знака числа производится инвертированием каждого разряда числа: положительный разряд меняется на отрицательный и наоборот, ноль остается без изменений.

${+0-}_{3} = 8_{10}$

${-0+}_{3} = - 8_{10}$

Округление

Другой важной особенностью троичной системы является механизм округления чисел — простым отбрасыванием младших разрядов получается наилучшее при данном оставшемся количестве цифр приближение этого числа и округление не требуется. Это следствие того, что абсолютная величина части числа, представленной отбрасываемыми младшими цифрами, никогда не превосходит половины абсолютной величины части числа ( $\frac{0,+}{2} = \frac{1}{6} > 0,0+ = \frac{1}{9}$ ), соответствующей младшей значащей цифре младшего из сохраняемых разрядов.

Округлим троичное число $0,++++ = 0,493827$ до 3 знаков после запятой: $0,+++ = 0,48148$ , до 2 знаков дает: $0,++ = 0,4444(4)$ , до 1 знака — $0,+ = 0,3333(3)$ .

Сложение

Сложение производится по общим правилам для позиционных систем.

Слагаемое 1	+	+	+	0	0	-	-	-
Слагаемое 2	-	0	+	-	+	-	0	+
Сумма	0	+	-	-	+	+	-	0
Перенос	0	0	+	0	0	-	0	0

Примечание: следует отметить что разрядная сетка с двумя разрядами не переполняется вплоть до 4 слагаемых. Таким образом наименьшим оптимальным сумматором можно считать сумматор для четырёх одноразрядных операндов: «+» + «+» + «+» + «+» = «+-» + «+-» = «++»

Вычитание

Операция вычитание выполняется как сложение с инвертированием вычитаемого или уменьшаемого.

«+0-» - «-+» = «+0-» + «+-» = «+0+».

Умножение

Умножение производится по общим правилам для позиционных систем.

Таблица умножения
	+	-
+	+	-
0	0	0
-	-	+

Умножение 8 (+0-) на 8 (+0-), в результате получаем 64:

			+	0	-
		×
			+	0	-
			-	0	+
	+
		0	0	0
+
	+	0	-
	+	-	+	0	+

Примечание: умножение в троичной системы на $3^{n}$ , где $n > 0, n \in N$ , сводится к добавлению к числу $n$ – младших разрядов с нулевым значением: $4 = ++$ ; $12 = ++0$ ; $36 = ++00$ , также эта операция называется троичный сдвиг влево.

Деление

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

Пример: разделим 25 на 5.

	+	0	-	+	+	-	-
-					+	+
	+	-	-			+
		+	0	+
	-
		+	-	-
		+	-	-
	-
		+	-	-
				0

$\to$

		+	+
+
			+
	+	-	-

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

Примечание: деление числа на $3^{n}$ , где $n > 0, n \in N$ , осуществляется сдвигом вправо: $18 = +-00$ ; $6 = +-0$ ; $2 = +-$ ; $\frac{2}{3} = +,-$ .

Признак делимости на 2

Число a в троичной системы можно представить в виде $a = \bar{a_{n} a_{n-1} \dots a_{1} a_{0}} = (3^{n} - 1) \cdot a_{n} + (3^{n-1} - 1) \cdot a_{n-1} + \dots + (3^{2} - 1) \cdot a_{2} + (3 - 1) \cdot a_{1} + a_{n} + a_{n-1} + \dots + a_{1} + a_{0}$ , где $a_{i} \in [- 1,0,1]$ , $i = 0, 1, \dots, n$ , $a_{n} \neq 0$ .

Обозначим $b = (3^{n} - 1) \cdot a_{n} + (3^{n-1} - 1) \cdot a_{n-1} + \dots + (3^{2} - 1) \cdot a_{2} + (3 - 1) \cdot a_{1}$ ,

$c = a_{n} + a_{n-1} + \dots + a_{1} + a_{0}$ , т.е. $a = b + c$ .

Рассмотрим число $b = (3^{n} - 1) \cdot a_{n} + (3^{n-1} - 1) \cdot a_{n-1} + \dots + (3^{2} - 1) \cdot a_{2} + (3 - 1) \cdot a_{1}$ .

Множителями $a_{i}$ , является $(3^{k} - 1)$ .

При любом $k \geq 1$ $(3^{k} - 1) = (3 - 1) \cdot (3^{k-1} + 3^{k-2} + \dots + 3 + 1) = 2 \cdot (3^{k-1} + 3^{k-2} + \dots + 3 + 1)$ , следовательно, можно записать $b = 2 \cdot (\dots)$ , т.е. $b$ делится 2.

Следовательно, число $a = b + c$ делится на 2 тогда, когда делится на 2 число $c = a_{n} + a_{n-1} + \dots + a_{1} + a_{0}$ , которое представляет собой сумму цифр числа $a$ .

Число в троичной системы делится на 2 (число четное), если сумма значений его разрядов делится на 2.

Пример:

Числа, которые делятся на 2			Числа, которые не делятся на 2
Значение в троичной системе	Сумма разрядов	Значение в десятичной системе	Значение в троичной системы	Сумма разрядов	Значение в десятичной системе
+-	0	2	+	1	1
++	2	4	+0	1	3
+-0	2	6	+--	-1	5
+0-	2	8	+-+	1	7
+0+	2	10	+00	1	9
++0	2	12	++-	1	11
+---	4	14	+++	3	13

Признак делимости на 3

Число a в троичной системы можно представить в виде $a = \bar{a_{n} a_{n-1} \dots a_{1} a_{0}} = 3^{n} \cdot a_{n} + 3^{n-1} \cdot a_{n-1} + \dots + 3^{1} \cdot a_{1} + 3^{0} \cdot a_{0}$ , где $a_{i} \in [- 1,0,1]$ , $i = 0, 1, \dots, n$ , $a_{n} \neq 0$ .

Зададим число $b = a - a_{0}$ , т.е. $b = 3^{n} \cdot a_{n} + 3^{n-1} \cdot a_{n-1} + \dots + 3^{1} \cdot a_{1} = 3 \cdot (3^{n-1} \cdot a_{n} + 3^{n-2} \cdot a_{n-1} + \dots + 3^{1} \cdot a_{2} + a_{1})$ .

Отсюда следует, что число $b$ делится на 3, а число $a = b + a_{0}$ делится на 3 тогда и только тогда, когда $a_{0}$ делится на 3, этому соответствует значение $a_{0} = 0$ , таким образом, числа в троичной системы делятся на 3, если младший разряд равен нулю.

Пример:

Числа, которые делятся на 3		Числа, которые не делятся на 3
Значение в троичной системе	Значение в десятичной системе	Значение в троичной системе	Значение в десятичной системе
+0	3	+	1
+-0	6	+-	2
+00	9	++	4
++0	12	+0-	8