Системы счисления. Внутреннее целых и вещественных чисел. Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем. - презентация

1 Системы счисления. Внутреннее целых и вещественных чисел. Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ОСНОВЫ ПРОГРАММИРОВАНИЯ

2 Системы счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2

3 Системы счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 Число –абстрактная сущность для описания количества. Цифры – это знаки, используемые для записи чисел. Чисел больше чем цифр => для записи числа используется комбинация цифр. Система счисления (CC): символический метод записи чисел, представление чисел с помощью письменных знаков. В СС каждое число имеет уникальное представление. Величина числа может зависеть и не зависеть от порядка цифр в записи. Систем счисления подразделяются на: позиционные непозиционные смешанные

4 Позиционные системы счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Под позиционной системой счисления обычно понимается b-ричная система счисления, которая определяется целым числом b, называемым основанием системы счисления. Целое число без знака x в b-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа b: где a k – набор весовых коэффициентов разрядов, k – номер разряда. Например: 4285 = т.е. a = {5, 8, 2, 4}

5 Наиболее употребляемые позиционные системы счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 В позиционных системах чем больше основание системы, тем меньшее количество разрядов (цифр) требуется при записи числа. bНазваниеОписание 1единичнаясчет на пальцах, зарубки, узелки 2двоичнаядискр. математика, информатика 8восмеричнаяпрограммирование, информатика 10десятичнаяиспользуется повсеместно 12двенадцатеричнаясчет дюжинами, время 16шестнадцатеричнаяпрограммирование, информатика 60шестидесятеричнаявремя, углы, координаты

6 Непозиционные системы счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 В непозиционных СС значение цифры не зависит от ее расположения. Однако такая СС может накладывать ограничения на положение цифр (например, расположение по убыванию). Римская система счисления. Цифры: Натуральные числа записываются при помощи повторения римских цифр. Если большая цифра стоит перед меньшей, то они складываются (принцип сложения), иначе – меньшая вычитается из большей (принцип вычитания) ? ? ? XCIX - ? DLXXXIII - ? MMXII - ? IVXLCDM

7 Непозиционные системы счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 В непозиционных СС значение цифры не зависит от ее расположения. Однако такая СС может накладывать ограничения на положение цифр (например, расположение по убыванию). Римская система счисления. Цифры: Натуральные числа записываются при помощи повторения римских цифр. Если большая цифра стоит перед меньшей, то они складываются (принцип сложения), иначе – меньшая вычитается из большей (принцип вычитания) MMMCDXXI CMLXXIV DCCCXXXVIII XCIX - 99 DLXXXIII MMXII IVXLCDM

8 Смешанные системы счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Смешанная система счисления является обобщением b-ричной системы счисления. Зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел {b k }, и каждое число в ней представляется как линейная комбинация: где на коэффициенты a k, называемые как и прежде цифрами, накладываются некоторые ограничения. Записью числа x в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса k, начиная с первого ненулевого a k.

9 Представление времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. Величина «d дней, h часов, m минут, s секунд» соответствует значению

10 Недостатки непозиционных и смешанных систем счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 Непозиционные СС: Требуют постоянного введения новых знаков для записи больших чисел. Не предусмотрено представление дробных и отрицательных чисел. Затруднено создание универсальных алгоритмов выполнения арифметических операций. Смешанные СС: Трудны для восприятия человека. Больше подходят для решения конкретной задачи (представление времени).

11 Перевод чисел между позиционными системами (способ 1) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 Перевод из системы счисления с основанием b в CC с основанием с: Примеры: x b x c x b = a N a N-1 … a 1 a 0 x c = (a N ) c (b c ) N + (a N–1 ) c (b c ) N-1 + … + (a 1 ) c (b c ) 1 + (a 0 ) c (b c ) = = = = AF 16 = = = = 4 16 A A = Вычисление в недесятичной системе счисления затруднительны Вычисление в недесятичной системе счисления затруднительны

12 Перевод чисел между позиционными системами (способ 2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» = Для перевода числа x a в систему с основанием b необходимо разделить x a на b. Деление продолжать до тех пор, пока частное не станет меньше b. Остатки от деления, записанные в обратном порядке, начиная с частного, будут искомым числом.

13 Анализ способа 2 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 mod – остаток от деления

14 Анализ способа 2 (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14

15 Алгоритм перевода чисел между позиционными системами по способу 2 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 a 0 = x mod b, x = x div b, (1) a 1 = x mod b, x = x div b, (2) a 2 = x mod b, x = x div b, (3) … a N–1 = x mod b, x = x div b, (N-1) a N = x, (x < b), (N) Начало x x x > 0 y = 0 s = 1 y = 0 s = 1 y = y + (x mod b)s x = x div b s = s b y = y + (x mod b)s x = x div b s = s b Конец

16 Двоичная система счисления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 Транзистор Элементная база позволяет создавать приборы, имеющие два устойчивых состояния Наиболее удобной является двоичная система счисления Конденсатор Ферромагнетики

17 Двоичная арифметика СЛОЖЕНИЕ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 x / yx / y x + y Примеры: , , ,001

18 Двоичная арифметика УМНОЖЕНИЕ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 x/y x y Примеры: *101 * _

19 Двоичная арифметика ВЫЧИТАНИЕ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 x – y Примеры: = -( ) x/y

20 Двоичная арифметика ДЕЛЕНИЕ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 Деление в двоичной системе счисления выполняется, как и в десятичной системе. Пример:

21 Внутреннее представление целых чисел в ЭВМ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21

22 Представление чисел в ЭВМ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 Особенности представления чисел в ЭВМ: используется двоичная система счисления ограниченное количество разрядов в ЭВМ используется память, элементарная ячейка которой (бит) может иметь только 2 состояния (0 и 1). Поэтому отсутствует возможность хранить знаки: ( "+", "–" и "." ).

23 Представление целых чисел без знака © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 23 Пусть дана ячейка памяти, размер которой k бит. Существует 2 k всевозможных битовых наборов длины k. Следовательно, всего возможно представить 2 k различных чисел. Существует (2 k )! способов закодировать беззнаковые числа битовыми наборами. Среди всех теоретически возможных способов наиболее удобно использовать k-разрядную запись этого числа в двоичной системе счисления. Это позволяет естественным образом реализовать арифметические операции над числами = =

24 Сложение и вычитание целых чисел без знака © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 24 Сложение и вычитание k-разрядных целых чисел без знака происходит по обычным для позиционных систем счисления правилам. Примеры (для k = 3): = ; = Ситуации, когда уменьшаемое меньше вычитаемого или когда результат суммы не умещается в k разрядов, считаются ошибочными и должны отслеживаться устройством компьютера. Обработка переполнения: Если при сложении двух k-разрядных чисел возникает (k+1)-й разряд, то он будет отброшен. Пример (для k = 3): = = = = 1 10

25 Представление знаковых целых Отрицательные числа могут быть представлены в ЭВМ несколькими способами, выбор одного из которых оказывает влияние на реализацию арифметических операций. Для представления знаковых целых чисел используются три способа: 1) прямой код; 2) обратный код; 3) дополнительный код. 25 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

26 Прямой код 26 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Это наиболее очевидный и близкий к естественному способ записи чисел. Число формируется из одного знака и фиксированного количества разрядов (цифр), представляющих собой модуль числа. При формировании прямого кода в двоичной системе старший бит (разряд) используется для хранения знака: 0 ~ "+", 1 ~ "-". Например: = , = = , =

27 Обратный код 27 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Обратный код отрицательного числа в двоичной СС формируется путем инвертирования каждого разряда, включая знак, на противоположный. Также для формирования обратного кода можно использовать следующее выражение: из максимального числа, состоящего из 1-ц во всех разрядах, вычесть модуль отрицательного числа. -x = |x| (для 8-битных целых) = , – = – = – =

28 Обратный код (сумма) 28 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Сложение в обратном коде происходит следующим образом: по обычному алгоритму складываются все разряды, включая знаковый. Если результат имеет длину k+1 (был перенос при сложении старших разрядов операндов, иначе – нулю). Значение левого k+1-го разряда добавляется к младшему разряду результата. Получаем k-разрядный набор, который и будет суммой двух чисел в обратном коде. – = I (– ) = = II = = Вычитание чисел в обратном коде сводится к сложению x – y = x + (–y). Вычитание чисел в обратном коде сводится к сложению x – y = x + (–y).

