Граф-схемы алгоритма с операндой

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

Первый операнд представлен в формате одинарной точности, второй в формате двойной точности числа с плавающей точкой.

Сначала разрабатывается алгоритм выполнения данной операции. Алгоритм построен на основе стандарта чисел с плавающей точкой IEEE 754.

Представлено словесное описание алгоритма и его граф-схема (ГСА).

операнда алгоритм точка число

1. ПОСТАНОВКА ЗАДАЧИ

Операнды с плавающей точкой и результат выполнения операции должны быть представлены в форматах стандарта IEEE 754 и удовлетворять требованиям стандарта.

Тип выполняемой операции определяем в табл. 1 по порядковому номеру студента в списке группы.

Я имею порядковый номер 1 в списке группы поэтому мое задание курсовой работы заключается в сложении чисел с плавающей точкой.

Сочетания форматов операндов определяем по табл. 2. Для группы АЕ-125 имеем следующие данные: первый операнд в формате bias32, второй операнд в формате bias64.

Рассмотрим выполнение операции над операндами в одинаковых или разных форматах одинарной или двойной точности стандарта IEEE 754.

Правила вычитания совпадают с правилами сложения, если при вычитании код 0 в знаковом разряде вычитаемого интерпретировать как знак (-), а код 1, - как знак (+). Поэтому ограничимся рассмотрением правил выполнения операции сложения.

Формат результата должен быть равным более длинному формату операнда.

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

Примем, что оба операнда представлены в одинаковом формате и старшие разряды мантисс заданы явно.

Если хотя бы один операнд является сигнализирующим NaN, то признак исключительной ситуации невыполнимая операция устанавливают в 1 и формируют сигнал прерывание. Последующие действия описаны в раздеде 5.5.

Если один или оба операнда простые NaN, то в результат копируется одно из NaN.

Если один из операндов равен нулю, то результат равен другому операнду.

Если оба операнда равны нулю, то результат равен нулю. Если оба операнда (+0) или оба (-0), то знак нулевого результата, должен совпадать со знаком операндов. Если знаки операндов не совпадают, то знак результата может быть любым.

Если один или оба операнда бесконечность, то результат определяют по табл.5.5. Однако, если один из операндов ?? а другой ?? то возникает исключительная ситуация невыполнимая операция. Ее признак устанавливают в 1 и формируют сигнал прерывания. При отсутствии обработки по прерыванию результат должен получить зарезервированное на этот случай значение простого NaN.

Если оба операнда являются числами не равными нулю или бесконечности, то выполняется сложение с последующей нормализацией результата и округлением. Стандарт IEEE 754 настоятельно рекомендует вычислять промежуточный результат выполнения операции до его округления точно.

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

Чтобы вычислить знак и мантиссу промежуточного результата необходимо

- при равных знаках операндов мантиссы сложить и принять знак результата равным знаку операндов;

- при разных знаках операндов из большей мантиссы вычесть меньшую и принять знак результата равным знаку операнда с большей мантиссой. При равных мантиссах результат равен нулю со знаком (+) во всех режимах округления кроме округления до . При округлении до знак нулевого результата должен быть (-). Это правило не распространяется на случай сложения операндов равных нулю. Нулевой результат будет вычислен точно.

Порядок промежуточной суммы, если ее мантисса не равна нулю, следует принять равным большему из порядков операндов.

Мантиссу промежуточной суммы следует нормализовать и изменить соответственно порядок. Округлению до точности формата подлежит нормализованная мантисса. Если отбрасываемые разряды не равны нулю, складывается исключительная ситуация потери точности.

При разработке процесса вычисления суммы необходимо учитывать ряд обстоятельств рассматриваемых ниже.

1. Порядки операндов равны, если их смещенные порядки равны или один смещенный порядок 0, а другой равен 1.

2. Нельзя нормализовать мантиссу суммы равную нулю. Поэтому следует, либо проверять мантиссу суммы до ее нормализации на 0 и записывать в результат код нуля; либо предварить вычисление нулевой мантиссы суммы. Значение суммы равное 0 может быть только при разных знаках операндов и равных смещенных порядках и мантиссах. Проверив это условие, можно в результат записать код 0, не выполняя иных вычислений. Последний вариант предпочтительнее.

Ниже будем рассматривать обстоятельства, которые следует учитывать при результате сложения не равном нулю.

3. Если оба операнда ненормализованные числа, то сумма мантисс будет вычислена точно и в формате результата, так как выравнивание порядков не выполняется и дополнительные поля мантисс содержат нули. Переполнение суммы мантисс сложиться не может, так как мантиссы операндов меньше 1. Поэтому можно не выполнять нормализацию и округление результата. Если сумма мантисс нормализованная, следует принять смещенный порядок суммы равным 1.

