Галс точные таблицы - Gals accurate tables - Wikipedia

Точные таблицы Гала это метод, разработанный Шмуэль Гал предоставить точные значения специальные функции используя Справочная таблица и интерполяция. Это быстрый и эффективный метод генерации значений таких функций, как экспоненциальный или тригонометрические функции с точностью до последнего бита почти для всех значений аргументов без использования арифметики повышенной точности.

Основная идея точных таблиц Гала - это разные таблицы для вычисляемой специальной функции. Обычно диапазон делится на несколько поддиапазонов, каждый с предварительно вычисленными значениями и формулами коррекции. Чтобы вычислить функцию, найдите ближайшую точку и вычислите поправку как функцию расстояния.

Идея Гала состоит не в том, чтобы предварительно вычислить равноотстоящие значения, а в том, чтобы возмущать точки Икс так что оба Икс и ж(Икс) очень точно представлены в выбранном числовом формате. Путем поиска примерно 1000 значений по обе стороны от желаемого значения Икс, можно найти такое значение, что ж(Икс) может быть представлен менее чем ± 1/2000 бит ошибка округления. Если поправка также вычисляется с точностью ± 1/2000 бит (что не требует дополнительной точности с плавающей запятой, пока поправка меньше 1/2000 величины сохраненного значения ж(Икс), и вычисленная поправка находится более чем на ± 1/1000 бита от ровно половины бита (сложный случай округления), тогда известно, следует ли округлять точное значение функции в большую или меньшую сторону.

Этот метод обеспечивает эффективный способ вычисления значения функции с точностью до ± 1/1000 наименее значимого бита, то есть 10 дополнительных битов точности. Если это приближение более чем на ± 1/1000 бита отстоит от ровно посередине между двумя представляемыми значениями (что происходит почти во всех случаях, кроме 2/1000, т.е. 99,8% времени), то правильно округленный результат очевиден.

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

В 2/1000 (0,2%) случаев требуется оценка функции с более высокой точностью для разрешения неопределенности округления, но это бывает достаточно редко, чтобы не повлиять на среднее время вычисления.

Проблема генерации значений функции с точностью до последнего бита известна как дилемма изготовителя стола.

Смотрите также

• Плавающая точка
• Округление

Рекомендации

• Гал, Шмуэль (1986). «Вычисление элементарных функций: новый подход к достижению высокой точности и хорошей производительности». В Miranker, Willard L .; Тупин, Ричард А. (ред.). Точные научные вычисления (1-е изд.). Proceedings of Computations, Symposium, Бад-Нойенар, Федеративная Республика Германия, 12-14 марта 1985 г .: Springer-Verlag Берлин Гейдельберг. п. 1–16. ISBN  978-3-540-16798-3.
• Гал, Шмуэль; Бачелис, Борис (1991). «Точная элементарная математическая библиотека для стандарта IEEE с плавающей запятой». Транзакции ACM на математическом ПО.
• Мюллер, Жан-Мишель (2006). Элементарные функции: алгоритмы и реализация (2-е изд.). Бостон, Массачусетс, США: Биркхойзер. ISBN  978-0-8176-4372-0. LCCN  2005048094.
• Мюллер, Жан-Мишель (12 декабря 2016 г.). Элементарные функции: алгоритмы и реализация (3-е изд.). Бостон, Массачусетс, США: Биркхойзер. ISBN  978-1-4899-7981-0.
• Stehlé, Damien; Циммерманн, Пауль (2005). "Возвращение к методу точных таблиц Гала" (PDF). 17-й симпозиум IEEE по компьютерной арифметике (ARITH'05). С. 257–264. Дои:10.1109 / ARITH.2005.24. ISBN  0-7695-2366-8. В архиве (PDF) из оригинала на 2018-01-15. Получено 2018-01-15.