Простейшие приемы анализа погрешностей

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

1) неустранимая погрешность (возникающая из-за неточности исходной информации);

2) погрешность метода;

3) погрешность вычислений (возникающая из-за округлений).

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

Относительная оценка погрешности одиночного сложения:

½g_x±y½<=½x/(x±y)½*½g_x½+½y/(x±y)½*½g_y½+½g_±½

1

½g_±*/½<= *b^1-t

1/2

 

(работает в области нормализованных чисел), где b - основание системы счисления принятой в компьютере, t – длинна мантиссы.

Относительная оценка результата одиночного умножения:

½g_x*/y½<½g_x½+½g½+½g_*/½

Машинное представление каждого числа х можно охарактеризовать двумя величинами:

1) Абсолютная погрешность: D_x= x’ – x, где x’ – приближенное значение x.

2) Относительная погрешность: g_x= (D_x/x) ( или (D_x/x’))

g_x= (D_x/x’)= (D_x/(x+D_x)) = (D_x/x)*(1/(1+(D_x/x))) = (D_x/x)*(1-(D_x/x)+ +(D_x/x)²-…) = (D_x/x) + O((D_x/x)²) » (D_x/x). При этом с точностью до линейных членов величины равны .

Докажем написанные ранее формулы.

D_x-y=D_x+D_y+D _-; D _-- погрешность округления;

g_x-y = (D_x-y/(x-y))=(x*D_x)/((x-y)*x)-(y*D_y)/((x-y)*y)+ (D _-/(x-y))=

=(x/(x-y))*g_x+(y/(x-y))*g_y+g_-;

 

 

½g_-½<= 1/2 *b^1-t

 