Исключительная ситуация потери значимости сложиться не может, так как нет потери точности.

4. Если один или оба операнда нормализованные числа с одинаковыми знаками, то денормализация суммы вправо случиться не может. Возможно переполнение точной суммы мантисс на 1 разряд влево, но только при , где - модуль разности мантисс. Возможна исключительная ситуация переполнения формата результата. Исключительная ситуация потери значимости сложиться не может.

Существуют две причины возникновения исключительной ситуации переполнения формата.

I Переполнение точной суммы мантисс.

II Переполнение суммы мантисс после округления до точности формата.

Обе причины могут вызвать исключительную ситуацию переполнения, только если порядок суммы мантисс при нормализации равен (код смещенного порядка 11…10). Нормализация мантиссы вправо на 1 разряд влечет увеличение порядка до , что приводит к переполнению формата.

Переполнение нормализованной мантиссы суммы при округлении до точности формата возможно во всех режимах округления, кроме округления до нуля. В иных режимах округления переполнение может случиться, если в сохраняемых разрядах дробной части мантиссы суммы содержится код 11…1. Дополнительные условия переполнения в режиме округления:

- до ближайшего числа, - старший отбрасывемый бит содержит 1;

- до , - знак промежуточного результата (+) и отбрасываемые биты не равны нулю;

- до , - знак промежуточного результата (-) и отбрасываемые биты не равны нулю.

Если случилось переполнение точной суммы мантисс до округления, то при ее округлении после нормализации переполнение суммы мантисс и соответственно результата сложиться не может. Следовательно, после вычисления точной суммы сдвиг суммы мантисс вправо может выполняться не более чем на 1 разряд.

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

Можно проявить исключительную ситуацию переполнения, анализируя код точной суммы мантисс до ее нормализации и округления.

Исключительная ситуация переполнения сложится, если

- порядок точной суммы и мантисса переполнена;

- порядок точной суммы , мантисса нормализованная и сложились условия для ее переполнения при округлении.

Действия системы при переполнении определены в разделе 5.5.

5. Если один или оба операнда нормализованные числа с разными знаками, то переполнения суммы мантисс и суммы случиться не может. Возможна денормализация суммы вправо, что потребует ее нормализацию влево.

При сумма будет вычислена точно в пределах формата результата, что позволяет не выполнять ее округление. Действительно, при выравнивание порядков не выполнялось и поэтому дополнительные разряды суммы мантисс будут равны нулю.

При сумма мантисс чисел с разными знаками не равная нулю обязательно денормализована вправо не более чем на разряд, так как оба операнда в рассматриваемом случае нормализованные и их мантиссы не равные.

При в дополнительное поле выдвинут только один разряд мантиссы операнда и соответственно суммы мантисс. Сумма мантисс чисел с разными знаками может быть нормализованной или денормализованной вправо не более чем на разрядов.

Если сумма мантисс нормализованная, то при промежуточный результат следует округлить. При округлении переполнение мантиссы случиться не может, так как выполнялось вычитание мантисс и поэтому значение сохраняемых разрядов мантиссы суммы меньше максимального. Ситуация потери значимости сложиться не может, так как после округления в любом режиме мантисса и число будут нормализованными.

Нормализации суммы влево при может препятствовать малая величина смещенного порядка e промежуточной суммы. Например, пусть смещенный порядок (порядок ) и сумма мантисс денормализована вправо на 5 разрядов (содержит 0 в разряде целого и в четырех старших разрядах дробной части). Для нормализации мантиссы ее следует сдвинуть на 5 разрядов влево, что потребует уменьшения порядка на 5. Сделать это нельзя, так как порядок нормализованного числа не может быть меньше . Поэтому сумму мантисс следует сдвинуть только на разряда влево. Результат будет числом ненормализованным и, следовательно, его смещенный порядок следует принять равным 0. Из сказанного вытекает правило нормализации влево.

Если количество нулей в старших разрядах мантиссы суммы, включая разряд целого, , то мантиссу следует сдвинуть только на разрядов влево и смещенный порядок результата принять равным 0. Результат останется числом ненормализованным. При мантиссу следует сдвинуть на разрядов влево, и смещенный порядок результата принять равным .

Из этого правила следует, что при нормализация влево суммы мантисс будет выполняться обязательно и не менее чем на один разряд. Так как при за пределы основного поля мантиссы выдвинут только один разряд, то после нормализации результат будет вычислен точным в пределах формата результата, и его можно не округлять. Следовательно, если результат останется числом ненормализованным, то ситуация потери значимости сложиться не может, так как нет потери точности.

