равен О или 1, если это возможно (так, чтобы цифрами были только О и 1). Для того чтобы увидеть, что это всегда возможно, предположим, что выполняется деление произвольного комплексного целого числа а+Ы на -l + i. Требуется найти диг такие, что q - комплексное целое число, г равно О или 1 и

a+bi = {q, +q,i){-\ + i) + r,

где qr и qi означают действительную и мнимую части q соответственно. Приравнивая действительные и мнимые части и решая одновременно полученные уравнения, получим

Ь-а + г

-а-Ь + г

Ясно, что если аиЬ оба четны или оба нечетны, то выбор г=0 дает нам комплексное целое число q. Если же одно из чисел аиЬ четно, а второе - нет, то комплексное целое число q можно получить при выборе г= 1,

Таким образом, целое число 2 может быть преобразовано к основанию -1 + i так, как показано ниже.

Поскольку действительная и мнимая части целого числа 2 четны, просто выполняем деление, зная, что остаток равен 0:

remO.

+ (-И-0(-1-0

Действительная и мнимая части числа -1 -1 нечетны, так что остаток опять равен 0:

(-1-0(-1-0 . " „ + (-И-0(-1-0

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

\ = 1 (остаток 1).

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

-- = О (остаток 1). -1+1

Таким образом получено нулевое частное, и процесс на этом завершается. Считывая полученные при делении остатки, получаем, что представление 2 в системе счисления по основанию -1 + 1 имеет вид 1100.

В табл. 12.3 показаны все битовые строки от 0000 до 1111 и их интерпретация в системе счисления по основанию -l + i, а также представление в этой системе десятичных чисел от -15 до +15.

Таблица 12.3. Преобразования меу десятичной системой счисления и системой счисления по основанию -1 + i

Правила сложения в системе счисления по основанию -l + i (кроме тривиальных правил сложения с участием нулевых битЬв) выглядят следующим образом:

1 + 1 = 1100

1 + 1+1 = 1101

1+ 1+ 1+ 1 = 111010000

1+1+1 + 1+1 = lllOlbOOl

1+1+1+1+1+1 = 111011100

1+1+1+1 + 1+1+1 = 111011101

1+1+1+1+1+1+1+1 = 111000000

При сложении двух чисел наибольшее количество переносов, которое может возникнуть в одном столбце, - шесть, так что максимальная сумма, которая может быть получена в одном столбце, - 8 (111000000). Это делает построение сумматора крайне сложной задачей. Если бы нашелся кто-то разрабатывающий компьютер с комплексной арифметикой, то, вне всяких сомнений, гораздо лучше было бы хранить действительную и мнимую части отдельно, причем каждая часть имела бы более разумное представление, например в дополнительном к 2 коде.

Щ.Ъ. Другие системы счисления

Система счисления по основанию -1-i имеет, по сути, все те же свойства, что и система счисления по основанию -l + i, рассмотренная выше. Если некоторая битовая стро-

Этот способ был использован в 1940 году в Bell Labs в Complex Number Calculator Джорджа Стибица (George Stibitz) [35].

12.3. ДРУГИЕ СИСТЕМЫ СЧИСЛЕНИЯ

ка представляет число а+Ы в одной из этих систем, то в другой та же битовая строка представляет число а-Ы.

Основания систем счисления 1 + / и 1-i также могут представлять все комплексные целые числа с использованием цифр 1 и 0. Эти две системы счисления имеют такое же соотношение между представлением чисел в них, как и системы по основанию -l±i. В системах счисления по основанию 1 ± i представление некоторых целых чисел имеет бесконечную строку единиц в левой части, аналогично представлению отрицательных чисел в дополнительном к 2 коде. Это естественным образом вытекает из использования однородных правил для сложения и вычитания, как и в случае дополнительного кода. Одним из таких чисел является число 2, которое (в любой из систем счисления) имеет вид ... 11101100. Таким образом, сложение в этих системах счисления имеет очень сложное правило: 1+1 = ...11101100.

Группируя в пары биты в представлении целого числа в системе счисления по основанию -2, можно получить представление положительных и отрицательных чисел в системе счисления по основанию 4 с использованием цифр -2, -1, О и 1, например:

-14,,, =110110 , =(-1)(1)(-2) =-1-4= +1.4-2-4.

Аналогично, группированием пар битов в представленци числа в системе счисления по основанию -1 +1 будет получено представление комплексного числа в системе счисления по основанию -2/ с использованием цифр О, 1, -l+i и i. Однако оно слишком сложное, чтобы представлять интерес.

Аналогична и "мнимочетверичная" система счисления [39]. Она представляет комплексные числа с использованием в качестве основания системы счисления величины 2i и цифр О, 1, 2 и 3. Для представления некоторых целых чисел, а именно с нечетной мнимой компонентой, при этом приходится использовать цифры справа от десятичной точки. Например, i в системе счисления по основанию 2i имеет вид 10.2.

12.4. Какое основание наиболее эффективно

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

Будем считать, что стоимость схемы с b состояниями пропорциональна Ь, так что схема с тремя состояниями на 50% дороже бинарной, а с четьфьмя - в два раза дороже бинарной.

Предположим, что вы хотите хранить в регистрах целые числа от О до некоторого максимального значения М. Представление целых чисел от О до Л/ в системе счисления по основанию b требует [log [М +1) цифр (например, для представления всех целых

чисел от О до 999999 в десятичной системе счисления требуется log,(, (1000000) = 6 цифр).

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

c = k\og,{M +1)Ь,

где с - стоимость регистра, а к - константа. Наша задача - найти значение Ь, которое минимизирует стоимость для данного значения М.