Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

3.2. СИСТЕМЫ СЧИСЛЕНИЯ
83
Как показано в § 3.1, запись произвольного действительного чис- ла x (x > 0) в десятичной системе представляет собой перечисление всех коэффициентов разложения числа x по степеням числа 10:
a
k
a
k−1
. . . a
1
a
0
.a
−1
a
−2
. . . a
−n
. . . .
На этих же принципах основаны и другие позиционные системы счис- ления с любым целым числом P (P > 1), которое называется основанием
счисления. В каждой из этих систем используется P различных символов,
называемых цифрами, для обозначения некоторых различных натуральных чисел, называемых базисными. В дальнейшем в качестве базисных прини- маются целые числа от 0 до P − 1.
Запись произвольного числа x в системе счисления с основанием P так- же определяется разложением этого числа x по последовательным степеням числа P :
b
k
P
k
+ b
k−1
P
k−1
+ . . . + b
1
P
1
+ b
0
P
0
+ b
−1
P
−1
+ b
−2
P
−2
+ . . . ,
где каждый коэффициент b
i
является одним из базисных чисел и обознается одной цифрой. Аналогично записи в десятичной системе число x в P -ичной системе изображается последовательностью своих коэффициентов с разде- лением целой и дробной частей с помощью точки: x = b
k
b
k−1
. . . b
0
.b
−1
b
−2
. . . .
Для указания используемой системы счисления будем основание системы
(в ее десятичной записи) приводить в качестве нижнего индекса у записи числа, например 758 16
Арифметические операции над числами в любой P -ичной системе выпол- няются по тем же правилам, что и в десятичной, поскольку все они осно- вываются на правилах выполнения операций над соответствующими много- членами. При этом используются таблицы сложения и умножения, которые имеют место в системе счисления с данным основанием.
2.
Двоичная система
При P = 2 для записи чисел используются всего две цифры: 0 и 1.
Пример 3.2.1. 23 10
= 1 · 2 4
+ 0 · 2 3
+ 1 · 2 2
+ 1 · 2 1
+ 1 · 2 0
= 10111 2
,
29 32
= 1 · 2
−1
+ 1 · 2
−2
+ 1 · 2
−3
+ 0 · 2
−4
+ 1 · 2
−5
= 0.11101 2
. ¤

84
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Полезно запомнить запись в двоичной системе первых шестнадцати на- туральных чисел:
0 1
2 3
4 5
6 7
0000 0001 0010 0011 0100 0101 0110 0111 8
9 10 11 12 13 14 15 1000 1001 1010 1011 1100 1101 1110 1111
При выполнении арифметических операций над числами в двоичной системе используются следующие таблицы сложения и умножения:
0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10;
0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1.
Поскольку в этой системе для изображения чисел берутся только две цифры, для построения компьютера можно использовать элементы, име- ющие лишь два различных устойчивых состояния, одно из которых соот- ветствует цифре 0, а другое — цифре 1. При этом алгебраическая система с носителем, состоящим из двоичных кодов, изоморфна соответствующей алгебраической системе, элементы которой имеют десятичную запись.
3.
Восьмеричная система
В
восьмеричной системе счисления используются цифры
0, 1, 2, 3, 4, 5, 6, 7. Запись числа основывается на его разложении по сте- пеням числа восемь с указанными коэффициентами.
Пример 3.2.2.
215 10
= 192 + 16 + 7 = 3 · 8 2
+ 2 · 8 1
+ 7 · 8 0
= 327 8
,
30.25 10
= 3 · 8 1
+ 6 · 8 0
+ 2 · 8
−1
= 36.2 8
. ¤
4.
Шестнадцатеричная система
В этой системе для записи базисных чисел от нуля до пятнадцати ис- пользуются следующие символы (цифры): от 0 до 9 — те же самые арабские цифры, а для следующих чисел — от десяти до пятнадцати — символы a, b,
c, d, e, f .
Пример 3.2.3. ae.8 16
= 10 · 16 + 14 + 8/16 = 160 + 14 + 0.5 = 174.5 10
. ¤

