§ 2. «Большая» конечная арифметика

Мы уже построили арифметику для . Возникает вопрос: как можно расширить эту систему, чтобы иметь возможность считать после 5? Для этого достаточно иметь множество n-значных чисел (наборов из n элементов из ) с арифметикой над . Чтобы проиллюстрировать это, рассмотрим упорядоченную тройку из , т.е. элементы множества по правилу

если или и или и В этом случае элементы будут упорядочены следующим образом:

……………………………

……………………………

Таким образом, существует 6³=216 различных троек. Поэтому нужно уметь производить арифметические вычисления над в пределах от 0 до 215. В приведённом выше упорядочивании элементов из

непосредственно предшествует

непосредственно предшествует

……………………………………………………

непосредственно предшествует

Следовательно, хотелось бы, чтобы выполнялось соотношение

Однако до сих пор не было представления 1 в . И хо­тя это соотношение выглядит естественным, мы должны заботиться о том, чтобы не использовать ни одного не определенного понятия. Для облегчения описания пред­ставим как и рассмотрим сумму ( и ( . Покомпонентное сложение даёт ( , где сложение осуществляется в , и пока, как кажется, этого достаточно.

П р и м е р 2.1. Рассмотрим соотношение

,

которое будет более наглядным, если записать его в виде

Однако

(=1?)

(=0?). //

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

Т а б л и ц а 4.9

	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	0	0	1
2	0	0	0	0	1	1
3	0	0	0	1	1	1
4	0	0	1	1	1	1
5	0	1	1	1	1	1

Возьмём любые два числа a и b из . Тогда их сумма (в Z) составляет

.

П р и м е р 2.2. 4 плюс 4 даёт в Z.

Таблица даёт «обычную» сумму двух элементов из , в то время как таблица показывает, когда необходим «переход» в следующее множество , и содержит только нули и единицы. Значения в ограничены, потому что если

и ,

То

(и n=6 в ). //

В действительности можно получить лучшую оценку, поскольку

и ,

и, следовательно,

Возвращаясь к суммированию ( и ( и обозначая ответ через ( , получим

d₀ = a₀ + _ab₀,

x₀ = a₀ + _cb₀,

d₁ = a₁ + _ab₁ + _ax₀,

x₁= если a₁ + _сb₁ = 1 тогда 1,

иначе(a₁ + _ab₁) + _ax₀,

d₂ = a₂ + _ab₂ + _ax₁,

x₂= если a₂ + _сb₂ = 1 тогда 1,

иначе(a₂ + _ab₂) + _cx₁,

Поскольку и или , то переносимый результат из никогда не может быть больше 1.

Заметим, что в наших определениях числа и в действуют, как 0 и 1 в новой арифметике. Кроме этого, если , то результат сложения может оказаться слишком большим для . В этом слу­чае говорят, что произошло «переполнение». Этот случай мы обсудим более подробно в § 3 гл. 4, а до конца пара­графа возможность перевыполнения будем игнорировать.

Аналогично можно использовать операции и (таблицы произведения и переноса), заданные в табл. 4.10 для того, чтобы производить умножение над , однако мы не будем этим заниматься.

Д о сих пор мы рассматривали только символы, имею­щие вид положительных чисел. Конечно, с символами 0, 1, 2, ... можно обращаться «естественным» образом, и, следовательно, их можно интерпретировать как неот­рицательные числа. Арифметика над , оперирует с чис­лами от до , которые были получены из последовательности (от 0 до 5) в . Если взять множество вместо , то получим систему, которая содержит отрицательные числа, но ведёт себя странным образом.

Если мы возьмём два множества и множество , которое назовём , и образуем множество , то можно построить арифметику с числами от до . На самом деле арифметика является той же самой, за исключением того, что значения и в сейчас интерпретируются как соответственно. Поэтому, например, вычисляется в Z как

.

Биекция между двумя системами, определённая следующим образом:

в остальных случаях,

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

(В это дает

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

( эквивалентно ), а второе – вид

Они имеют место тогда и только тогда, когда

, , .

Таким образом, чтобы вычислить обратное по сложению число к , мы должны сначала найти число , которое называют дополнением по , и затем прибавить Это даст дополнение до . Проиллюстрируем этот процесс на следующем примере.

П р и м е р 2.3. Найдём обратные элементы к и .

Из

получаем (дополнение до 5)

(дополнение до 6)

Проверим результат

Поэтому . //

Таким образом, вычитание сводится к сложению с соответствующим дополнением.

П р и м е р 2.4. Вычислим .

Берём

получаем (дополнение до 5)

результат (дополнение до 6)

прибавим

= ( .

Проверяя вычисления над , получаем //

Конечно, причиной образования так называемых дополнений до и является тот факт, что мы проводим вычисления над (или ).

В общем случае, если вычисления проводятся в , мы должны использовать дополнение до и соответственно.

Надо подчеркнуть, что в вычислениях на ЭВМ мы обычно имеем дело с для некоторых фиксированных и и очень редко – с множеством . Таким образом совокупность, имеющихся в нашем распоряжении числе всегда ограничена, и, хотя границы могут быть очень большими, мы не должны забывать о том, что они существуют. Риск тем более велик по той причине, что в записи обычно опускают запятые и все нули, стоящие слева от первой ненулевой цифры за исключением числа . Следовательно, запишется как 134, как 6 и как 0.

У п р а ж н е н и е 4.2. Обозначим через , где

, если чётное,

и

, если нечётное.

Вычислить: а) ; б) ; в) в каждой из «естественных» арифметик , , , . (З а м е ч а н и е: числа в примерах заданы над ; поэтому вначале требуется перевести их в соответствующую систему, а потом проводить вычисления.)