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

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

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 Кбайт). Последние три вида выравнивания выполняются в основном для сегментов. При правильном выравнивании доступ к данным выполняется быстрее!

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

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

Данные системы Turbo Pascal

Классы памяти:

1. Статический - постоянно присутствуют в памяти от начала до конца работы программы(типизированные константы; константы и переменные основной части программы).

Особый интерес в связи с этим представляют собой типизированные

константы. Дело в том, что даже если эта константа объявлена в

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

Пример:

procedure <имя процедуры>;

const

x:integer = 20; { x - типизированная константа}

begin

<делаем что-нибудь>

x:=30;

end;

При первом вызове этой процедуры переменной X присвоится значение 20, но при повторном ее вызове X будет равно уже 30, т.к. повторной инициализации переменной X не происходит (статический класс памяти).

2. Автоматический - память объектам выделяется при входе в блок и освобождается при выходе из него (локальные переменные подпрограмм)

3. Управляемая память(динамическая) - пользователь сам решает когда и сколько памяти ему нужно. Для реализации динамической памяти используются переменные типа указатель. Работа с динамической памятью реализуется через так называемую кучу, которая состоит из всей свободной памяти на данном компьютере. Когда пользователю необходимо выделить память он посылает администратору кучи запрос на выделение необходимого количества памяти с помощью функций GetMem или New. Если такое количество есть, то указателю присваивается адрес начала свободной области памяти необходимого объема. А потом пользователь интерпретирует полученную память так как хочет. В конце работы пользователь обязан вернуть то количество памяти которое он взял.

Примечание:

Наглядный пример - блокнот из 11 страниц в котором пишут карандашом. Естественно, что в любой момент любую страницу можно очистить стирательной резинкой. Давайте поработаем администратором кучи. Для начала зарезервируем одну страницу для рабочих нужд (на ней мы будем хранить указатели). Указатель - это ссылка на место в блокноте где мы храним связанные с ними (указателями) данные. Прежде чем работать с какой-либо из страниц блокнота мы на нашей страничке записываем данные о начальной страничке наших данных, а также количество взятых страниц. Т.е. например для пункта 2 (см. текст ниже)

мы пишем например так:

Работа1 - 1 страница - 3 страницы

Записи такого вида позволяют не запутаться компилятору в сложной структуре памяти.

1) Блокнот в начале работы пустой:

0 0 0 0 0 0 0 0 0 0

это означает что все 10 страниц - пустые (0 - ничего нет)

2) Предположим, что нам понадобилось для 1 работы 3 страницы. Ищем первые три пустые

страницы и забираем их (это в переводе на компьютерный язык называется выделением

памяти):

1 1 1 0 0 0 0 0 0 0

3) Для следущей 2 и 3 работы понадобилось соответственно 1 и 4

страницы. Получим:

1 1 1 2 3 3 3 3 0 0

4) Теперь предположим, что 2 работу мы сделали и страницы, выделенные

под эту работу нам не нужны, - стираем все что на них написано и

они снова готовы к использованию(освобождение памяти):

1 1 1 0 3 3 3 3 0 0

5) Теперь освободим страницы для работы 1 и выделим для 4 работы 2

страницы

0 0 0 0 3 3 3 3 0 0

4 4 0 0 3 3 3 3 0 0

6) Как вы видите страницы оказались фрагментированными: сначала идут 2

занятые страницы, потом 2 пустые, потом 4 занятые и 2 пустые

страницы, т.е. свободно 4 страницы.

Предположим, что теперь вам необходимо 3 страницы для следующей

работы. Казалось бы, чего проще - ведь четыре пустых страницы, но на

самом деле вы не сможете выделить страницы, т.к. не сможете найти 3

подряд идущих страницы. Обидно, но так же обстоит дело и на

компьютере: из-за фрагментации кучи может возникнуть ситуация когда

свободно больше памяти чем надо, а выделить необходимый объем вам не

удастся и в таких случаях фиксируется ошибка.

4. Базированный класс - память объектам выделяется в одних и тех же участках памяти.

Пример:

var

x:longint;

b:array[1..4] of byte absolute x;

В данном примере память для объекта b, который является массивом из 4 байт, выделяется в том же самом месте, что и для переменной X. Меняя значения массива мы тем самым меняем значение X.

Пример с указателями:

type

ab = array[1..4] of byte; {вводим новый тип}

var

x:longint;

pb:^ab; {pb - указатель на массив из 4 элементов}

begin

<делаем что-нибудь>

pb:=@x; {pb указывает на адрес переменной X}

Примечание:операция @ - взятие адреса объекта

Типы данных:

Логические:

boolean - 1 байт (нормализованный)

ByteBool ¦

WordBool ¦} ненормализованные

LongBool ¦ 0 - false, иначе - true

Целые беззнаковые:

Byte - 1 байт. Значения: 0..255

Word - 2 байта. Значения: 0..65535

Целые знаковые:

ShortInt - 1 байт. Значения: -128..127

Integer - 2 байта. Значения: -32768..32767

LongInt - 4 байта. Значения: -2147483648..2147483647

Вещественные типы данных:

арифметических выражениях и занимают в памяти от 4 до 10 байт.

Эффективное использование типов single, double, extended, comp возможно только при наличии сопроцессора 8087 при включенной директиве {$N+}. По умолчанию она находится в выключенном состоянии {$N-}. Вещественные десятичные числа в форме с плавающей точкой в таблице представлены в экспоненциальном(научном) виде: mE+p, где m - мантисса (целое или дробное число с десятичной точкой), "E" означает "десять в степени", p - порядок (целое число).

5.18e+02 = 5.18 * 10^2 = 518

10e-03 = 10 * 10^-3 = 0.01

Пример:

var

Summa: Single;

Root1, Root2: Double;

Символьные:

Char - 1 байт (код ASCII - кодовая таблица IBM PC)

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

Строки символов:

В Turbo Pascal для строк существует такая структура данных как string.

Описывается она по-разному:

string - 256 байт (строка из не более чем 255 символов)

string[max] - max+1 байт (строка из не более чем max символов, где

0<max<256)

Как легко видеть размер строки на 1 байт больше, чем количество доступных символов.

Пример:

var

Name: string[30]; {Строка не более чем из 30 символов}

Address: string; {Строка не более чем из 255 символов}

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: