Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
x = 0.q −1 q −2 . . . q −m . . . Значит, x = q −1 Q −1 + q −2 Q −2 + . . . + q −m Q −m + . . . , где q i — коэффициенты Q-ичного разложения, подлежащие определению. Нетрудно убедиться, что эти коэффициенты можно получить путем после- довательного умножения на Q сначала исходного числа x, а затем дробной 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. 3.4. СПИСОЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЕЛ 91 2. Списочное представление целых и рациональных чисел Как уже отмечалось, компьютерное представление целых чисел ограни- чено длиной машинного слова. Для расширения возможностей такого пред- ставления и выполнения точных арифметических действий можно исполь- зовать задание целых чисел в виде списков. При этом, однако, необходи- мо разработать специальное программное обеспечение, позволяющее выпол- нять арифметические операции над списками. Пусть P — такое основание счисления, что P − 1 — наибольшее значение, хранимое в компьютерном слове. Рассмотрим два типа целых чисел. Если −(P − 1) 6 m 6 P − 1, то целое число m называется коротким. Осталь- ные целые числа называются длинными. Длинные числа m представляются в виде списка m = (m 0 , m 1 , . . . , m k ), k > 1, где m i — короткие целые числа (|m i | 6 P − 1), являющиеся коэффициентами в выражении m = k P i=0 m i · P i и имеющие тот же знак, что и число m. При хранении числа m в виде списка информацию о знаке будем записывать только в m k Пример 3.4.1. Предположим, что P = 10 3 , т. е. компьютерное сло- во может содержать только три десятичные цифры. Представление числа m = +23456789 в виде списка выглядит следующим образом: m = (789, 456, +23). ¤ Рациональные числа r = m n представляются списками r = (m, n), где m, n — списки, представляющие целые числа m и n. 3. Классические алгоритмы целочисленной арифметики Рассмотрим классические алгоритмы выполнения арифметических опе- раций с длинными целыми числами. Пусть m = k P i=0 m i · P i и n = l P i=0 n i · P i — длинные целые числа, m = (m 0 , m 1 , . . . , m k ) и n = (n 0 , n 1 , . . . , n l ) — соот- ветствующие списки. При сложении списков m и n последовательно скла- дываются (с использованием встроенной в компьютер операции сложения) короткие целые числа, находящиеся в соответствующих координатах спис- ков, и при сложении координат учитываются переносы от меньших разрядов к большим аналогично сложению десятичных чисел. Полученный список s 92 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ называется суммой списков m и n: m + n. Точно так же, используя школь- ные алгоритмы целочисленного умножения, поразрядным перемножением коротких целых чисел с переносом от меньших разрядов к большим опреде- ляется произведение списков m и n: m · n. Предложение 3.4.1. Алгебра hZ; +, ·i изоморфна алгебре hZ; +, ·i, где Z — множество списков, задающих целые числа. ¤ При делении m на n ищутся целые числа q и r, обладающие свойством делимости с остатком: m = nq + r, 0 6 r < n. Для определения операции деления со списками достаточно описать случай, когда n 6 m < P n. Общий случай сводится к этому случаю аналогично тому, как к нему сво- дится общий случай деления столбиком. Пример 3.4.2. При делении 1234 на 23 сначала делится 123 (начальное число m) на 23 (число n): 123 = 23 · 5 + 8, затем 84 (новое число m) делится на 23: 84 = 23 · 3 + 15. Таким образом, имеем 1234 = (23 · 5 + 8) · 10 + 4 = = 23 · 50 + 84 = 23 · 50 + 23 · 3 + 15 = 23 · 53 + 15. ¤ Наиболее очевидный подход к решению состоит в угадывании частно- го q по наиболее значимым цифрам чисел m и n. Полученное таким путем частное называется пробным частным и обозначается через q t . Согласно нашим предположениям, m = m 0 + . . . + m k · P k , n = n 0 + . . . + n k−1 · P k−1 , n 6 m < P n. Обозначим через [x] целую часть числа x, т. е. наибольшее целое число, не превосходящее числа x. Положим q t ( P − 1, если m k = n k−1 , h m k P +m k−1 n k−1 i , если m k < n k−1 . Пример 3.4.3. Обозначим истинное частное через q. Тогда при P = 10 имеем: • если m = 600, n = 69, то m 2 = n 1 , а следовательно, q t = 9, в этом случае q = 8; • если m = 480, n = 59, то q t = [48/5] = 9, в этом случае q = 8; • если m = 200, n = 29, то m 2 = n 1 , поэтому q t = 9, в этом случае q = 6. ¤ Отметим, что во всех случаях q t слишком велико, однако при n = 69 уга- данное значение не так плохо, как при n = 29. Величина такого отклонения объясняется следующей теоремой. 3.5. ДЕЛИМОСТЬ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ 93 Теорема 3.4.2. Если целые числа q t и q являются пробным частным и частным соответственно при делении m на n, то q t > q. Более того, если n k−1 > P/2, то q t − 2 6 q 6 q t , т. е. q t равно либо q, либо q + 1, либо q + 2. Доказательство. Из qn 6 m, используя неравенство m 0 + . . . + +m k−2 P k−2 < P k−1 , получаем, что qn k−1 P k−1 < (1 + m k−1 + m k P )P k−1 , сле- довательно, qn k−1 < m k−1 + m k P , где q 6 P − 1. Тогда из определения q t , очевидно, следует, что q t > q. Предположим теперь, что n > P/2. В этом случае достаточно показать, что (q t − 2)n 6 m. Используя неравенство n 0 + . . . + n k−2 · P k−2 < P k−1 , получаем (q t − 2)n < (q t − 2)(n k−1 + 1)P k−1 = (q t n 1 + (q t − 2 − 2n k−1 ))P k−1 6 6 (m k P + m k−1 )P k−1 + (q t − 2 − 2n k−1 )P k−1 по определению q t . Поскольку n k−1 > P/2 и q t 6 P − 1, имеем q t − 2 − 2n k−1 < 0, (m k P + m k−1 )P k−1 + (q t − 2 − 2n k−1 )P k−1 6 (m k P + m k−1 )P k−1 6 6 (m k P + m k−1 )P k−1 + m k−2 P k−2 + . . . + m 0 = m, что и требовалось доказать. ¤ Чтобы добиться выполнения условия, что старшая цифра делителя боль- ше либо равна P/2, нужно домножить m и n на 2 e , где 2 e — наибольшая степень 2, для которой 2 e · n < P k+1 . Затем делим 2 e · m на 2 e · n. Пример 3.4.4. Рассмотрим P = 10, m = 200, n = 29. Вычислим наибольшее число e, для которого 2 e · 29 < 1000. Получаем e = 5 и 2 e · m = 32 · 200 = 6400, 2 e · n = 32 · 29 = 928. Имеем q t = [64/9] = 7, что отличается от истинного частного q = 6 на единицу. ¤ После нахождения пробного частного q t достаточно выбрать истинное частное среди чисел q t , q t − 1, q t − 2. § 3.5. Делимость в кольце целых чисел Будем говорить, что ненулевое целое число a делит целое число b или a является делителем b (записывается a | b), если существует такое целое чис- ло c, что b = a · c. Например, ±7 | 28, так как 28 = 7 · 4 и 28 = (−7) · (−4). Для любого ненулевого числа a имеем a | 0, ±1 | a и ±a | a. Понятие делителя будет очень важным в нашем изложении теории целых чисел. 94 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Одно из основных свойств целых чисел — свойство делимости или ев- клидовости. Теорема 3.5.1 (свойство евклидовости). Для любого a и любого нену- левого b существуют единственные (целые) частное q и остаток r такие, что a = b · q + r, 0 6 r < |b|. Доказательство. Рассмотрим множество целых чисел вида a − kb, где k ∈ Z. Выберем в этом множестве наименьшее неотрицательное число (такое число существует, поскольку система hω; 6i является вполне упорядоченным множеством). Обозначим это число через |