Как компьютеры рассчитывают значения грехов? [закрыто]

28

Как компьютер вычисляет значение греха? Логично, что, когда я думаю об этом, единственный очевидный способ - это поместить много значений sin в память, а когда нужно «вычислить» значение sin, он просто извлечет данные с определенного адреса памяти (например, sin (x) извлечь данные из адреса памяти, содержащего значение sin (x)) Это кажется единственным возможным способом сделать это. Или есть функция, которую можно использовать для вычисления греха значения? Я действительно пытаюсь спросить, как компьютер вычисляет грех на базовом уровне. Есть ли способ аппроксимировать значения sin, используя другую функцию, состоящую из более «базовых» операций, и ALU сможет выполнять несколько «базовых» операций для аппроксимации значения sin, или это просто извлечение значений из памяти?

zack1544
источник
10
Google "CORDIC". Гугл "Тейлор сериал". И ваши мысли о памяти не ясны.
Евгений Ш.
8
Метод «памяти» - это метод оптимизации, который часто используется (название «таблица соответствия»). Но нет, изначально на компьютере его нет. Но если вы когда-нибудь бродили о том, как компьютер рассчитывает <placeholder>, Google " <placeholder>алгоритм расчета". Это работает лучше, чем спрашивать о SE в большинстве случаев ..
Евгений Ш.
5
В дополнение к CORDIC и Taylors ', убедитесь, что вы также ищите Чебышева в сочетании с нелинейными минимаксными методами. Тейлор ограничивает среднюю ошибку, в то время как Чебышев ограничивает максимальную ошибку и тоже закрывается быстрее. Минимакс необходим, потому что константы не бесконечно точны и не являются операциями. И вам нужно эксплуатировать симметрии, как сумасшедшие!
Джон
3
Знаете ли вы, что существует ряд, который можно использовать для вычисления греха так же, как и для cos, log, показателей, пи, квадратных корней и т. Д.
Andy aka
2
Конечно, вы можете иметь контент в памяти компьютера «в первую очередь» - как вы думаете, компьютеры загружаются? Начальные значения могут быть подключены к схеме, встроены в ячейки памяти только для чтения или слои металлизации микросхемы, сожжены в предохранители, сохранены в виде захваченного заряда, а также считаны с диска, перфоленты или тумблеров - любой метод, используемый для программного обеспечения в принципе полезно и для предварительно вычисляемых таблиц, и на самом деле многим алгоритмам нужны различные константы. Что лучше всего действительно должно быть решено на основе требований, технологий и даже того, какие ресурсы остались после других потребностей.
Крис Страттон

Ответы:

30

Обычно функции sin (x) с высоким разрешением реализуются с помощью алгоритма CORDIC (COrdiate Rotation DIgital Computer), который может быть выполнен с небольшим количеством итераций, используя только сдвиги и сложения / вычитания и небольшую таблицу поиска. Оригинальный документ CORDIC вычислительная техника Джек Volder от 1959 г. Он также хорошо работает , когда реализован с аппаратными средствами в FPGA (и аналогичный алгоритм будет реализован в аппаратном FPU для тех тысячных , которые имеют FPU).

Для более низкого разрешения, например, для создания синтезированной синусоидальной волны для частотно-регулируемого преобразователя или двигателя (преобразователь частоты), справочная таблица (LUT) с интерполяцией или без нее работает хорошо. Необходимо сохранить значения только для одного квадранта синусоиды из-за симметрии.

Как указывает @Temlib, алгоритмы, используемые в современных FPU, используют уменьшение диапазона с последующей оценкой с использованием чего-то вроде алгоритма Ремеза, чтобы ограничить максимальную абсолютную ошибку. Более подробную информацию можно найти в этой статье Intel. Официальная проверка тригонометрических функций с плавающей запятой .

Спехро Пефхани
источник
2
CORDIC скорее для чисто аппаратного преобразования фиксированных функций (его первое историческое применение). Для компьютера с FPU полиномиальные аппроксимации являются более быстрыми и более подходящими, поскольку они повторно используют существующие арифметические операторы вместо специальной машины сдвига и сложения CORDIC.
TEMLIB
1
@TEMLIB Да, это верный момент, я добавлю это к ответу. CORDIC использовался и в первых научных калькуляторах, таких как HP-35.
Спехро Пефхани
Насколько мне известно, в CORDIC была реализована первая аппаратная реализация настольного калькулятора HP 9100A. Он имел печатную плату размером около квадратного фута, покрытую диодами, которая служила ПЗУ для хранения параметров, используемых алгоритмами CORDIC.
Hot Licks
@HotLicks - вы ошиблись, CORDIC был разработан и использовался в бортовом навигационном компьютере почти за десять лет до HP 9100A.
Крис Страттон
@ChrisStratton - я исправлен.
Hot Licks
14

Большинство библиотек компьютерных триггеров основаны на полиномиальных аппроксимациях , что обеспечивает лучший баланс между скоростью и точностью. Например, дюжины или около того операций умножения и сложения / вычитания достаточно, чтобы обеспечить полную точность с одинарной точностью для синуса и косинуса.

Дэйв Твид
источник