Точные таблицы Гала
Точные таблицы Гала — это метод, разработанный Шмуэлем Галем для получения точных значений специальных функций с использованием справочной таблицы и интерполяции . Это быстрый и эффективный метод генерации значений таких функций, как экспоненциальные или тригонометрические функции, с точностью до последнего бита. точность почти для всех значений аргументов без использования арифметики расширенной точности.
Основная идея точных таблиц Гала — это другая таблица для вычисляемой специальной функции. Обычно диапазон делится на несколько поддиапазонов, каждый из которых содержит заранее рассчитанные значения и формулы коррекции. Чтобы вычислить функцию, найдите ближайшую точку и вычислите поправку как функцию расстояния.
Идея Гала состоит в том, чтобы не вычислять заранее равноотстоящие значения, а скорее воздействовать на точки x так, чтобы и x, и f ( x ) были почти точно представимы в выбранном числовом формате. Путем поиска примерно 1000 значений по обе стороны от желаемого значения x можно найти такое значение, что f ( x менее ±1/2000 бит ) может быть представлено с ошибкой округления . Если поправка также вычисляется с точностью ±1/2000 бит (что не требует дополнительной точности с плавающей запятой, пока поправка меньше 1/2000, величина сохраненного значения f ( x ) и вычисленная поправка отличается более чем на ±1/1000 бита от ровно половины бита (сложный случай округления), то известно, следует ли округлять точное значение функции в большую или меньшую сторону.
Этот метод обеспечивает эффективный способ вычисления значения функции с точностью до ±1/1000 младшего значащего бита, т.е. с точностью до 10 дополнительных битов. Если это приближение отклоняется более чем на ±1/1000 бита от середины между двумя представимыми значениями (что происходит в 99,8% случаев), то правильно округленный результат очевиден.
В сочетании с резервным алгоритмом повышенной точности это позволяет вычислить правильно округленный результат за очень разумное среднее время. В 2/1000 (0,2%) случаев такая оценка с более высокой точностью требуется для устранения неопределенности округления, но это происходит достаточно редко и мало влияет на среднее время расчета.
Проблема генерации значений функции, точных до последнего бита, известна как дилемма составителя таблицы .
См. также
[ редактировать ]Ссылки
[ редактировать ]- Гал, Шмуэль (1986). «Вычисление элементарных функций: новый подход для достижения высокой точности и хорошей производительности». В Миранкере, Уиллард Л.; Тупен, Ричард А. (ред.). Точные научные расчеты (1-е изд.). Труды вычислений, симпозиум, Бад-Нойенар, Федеративная Республика Германия, 12-14 марта 1985 г.: Springer-Verlag Berlin Heidelberg. п. 1–16. ISBN 978-3-540-16798-3 .
{{cite book}}: CS1 maint: местоположение ( ссылка ) - Гал, Шмуэль ; Бачелис, Борис (1991). «Точная элементарная математическая библиотека для стандарта IEEE с плавающей запятой». Транзакции ACM в математическом программном обеспечении .
- Мюллер, Жан-Мишель (2006). Элементарные функции: алгоритмы и реализация (2-е изд.). Бостон, Массачусетс, США: Биркхойзер . ISBN 978-0-8176-4372-0 . LCCN 2005048094 .
- Мюллер, Жан-Мишель (12 декабря 2016 г.). Элементарные функции: алгоритмы и реализация (3-е изд.). Бостон, Массачусетс, США: Биркхойзер . ISBN 978-1-4899-7981-0 .
- Стеле, Дэмиен; Циммерманн, Пол (2005). «Возвращение к методу точных таблиц Гала» (PDF) . 17-й симпозиум IEEE по компьютерной арифметике (ARITH'05) . стр. 257–264. дои : 10.1109/ARITH.2005.24 . ISBN 0-7695-2366-8 . Архивировано (PDF) из оригинала 15 января 2018 г. Проверено 15 января 2018 г.