При сумма мантисс может быть денормализована не более чем на 1 разряд, так как после выравнивания порядков одна мантисса не меньше 1, а другая меньше . Ненормализованную сумму мантисс следует нормализовать влево, уменьшая смещенный порядок на 1. Так как порядок суммы до нормализации превышает минимальный не менее чем на 2, а уменьшить его при нормализации придется только на 1, то промежуточный результат всегда число нормализованное, и часть его значащих разрядов находится за пределами основного поля мантиссы. Поэтому при промежуточный результат следует обязательно округлить. При округлении переполнение мантиссы случиться не может, так как выполнялось вычитание мантисс и поэтому значение сохраняемых разрядов мантиссы суммы меньше максимального. Исключительная ситуация потери значимости сложиться не может, так как результат всегда нормализованный.

6. При выполнении операции сложения/вычитания исключительная ситуация потери значимости сложиться не может. Этот вывод следует из анализа результатов выполненного в п.п.3 - 5.

7. Нулевой результат выполнения операции сложения/вычитания всегда точный.

Действительно. Точный промежуточный результат сложения/вычитания не равных по модулю чисел может быть нормализованным или ненормализованным. Результат округления нормализованного промежуточного результата не может стать равным нулю, что очевидно. Ненормализованный промежуточный результат всегда вычислен в формате результата, что следует из анализа выполненного в п.п.3 - 5 и поэтому не подлежит округлению и не может стать равным нулю.

Нулевой результат выполнения операции сложения/вычитания может быть получен только при сложении/вычитании равных по модулю чисел и, следовательно, он точный.

8. Разность порядков операндов может в предельном случае быть равной . Чтобы вычисить точный промежуточный результат, как это настоятельно рекомендует стандарт IEEE 754, необходимо при выравнивании порядков сдвигать мантиссу операнда в предельном случае на разрядов вправо, сохраняя все ее разряды в дополнительном поле длинной не менее бит.

Если, например операнды представлены в формате двойной точности, то разность порядков операндов может составить 2045. Это потребует выполнить сдвиг мантиссы на 2045 разрядов и сохранить значение сдвинутой мантиссы длиной 2045+52 разряда в поле соответствующей длины. Кроме того, при разных знаках операндов необходимо выполнить вычитание сдвинутой мантиссы. Для этого придется к большей мантиссе приписать справа 2045 нулей. Затраты оборудования для хранения, сдвига, вычитания и других сопутствующих операций при такой длине мантисс неприемлемо велики.

2. СЛОВЕСНОЕ ОПИСАНИЕ

В начале пользователь заносит начальные данные, а именно число А(число с плавающей точкой одинарного формата - 32 бита), число В(число с плавающей точкой двойного формата - 64 бита) и коэффициент округления.

Первым делом производим проверку порядка числа А, равен ли он 255(блок 1), если да то значит, что в число А содержит сигнализирующий NaN, тихий NaN или бесконечность. Затем проверяем мантиссу на равенство 0(блок 2). Если в мантиссе числа А не ноль, то значт в нем либо сигнализ. NaN, либо тихий NaN. Для определения сигнализирующего NaN проверяем старший бит мантиссы на 0(блок 9).Если сигн.NaN записываем его в результат, выполняем установку флагов в 10000(вызываем прерывание) и алгоритм завершается. Если в числе А тихий NaN, то нужно проверить число В на сигнализирующий NaN, для этого в блоке 10 проверяем порядок числа В, если он не равен максимальному, то значит в числе В обычное число, поэтому в результат записываем NaN, если же порядок В равен максимальному, то в В записано либо NaN, либо бесконечность, в блоке 13 выполняем проверку мантиссы числа В, если она равная 0 то в числе В записана бесконечность, поэтому в результат записываем NaN числа А. Если же нет, то проверяем старший бит мантиссы на ноль с целью проверки числа В на сигнализирующий NaN(блок 14). Если в В сигнализирующий NaN записываем его в результат и вызываем прерывание(блок 15). Если в числе А оказалась записана бесконечность, то по аналогии выполняем проверку числа В на сигнализирующий и тихий NaN. Если в В записано число, то в результат записываем А(блок 7) и устанавливаем флаги 00000, если в числе В записана бесконечность то в блоке 5 сравниваем знаки двух чисел, если они одинаковы то в результат записываем В, если же знаки разные происходит невыполнимая операция(сложение бесконечностей с разными знаками) устанавливаем флаги в 10000 и вызываем прерывание.

