Вычисление вещественных чисел: с плавающей запятой, TTE, теория доменов, и т. Д.
19
В настоящее время вычисление действительных значений в большинстве популярных языков все еще выполняется с помощью операций с плавающей запятой. С другой стороны, теории, такие как эффективность второго типа (TTE) и теория предметной области, давно обещали точное вычисление действительных чисел. Очевидно, что проблема точности с плавающей запятой не уменьшилась в своей актуальности, так почему же эти теории не стали более распространенными и почему нет более заметных их реализаций?
Например, существуют ли области приложений, в которых нас не волнуют ошибки с плавающей запятой? Существуют ли существенные проблемы сложности?
Я работаю в вычислениях действительных чисел, и я хотел бы знать реальный ответ. Но я могу предположить. Это социологическая проблема, я думаю.
Сообщество людей, которые работают над точной реальной арифметикой, состоит из теоретиков, которые не привыкли к разработке программного обеспечения. Таким образом, они обычно передают задачу реализации студентам (заметное исключение - iRRAM Норберта Мюллера ), или у них есть свои собственные игрушечные реализации .
Люди, у которых есть необходимое программирование, не имеют необходимого теоретического образования. Без твердой теоретической основы трудно правильно составить точную реальную арифметику. Например, ошибочно добавлять много действительных чисел в forцикл, так как вы получите неприемлемую производительность из-за потери точности. Если вы хотите добавить много и много реалов, вы должны сделать это с древовидной структурой, принимая во внимание величины частичных сумм. Еще одна вещь , которую трудно получить через что <и =как общая булевой функции на переАльсу просто не существует (вы можете иметь , =но она либо возвращается falseили расходится и <расходится при введении двух равных реалов).
Наконец, совершенно не ясно, что мы знаем, как реализовать библиотеки для точной реальной арифметики. Это не обычные части библиотек, которые просто определяют некоторые типы данных и некоторые функции для них. Часто точная настоящая арифметика требует специальных режимов управления. Например, iRRAM берет на себя основное выполнение программы (буквально перехватывает main), а также стандартный ввод и вывод, так что он может перезапустить программу при потере точности. Моя библиотека для реальной арифметики в Хаскеле происходит в Stagedмонаде (которая по сути является Readerмонадой). Большинство людей ожидают, что реальные цифры будут «просто еще одним типом данных», но у меня есть сомнения по этому поводу.
Я почти полностью разбираюсь в точной реальной арифметике, но нельзя ли в ней реализовать суммирование Кахана?
JJG
1
Хм, я так не думаю. Думайте о точной реальной арифметике как о интервальной арифметике, которая самостоятельно настраивает промежуточную точность для достижения желаемой выходной точности.
Андрей Бауэр
3
В дополнение к отсутствию понимания программистами факта, что действительные числа являются бесконечными объектами и их последствиями для того, что может быть сделано программно, я думаю, что нехватка аппаратной поддержки также важна. Трудно убедить людей использовать что-то со значительными затратами времени и памяти только для корректности.
Каве
1
Я видел, что есть некоторая активность в реализации реальных вычислений с коиндуктивными типами. Мне кажется, что коиндуктивные типы все еще довольно сложны, чтобы получить права (я, конечно, не эксперт в этом), но вы думаете, что это обещает более широкое использование точных реальных вычислений?
Колдун из
3
Любая реализация, которая использует потоки цифр или что-либо еще, имеющее фиксированную скорость сходимости, с самого начала имеет недостатки, так как она будет сходиться слишком медленно. Кроме того, потоковые реализации, как правило, вынуждают вас вычислять все предыдущие аппроксимации, чтобы получить следующее, что также является ошибкой проектирования.
Андрей Бауэр
10
В общем, люди всегда заботятся об ошибках с плавающей точкой. Однако я не согласен с Андреем и не думаю, что поплавки предпочтительнее, чем действительные числа произвольной точности (по большей части) по социологическим причинам.
Я полагаю, что главный аргумент против точного вычисления реалов - это производительность . Итак, короткий ответ: всякий раз , когда производительность важнее точности, вам нужно использовать числа с плавающей запятой .
На ум приходит применение вычислительной гидродинамики для проектирования аэродинамики автомобилей или самолетов, где небольшие ошибки в вычислениях легко компенсируются астрономическими преимуществами использования выделенных модулей с плавающей запятой, обнаруженных во многих широко распространенных процессорах.
В частности, проблема представления широкого диапазона действительных чисел с использованием фиксированного числа битов не так тривиальна, как может показаться на первый взгляд. При численном моделировании значения могут широко варьироваться (например, при наличии турбулентности), поэтому вычисления с фиксированной точкой не подходят.
Даже если аппаратная точность не фиксируется, использование произвольных чисел точности может быть на несколько порядков медленнее, чем использование чисел с плавающей запятой. На самом деле, даже в хорошем случае были все числа рациональные, простые операции , как инвертирование матрицы может привести к большим, трудно контролировать знаменатели (см здесь для примера). Многие большие линейные пакеты оптимизации используют плавающие точки с соответствующими режимами округления, чтобы найти приблизительные решения из-за этой точной проблемы (см., Например, большинство программ, найденных здесь ).
Есть ли пробные промежутки между некой формой точных реальных вычислений и вычислений с плавающей запятой?
Колдун из
1
Боюсь, я этого не знаю. У Шона Гао есть некоторые интересные результаты о сложности приближенных процедур принятия решений по реалам (см. Его реферат диссертации ), и, конечно, знаменатель в обратной матрице растет в худшем случае, как ее детерминант .
Коди
-6
π
Я хочу сказать, что если вы собираетесь точно вычислять, у вас должны быть заполнители для специальных имен, а также для привычных имен натуральных чисел. В какой-то момент вы захотите приблизить точное значение, чтобы применить его к чему-то в реальном мире. Как выясняется, гораздо эффективнее с самого начала иметь дело с целой проблемой в виде приближений, если только у вас нет особых потребностей.
В общем, люди всегда заботятся об ошибках с плавающей точкой. Однако я не согласен с Андреем и не думаю, что поплавки предпочтительнее, чем действительные числа произвольной точности (по большей части) по социологическим причинам.
Я полагаю, что главный аргумент против точного вычисления реалов - это производительность . Итак, короткий ответ: всякий раз , когда производительность важнее точности, вам нужно использовать числа с плавающей запятой .
На ум приходит применение вычислительной гидродинамики для проектирования аэродинамики автомобилей или самолетов, где небольшие ошибки в вычислениях легко компенсируются астрономическими преимуществами использования выделенных модулей с плавающей запятой, обнаруженных во многих широко распространенных процессорах.
В частности, проблема представления широкого диапазона действительных чисел с использованием фиксированного числа битов не так тривиальна, как может показаться на первый взгляд. При численном моделировании значения могут широко варьироваться (например, при наличии турбулентности), поэтому вычисления с фиксированной точкой не подходят.
Даже если аппаратная точность не фиксируется, использование произвольных чисел точности может быть на несколько порядков медленнее, чем использование чисел с плавающей запятой. На самом деле, даже в хорошем случае были все числа рациональные, простые операции , как инвертирование матрицы может привести к большим, трудно контролировать знаменатели (см здесь для примера). Многие большие линейные пакеты оптимизации используют плавающие точки с соответствующими режимами округления, чтобы найти приблизительные решения из-за этой точной проблемы (см., Например, большинство программ, найденных здесь ).
источник
Я хочу сказать, что если вы собираетесь точно вычислять, у вас должны быть заполнители для специальных имен, а также для привычных имен натуральных чисел. В какой-то момент вы захотите приблизить точное значение, чтобы применить его к чему-то в реальном мире. Как выясняется, гораздо эффективнее с самого начала иметь дело с целой проблемой в виде приближений, если только у вас нет особых потребностей.
источник