3.2. СИСТЕМЫ СЧИСЛЕНИЯ
85 5.
Смешанные системы счисления
В некоторых случаях числа, заданные в системе счисления с основани- ем P , приходится изображать с помощью цифр системы с основанием Q
(Q < P ). Такая необходимость возникает, например, когда в память машины,
способной воспринимать только двоичные цифры, нужно ввести десятичные числа для их последующей переработки. В таких случаях используют сме-
шанные системы счисления, в которых каждый коэффициент разложения числа по степеням P записывается в Q-ичной системе. Такая смешанная система называется Q-P -ичной. При этом для записи каждого из упомя- нутых выше коэффициентов используется одно и то же количество Q-ичных разрядов, минимально необходимое для записи любого из допустимых коэф- фициентов.
Пример 3.2.4. Представим число 8903 10
в смешанной двоично- десятичной системе. Поскольку 8 10
= 1000 2
, 9 10
= 1001 2
, 3 10
= 0011 2
, имеем
8903 10
= 1000 1001 0000 0011 2−10
. ¤
Отметим, что запись в двоично-десятичной системе отличается от за- писи данного числа в двоичной системе счисления. Например, 8903 10
=
= 10001011000111 2
, что отличается от записи этого же числа в смешанной двоично-десятичной системе.
Особый интерес представляет случай, когда P = Q
l
(l ∈ ω). При этом запись любого числа в смешанной Q-P -ичной системе совпадает с записью этого числа в Q-ичной системе.
Пример 3.2.5. Если P = 8, Q = 2 (8 = 2 3
), то
2763 8
= 010 111 110 011 2−8
= 010 111 110 011 2
. ¤
Таким образом, запись числа в P -ичной системе счисления в случае
P = Q
l
является просто сокращенной записью изображения этого же числа в Q-ичной системе: для такой сокращенной записи Q-ичные цифры в изоб- ражении числа объединяются вправо и влево от точки в группы по l раз- рядов (дополняя, в случае необходимости, нужное количество нулей справа и слева), и каждое число, представленное в Q-ичной системе этой группой разрядов, записывается одной P -ичной цифрой.
Пример 3.2.6. 1011011011.111011 2
= 0010 1101 1011.1110 1100 2
=
= 0010 1101 1011.1110 1100 2−16
= 2db.ea
16
. ¤

86
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
6.
Перевод чисел из одной системы счисления в другую
В связи с использованием различных систем счисления возникает необхо- димость перевода чисел из одной системы в другую. Задача перевода состоит в следующем. Пусть известна запись числа x в системе счисления с основа- нием P : x = (p
n
p
n−1
. . . p
0
.p
−1
p
−2
. . . p
−k
)
P
, где p
i
— цифры P -ичной систе- мы. Требуется найти запись числа x в системе счисления с основанием Q:
x = (q
m
q
m−1
. . . q
0
.q
−1
q
−2
. . . q
−1
)
Q
, где q
i
— цифры Q-ичной системы. При этом можно ограничиться рассмотрением положительных чисел, поскольку перевод любого числа сводится к переводу его абсолютной величины с по- следующим приписыванием соответствующего знака.
Для определенности будем считать, что в процессе перевода должны ис- пользоваться только средства P -ичной арифметики. В связи с этим необхо- димо рассмотреть перевод из Q-ичной системы в P -ичную (Q → P ) и из P - ичной в Q-ичную (P → Q).
Перевод Q → P . Если известна запись числа x в Q-ичной системе
x = (q
m
q
m−1
. . . q
0
.q
−1
q
−2
. . . q
−1
)
Q
, перевод в P -ичную систему сводится к вы- числению значения многочлена
x = q
m
Q
m
+ q
m−1
Q
m−1
+ . . . + q
0
+ q
−1
Q
−1
+ q
−2
Q
−2
+ . . . + q
−l
Q
−l
,
что следует из правил записи числа x в Q-ичной системе.
Пример 3.2.7. Переведем число x = ba.8 16
в десятичную систему сред- ствами десятичной арифметики. Здесь Q = 16, P = 10. Имеем
x = 11 · 16 + 10 + 8 · 16
−1
= 186.5 10
. ¤
Перевод P → Q. Рассмотрим перевод целых чисел и правильных дробей.
В общем случае перевод любого числа сводится к независимому переводу его целой и дробной частей.
Перевод целых чисел. Пусть дана запись целого числа N в системе счис- ления с основанием P . Поскольку N — целое число, его запись в Q-ичной системе будет иметь вид N = (q
k
q
k−1
. . . q
0
)
Q
, где q
i
(0 6 q
i
< Q) — иско- мые цифры Q-ичной системы. Эта запись является сокращенной записью многочлена N = q
k
Q
k
+ q
k−1
Q
k−1
+ . . . + q
0