29 Дополнительный код 29 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Положительные числа в дополнительном коде представляются в двоичной системе счисления. Для представления отрицательных чисел формируется число (M(k)+1), где M(k) – максимальное двоичное число разрядности k (1-цы во всех разрядах). Далее (k = 8): M(8) + 1 = = – x = 0 – |x| = – |x| – 1 = 0 – 1 = – 1 = – = – = – = – 20 ноль имеет два представления в прямом и обратном коде, а в дополнительном коде представление нуля единственно.

30 Дополнительный код (сумма) 30 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» В дополнительном коде сложение происходит так: по обычному алгоритму: складываются все разряды, включая знаковый; единица переноса в (k+1)-й разряд отбрасывается (сложение по модулю 2 k ). – = – = – = I (– ) = = Вычитание чисел в дополнительном коде сводится к сложению x – y = x + (–y). Вычитание чисел в дополнительном коде сводится к сложению x – y = x + (–y)

31 Дополнительный код 31 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Сложение и вычитание по модулю 2 k Связь дополнительного и обратного кодов: = + 1 Дополнительный код – х = 0 – |х| = – |х| – 1 = 0 – 1 = – 1 = Обратный код – х = 0 – |х| = – |х| – 1 = 0 – 1 = – 1 =

32 Сравнение различных представлений знаковых чисел (двоичная система, 3 бит) 32 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Битовый набор Без знака Прямой код Обратный код Доп. код –0–3–4 1015–1–2–3 1106–2–1–2 1117–3–0–1

33 Недостатки дополнительного кода 33 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Битовый набор Доп. код –4 101–3 110–2 111–1 1.Несимметричность диапазона представи- мых значений относительно 0. Для рассмотренного примера не существует числа 4, однако есть число –4. Это может приводить к переполнению операции –x. 2.Поразрядный сдвиг вправо на один разряд для отрицательных чисел дает результат, отличный от результата для положительных: 5>>1 = 2, -5>>1 = -3. В общем случае результат сдвига может быть описан следующей формулой: x>>1 = x/2, где y = x - округление в меньшую сторону (ближайшее к x целое, такое, что y < x),например 6.7 = 6.

34 Внутреннее представление вещественных чисел в ЭВМ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 34

35 Вещественные числа 35 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» В памяти ЭВМ не предусмотрено специальных средств для запоминания десятичной точки. Существует два способа представить вещественное число в виде десятичной дроби: 1. Явно указав позицию запятой внутри числа: , ; 2. Научный, с помощью степени (например по основанию 10): *10 1, 0.98*10 -2.

36 Вещественные числа с фиксированной запятой (точкой) 36 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Данное представление соответствует первому варианту записи вещественных чисел. Положение точки внутри байта (байтов) задается фиксировано. Например: пусть для хранения используется 1 байт, для хранения целой части отведем биты с 0 по 4, для дробной – с 5 по 7: Недостатки: 1) Малый диапазон значений. 2) Неэффективное использование памяти при работе только с малыми числами или только с большими числами.

37 Научная форма записи вещественных чисел 37 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Научная форма записи вещественных чисел позволяет представить одно и то же число множеством различных способов. Например, постоянная Планка h = может быть записана одним из следующих способов: 1) ) ) ) )…

38 Вещественные числа с плавающей запятой (точкой) 38 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» p-разрядным числом с плавающей точкой по основанию b с избытком q называется пара величин (e,f), которой соответствует значение: ( e, f ) = f b (e – q) e – порядок – беззнаковое целое число, изменяющаяся в определенном промежутке. f – мантисса – знаковое вещественное число с фиксированной точкой, при этом | f | < 1, т.е. разделяющая точка находится в крайней слева позиции. q – избыток, для знакового представления порядка. Число с плавающей точкой является нормализованным, если: 1) наиболее значимая цифра в представлении f отлична от нуля: 1/b | f | < 1 2) f = 0 и е принимает наименьшее возможное значение Например: 0.615, 0.101, 6.15, 0.01

