Актуальность вычислений с фиксированной и произвольной точностью

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

Существуют ли какие-либо ОСНОВНЫЕ трудности при использовании, скажем, решателя собственных значений с фиксированной точкой? Насколько медленными / быстрыми, неточными / точными они будут?

Связанные: это и это

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

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

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

Раньше я думал, что представления с плавающей точкой были грубыми или неточными (зачем тратить биты на показатель степени ?!). Но со временем я понял, что это действительно одно из лучших представлений для реальных чисел. Вещи в природе проявляются в логарифмическом масштабе, поэтому реальные данные охватывают широкий диапазон показателей. Также для достижения максимально возможной относительной точности требуется работа с логарифмическими масштабами, что делает отслеживание показателя степени более естественным. Единственный другой претендент на «естественное» представление - это симметричный индекс уровня . Однако сложение и вычитание гораздо медленнее в этом представлении, и ему не хватает аппаратной поддержки IEEE 754. Огромное количество идей было вложено в стандарты с плавающей запятой.Столпом числовой линейной алгебры. Я думаю, он знает, что такое «правильное» представление чисел.

В качестве примера того, почему точная арифметика / арифметика с фиксированной точкой используется так редко, рассмотрим это:

• В методе конечных элементов, как и почти во всех других методах, используемых в научных вычислениях, мы получаем линейные или нелинейные системы, которые являются лишь приближением к реальному миру. Например, в FEM решаемая линейная система является лишь приближением к исходному уравнению в частных производных (которое само по себе может быть только приближением к реальному миру). Так зачем прикладывать огромные усилия для решения чего-то, что является лишь приближением?

• Большинство используемых нами сегодня алгоритмов итеративны по своей природе: метод Ньютона, сопряженные градиенты и т. Д. Мы прекращаем эти итерации всякий раз, когда мы убеждены, что точность итеративного приближения к решению задачи достаточна. Другими словами, мы завершаем работу до того, как имеем точное решение. Как и прежде, зачем использовать точную арифметику для итерационной схемы, когда мы знаем, что мы только вычисляем приближения?

Если вы посмотрите на эту библиотеку для правильного округления: CRlibm , вы увидите в документации, что, как правило, алгоритмы должны быть проверены на точность (с обоснованными доказательствами). Почему? Стабильность и скорость сходимости результата функции не имеют универсального ответа. Короче говоря, нет «бесплатного обеда» - вы должны работать, чтобы доказать, что ваши рассуждения верны. Это происходит из-за поведения моделируемых функций, а не из-за аппаратного обеспечения (используете ли вы целочисленные единицы или числа с плавающей запятой, хотя да, у обоих есть «ошибки», такие как переполнение / понижение, ненормальные числа и т. Д.), Даже если результат вы ищете сходится к целому числу, алгоритм, используемый для поиска результата, не обязательно очень стабильным.

Eigen - это библиотека C ++, которая имеет множество алгоритмов для решения матриц, каждый из которых имеет свои свойства. Эта страница содержит таблицу, в которой обсуждаются соотношения скорости и точности для различных алгоритмов, используемых для решения матрицы. Я подозреваю, что библиотека Eigen может делать то, что вы хотите. :-)

Для некоторых хороших примеров того, как высокоточная арифметика была полезна в математике, взгляните на книгу « Математика по эксперименту » Джонатана Борвейна и Дэвида Бейли. Также есть продолжение , которое я не читал.