Лекция
Привет, Вы узнаете о том , что такое точные таблицы галя, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое точные таблицы галя, единица на последнем месте, единица наименьшей точности, ulp, дилемма составителя таблиц , настоятельно рекомендую прочитать все из категории Численные методы.
Точные таблицы Гала — это метод, разработанный Шмуэлем Галом ( математик и профессор статистики Хайфского университета в Израиле) для получения точных значений специальных функций с использованием интерполяционной таблицы и интерполяции . Это быстрый и эффективный метод генерирования значений таких функций, как экспоненциальные или тригонометрические функции, с точностью до последнего бита почти для всех значений аргументов без использования арифметики повышенной точности.
|
Шмуэль Галь
|
|
|---|---|
 |
Основной идеей точных таблиц Гала является иная табуляция для вычисляемой специальной функции. Обычно диапазон делится на несколько поддиапазонов, каждый из которых имеет предварительно вычисленные значения и формулы коррекции. Чтобы вычислить функцию, найдите ближайшую точку и вычислите поправку как функцию расстояния.
Идея Гала состоит в том, чтобы не предварительно вычислять значения, расположенные через равные промежутки, а скорее возмущать точки x так , чтобы и x , и f ( x ) были почти точно представлены в выбранном числовом формате. При поиске приблизительно 1000 значений по обе стороны от желаемого значения x можно найти такое значение, что f ( x ) может быть представлено с ошибкой округления менее ±1/2000 бит . Если коррекция также вычисляется с точностью ±1/2000 бит (что не требует дополнительной точности вычислений с плавающей запятой, если коррекция меньше 1/2000, то величина сохраненного значения f ( x), а вычисленная поправка более чем на ±1/1000 бита отличается от ровно половины бита (сложный случай округления), то известно, следует ли округлить точное значение функции вверх или вниз.
Этот метод обеспечивает эффективный способ вычисления значения функции с точностью до ±1/1000 младшего значащего бита, т. Об этом говорит сайт https://intellect.icu . е. с точностью до 10 дополнительных битов. Если это приближение более чем на ±1/1000 бита отстоит точно от середины между двумя представимыми значениями (что происходит в 99,8% случаев), то правильно округленный результат ясен.
В сочетании с резервным алгоритмом повышенной точности это может вычислить правильно округленный результат за очень разумное среднее время. В 2/1000 (0,2%) времени такая высокоточная оценка требуется для разрешения неопределенности округления, но это достаточно редко, чтобы мало влиять на среднее время расчета.
Проблема генерирования значений функций с точностью до последнего бита известна как дилемма составителя таблиц .
Уильям М. Кахан ввел термин «Дилемма Составителя таблиц» для обозначения неизвестной стоимости округления трансцендентных функций :
Никто не знает, сколько будет стоить правильное округление y w для каждых двух аргументов с плавающей запятой, при которых не происходит переполнение/недостаточное значение. Вместо этого уважаемые математические библиотеки вычисляют элементарные трансцендентные функции в основном за чуть более половины ulp и почти всегда хорошо за один ulp. Почему нельзя округлить y w в пределах половины ulp, как SQRT? Потому что никто не знает, сколько вычислений это будет стоить... Не существует общего способа предсказать, сколько дополнительных цифр придется перенести, чтобы вычислить трансцендентное выражение и правильно его округлить.до некоторого заранее заданного количества цифр. Даже тот факт (если он верен), что в конечном итоге будет достаточно конечного числа дополнительных цифр, может быть глубокой теоремой.
Стандарт IEEE 754 для операций с плавающей запятой гарантирует, что сложение, вычитание, умножение, деление, плавное умножение-сложение , квадратный корень и остаток с плавающей запятой дадут правильно округленный результат операции с бесконечной точностью. В стандарте 1985 года для более сложных функций не было такой гарантии, и они, как правило, в лучшем случае точны только до последнего бита. Однако стандарт 2008 года гарантирует, что соответствующие реализации будут давать правильно округленные результаты, соответствующие активному режиму округления; однако реализация функций не является обязательной.
Используя теорему Гельфонда-Шнайдера и теорему Линдеманна-Вейерштрасса , можно доказать, что многие стандартные элементарные функции возвращают трансцендентные результаты, за исключением некоторых хорошо известных аргументов; поэтому с теоретической точки зрения такие функции всегда можно правильно округлить. Однако для реализации такой функции определение предела для заданной точности того, насколько точными должны быть вычислены результаты, прежде чем можно будет гарантировать правильно округленный результат, может потребовать много времени вычислений или может быть недостижимым. На практике, когда этот предел неизвестен (или известен только очень большой предел), в реализации необходимо принять какое-то решение (см. Ниже); но в соответствии с вероятностной моделью правильное округление может быть удовлетворено с очень высокой вероятностью при использовании промежуточной точности до удвоенного количества цифр целевого формата плюс некоторая небольшая константа (после учета особых случаев).
Вау!! 😲 Ты еще не читал? Это зря!Редактировать
Исследование, описанное в статье про точные таблицы галя, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое точные таблицы галя, единица на последнем месте, единица наименьшей точности, ulp, дилемма составителя таблиц и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Численные методы
Из статьи мы узнали кратко, но содержательно про точные таблицы галя
Комментарии
Оставить комментарий
Численные методы
Термины: Численные методы