Лекция 3 Представление числовой информации в ЭВМ
Память компьютера, отводимую для хранения числа или другого элемента данных в числовом коде, удобно описать моделью разрядной сетки массива (линейной таблицы) b-ичных разрядов, имеющего постоянные размер k и формат, определяющий смысл отдельных разрядов. Размер разрядной сетки обычно равен или кратен размеру машинного слова и размеру минимальной порции данных, обрабатываемой одной командой процессора. Эти константы определяются архитектурой процессора и количеством разрядов, которые могут передаваться одновременно от процессора к памяти или обратно по шине данных. В большинстве компьютеров эти единицы кратны 1 байту. Формат разрядной сетки и правила выполнения арифметических операций определяются архитектурой процессора. Современные процессоры умеют работать с разрядными сетками, различающимися по размеру и формату. В языках программирования манипулирование числами разного формата реализуется через различные числовые типы данных.
Модели чисел Беззнаковые Целые Знаковые Числа Вещественные С фиксированной точкой С плавающей точкой
Представление целых без знака Модель беззнаковых целых описывает представление неотрицательного целочисленного диапазона [0.. N max ] в сетке разрядности k. В записи числа допускаются только k разрядов целой части; цифры, возникающие в результате операций в прочих разрядах, отсекаются. Более короткие числа дописываются нулями слева k = k = k = (усечение) 1
Формулы для максимальных и минимальных беззнаковых чисел в разрядной сетке Максимальное число в k-разрядной сетке в b-ичной системе счисления: N max (k, b) = b k – 1 «Следующим» числом за максимальным будет минимальное число 0.
Арифметика по модулю Выборка k младших цифр b-ичного числа N равносильна взятию остатка Q от деления N на b k. Говорят, что N сравнимо с Q по модулю b k, что записывается как N = Q(mod b k ) Множество чисел, сравнимых с Q по модулю b k, это все числа вида Q + n * b k, где n произвольное целое. Все они имеют в k-разрядной сетке одинаковое представление. Поэтому взятие остатка по модулю равносильно приведению исходного числа в интервал [0.. b k –1] прибавлением или вычитанием величины модуля некоторое число раз. Пример: Числа 3, 259 = , 515 = , 1027 = в 8-разрядной сетке в 2-с.с. имеют одинаковое представление:
Представление целых со знаком Модель знаковых целых описывает представление целочисленного диапазона [N min.. N max ] в сетке разрядности k. Старший разряд кодирует знак числа. В остальных k – 1 разрядах хранятся младшие значащие цифры числа, остальные отсекаются, как и при беззнаковом кодировании. При таком кодировании N min = –N max. Хранение числа в виде знака и модуля на практике оказывается неудобным: ноль имеет двойное представление (со знаком и без), из-за чего представимый диапазон сужается на единицу, по-разному реализуются операции сложения и вычитания. Поэтому на практике применяют другой способ кодирования дополнительный код.
Дополнительный код Дополнительный код позволяет кодировать различными наборами цифр целочисленный интервал [–b k–1.. + b k–1 – 1]. При этом числа из положительной половины этого интервала имеют те же коды, как при беззнаковом кодировании, а отрицательная половина отображается на вторую половину беззнакового интервала [b k–1... b k – 1] по правилу (–N) (b k – N)
Пример [ – b k–1.. + b k–1 – 1] k = 4, b = 2; N max = 2 3 –1 = 7; N min = –2 3 = –8; –1 (10) = 1111 (2) ;
Алгоритм A11 вычисляет представление ( – N) в дополнительном коде в b-ичной разрядной сетке размера k взять младшие k знаков в записи числа N; при необходимости дополнить нулями слева; заменить в полученной записи каждую цифру ее дополнением до b–1, максимальной цифры с. с. (для двоичной системы это равносильно инверсии разрядов: замене нулей единицами и наоборот); к полученному числу прибавить единицу. Действия алгоритма Д равносильны вычислению: ((b к – 1) – N) + 1 = b k – N
Свойства дополнительного кода алгоритм Д дает правильное представление обратных по знаку чисел как положительных, так и отрицательных; в частности, его повторное применение к своему результату восстанавливает исходное число N; для двоичной с. с: если приписать к числу его знак старшей цифрой и выполнить алгоритм Д над расширенной записью, то правильный знак обратного числа получается автоматически; ноль имеет единственное представление: алгоритм Д для ноля выдает снова ноль; то же свойство имеет минимальное отрицательное число b k–1, не имеющее положительного «антипода»: его дополнение равно ему самому.
Пример Представить в дополнительном коде в 4-разрядной сетке число –321 (7) в 7-с.с. выравнивание: 0321 дополнение до старшей цифры: 6345 прибавление единицы: 6346
Выполнение арифметических операций в разрядной сетке Формирование знакового разряда результата арифметических операций в поразрядных алгоритмах можно осуществить регулярным образом: как если бы он был просто дополнительным старшим разрядом числа. Избавляемся от реализации вычитания отдельным алгоритмом: действительно, так как а – b = а+ (– b), достаточно перевести вычитаемое в дополнительный код и выполнить сложение. Поразрядное сложение чисел со знаком и без знака можно осуществить единым алгоритмом: манипуляции с цифрами одинаковы, различается лишь способ интерпретации конечного результата как знакового или беззнакового числа. (Для умножения и деления это не проходит без дополнительных приведений.)
Пример : в ычислить разность 25 – 3 для 8-разрядной двоичной сетки перевод +25 в 2-с.с. со знаком: выравнивание: знаковое расширение до 8 разрядов: перевод +3 в 2-с.с. со знаком: 011 выравнивание: знаковое расширение +3 до 8 разрядов: перевод +3 в дополнительный код (так как это вычитаемое): разрядное сложение с переносом (без знака): ) приведение: отсечение старших разрядов вне сетки: результат положительное знаковое число 22. +
Перенос и переполнение При выполнении арифметических операций результат может оказаться вне границ допустимого интервала. Приведение по модулю (путем усечения значащих цифр в старших разрядах) вызывает отклонение полученного результата от истинного. Эта ситуация называется переполнением разрядной сетки. Беззнаковое переполнение (арифметический перенос), т.е. выход за границы интервала [0.. b k – 1], при сложении равносильно переносу 1 из старшего k–1-го разряда в несуществующий k-й. При вычитании (большего числа из меньшего) переполнение равносильно заёму 1 из несуществующего k-го разряда в старший k–1-й (разность отрицательна, приведенная разность оказывается больше уменьшаемого, что тоже ненормально). Процессор контролирует эти ситуации установкой флажка переноса (carry flag) в регистре состояния, который можно проверить, чтобы выполнить обработку переноса.
Знаковое переполнение, т. е. выход из интервала [–b k.. b k–1 – 1], возникает при сложении положительных чисел в случае переноса 1 в знаковый k-1-й разряд результата (приведенная сумма становится отрицательна) или при сложении отрицательных с заёмом из знакового разряда (приведенная сумма становится положительна); аналогично при вычитании. Процессор контролирует знаковое переполнение установкой флажка переполнения (overflow flag) в регистре состояния. Так как операции типа сложения для знаковых и беззнаковых чисел реализуются одной командой, флажки переноса и переполнения формируются одновременно, но для знаковой арифметики несущественно состояние переноса, а для беззнаковой переполнения.
Примеры 1: : )1: перенос = 1, переполнение = 0 Числа со знаком: (-4)+(-5)=(-9) – перенос не имеет смысла Числа без знака: = 493 = (256 + )237 – перенос указывает, что произошло беззнаковое переполнение + 0: : : перенос = 0, переполнение = 1 Числа со знаком: =(256) – знаковое переполнение Числа без знака: = 129 – переполнение не имеет смысла, ошибки нет +
Конечное представление действительных чисел: арифметика погрешностей Любой действительный интервал содержит бесконечное множество чисел. Для представления в конечной памяти применяется дискретизация интервала: разбиение его на достаточно малые подынтервалы, в каждом из которых все числа сводятся к одному и тому же числу-представителю, становясь, таким образом, неразличимыми. Ширина сводимого интервала определяет максимальную погрешность представления отклонение значения истинного числа от значения его представления. rR
Первый способ разбиения Усечение дробной части числа R после некоторого разряда k. Получаемый представитель r имеет не более k значащих цифр в дробной части и представляет все числа из интервала [r...r + ε], где ε = b -k максимальная абсолютная погрешность, равная расстоянию между представителями, равномерная вдоль всей числовой оси. r r+
Второй способ разбиения Усечение после разряда - k с округлением по - k-1-му приводит к представлению числом r симметричного интервала [r - ε...r + ε], где ε = b -k /2, и дает вдвое меньшую оценку максимальной абсолютной погрешности при том же расстоянии между представителями. r r+ r-
Третий способ разбиения Усечение после k старших значащих разрядов числа с округлением приводит к неравномерным по ширине сводимым интервалам, сгущающимся вокруг нуля: число r представляет интервал [r - ε r... r + ε r ]. где ε r = b -k+p /2, p - порядок нормализованного вещественного числа r. Погрешность представления здесь относительная, так как зависит от абсолютной величины числа. r r+ r r r- r r 0
Погрешности, возникающие при представлении действительных чисел, растут при любых арифметических операциях над ними, как видно из следующих формул: Пусть,тогда Растущая недостоверность вычислений с действительными числами приводит к необходимости предварительного анализа расчетных формул с оценкой максимальной погрешности, а также специальной организации вычислений, минимизирующей ее. Например, вычисление выражения (а + Ь)* (с + d) дает меньшую погрешность при раскрытии скобок, а выражения (а/Ь)*(c/d) при перегруппировке в одну дробь. Арифметика погрешностей
Формат с фиксированной точкой Модель действительных чисел с фиксированной точкой аналогична представлению целых чисел со знаком: под хранение целой и дробной части отводится известное число битов, т. е. привязка номеров разрядов числа к разрядам сетки фиксирована и позиция разделяющей двоичной точки известна. Разряды отсутствующих цифр заполняются незначащими нулями слева в целой части и справа в дробной. Отрицательные числа могут храниться в дополнительном коде. Погрешность представления в данной модели равномерна: ε = b -kд /2. Арифметические операции над числами с фиксированной точкой можно выполнять поразрядно, рассматривая их без точки, как знаковые целые. После умножения точка ставится перед 2k Д -й цифрой результата справа, младшие k Д разрядов отбрасываются, причем по старшему из них выполняется округление младшей цифры результата (усечение) k ц = k д = 8
Для деления ненулевое делимое сдвигается влево на р1 позиций до появления первой единицы в старшем разряде сетки, а делитель влево на р2 позиций, до получения максимального числа, которое меньше делимого. Число р = p2 - p1 + 1 определяет количество значащих цифр перед точкой в результате (или количество ведущих нулей в дробной части, если р < 0). Если р > k ц, деление заведомо даст слишком большое частное (переполнение); если р < -k Д - 1, результатом будет машинный ноль. Деление можно выполнять «столбиком» (вычитанием делителя со сдвигом остатка влево) до получения р + k д +1 цифр результата (последняя цифра используется для округления). Заметим, что при выполнении округления также возможно переполнение. Деление действительных чисел в формате с фиксированной точкой
Диапазон представления чисел в формате с фиксированной точкой k – количество разрядов под целую часть; µ – количество разрядов под дробную часть; N число, которое можно представить в такой разрядной сетке: 2 -µ |N| 2 k -2 -µ
Формат с плавающей точкой Модель действительных чисел с плавающей точкой служит для представления чисел с максимальной относительной точностью, измеряемой количеством хранимых значащих цифр действительного числа. Для этого используется запись числа в нормализованной форме R = ±m*b p, где 1 = b 0 < т < b 1, (форма 1) либо R = ±m*b p, где 0 < т < b 0, (форма 2) где p – целое число. m число, полученное перенесением точки в позицию после первой значащей цифры числа R, называется мантиссой. p количество разрядов, на которое была перенесена точка, называется порядком. Примеры: (10) = * 102 ( мантисса, 2 порядок) (2) = 1.011*2–4 (1.011 мантисса, –4 порядок)
Представление чисел в формате с плавающей точкой в разрядной сетке Таким образом, число R может быть представлено парой целых чисел ( m ', р ). Для хранения цифр мантиссы и порядка отводится фиксированное число разрядов сетки ( km и kр ), в которых они хранятся, как обычные целые, при этом порядок обычно хранится как знаковое целое в дополнительном коде, а мантисса как беззнаковое целое. Знак вещественного числа хранится в отдельном разряде.
Представимый этой моделью интервал чисел имеет верхнюю границу R max = +т тах * b pmax и нижнюю R min = -R max Минимально представимое число, отличное от 0: ε 1 = m min * b pmin. и относительная погрешность представления чисел в модели: ε 2 = b -km /2. Для приведенной двоичной модели (форма 1): Для формы 2: m max = ( b 0 - m min ) = (b 0 - b -km ); Диапазон представления чисел с плавающей точкой