Алгоритм BKM является сдвиг-сложением алгоритм для вычисления элементарных функций , впервые опубликованный в 1994 году Жан-Клод Bajard, Сильвануса Кла и Жан-Мишель Мюллер. BKM основан на вычислении комплексных логарифмов ( L-режим ) и экспонент ( E-режим ) с использованием метода, аналогичного алгоритму, который Генри Бриггс использовал для вычисления логарифмов. Используя предварительно вычисленную таблицу логарифмов отрицательных степеней двойки, алгоритм BKM вычисляет элементарные функции, используя только операции сложения, сдвига и сравнения целых чисел.
BKM похож на CORDIC , но использует таблицу логарифмов, а не таблицу арктангенсов . На каждой итерации выбор коэффициента производится из набора из девяти комплексных чисел 1, 0, −1, i, −i, 1 + i, 1 − i, −1 + i, −1 − i, а не из только -1 или +1, как используется CORDIC. BKM обеспечивает более простой метод вычисления некоторых элементарных функций, и в отличие от CORDIC, BKM не требует масштабного коэффициента результата. Скорость сходимости BKM составляет примерно один бит на итерацию, как и CORDIC, но для BKM требуется больше предварительно вычисленных элементов таблицы для той же точности, потому что таблица хранит логарифмы сложных операндов.
Как и другие алгоритмы в классе сдвига и сложения, BKM особенно хорошо подходит для аппаратной реализации. Относительная производительность программной реализации BKM по сравнению с другими методами, такими как полиномиальные или рациональные аппроксимации, будет зависеть от доступности быстрых многобитовых сдвигов (т. Е. Сдвигового сдвига ) или аппаратной арифметики с плавающей запятой .
Ссылки [ править ]
- Бахар, Жан-Клод; Кла, Сильванус; Мюллер, Жан-Мишель (август 1994). «BKM: новый аппаратный алгоритм для сложных элементарных функций» (PDF) . Транзакции IEEE на компьютерах . 43 (8): 955–963. DOI : 10.1109 / 12.295857 . ISSN 0018-9340 . Архивировано (PDF) из оригинала 21 декабря 2017 года . Проверено 21 декабря 2017 .
- Бахар, Жан-Клод; Имбер, Лоран (1999-11-02). Лук, Франклин Т. (ред.). «Оценка сложных элементарных функций: новая версия BKM» (PDF) . Труды SPIE, расширенные алгоритмы обработки сигналов, архитектуры и реализации IX . Расширенные алгоритмы обработки сигналов, архитектуры и реализации IX. Общество инженеров фотооптического приборостроения (SPIE). 3807 : 2–9. Bibcode : 1999SPIE.3807 .... 2B . DOI : 10.1117 / 12.367631 . Проверено 9 июня 2020 . [1]
- Имбер, Лоран; Мюллер, Жан-Мишель; Рико, Фабьен (2006-05-24) [2000-06-01, сентябрь 1999]. «Алгоритм Radix-10 BKM для вычисления трансцендентальных чисел на карманных компьютерах» . Журнал обработки сигналов СБИС (Отчет об исследовании). Kluwer Academic Publishers / Национальный институт исследований в области информатики и автоматизации (INRIA). 25 (2): 179–186. DOI : 10,1023 / A: 1008127208220 . ISSN 0922-5773 . РР-3754. INRIA-00072908. Тема 2. Архивировано 11 июля 2018 года . Проверено 11 июля 2018 . [2] [3]
- Мюллер, Жан-Мишель (2006). Элементарные функции: алгоритмы и реализация (2-е изд.). Бостон, Массачусетс, США: Birkhäuser . ISBN 978-0-8176-4372-0. LCCN 2005048094 .
- Мюллер, Жан-Мишель (12 декабря 2016 г.). Элементарные функции: алгоритмы и реализация (3-е изд.). Бостон, Массачусетс, США: Birkhäuser . ISBN 978-1-4899-7981-0.
Дальнейшее чтение [ править ]
- Йорке, Гюнтер; Лампе, Бернхард; Венгель, Норберт (1989). Arithmetische Algorithmen der Mikrorechentechnik (на немецком языке) (1-е изд.). Берлин, Германия: VEB Verlag Technik . С. 280–282. ISBN 3-34100515-3. . EAN 9783341005156 . MPN 5539165. Лицензия 201.370 / 4/89 . Проверено 1 декабря 2015 .
- Меггитт, Джон Э. (1961-08-29). «Псевдоделение и процессы псевдоумножения» . Журнал исследований и разработок IBM . Ривертон, Нью-Джерси, США: IBM Corporation (опубликовано в апреле 1962 г.). 6 (2): 210-226, 287. DOI : 10,1147 / rd.62.0210 . Проверено 1 декабря 2015 .
- Чи Чен, Тянь (июль 1972 г.). «Автоматическое вычисление экспонент, логарифмов, отношений и квадратных корней» . Журнал исследований и разработок IBM . Сан-Хосе, Калифорния, США; Ривертон, Нью-Джерси, США: Исследовательская лаборатория IBM в Сан-Хосе ; Корпорация IBM . 16 (4): 380–388. DOI : 10.1147 / rd.164.0380 . Проверено 1 декабря 2015 .
Внешние ссылки [ править ]
- Revol, Натали; Якубсон, Жан-Клод. «Ускоренные алгоритмы сдвига и сложения» (PDF) . Бостон, США: Лаборатория числового анализа и оптимизации (ANO) Университета наук и технологий Лилля ; Kluwer Academic Publishers . Архивировано (PDF) из оригинала 21 декабря 2017 года . Проверено 21 декабря 2017 .