39 p-разрядные нормализованные числа 39 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ( e, f ) = f b e-q В ЭВМ для хранения вещественных чисел отводится ограниченное число разрядов, т.е. f b p – целое число и –b p f b p b p, Пример: 6-разрядное вещественное число, е – 2 разряда, избыток q = 50, основание b = 10. Постоянную Авогадро – физическая величина, численно равная количеству атомов, молекул и т.д. в 1 моле вещества: N A = 6, (18)·10 23 = 6, (18) · моль 1 Нормализованная форма ( e, f ): ( e, f ) = (74, 0, (18)) p-разрядное представление (e',f '): f ' 10 6 = [f 10 6 ] = [ , (18)] = (e',f ') = (74, 0,602214)

40 Стандарт IEEE (Single precision) 40 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Размер, выделяемый для хранения: 4 байта (32 бита) (e, f,s) = s1.f b e-q f: 23 бит; e: 8 бит; s: 1 бит, b = 2, q = – 1 = fes В стандарте IEEE понятие нормализованной дроби несколько изменено: 1 2 | f | < 10 2 Например: ,

41 Примеры внутреннего представления вещественных чисел (1) 41 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ( e, f,s) = s1.f b e-q Десятичное представление1 Двоичное представление Результат упаковки (hex)3f Двоичное представление f1.0 e =7F 16 = s0 (~ "+" ) ( 127, 0,0) = = fes

42 Примеры внутреннего представления вещественных чисел (2) 42 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ( e, f,s) = s1.f b e-q Десятичное представление Двоичное представление Результат упаковки (hex)bf Двоичное представление f1.0 e =7F 16 = s1 (~ "–" ) ( 127, 0,1) = – = –1.0 0 fes

43 Примеры внутреннего представления вещественных чисел (3) 43 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ( e, f,s) = s1.f b e-q Десятичное представление Двоичное представление = Результат упаковки (hex) 3d Двоичное представление f1.0 e =7B 16 = s0 (~ "+" ) ( 127, 0,0) = = = fes

44 Примеры внутреннего представления вещественных чисел (4) 44 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ( e, f,s) = s1.f b e-q Десятичное представление 5.3 Двоичное представление … Результат упаковки (hex) 40 a9 99 9a Двоичное представление f e =81 16 = s0 (~ "+" ) ( 127, 0,0) = … = … fes

45 Анализ числа © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» = = = = , , , , , , , , , = 5, , = 5,

46 Примеры внутреннего представления вещественных чисел (5) 46 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ( e, f,s) = s1.f b e-q Десятичное представление 5.1 Двоичное представление … Результат упаковки (hex) 40 a Двоичное представление f e =81 16 = s0 (~ "+" ) ( 127, 0,0) = … = … fes

47 Анализ числа © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» = = = = 5 + 0, , , , , , , , , , = 5,

48 Ошибки округления 48 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Технические средства не позволяют хранить числа, заданные бесконечными дробями Необходима замена любого числа конечной дробью, ограниченной доступным количеством разрядов. Данная операция называется округлением. Округлением числа x = ±d n …d s+1 d s d s–1 d s–2 до s разрядов в заданной СС называется его замена числом x s = ±d n …d s+1 d s, в котором разряды (s – 1), (s – 2), … являются нулевыми. Разность (x – x s ) называется ошибкой округления.

49 Способы округления 49 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1.Отбрасывание разрядов (s – 1), (s – 2),… как это реализовано для целых чисел. Достоинством данного подхода является простота аппаратурной реализации. Недостатком служит то, что знак ошибки (x * x) всегда противоположен знаку x. Ошибка имеет тенденцию накапливаться. 2.Округление по правилам, используемым в арифметике. Вещественные числа X i s, имеющие нулевые младшие разряды (s – 1), (s – 2), … располагаются на числовой оси с шагом b s, как показано на рисунке. При этом среди этих чисел есть число x *, которое наиболее близко к x и | x * x | b s X 3 -2 X 2 -2 X 0 -2 X 1 -2 X X x x*x* X …… b = 2, s =-2:

