Лекция2 - 2015

Влияние ошибок округления на результаты алгоритмов вычислительной геометрии

лекция 2

Проблемы организации вычислений

Дмитрий Орлов, к.т.н.

Национальный исследовательский университет «МЭИ»

Кафедра Вычислительных машин, систем и сетей

1

Организация вычислений с ослаблением влияния ошибок округления

на уровне процедур

на уровне операций

•для каждого алгоритма необходимы две реализации

•все проверки – вручную

Point A,B,C; //...

res=ORIENTATION_INTERVAL(A,B,C); if( !ISAUTHENTIC(RES) ){

RES=ORIENTATION_EXACT(A,B,C);

}

Начало
Входные
данные.
Считаем, что
они заданы
точно
Выбор операции
Добавление операции
в граф истории
вычислений
Выполнение операции
Достоверный	да
результат
получен?
нет
Обновление
результата
вычислений
Вычисления	нет
закончены?
Результат
алгоритма
Конец

•для каждого алгоритма необходима одна реализация

•все проверки – автоматизированы

•необходимо сохранение графа истории вычислений

2

Реализация вычислений с ослаблением влияния ошибок округления

Разработанная реализация:

-использует алгоритм оценки достоверности результата;

-при получении недостоверного результата происходит его пересчёт с использованием вычислений с исключением ошибок округления;

-«прозрачна» для пользователя;

-реализована поддержка основных арифметических операций, сравнений, преобразования в целые числа;

-для повторения вычислений необходимо хранить их историю.

История вычислений:

-каждое число является результатом какой-либо операции;

-для каждой операции хранятся указатели на её аргументы;

-таким образом, история вычислений хранится в виде направленного ациклического графа.

3

Вычисления с исключением ошибок округления: реализация на CPU

•используются вычисления в рациональных числах

•рациональные числа представлены обыкновенными дробями

•числитель и знаменатель обыкновенной дроби представлены целыми числами изменяемой разрядности

4

Граф истории вычислений

Представлена направленным ациклическим графом.
Узлы: числа и операции.
Дуги: указатели.				30029						−1
							−	15014
Пример: история вычислений для результата выражения
				30031				15015
30029	30031	15014	15015

/

/

1

-

/

результат

5

Особенности организации вычислений на CPU

Представление графа истории

Диаграмма структуры классов

вычислений в памяти ЭВМ

разработанной библиотеки

Применение разработанной библиотеки: в исходном коде алгоритма замена

FLOAT на ERRORCONTROLLED

6

Вычисления с ослаблением влияния ошибок округления: реализация на CPU

•автоматическое построение графа истории вычислений

•каждая вершина графа представляет некоторое число

•пользователю доступны только указатели на вершины графа

•в каждой вершине изначально заполняется только объект вычислений с автовалидацией

•точное значение результата заполняется только при обновлении графа

7

Вычисления с ослаблением влияния ошибок округления: пример функционирования

Построение графа истории вычислений для выражения		30029		−	15014		−1
		30031			15015

8

Вычисления с ослаблением влияния ошибок округления: пример функционирования

	30029				15014			−1
Вычислим результат выражения				−				> 450915465
	30031				15015

9

Вычисления с ослаблением влияния ошибок округления: пример функционирования

	30029				15014			−1
Вычислим результат выражения				−				> 450915465
	30031				15015