Если в результате проверки в блоке 1 оказалось, что А это число, тогда выполняем по аналогии проверку порядка числа В, если он максимальный, то значит что в В записано тихий или сигнализирующий NaN или бесконечность. Первым делом проверяем мантису на 0(блок 25), если мантисса 0 то в результат записываем бесконечность(В). Если мантисса отличная от 0 то проверяем на сигнализирующий NaN, путем проверки старшего бита мантиссы на 0. Если NaN сигнализирующий записываем его в результат и вызываем прерывание, если нет, то просто записываем его в результат.

Если оказалось, что А число и В число, то в блоке 26 проверяем равно ли число А нулю, если да то в результат записываем В. Если нет то в блоке 27 проверяем число В на равенство нулю, если да, то в результат записываем А, если же нет то выполняем растяжение числа А(32 бита) к 64-х битному числу с плавающей точкой. Для этого в блоке 30 проверяем равен ли порядок числа А нулю, если да то число А ненормализированное, для его расширения в порядок числа С(64 битное число в котором будет сохранено растянутое число В) записываем разность порядков двух форматов а именно 896(блок 31), затем до тех пока в старшем бите мантиссы не появится 1, выполняем сдвиг в лево, с уменьшением порядка на 1(блоки 33 и 34). Как только в старшем бите числа А появилась единица выполняем последний сдвиг в лево и переписываем мантиссу из А в С, оставшиеся разряды мантиссы заполняем нулями. Если же число А нормализированное, то в порядок числа С записываем сумму порядка А и разности порядков двух форматов(896) и переписываем мантиссу числа А в С, недостающие разряды заполняем нулями.

Затем выполняем проверку нормализировано В или нет(если не то результат сложения получится денормализированным) блок 81, если нет переходим к пункту , если да, то проверяем равен ли порядок А минимальному, если да то проверяем и мантиссу А на 0 блок(83) далее в зависимости от знака выполняем необходимое действие. Если мантисса А больше 53 устанавливаем флаги 00010, как признак потери точности.

Далее прежде чем приступить в выполнению действия(сложение), необходимо найти разность порядков числа С и В, в блоке 41 результат разности записывается в D, в блоке 42 проверяем равно ли D нулю, если да, то значит порядки чисел одинаковые и можно выполнять действие, если же нет то сначала нужно выровнять порядки, для этого в блоке 61 проверяем D больше нуля или нет. Если да, то значит что порядок числа С больше порядка числа В, затем проверяем разность порядков больше 52(количество разрядов мантиссы) если да, то при сдвиге мантисса числа В выйдет за границы, поэтому в результат записываем С и устанавливаем флаги в 00010, как признак потери точности. Если разность меньше 52, то тогда выполняем сдвиг мантиссы числа В вправо на D разрядов, при этом увеличивая порядок числа В на 1(блоки 63, 64, 65) и сохраняем выдвинутые разряды в 3 дополнительных разряда. И возвращаемся в пункт 7. Если разность порядков меньше 0 то значит, число В имеет больший порядок, поэтому выполняем аналогичные действия проверки и сдвига для числа С(блоки 71, 72, 73) и также возвращаемся в пункт 7.

Если порядки чисел С и В равные проверяем равенство знаков(блок 43). Если знаки не равные то тогда необходимо выполнить операцию вычитания, т.е. от большей мантиссы отнять меньшую, в блоке 44 определяем мантисса какого числа является большей. Если С то в от С отнимаем В и записываем в результат знак С(блоки 49, 50, 51), если же В больше, то от В отнимаем С и в результат записываем знак числа В(блоки 52, 53, 54).

Затем проверяем старший бит мантиссы результата, если там 0, то тогда нужно нормализировать результат(блоки 56, 57). Если результат нормализирован, переходим к округлению результата.

Если знаки операндов равны то необходимо выполнить сложение. Для этого с целью не потерять старший бит, записываем результат сложения мантисс в В, Если в нулевом разряде В единица, увеличиваем порядок на 1 и переходим к округлению результата.

ЗАКЛЮЧЕНИЕ

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

Результатом проделанной работы может служить Граф схема алгоритма. Описание которой в соответствии с каждым блоком находится в данной пояснительной записке. Данная работа позволила закрепить и применить на практике имеющиеся знания стандарта IEEE-754.

ПЕРЕЧЕНЬ ЛИТЕРАТУРЫ

1. Введение в стандарт IEEE 754-1985 “Двоичная арифметика с плавающей точкой”

2. Бибило Петр Николаевич «Основы языка VHDL». Изд. 3е. доп. - М.: Издательство ЛКИ, 2007 - 328с.

Размещено на Allbest.ru