50 Примеры применения алгоритмов округления для числа © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Отбрасывание разрядов: 5.3 = = 5, = 5, , ,3 = 2.86 · Округление с использованием правил арифметики: 5.3 = = = = 5, = 5, , – 5,3 = 1.91 · 10 -7

51 Примеры применения алгоритмов округления для числа © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Отбрасывание разрядов: 5.1 = = 5, , ,1 = 0.95 · Округление с использованием школьной арифметики 5.1 = = 5, , ,1 = 0.95 · 10 -7

52 Машинный ноль 52 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ( e, f,s) = s1.f b e-q Десятичное представление 0 Двоичное представление 0 Результат упаковки (hex) Двоичное представление f e =0 16 =0 10 s0 (~ "+" ) ( 0, 0,0) = … = … fes

53 Машинный ноль 53 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Число ω, для которого f = 0, мантисса m = 1.0, а порядок e принимает наименьшее значение (для float e = 0 => (e – q)= – 127) называется машинным нулем. Оно совпадает с минимальным положительным числом, которое может быть представлено числом с плавающей точкой при заданных размерностях f и e (для float размерность f – 23 бита, e – 8 бит). Любое число x < ω рассматривается как 0! ( e, f,s) = s1.f b e-q

54 Погрешности измерений 54 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Абсолютная погрешность (Δх) разность между приближенным значением некоторой величины и ее точным значением: Δх = |x п – x т |, где x т – точное значение, а x п – приближенное. Относительная погрешность (δx) – погрешность измерения, выраженная отношением абсолютной погрешности измерения к действительному или измеренному значению рассматриваемой величины: δx = Δх/x п, δx – безразмерная величина. В отличие от чисел с фиксированной точкой, сетка чисел, которые способна отобразить арифметика с плавающей точкой, неравномерна: она более густая для чисел с малыми порядками и более редкая для чисел с большими порядками. Для чисел с фиксированной точкой постоянным является порядок абсолютной погрешности. Для чисел с плавающей точкой постоянным является порядок относительной погрешности.

55 Погрешности вещественных чисел с фиксированной точкой 55 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Рассмотрим 2-хразрядные числа с фиксированной точкой, один разряд отводится под целую часть, второй – под дробную. x 0.0 … … Δх 1 = | x п – x т | = | – 0.1 | = 0.023, порядок Δх 2 = | x п – x т | = | – 1.2 | = 0.015, порядок δx 1 = Δх/x п = 0.023/ , порядок δx 2 = Δх/x п = 0.015/ ,0127, порядок 10 -2

56 Погрешности вещественных чисел с плавающей точкой 56 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Рассмотрим 2-хразрядные числа с плавающей точкой, один разряд отводится под мантиссу, второй – под порядок. x 0.0 … 0.1· · · · · · · ·10 9 Δх 1 = | x п – x т | = 0.023·10 -9, порядок Δх 2 = | x п – x т | = 0.023·10 9, порядок δx 1 = Δх/x п = 0.023·10 -9 / 0.123· , порядок δx 2 = Δх/x п = 0.023·10 9 / 0.123· , порядок 10 -1

57 Машинный эпсилон 57 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Машинным эпсилоном называется наименьшее положительное число ε такое, что 1 ε 1, где машинное сложение. Пример: Пусть даны два числа: a и b = a + γ. Если γ = a·λ < a·ε, то с точки зрения машины a = b. a < a + γ < a·(1 λ) < a·(1 ε) 1 λ = 1, если λ < ε.

58 Программа поиска машинного эпсилона 58 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» #include int main() { float e,e1; int k=0; e=1.0; do { e=e/2.0; e1=e+1.0; k++; } while (e1>1.0); printf("Число делений на 2: %d\n", k); printf("Машинный эпсилон: %e\n", e); return 0; } Результаты работы: Число делений на 2: 24 Машинный эпсилон: e-08

59 Влияние точности вычислений на результат 59 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» #include int main() { float a = e5, b = e5, c = 1.3; float x1 = a + b; x1 = x1 + c; float x2 = b + c; x2 = x2 + a; printf("x1 = %f, x2 = %f, ",x1, x2); printf("x1 - x2 = %f\n", x1 - x2); } $./float_assoc x1 = , x2 = , x1 - x2 = Одним из наглядных примеров влияния на результат арифметики с ограниченной разрядностью является нарушение некоторых аксиом. Аксиома ассоциативности: (a + b) + c = a + (b + c)

