Продолжаю серию статей по работе с плавающей запятой.
В первая статья Я дал краткое математическое введение и показал самый простой и очевидный способ вычисления синуса на примерах программ с разными подводными камнями.
Сегодня статья будет немного в другом стиле.
Практики здесь не будет, но мы углубимся в математику и проникнем в святая святых — код стандартной библиотеки.
Я также отвечу на вопрос в конце первой статьи.
Итак, начнем.
Еще немного математики
Очевидно, что чем быстрее убывает по абсолютной величине ряд Тейлора, тем меньше членов необходимо для достижения требуемой точности.И похоже, что результат будет более точным (подробнее об этом будет сказано ниже).
Для сравнения, например, возьмем член седьмой степени ряда Тейлора ( 
) в 
И 
.
Значения выражения будут 
И 
соответственно.
Огромная разница, не так ли? Итак, попробуем найти способ уменьшить верхнюю границу интервала вычисления функции синуса.
Расширение ряда вокруг заданных значений
Чтобы понять этот метод, нам нужно вернуться на первый курс института и вспомнить определения ряда Тейлора ( вики ).В двух словах: зная функцию и ее производные в некоторой точке, можно найти значения функции в окрестности этой точки, разложив ее в ряд Тейлора.
Для синусоидальной функции это означает следующее 
Что дает нам такой подход с практической точки зрения? Представим, что у нас есть интервал от 
до 
.
Выделим на этом интервале 10 линейно распределенных точек (выбор неоптимален): 
, 
, 
, 
.
Для каждой точки рассчитываем таблицу с синусом и его производными в данной точке.
Теперь вы можете изменить функцию так, чтобы при получении значения 
функция принимает ближайшее значение 
и выстраивает его в ряд вокруг точки
, а не около нуля( 
).
Использование тригонометрических преобразований
Если мы вернемся еще дальше, в среднюю школу, мы сможем вспомнить одну очень важную формулу:
А дальше все то же самое, что и в предыдущем пункте.
Выбираем точки внутри интервала, вычисляем для них синус и косинус, а при вызове функции синуса ищем ближайшую и по формуле выше вычисляем синус по малому значению 
.
Подумайте, какой из этих двух методов лучше выбрать, а пока перейдем от математики к практическим расчетам.
Распределительное свойство умножения в мире чисел с плавающей запятой
Пришлось все-таки спрашивать в Интернете совета, как это все-таки называется.
.
Оказывается, это распределительное свойство.
Вернемся к вопросу, который я задал в конце первой части.
А именно, почему математически эквивалентные выражения 
И 
может ли давать разные результаты в вычислениях с плавающей запятой? Самый простой способ проиллюстрировать это на примере.
Давайте возьмем гипотетическую систему, которая работает с числами с плавающей запятой в десятичном формате с точностью до 4 цифр.
Давайте представим, что 
, 
, А 
.
Для начала возьмем выражение в скобках и посчитаем его пошагово, не забывая на каждом шаге округлять:
1) 
2) 
Ответ получен 
Теперь пошагово посчитаем второе выражение: 
Ответ получен 
Правильный ответ: 0,0574806652.
Как видите, ответ, полученный во втором случае, гораздо ближе к истинному, чем в первом.
Если объяснить это на пальцах, то представьте, что когда в первом случае мы прибавляем число к 1,0
мы просто выбрасываем последние две цифры.
Их больше нет. Во втором случае отбрасывание происходит в самом конце, после умножения.
Те.
во втором случае операция(и) умножения является более точной.
На этом вроде можно закончить, но присмотритесь к первому методу и скажите, какой будет результат расчета.
.
И.
У нас есть способ округлять числа с плавающей запятой! Не игнорируйте этот пример.
Дайте себе время разобраться в этом.
Позже в этой и последующих статьях мы будем очень интенсивно использовать округление чисел.
Отметим еще одну особенность этого выражения.
Представьте, что нам недостаточно четырехзначной точности для переменной.
Что делать? И здесь у нас уже есть ответ – представьте число в виде 
и сохраните его в памяти как сумму двух цифр.
И, соответственно, выполнять операции (например, умножение) отдельно для обоих слагаемых.
Подробнее данная техника описана в статье Добавление двух чисел с плавающей запятой без потери точности .
В предыдущей статье я также писал, что метод
есть одна неприятная особенность.
И вот что это такое.
Число 
всегда обрезается по последней значащей цифре числа 
.
Это означает, что независимо от количества
, Если 
, то ошибка в последнем знаке всегда возможна даже при малых
.
А это неприемлемо в подходе, описанном в следующей главе.
Как это работает на примере библиотеки GNU
Так как? Какой из двух способов, описанных в начале статьи, вы выбрали для точного расчета синуса? Какой бы метод вы ни выбрали, оба метода верны.Более того, они абсолютно идентичны.
Хоть поверьте, хоть проверьте.
Ниже я буду использовать школьные формулы.
Их легче объяснить.
Вооружившись знаниями, полученными в предыдущей и этой статье, вы легко разберетесь в коде стандартной библиотеки.
Давайте откроем файл s_sin.c и найдите там функцию __грех : 
Его код довольно прост. Легко заметить, что он вызывает различный набор функций в зависимости от ограничений входной переменной.
В этой статье мы обсудим раздел кода 218-224 для углов 2^-26.<|x|< 0.855469. It can be seen that in this section of the code the function do_sin (x, 0) is called. We will dwell on this function in more detail: 
- Предположим, что dx=0, чтобы упростить пояснения.
- 129-130 В самом начале мы понимаем, что когда abs(x)<0.126, i.e. x value is small enough, we calculate the sine directly using the Taylor series. Since there is nothing significantly new in this macro compared to the code described in the previous part, we move on immediately.
- 136-137. Округляя число, о котором мы говорили выше.
По сути x разлагается на 2 части.
Большая часть u и остальная часть x. В качестве гипотетического примера предположим, что у нас есть число 0,345678. После этой операции это число разложится на два u=0,34, и x станет 0,005678.
- 140-142. Вычисление синуса ( s ) и косинуса ( c ) x из предыдущего абзаца ряда Тейлора.
Обратите внимание, что cos(x)=1-c, поскольку в разложении нет первого члена 1,0, а остальные члены имеют противоположные знаки (см.
исходный файл), чем в ряду Тейлора для косинуса.
- 143. Получены табличные значения переменной u. Если мы воспользуемся нашим гипотетическим примером выше, при u=0,34 мы возьмем элемент таблицы номер 34. sin(u)=sn+ssn, cos(u)=cs+ccs. sn и cs — «большие» части значения синуса и косинуса в точке u, а ssn и ccs — маленькие части.
- 144-145. Используя вторую формулу из этой статьи, мы получаем sin(u+x)=(sn+ssn)*(1-c)+(cs+ccs)*s. Уже зная, как правильно складывать и умножать числа с плавающей запятой, раскройте скобки и сравните полученное выражение с 144-145. Тот, кто проведет расчеты, получит в конце небольшой сюрприз.
Много математики осталось позади.
Например, как рассчитать размер таблицы и самих элементов в ней? Откуда взялись магические числа 0,126 и 0,855469? Когда отсечь расчет возле Тейлора? Поправки к коэффициентам ряда Тейлора для уточнения результата.
Все это, конечно, интересно, но объективно представленный метод имеет множество недостатков: необходимо вычислять синус (s) и косинус (с) одновременно, что требует в два раза больше вычислений ряда Тейлора 1 .
Умножение на табличные значения, как видим, тоже не бесплатно.
Также сохранить таблицу размером 3520 байт в оперативной памяти, конечно, не проблема, но доступ к ней (даже в кеше) может оказаться дорогостоящим.
Поэтому в следующей части мы попробуем избавиться от знака и вычислить синус на интервале [0,126, 0,855469] напрямую, но более точно, чем в первой главе.
Прежде чем мы закончим, небольшой вопрос.
Большое число в этом примере — 52776558133248=3*2. 44 .
Откуда взялось это число, например, 2 45 ? Сформулирую вопрос точнее.
Почему 3*2 оптимально при округлении чисел? Н , а не, например, 2 Н+1 ? Другой вопрос: какое N следует выбрать, чтобы округлить число до целого числа? 1 Стоит отметить, что существенное преимущество такого подхода может появиться при одновременном вычислении синуса и косинуса под одним и тем же углом.
Вторую функцию можно вычислить практически бесплатно.
Теги: #математика #Алгоритмы #программирование #вычисления с плавающей запятой
-
Жи-Интеллект
19 Oct, 24 -
Черный Чемодан Чубайса
19 Oct, 24 -
Релиз Wordpress 2.7.1
19 Oct, 24 -
Directaccess В Windows 7. Часть 3
19 Oct, 24 -
Подставка Для Ноутбука С Вентилятором
19 Oct, 24 -
Свой Pix2Code С Блэкджеком, Но Без Нейронов
19 Oct, 24 -
Создаем Дизайн-Систему
19 Oct, 24
