Ответы 190 страниц (1184228), страница 41

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 41)

1.0 = +20*1.0

Здесь порядок равен 0, мантисса - 1. В двоичном коде мантисса состоит из одних нулей, так как старший разряд мантиссы (всегда единичный) в коде отсутствует. Порядок хранится в двоичном коде в смещенном виде, он равен 127 в случае float и 1023 в случае double;

3.5 = +21*1.75

Порядок равен единице, мантисса состоит из трех единиц, из которых в двоичном коде хранятся две: 1100...0; смещенный порядок равен 128 для float и 1024 для double;

0.625 = +2-1*1.25

Порядок отрицательный и равен -1, дробная часть мантиссы равна 0100...0; смещенный порядок равен 126 для float и 1022 для double;

100.0 = +26*1.5625

Порядок равен шести, дробная часть мантиссы равна 100100...0; смещенный порядок равен 133 для float и 1029 для double.

При выполнении сложения двух положительных плавающих чисел происходят следующие действия:

выравнивание порядков. Определяется число с меньшим порядком. Затем последовательно его порядок увеличивается на единицу, а мантисса делится на 2, пока порядки двух чисел не сравняются. Аппаратно деление на 2 соответствует сдвигу двоичного кода мантиссы вправо, так что эта операция выполняется быстро. При сдвигах правые разряды теряются, из-за этого может произойти потеря точности (в случае, когда правые разряды ненулевые);

сложение мантисс;

нормализация: если мантисса результата стала равна или превысила двойку, то порядок увеличивается на единицу, а мантисса делится на 2. В результате этого мантисса попадает в интервал 1 m<2. При этом возможна потеря точности, а также переполнение, когда порядок превышает максимально возможную величину.

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

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

Источники погрешности при вычислениях на параллельных системах.

В общем случае, арифметические операции над элементами дискретного подмножества вещественных чисел F не корректны.

Результат арифметических операций чисел с плавающей запятой может:

- иметь абсолютное значение, больше M (максимального числа) - машинное переполнение;

- иметь ненулевое значение, меньшее m (минимального числа) по абсолютной величине - машинный нуль;

- иметь значение в диапазоне [m:M] и тем не не менее не принадлежать множеству F (произведение двух чисел из F, как правило, записывается посредством 2t либо 2t-1 значащих цифр);

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

А) Пусть x=9.900 y=1.000 z=-0.999 и тогда:

1 (x+y)+z = 9.910

2 x+(y+z) = 9.901

В) Пусть x=1100. y=-5.000 z=5.001 и тогда:

1 (x*y)+(x*z) = 1.000

2 x*(y+z) = 1.100

Здесь операции + и * - плавающие машинные операции. Такие 'чиcленные' процессы называют иногда 'неточными', здесь нарушаются ассоциативный и дистрибутивный законы арифметики..

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

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

Формула полной ошибки для суммирования положительных чисел Ai(i=1,..,n) имеет вид: Ds = A1*da1 + A2*da2 +...+ An*dan + d1*(A1+A2) +..+ d(n-1)*(A1+..+An) + dn , где

dai - относительные ошибки представления чисел в ЭВМ, а di - относительные ошибки округления чисел при каждой следующей операции сложения. Пусть: все dai = da и di = d , a Ks = A1+A2+..+An, тогда: Ds = da*Ks + d*[(n-1)*A1+(n-1)*A2 +...+ 2*A(n-1) + An]

Очевидно, что наибольший "вклад" в сумму ошибок вносят числа, сум­мируемые вначале. Следовательно, если суммируемые положительные числа упорядочить по возрастанию, максимально возможная ошибка суммы будет минимальной. Изменяя порядок суммирования чисел можно получать различные результаты. Но если даже слагаемые отличаются друг от друга незначительно, на точность результата может оказать влияние способ суммирования. Пусть суммируются 15 положительных чисел, тогда ошибка результата: Ds = da*Ks + d*(14*A1+14*A2+13*A3+....+2*A14+A15).

Слагаемое da*Ks не зависит от способа суммирования, и далее не учитывается. Пусть слагаемые имеют вид: Ai = А0+ei, где i=1,...,15, тогда: Dss = 199*(A0+em)*d, где em = max(ei), d - ошибка округления при выполнении арифметической операции сложения.

Если провести суммирование этих чисел по группам (три группы по четыре числа и одна группа из трех чисел), то ошибки частных сумм имеют вид:

Ds1 = d*(3*A1+3*A2+2*A3+A4) <= 9*d*(A0+em)

Ds2 = d*(3*A5+3*A6+2*A7+A8) <= 9*d*(A0+em)

Ds3 = d*(3*A9+3*A10+2*A11+A12) <= 9*d*(A0+em)

Ds4 = d*(3*A13+2*A14+A15) <= 5*d*(A0+em)

