анализ точности вычислений на ПК

[[e-mail]]

Всем привет!

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

Параллельно у меня есть связанные с предыдущим вопросы, на которые тоже ищу ответы, но практически безрезультатно, а значит - не там )).

1. Есть функция, вычисление точных значений которой "в лоб" вручную весьма трудоёмкое (специальные функции, к примеру) или вообще невозможно (Erf-функция) . Есть выражения для приближенных значений этой функции и я могу провести вычисления на бумаге (разложение в ряд, не обязательно Фурье).
Вопрос: Есть ли готовый аппарат, позволяющий оценивать погрешность, вносимую использованием приближения. При этом можно ли оценить эту погрешность, не прибегая к ЭВМ.

2. Наверняка есть литература по информационным дисциплинам, в которой подробно рассматриваются ошибки округления, возникающие в ходе элементарных (арифметических и присваивания между различными типами) действий, инструкций. Что почитать?

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

[blondinko]

Пожалуй, попробую ответить.

На всякий случай: при использовании стандартных типов, таких как float, double и long double, для точности существует оценка сверху, обусловленная объёмом разрядной сетки мантиссы. В процессе вычислений эта оценка только падает. И делать это она может как по вине алгоритма, так и по вине данных (что, впрочем, тоже в некоторой степени зависит от алгоритма).
Что до конкретных методов, то «по данным» навскидку могу назвать оценку обусловленности матриц. По алгоритмам — увы, не в курсе.
К слову, если Вам нужно как-то избавляться от ограничений точности, а не просто их оценить — то есть множество библиотек «длинной арифметики», позволяющих проводить вычисления на разрядной сетке произвольного размера, но ценой некоторой потери производительности.

-- 04.09.2014, 23:47 --

Ах да, забыл.

[e-mail] в сообщении #903980 писал(а):

2. Наверняка есть литература по информационным дисциплинам, в которой подробно рассматриваются ошибки округления, возникающие в ходе элементарных (арифметических и присваивания между различными типами) действий, инструкций. Что почитать?

В целочисленных типах не может возникать никакой потери точности, кроме переполнения (попытки записи в двоичный разряд, который «вылезает» за разрядность операнда и следовательно не может быть перезаписан). Такие ситуации на аппаратном уровне ловятся анализом флагового регистра ЦП на наличие так называемого флага переполнения.
Про числа же с плавающей точкой — тех типов, что поддерживаются на машине аппаратно — можно упрощённо судить по виду результата. Если сильно вкратце, то чем больше целая часть ответа, тем меньше верных знаков он имеет после запятой. Была у Pavia, по-моему, хорошая статья на эту тему, но пока не смог откопать…

[e-mail] в сообщении #903980 писал(а):

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

Ну, положим, не такой уж и фантастики. Ищите «вычисления с фиксированной точкой». Это такая модель вычислений, когда дробное число представляется в виде двух целых, одно из которых знаковое и считается целой частью, а второе — беззнаковое, и считается дробной.
При этом мантисса полагается равной $k \over K + 1$, где $k$ — это непосредственно значение второго целого, а $K$ — максимальное значение, которое оно может принимать.

[[e-mail]]

Спасибо. Хочу уточнить - речь идет не об избавлении, а именно об оценке.

Вы правильно заметили, что в процессе вычислений оценка только падает (падает точность). Весьма интересно было бы узнать - насколько упадет точность за миллионы пусть однотипных операций.

[arseniiv]

Думаю, в этой теме не будет лишней ссылка на What Every Computer Scientist Should Know About Floating-Point Arithmetic, by David Goldberg (ну почти). Там, вроде, не все вопросы рассматриваются, но тоже подспорье и хотя бы начало!

[Sonic86]

[e-mail] в сообщении #903980 писал(а):

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

Есть: задачи, сводимые к задачам выполнимости КНФ, могут быть сформулированы как задачи булева линейного программирования. Можно переводить логику в арифметику исходя из соотношений $ab=0 \Leftrightarrow a=0 \vee b=0; \ a^2+b^2 = 0 \Leftrightarrow a=0 \wedge b=0$. Правда, вряд ли это поможет.