3.2. СИСТЕМЫ СЧИСЛЕНИЯ
87
Для определения q
0
разделим обе части последнего равенства на Q:
N/Q = q
k
Q
k−1
+ . . . + q
1
+ q
0
/Q. Приравнивая между собой целые и дробные части в левой и правой частях (учитывая, что q
i
< Q), получим, что q
0
есть остаток от деления N на Q.
Целочисленное частное от деления N на Q обозначим через N
1
Тогда N
1
= q
k
Q
k−1
+ . . . + q
1
. Поскольку N
1
есть целое число, к нему можно применить тот же прием для определения значения q
1
, которое равно остат- ку от деления N
1
на Q. Полученное при этом частное обозначим через N
2
и т. д. Этот процесс заканчивается, когда очередное частное окажется рав- ным нулю. Для окончательной записи числа N в Q-ичной системе нужно в соответствующем порядке записать коэффициенты q
i
, изображая каждый из них одной Q-ичной цифрой.
Пример 3.2.8. 1. Переведем десятичное число N = 23 в двоичную систему средствами десятичной арифметики (P = 10, Q = 2):
23/2 = 11 + 1/2, q
0
= 1, N
1
= 11,
11/2 = 5 + 1/2, q
1
= 1, N
2
= 5,
5/2 = 2 + 1/2, q
2
= 1, N
3
= 2,
2/2 = 1 + 0/2, q
3
= 0, N
4
= 1,
1/2 = 0 + 1/2, q
4
= 1, N
5
= 0.
Поскольку числа нуль и единица в каждой из этих систем обозначаются цифрами 0 и 1, то в процессе деления сразу получены искомые двоичные цифры: N = 10111 2
2. Переведем число N = 175 10
в шестнадцатеричную систему:
175/16 = 10 + 15/16, q
0
= 15, N
1
= 10,
10/16 = 0 + 10/16, q
1
= 10, N
2
= 0.
Таким образом, N = 10 · 16 1
+ 15 · 16 0
. Число 10 соответствует шестнадцате- ричной цифре a, число 15 — цифре f , следовательно, N = af
16
. ¤
Перевод дробных чисел. Пусть требуется перевести в P -ичную систему правильную дробь x (0 6 x < 1), заданную в ее P -ичной записи:
x = 0.p
−1
p
−2
. . . p
−k
. Запись этого числа в Q-ичной системе будет иметь вид

88
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
части очередного полученного произведения. Этот процесс продолжается до тех пор, пока дробная часть очередного произведения не окажется рав- ной нулю либо не будет достигнута требуемая точность изображения числа x
в Q-ичной системе.
Пример 3.2.9. Перевод числа x = 0.1 10
в двоичную систему приводит к такой последовательности действий:
0.1 · 2 = 0.2, q
−1
= 0, дробная часть = 0.2,
0.2 · 2 = 0.4, q
−2
= 0, дробная часть = 0.4,
0.4 · 2 = 0.8, q
−3
= 0, дробная часть = 0.8,
0.8 · 2 = 1.6, q
−4
= 1, дробная часть = 0.6,
0.6 · 2 = 1.2, q
−5
= 1, дробная часть = 0.2,
. . .
Очевидно, что дальше результаты будут повторяться, и поэтому
x = (0.0001100110011 . . .)
2
= 0.0(0011)
2
. ¤
§ 3.3.
Компьютерная алгебра и численный анализ
Термин компьютерная алгебра объясняется способностью компьюте- ров манипулировать математическими выражениями, заданными символь- но, а не численно. Системы компьютерной алгебры освобождают от рутин- ной работы, связанной с численными ошибками (усечение и округление).
Прежде чем рассматривать точную арифметику, реализуемую в систе- мах компьютерной алгебры, отметим неотъемлемые недостатки численных расчетов с использованием компьютеров. Компьютер — это машина с конеч- ной памятью, состоящей из слов конечной длины алфавита {0, 1}. Элементы компьютерного слова называются битами. Обычно длина компьютерного слова составляет 16 или 32 бита, при этом максимальное целое число, кото- рое можно разместить в слове (в двоичной системе счисления), составляет
2 16
−1 или 2 32
−1, что соответствует пятизначным или десятизначным числам в десятичной системе счисления.
При выполнении численных расчетов на компьютере обычно возникает проблема представления бесконечного множества вещественных чисел в ко- нечной памяти. Наиболее распространенным способом решения этой пробле- мы в численном анализе является приближение (округление) вещественных чисел с использованием конечного множества с плавающей точкой.