D_x/y = x’/y’ - x/y+D _/ = (x/y)((1+g_x)/(1+g_y)-x/y + D_/

g_x/y =(D_x/y/(x/y))= (1+g_x)/(1+g_y)-1 +g_/ = (1-g_x)(1-g_y+g_y²-g_y³+…)-1 +g_/ =

= g_x-g_y+g_/ +O(½ g½²) » g_x-g_y+g_/

Формулы погрешности при сложении и умножении доказываются аналогично.

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

g_x±y » (x/(x±y))*g_x±(y/(x±y))*g_y+g_±;

g_x/y » g_x-g_y+g_/;

g_x*y » g_x+g_y+g_*;

g_Öx » (1/2)*g_x+g_Ö;

 

Рассмотрим случай непарного сложения: z = x₁+x+₂…+x_n. Накопление погрешности удобно изобразить следующим графом.

 

Где g_x1,g_x2,g_x3,… - относительные погрешности соответствующих слагаемых, g₊₁,g₊₂,g₊₃,g₊₄, … - относительные погрешности машинного представления парных сумм. При этом наглядно видно, что при увеличении числа слагаемых погрешности увеличиваются, так как идет суммирование произведений погрешностей ( они записаны возле стрелок) вдоль каждой ветви графа.

 

g_z » (x₁/z)*g_x1+(x₂/z)*g_x2+ … + (x_n/z)*g_xn +((x₁+x₂)/z)*g₊₁+

+((x₁+x₂+x₃)/z)*g₊₂+ … + ((x₁+x₂+ … +x_n)/z)*g_+n-2 + g_+n-1.

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

½g_z½£½x₁/z½*½g_x1½+…+½x_n/z½*½g_xn½+{½(x₁+x₂)/z½+ … +

1

+ ½(x₁+x₂+ … +x_n)/z½}* *b^1-t1 +

1/2

 

 

1

+ *b^1-t2

1/2

 

Причем величина погрешности существенным образом зависит от того пересылается ли промежуточное значение в память.

Если ½z½<<½x_i½, то ½g_z½ может быть очень велика. Если промежуточная сумма ½x₁+…+x_k½>>½z_k½, то влияние погрешности округления может оказаться катострофичным.

Рассмотрим для примера десятичный плавающий процессор с точностью 4 значащих десятичных цифры. Сложим 1 и 1*10^-4 (10000 раз).

Если единица прибавляется в начале

1+ 1.000*10^-4=1.0001*10⁰»1.000*10⁰ и т.д. 10000 раз.

å=1.

Если единицу прибавлять в конце:

1.000*10^-4+1.000*10^-4=2.000*10^-4

…

9.000*10^-4+1.000*10^-4=1.000*10^-3

…

9.999*10^-1+1.000*10^-4=10.000*10^-1=1.000*10⁰

1.000*10⁰+1.000*10⁰=2

å=2.

Рассмотрим другой пример: пусть надо вычислить

 

Sin x= å (-1)ⁱ * X²ⁱ⁺¹/ (2i+1)! + O(½X²ⁱ⁺³/(2i+3)!½)

i=1..n

Формула Тейлора–Маклорена

 

В случае когда½Х½<= O(1)- результат достаточно точен.

Напротив в случае когда ½Х½>> O(20)-результат ложен.

 

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

 

АДРЕСА

Каждая ячейка памяти имеет адрес, который используется для ее нахождения. Адреса - это числа, начиная с нуля для первой ячейки увеличивающиеся по направлению к последней ячейке памяти. Поскольку адреса - это те же числа, компьютер может использовать арифметические

операции для вычисления адресов памяти.

Если в ЭВМ используется память большого размера, тогда для ссылок на ее ячейки приходится использовать "длинные" адреса (т.е. большие по размеру), а поскольку эти адреса указываются в командах, то эти команды оказываются "длинными" (речь, конечно же, идет о машинных командах). Это плохо, т.к. увеличиваются размеры машинных программ. Сократить размеры команд при "длинных" адресах можно, например, так. Любой адрес А можно представить в виде суммы B+D, где В - начальный адрес (база) того участка (сегмента) памяти, в котором находиться ячейка А, а D - это смещение, адрес ячейки А, отсчитанной от начала этого сегмента (от В). Если сегменты памяти небольшие, тогда и величина D будет небольшой, поэтому большая часть "длинного" адреса А будет сосредоточена в базе В. Этим и можно воспользоваться: если в команде надо указать адрес А, тогда "упрятываем" базу В в какой-нибудь регистр, а в команде вместо А указываем этот регистр и смещение D. Поскольку для записи D нужно меньше места, чем для адреса А, то тем самым уменьшается размер команды. С другой стороны, благодаря модификации адресов данная команда будет работать с адресом, равным сумме D и содержимого регистра, т.е. с нужным нам адресом А. Рассмотренный способ задания адресов в командах называется сегментированием адресов.

 

Далее рассматривается работа процессоров Intel *8086 при формировании физического адреса в реальном режиме работы. При этом следует учитывать, что работа других процессоров может происходить по-другому, но общий алгоритм работы скорее всего такой же. Однако следует учесть, что работа процессоров в защищенном режиме резко отличается от приведенного ниже.

Большая часть арифметических операций, которые может выполнять микропроцессор 8088, ограничивается манипуляцией с 16-разрядными числами, что дает диапазон значений от 0 до 65.535 или 64 Кбайта. Поскольку полный адрес должен состоять из 20 разрядов, необходимо было разработать способ управления 20 разрядами. Решение было найдено путем использования принципа сегментированной адресации.

 

Если взять 16-ти разрядное число и добавить к нему в конце четыре двоичных нуля, то получится 20-ти разрядное число, которое может использоваться как адрес. Добавлением четырех нулей или сдвиг числа влево на четыре разряда фактически означает умножение числа на 16 и теперь диапазон значений будет составлять 1.024 Кбайт. К сожалению, число с четырьмя нулями в конце может адресовать только одну из 16 ячеек памяти - ту, адрес которой оканчивается на четыре нуля. Все остальные ячейки, адреса которых оканчиваются на любую из остальных 16 комбинаций из четырех бит, не могут быть адресованы при таком методе адресации. Для окончательного решения проблемы 20-разрядной адресации используются два 16-разрядных числа. Считается, что одно из них имеет еще четыре нуля в конце (выходящие за пределы разрядной сетки). Такое как бы 20-разрядное число называется сегментной частью адреса. Второе шестнадцатеричное

число не сдвигается на четыре разряда и используется в своем нормальном виде. Это число называется относительной частью адреса или смещением относительно начала сегмента. Сложением этих двух чисел получают полный 20-разрядный адрес, позволяющий адресовать любую из 1.024 Кбайт ячеек памяти в адресном пространстве IBM/PC. Сегментная часть адреса задает ячейку с адресом, кратным 16, эта ячейка называется границей параграфа. Окончательное значение указывает конкретную ячейку на определенном удалении от границы параграфа.

Чтобы лучше усвоить этот момент, рассмотрим все еще раз. Полный 20-разрядный адрес задается двумя частями, каждая из которых представляет собой 16-разрядное число. Сегментная часть адреса обрабатывается так, как будто он имеет четыре дополнительных нуля в конце. Эта сегментная часть может относиться к любой части всего адресного пространства - но она может указывать только на шестнадцатеричную границу, то есть, на адрес, оканчивающийся на четыре нуля. Относительная часть адреса прибавляется к сегментной части, образуя полный адрес. Относительная часть адреса может задавать любую ячейку памяти, отстоящую от ячейки, указываемой сегментной частью, не более чем на 64 Кбайта.

После указанных выше соображений вам уже, наверное, понятно, что полный адрес можно указать в 4 байтах (как это и делается на компьютере) - эта структура называется дальним указателем. Если мы хотим хранить только смещение, то достаточно всего 2 байт - ближний указатель. Структура указателей этих типов для компьютеров Intel приведена на рисунке:

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

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

Ее (стараничную модель) можно рассматривать как надстройку над сегментированной моделью. В случае использования этой модели оперативная память рассматривается как совокупность блоков фиксированного размера 4 Кбайт. Основное применение этой модели связано с организацией виртуальной памяти, что позволяет операционной системе использовать для работы программ пространство памяти большее, чем объем физической памяти. В страничной модели линейный адрес и физический адрес имеют разные значения. Эти названия являются синонимами только при отключении страничного преобразования адреса (в реальном режиме страничная адресация всегда отключена). Поэтому адресация происходит по следующей схеме: сначала логический адрес (записанный, например, в указателе) преобразуется в линейный адрес, а потом из линейного в физический (как вы увидели они в реальном режиме совпадают).

 

Методы оптимизации

Выравнивание:

Если вы хотите, чтобы ваша программа работала с максимальной скоростью, то надо учитывать малейшие нюансы в организации компьютера. Одним из таких мест является выравнивание. Дело в том, что компьютеры фирмы Intel читают информацию быстрее с кратных двум адресов, поэтому одно и тоже слово начинающееся с кратного адреса и с нечетного адреса будут прочитаны за различное время. В связи с этими обстоятельствами во многие компиляторы языков высокого уровня вводятся специальные директивы, чтобы компилятор размещал данные с кратных адресов. Но тут опять же надо следить за компилятором. Некоторые компиляторы не смотрят за записями (т.е. когда несколько разных типов данных объединяются в одну структуру) и выравнивают только начало записи, а не внутренние данные. В этом случае рекомендуется вводить фиктивные (неиспользуемые)данные. Существует несколько видов выравнивания: выравнивание по адресу кратному 2 (на границу слова), 4 (на границу двойного слова), 16 (на границу параграфа), 256 (на границу страницы размером 256 байт) и 4 Кбайта (адрес следующей страницы памяти размером 4 Кбайт). Последние три вида выравнивания выполняются в основном для сегментов. При правильном выравнивании доступ к данным выполняется быстрее!

 

Порядок заполнения данными:

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