а полная оценка ошибок округления будет Ds <= 32*d*(A0+em), что меньше

Dss. Итак суммирование по группам дает меньшую ошибку результата.

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

Точность плавающей арифметики. Машинный эпсилон.

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

a+b = a при b 0

Более того, для сложения не выполняется закон ассоциативности: a+(b+c) = (a+b)+c

Действительно, пусть ε - максимальное плавающее число среди чисел, удовлетворяющих условию 1.0+ε = 1.0 (приведенные выше рассуждения показывают, что такие числа существуют). Тогда (1.0+ε)+ε 1.0+(ε+ε) поскольку левая часть неравенства равна единице, а правая строго больше единицы (это следует из максимальности числа ε).

Число ε часто называют машинным эпсилоном или, чуть менее корректно, машинным нулем, поскольку при прибавлении к единице оно ведет себя как ноль. Величина машинного эпсилона характеризует точность операций компьютера. Она примерно одинакова для всех современных компьютеров: большинство процессоров работают с восьмибайтовыми плавающими числами (тип double в Си), а арифметика плавающих чисел подчиняется строгим международным стандартам.

Оценим величину машинного эпсилона для типа double. Число 1.0 записывается в плавающей форме как 1.0 = +20*1.0.

Порядок плавающего числа 1.0 равен нулю. При сложении 1.0 с числом ε производится выравнивание порядка путем многократного сдвига мантиссы числа ε вправо и увеличения его порядка на 1. Поскольку все разряды числа ε должны в результате выйти за пределы разрядной сетки, должно быть выполнено 53 сдвига. Порядок числа ε после этого должен стать равным порядку числа 1.0, т.е. нулю. Следовательно, изначально порядок числа ε должен быть равным -53: ε = 2-53*m где m - число в диапазоне от единицы до двух. Таким образом, величина машинного эпсилона составляет примерно

2-53 10-16

Приблизительно точность вычислений составляет 16 десятичных цифр. (Это также можно оценить следующим образом: 53 двоичных разряда составляют примерно 15.95 десятичных, поскольку 53/log210 53/3.321928 15.95.)

В случае четырехбайтовых плавающих чисел (тип float языка Си) точность вычислений составляет примерно 7 десятичных цифр. Это очень мало, поэтому тип float чрезвычайно редко применяется на практике. К тому же процессор сконструирован для работы с восьмибайтовыми вещественными числами, а при работе с четырехбайтовыми он все равно сначала приводит их к восьмибайтовому типу. В программировании следует избегать типа float и всегда пользоваться типом double.

Некоторые процессоры применяют внутреннее представление плавающих чисел с большим количеством разрядов мантиссы. Например, процессор Intel использует 80-битовое (десятибайтовое) представление. Поэтому точность вычислений, которые не записывают промежуточные результаты в память, может быть несколько выше указанных оценок.

Кроме потери точности, при операциях с вещественными числами могут происходить и другие неприятности:

переполнение - когда порядок результата больше максимально возможного значения. Эта ошибка часто возникает при умножении больших чисел;

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

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

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

бесконечно малое, или денормализованное, число - это ненулевое плавающее число с очень большим отрицательным порядком (т.е. очень маленькое по абсолютной величине);

Not a Number, или NaN - двоичный код, который не является корректным представлением какого-либо вещественного числа.

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

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

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

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

1. Балансировка дерева вычислений

Балансировка дерева вычислений (tree-height reduction or balancing) выражений позволяют использовать конвейерное АУ без пропуска рабочих тактов. Так, вычисление суммы вещественных чисел: A+B+C+D+E+F+G+H, будет запрограммировано как последовательность операций: (((A+B)+(C+D))+((E+F)+(G+H))); это нарушает заданную по умолчанию последовательность вычислений с накоплением одной частной суммы и может повлиять на результат.

2. Исключение общих подвыражений

Алгоритмы исключения общих подвыражений (Common subexpession elimination) также могут изменить порядок вычислений.

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

X = A + B + C + D ----> REG = B + C

Y = B + E + C X = A + D + REG

Y = E + REG

3. Разворачивание циклов

Разворачивание циклов (loop unrolling) - расписывание цикла последовательностью операторов присваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором) размножения.

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

DO I=1,100 DO I=1,100,4

A(I) = B(I) + C(I) A(I) = B(I) + C(I)

ENDDO A(I+1) = B(I+1) + C(I+1)

A(I+2) = B(I+2) + C(I+2)

A(I+3) = B(I+3) + C(I+3)

ENDDO

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

DO I=1,10 DO I=1,10,2

S = S + A(I) S = S + A(I)

ENDDO S1 = S1 + A(A+1)

ENDDO

S = S + S1

Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм.

192

Характеристики

Список файлов ответов (шпаргалок)