2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 анализ точности вычислений на ПК
Сообщение04.09.2014, 21:58 
Всем привет!

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

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

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

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

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

 
 
 
 Re: анализ точности вычислений на ПК
Сообщение04.09.2014, 22:27 
Пожалуй, попробую ответить.

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

-- 04.09.2014, 23:47 --

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

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

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

 
 
 
 Re: анализ точности вычислений на ПК
Сообщение04.09.2014, 22:47 
Спасибо. Хочу уточнить - речь идет не об избавлении, а именно об оценке.

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

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

 
 
 
 Re: анализ точности вычислений на ПК
Сообщение05.09.2014, 09:28 
zalex@pisem.net в сообщении #903980 писал(а):
И вопрос из разряда фантастики.
Есть ли аппарат, позволяющий для решения хотя бы небольшого круга некоторых задач перейти к решению задачи лишь на множестве целых чисел?
Есть: задачи, сводимые к задачам выполнимости КНФ, могут быть сформулированы как задачи булева линейного программирования. Можно переводить логику в арифметику исходя из соотношений $ab=0 \Leftrightarrow a=0 \vee b=0; \ a^2+b^2 = 0 \Leftrightarrow a=0 \wedge b=0$. Правда, вряд ли это поможет.

 
 
 
 Re: анализ точности вычислений на ПК
Сообщение05.09.2014, 09:55 
Sonic86 в сообщении #904061 писал(а):
zalex@pisem.net в сообщении #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 --

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

 
 
 
 Re: анализ точности вычислений на ПК
Сообщение05.09.2014, 12:25 
zalex@pisem.net в сообщении #904066 писал(а):
...Т.е. нет дисциплины, в которой есть готовые методы/подходы, позволяющие по виду программы без применения ЭВМ оценить точность вычислений?
Для ответа на вопрос, перечислите пожалуйста все виды программ.

 
 
 
 Re: анализ точности вычислений на ПК
Сообщение05.09.2014, 19:09 
Аватара пользователя
zalex@pisem.net
Меня самого интересовал данный вопрос. Раздел науки называется математика. Готового аппарата нет и пожалуй это индивидуальный подход к каждой задачи. Одной книги где было бы всё я не нашел.
Одно дело одна две операции и другое дело много операций где уже играет роль закон больших чисел.

Точность или погрешности бывают 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)


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

 
 
 
 Re: анализ точности вычислений на ПК
Сообщение07.09.2014, 18:47 
Я не пропал, я читаю и думаю )

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group