[[e-mail]]

Sonic86 в сообщении #904061 писал(а):

[e-mail] в сообщении #903980 писал(а):

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

Есть: задачи, сводимые к задачам выполнимости КНФ, могут быть сформулированы как задачи булева линейного программирования. Можно переводить логику в арифметику исходя из соотношений $ab=0 \Leftrightarrow a=0 \vee b=0; \ a^2+b^2 = 0 \Leftrightarrow a=0 \wedge b=0$. Правда, вряд ли это поможет.

Интересно покопать, сначала я смотрел в сторону логарифмирования.

-- 05.09.2014, 10:57 --

arseniiv, спасибо.

-- 05.09.2014, 10:59 --

blondinko, конечно интересуют неточности от применения Float. С целочисленными при грамотном анализе флагов состояния процессора (на низком уровне) или при умении обработки исключений (на высоком уровне) проблема вполне решаема.
Про вычисления с фиксированной точкой не слышал, спасибо, буду рыть.

-- 05.09.2014, 11:02 --

Но уже судя по ответам - положительного однозначного ответа на мой самый первый вопрос нет, так? Т.е. нет дисциплины, в которой есть готовые методы/подходы, позволяющие по виду программы без применения ЭВМ оценить точность вычислений?

[mihailm]

[e-mail] в сообщении #904066 писал(а):

...Т.е. нет дисциплины, в которой есть готовые методы/подходы, позволяющие по виду программы без применения ЭВМ оценить точность вычислений?

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

[Pavia]

[e-mail]
Меня самого интересовал данный вопрос. Раздел науки называется математика. Готового аппарата нет и пожалуй это индивидуальный подход к каждой задачи. Одной книги где было бы всё я не нашел.
Одно дело одна две операции и другое дело много операций где уже играет роль закон больших чисел.

Точность или погрешности бывают 3-х видов.

Точность исходных данных. Данные тоже бывают не достоверные и округленные то некоторого придела точности.
Точность метода. Математического аппарата, как правило вызванная усечением ряда.
Точность инструментальная. Обусловленная реализацией данного метода аппаратно. Как правила вызванная конечностью представления реальных чисел и как следствие округления при сложении умножение и других операциях.

Цитата:

1. Есть функция, вычисление точных значений которой "в лоб" вручную весьма трудоёмкое (специальные функции, к примеру) или вообще невозможно (Erf-функция) . Есть выражения для приближенных значений этой функции и я могу провести вычисления на бумаге (разложение в ряд, не обязательно Фурье).
Вопрос: Есть ли готовый аппарат, позволяющий оценивать погрешность, вносимую использованием приближения. При этом можно ли оценить эту погрешность, не прибегая к ЭВМ.

Да, можно. Для этого применяют экспоненциальную оценку.
К примеру
Numerical Recipes in C The Art of Scientific Computing 2nd Ed - William H. Press
Глава про интерполирование. Не уверен есть в книге вывод или нет.

Оценка для свертки через БПФ.
http://www.daemonology.net/tricl/fftconv_c.pdf
http://www.daemonology.net/tricl/roots_c.pdf

Цитата:

2. Наверняка есть литература по информационным дисциплинам, в которой подробно рассматриваются ошибки округления, возникающие в ходе элементарных (арифметических и присваивания между различными типами) действий, инструкций. Что почитать?

Это не в области информатике, а в области цифровой вычислительной техники. Сам не добрался.
Байков, "Аппаратурная реализация элементарных функций в ЦВМ"

Цитата:

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

Про это уже ответили. Числа с фиксированной точкой. Далее переход к целым числам и использования рациональной дроби. Можете к примеру почитать про безошибочные вычисления.
Конечно безошибочные вычисления возможно не для всех задач.
Грегори_Р.,_Кришнамурти_Е.-Безошибочные_вычисления__методы_и_приложения(1988)


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

[[e-mail]]

Я не пропал, я читаю и думаю )