60 Алгоритм сложения чисел с плавающей точкой (по Д. Кнуту) 60 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача: найти число ω = υ ν, p-разрядная арифметика а : (2p + 1) разрядный аккумулятор 1input υ, νp = 3, υ = 0,0185, ν = υ (e υ, ± f υ ) и ν (e ν, ± f ν ) υ=(-1,+0.185), ν=(1,+0.151) 3if e ν > e υ then1 > -1 4 υ ν (e ν e υ и f υ f ν ) υ=(1,+0.115), ν= (-1,+0.185) 5e ω = e υ e ω = 1 6 if (e υ e ν ) p + 2 then e υ e ν = 1 – (-1) = 2 < p +2=5 7 f ω = f υ 8else f ν = f ν >>(e υ e ν ), a= f ν /b (e υ e ν ) a = >> 100 = a = f υ + a, f ω = окр(a, p)a = = f ω = окр( ,3) = 0,153 ω = (1,153) normalize(ω) = (1,153) 10 (e ω, ± f ω ) ω 11 normalize(ω)

61 Алгоритм сложения чисел с плавающей точкой (по Д. Кнуту) 61 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача: найти число ω = υ ν, p-разрядная арифметика а : (2p + 1) разрядный аккумулятор 1input υ, νp = 3, υ = -0,00009, ν =0.1 2 υ (e υ, ± f υ ) и ν (e ν, ± f ν ) υ=(-4,-0.9), ν=(0,+0.1) 3if e ν > e υ then1 > -4 4 υ ν (e ν e υ и f υ f ν ) υ=(0,+0.1), ν= (-4,-0.9) 5e ω = e υ e ω = 0 6 if (e υ e ν ) p + 2 then e υ e ν = 0 – (-4) = 4 < p +2=5 7 f ω = f υ 8else f ν = f ν >>(e υ e ν ), a= f ν /b (e υ e ν ) a = 0.9 >> = a = = f ω = окр( ,3) = 0,0999 ω = (0,0.999) normalize(ω) = (-1,0.999) 9a = f υ + a, f ω = окр(a, p) 10 (e ω, ± f ω ) ω 11 normalize(ω)

62 Алгоритм сложения чисел с плавающей точкой (по Д. Кнуту) 62 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача: найти число ω = υ ν, p-разрядная арифметика а : (2p + 1) разрядный аккумулятор 1input υ, νp = 3, υ = -0,000009, ν =0.1 2 υ (e υ, ± f υ ) и ν (e ν, ± f ν ) υ=(-5,-0.9), ν=(0,+0.1) 3if e ν > e υ then1 > -5 4 υ ν (e ν e υ и f υ f ν ) υ=(0,+0.1), ν= (-5,-0.9) 5e ω = e υ e ω = 0 6 if (e υ e ν ) p + 2 then [e υ e ν = 0 – (-5) = 5] = [p +2=5] 7 f ω = f υ По алгоритму: ω = υ Пусть это не так, тогда: a = 0.9 >> = a = = f ω = окр( ,3) = 0,1 ω = (0,0.1) normalize(ω) = (0,0.1) 8else f ν = f ν >>(e υ e ν ), a= f ν /b (e υ e ν ) 9a = f υ + a, f ω = окр(a, p) 10 (e ω, ± f ω ) ω 11 normalize(ω)

63 Алгоритм нормализации чисел с плавающей точкой (по Д. Кнуту) 63 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача: обеспечить для числа ω = (e ω, ± f ω ), f ω < b выполнение условия: 1/b | f ω | < 1 normalize(ω) 1 ω (e, ± f) // распаковать 2if f = 0 then e = e min // машинный ноль! 3else 4 while f 1/b do 1/b | f | 5 f = f · b, e = e 1 6 while | f | 1 1/b | f | < 1 7 f = f / b, e = e окр( f, p ) // округлить до p разр. 9 if e > e max then переполнение порядка 10 if e < e min then исчезновение порядка 11 (e, ± f) ω // упаковать