СКИПОДы 2007 полная версия (1127795), страница 56
Текст из файла (страница 56)
Определяется число с меньшим порядком. Затем последовательноего порядок увеличивается на единицу, а мантисса делится на 2, пока порядки двух чисел несравняются. Аппаратно деление на 2 соответствует сдвигу двоичного кода мантиссывправо, так что эта операция выполняется быстро. При сдвигах правые разряды теряются,из-за этого может произойти потеря точности (в случае, когда правые разряды ненулевые);сложение мантисс;нормализация: если мантисса результата стала равна или превысила двойку, то порядокувеличивается на единицу, а мантисса делится на 2.
В результате этого мантисса попадает в188интервал 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.9102 x+(y+z) = 9.901В) Пусть x=1100. y=-5.000 z=5.001 и тогда:1 (x*y)+(x*z) = 1.0002 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 , aKs = 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 - ошибка округления при выполнении арифметической операции сложения.189Если провести суммирование этих чисел по группам (три группы по четыре числа и однагруппа из трех чисел), то ошибки частных сумм имеют вид: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 чрезвычайно190редко применяется на практике. К тому же процессор сконструирован для работы свосьмибайтовыми вещественными числами, а при работе с четырехбайтовыми он все равносначала приводит их к восьмибайтовому типу. В программировании следует избегать типаfloat и всегда пользоваться типом double.Некоторые процессоры применяют внутреннее представление плавающих чисел с большимколичеством разрядов мантиссы.
Например, процессор Intel использует 80-битовое(десятибайтовое) представление. Поэтому точность вычислений, которые не записываютпромежуточные результаты в память, может быть несколько выше указанных оценок.Кроме потери точности, при операциях с вещественными числами могут происходить идругие неприятности:переполнение - когда порядок результата больше максимально возможного значения. Этаошибка часто возникает при умножении больших чисел;исчезновение порядка - когда порядок результата отрицательный и слишком большой поабсолютной величине, т.е.
порядок меньше минимально допустимого значения. Эта ошибкаможет возникнуть при делении маленького числа на очень большое или при умножениидвух очень маленьких по абсолютной величине чисел.Кроме того, некорректной операцией является деление на ноль. В отличие от операций сцелыми числами, переполнение и исчезновение порядка считаются ошибочнымиситуациями и приводят к аппаратному прерыванию работы процессора. Программистможет задать реакцию на прерывание - либо аварийное завершение программы, либо,например, при переполнении присваивать результату специальное значение плюс илиминус бесконечность, а при исчезновении порядка - ноль. Заметим, что среди двоичныхкодов, представляющих плавающие числа, имеется несколько специальных значений.Перечислим некоторые из них:бесконечно большое число - это плавающее число с очень большим положительнымпорядком и, таким образом, очень большое по абсолютной величине.
Оно может иметь знакплюс или минус;бесконечно малое, или денормализованное, число - это ненулевое плавающее число с оченьбольшим отрицательным порядком (т.е. очень маленькое по абсолютной величине);Not a Number, или NaN - двоичный код, который не является корректным представлениемкакого-либо вещественного числа.Любые операции с константой NaN приводят к прерыванию, поэтому она удобна приотладке программы - ею перед началом работы программы инициализируются значениявсех вещественных переменных. Если в результате ошибки программиста при вычислениивыражения используется переменная, которой не было присвоено никакого значения, топроисходит прерывание из-за операции со значением NaN и ошибка быстро отслеживается.К сожалению, в случае целых чисел такой константы нет: любой двоичный кодпредставляет некоторое целое число.Перечислить алгоритмы оптимизации объектных программ, которыемогут повлиять на точность вычислений.Оптимизационные преобразования программ для их оптимального выполнения наконвейерных вычислителях могут проводиться системами программирования.