3.3. КОМПЬЮТЕРНАЯ АЛГЕБРА И ЧИСЛЕННЫЙ АНАЛИЗ
89 0
1 4
1 2
1 2
3 3
1 2
−
1 4
−
1 2
−1
−2
−3
−3 1
2
Рис. 3.1
Множество F чисел с плавающей точкой характеризуется основанием счисления P , точностью t и областью значений экспоненты [L, U ], где пара- метры P, t, L, U зависят от компьютера. Каждое число f ∈ F представляется в виде
f = ±
µ
d
1
P
+
d
2
P
2
+ . . . +
d
t
P
t
¶
P
e
,
где целые числа d
i
, i = 1, 2, . . . , t, удовлетворяют неравенствам 0 6 d
i
6 P −1,
L 6 e 6 U. Если d
1
6= 0, число f ∈ F называется нормализованным числом
с плавающей точкой.
Отметим, что при использовании чисел с плавающей точкой или целых чисел, помещающихся в одном компьютерном слове, арифметические опера- ции выполняются очень быстро, поскольку они производятся не программ- ным обеспечением, а электронными схемами компьютера.
Нетрудно подсчитать, что множество F содержит
2(P − 1)P
t−1
· (U − L + 1) + 1
нормализованных чисел с плавающей точкой (включая нуль). Эти числа размещены на числовой прямой равномерно не на всей области значений,
а только между последовательными степенями P .
Пример 3.3.1. На рис. 3.1 изображено 33-элементное множество норма- лизованных чисел с параметрами P = 2, t = 3, L = −1, U = 2. ¤
Приведенный пример показывает, что сумма (или произведение) данных чисел f
1
и f
2
из F может не принадлежать F и должна быть приближена ближайшим числом с плавающей точкой. Разность между истинным и при- ближенным значениями суммы (или произведения) является ошибкой округ- ления. Отметим также, что частичные операции сложения и умножения в F
не удовлетворяют законам ассоциативности и дистрибутивности. Например,
в 33-элементном множестве F справедливо 5/4 + (3/8 + 3/8) = 2, где 5/4,

90
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
3/8, 2 ∈ F . Однако (5/4 + 3/8) + 3/8 6= 2, поскольку в F не определена сумма
(5/4+3/8) и это выражение должно быть приближено в F либо числом 3/2,
либо числом 7/4. Ошибки округления могут возникать и при работе с це- лыми числами, например, при вычислении произведения двух s-значных чисел на компьютере, который не может обрабатывать числа, содержащие больше s цифр.
Таким образом, в численном анализе нужно тщательно оценивать ошиб- ки округления, возникающие при работе любого алгоритма. Это указывает на необходимость построения и использования программных систем, способ- ных обрабатывать выражения в символьном виде и производить безошибоч- ные вычисления. Опишем два подхода к построению таких систем, первый из которых использует списочное представление чисел, а второй — много- модульную арифметику.
§ 3.4.
Списочное представление чисел
1.
Списки и базисные операции над списками
Определим по индукции понятие списка над множеством S:
1) любой элемент a ∈ S является списком над множеством S;
2) если a
1
, . . . , a
n
— списки над множеством S, n > 0, то (a
1
, . . . , a
n
) —
список над множеством S;
3) никаких списков над множеством S, кроме построенных по пп. 1 и 2,
нет.
Список, соответствующий n = 0 в п. 2, называется пустым и обозна- чается так же, как и пустое слово, через Λ. По определению каждое слово непустого алфавита S является списком над S.
Определим основные операции над списками. Если a = (a
1
, . . . , a
n
) —
список, то
длина(a) ­ l(a) ­ n;
первый(a) ­ π
1
(a) ­ a
1
;
последний(a) ­ π
n
(a) ­ a
n
;
хвост(a) ­ π
2,...,n
(a) ­ (a
2
, . . . , a
n
);
развернутый(a) ­ π
n,...,1
(a) ­ (a
n
, . . . , a
1
);
если b = (b
1
, . . . , b
k
) — список, то
присоединение(b, a) ­ bˆa ­ (b
1
, . . . , b
k
, a
1
, . . . , a
n
);
отсоединение(b, bˆa) ­ a.