ПОД (пособие) (1184372), страница 57
Текст из файла (страница 57)
Величинамашинного эпсилона характеризует точность операций компьютера. Она примерноодинакова для всех современных компьютеров: большинство процессоров работают свосьмибайтовыми плавающими числами (тип 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 и ошибка быстро отслеживается.К сожалению, в случае целых чисел такой константы нет: любой двоичный кодпредставляет некоторое целое число.Перечислить алгоритмы оптимизации объектных программ, которыемогут повлиять на точность вычислений.Оптимизационные преобразования программ для их оптимального выполнения наконвейерных вычислителях могут проводиться системами программирования.
Этипреобразования, алгебраически эквивалентные, могут нарушить порядок вычислений,предписанный исходным текстом программы.Последствия таких преобразований обсуждались выше.Наиболее характерныепреобразования следующие.1911. Балансировка дерева вычисленийБалансировка дерева вычислений (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 + CY=B+E+CX = A + D + REGY = E + REG3. Разворачивание цикловРазворачивание циклов (loop unrolling) - расписывание цикла последовательностьюоператоров присваивания: либо полностью, либо размножение тела цикла с некоторымкоэффициентом (фактором) размножения.Производится частичное или полное разворачивание цикла в последовательный участоккода.
При частичном разворачивании используется так называемый фактор разворачивания(который можно задавать в директиве компилятору).DO I=1,100DO I=1,100,4A(I) = B(I) + C(I)A(I) = B(I) + C(I)ENDDOA(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,10DO I=1,10,2S = S + A(I)S = S + A(I)ENDDOS1 = S1 + A(A+1)ENDDOS = S + S1Здесь, суммирование проводится отдельно для четных и нечетных элементов споследующем сложением частных сумм.192.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
