Algoritmo BKM

El algoritmo BKM es un algoritmo de cambio y suma para calcular funciones elementales , publicado por primera vez en 1994 por Jean-Claude Bajard, Sylvanus Kla y Jean-Michel Muller. BKM se basa en calcular logaritmos complejos ( modo L ) y exponenciales ( modo E ) utilizando un método similar al algoritmo que Henry Briggs utilizó para calcular logaritmos. Al usar una tabla precalculada de logaritmos de potencias negativas de dos, el algoritmo BKM calcula funciones elementales usando solo operaciones de suma, desplazamiento y comparación de enteros.

BKM es similar a CORDIC , pero usa una tabla de logaritmos en lugar de una tabla de arctangents . En cada iteración, se elige un coeficiente de un conjunto de nueve números complejos, 1, 0, −1, i, −i, 1 + i, 1 − i, −1 + i, −1 − i, en lugar de solo -1 o +1 como lo usa CORDIC. BKM proporciona un método más simple para calcular algunas funciones elementales y, a diferencia de CORDIC, BKM no necesita un factor de escala de resultados. La tasa de convergencia de BKM es de aproximadamente un bit por iteración, como CORDIC, pero BKM requiere más elementos de tabla precalculados para la misma precisión porque la tabla almacena logaritmos de operandos complejos.

Al igual que con otros algoritmos de la clase Shift-and-Add, BKM se adapta particularmente bien a la implementación de hardware. El rendimiento relativo de la implementación de software BKM en comparación con otros métodos, como aproximaciones polinomiales o racionales , dependerá de la disponibilidad de cambios rápidos de múltiples bits (es decir, un desplazador de barril ) o aritmética de punto flotante de hardware .

Referencias

Bajard, Jean-Claude; Kla, Sylvanus; Muller, Jean-Michel (agosto de 1994). "BKM: Un nuevo algoritmo de hardware para funciones elementales complejas" (PDF) . Transacciones IEEE en computadoras . 43 (8): 955–963. doi : 10.1109 / 12.295857 . ISSN 0018-9340 . Zbl 1073.68501 . Archivado (PDF) desde el original el 3 de noviembre de 2018 . Consultado el 21 de diciembre de 2017 .
Skaf, Ali; Muller, Jean-Michel; Guyot, Alain (20 a 22 de septiembre de 1994). Implementación de hardware en línea para logaritmos y exponenciales complejos . ESSCIRC '94: XX Congreso Europeo de Circuitos de Estado Sólido. Ulm, Alemania. CiteSeerX 10.1.1.47.7521 . ISBN 2-86332-160-9. Consultado el 23 de agosto de 2021 .(5 páginas) [1] [2]
Bajard, Jean-Claude; Imbert, Laurent (2 de noviembre de 1999). Luk, Franklin T. (ed.). "Evaluación de funciones elementales complejas: una nueva versión de BKM" (PDF) . Procedimientos SPIE, algoritmos avanzados de procesamiento de señales, arquitecturas e implementaciones IX . Algoritmos, arquitecturas e implementaciones de procesamiento de señales avanzado IX. Sociedad de Ingenieros de Instrumentación Fotoóptica (SPIE). 3807 : 2-9. Código Bibliográfico : 1999SPIE.3807 .... 2B . doi : 10.1117 / 12.367631 . Archivado (PDF) desde el original el 9 de junio de 2020 . Consultado el 9 de junio de 2020 .(8 páginas) [3]
Imbert, Laurent; Muller, Jean-Michel; Rico, Fabien (24 de mayo de 2006) [1 de junio de 2000, septiembre de 1999]. "Algoritmo Radix-10 BKM para computación de trascendentales en computadoras de bolsillo" . Journal of VLSI Signal Processing (informe de investigación). Kluwer Academic Publishers / Institut national de recherche en informatique et en automatique (INRIA). 25 (2): 179–186. doi : 10.1023 / A: 1008127208220 . ISSN 0922-5773 . S2CID 392036 . RR-3754. INRIA-00072908. Tema 2 ISSN 0249-6399 . Archivado desde el original el 11 de julio de 2018 . Recuperado 2018-07-11 .(1 + 15 páginas) [4] [5] [6]
Didier, Laurent-Stéphane; Rico, Fabien (21 de enero de 2002). "Algoritmo BKM de alta radix con selección por redondeo" (PDF) . S2CID 17750192 . labio6.2002.009. hal-02545612. Archivado (PDF) desde el original el 23 de agosto de 2021 . Consultado el 23 de agosto de 2021 . [7] (1 + 11 páginas)
Didier, Laurent-Stéphane; Rico, Fabien (1 de diciembre de 2004). "Algoritmo High Radix BKM" . Algoritmos numéricos . Conferencia Internacional SCAN'2002. Springer Science + Business Media, LLC . 37 (1–4 [4]): 113–125. doi : 10.1023 / B: NUMA.0000049459.69390.ff . eISSN 1572-9265 . ISSN 1017-1398 . S2CID 2761452 . [8]
Muller, Jean-Michel (2006). Funciones elementales: algoritmos e implementación (2 ed.). Boston, MA, EE.UU .: Birkhäuser . ISBN 978-0-8176-4372-0. LCCN 2005048094 .
Muller, Jean-Michel (12 de diciembre de 2016). Funciones elementales: algoritmos e implementación (3 ed.). Boston, MA, EE.UU .: Birkhäuser . ISBN 978-1-4899-7981-0. ISBN 1-4899-7981-6 .

Otras lecturas

Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik (en alemán) (1 ed.). Berlín, Alemania: VEB Verlag Technik . págs. 280–282. ISBN 3-34100515-3. ISBN 978-3-34100515-6 . EAN 9783341005156 . MPN 5539165. Licencia 201.370 / 4/89 . Consultado el 1 de diciembre de 2015 .
Meggitt, John E. (29 de agosto de 1961). "Procesos de pseudo división y pseudo multiplicación" . Revista de investigación y desarrollo de IBM . Riverton, Nueva Jersey, EE. UU .: IBM Corporation (publicado en abril de 1962). 6 (2): 210-226, 287. doi : 10.1147 / rd.62.0210 . Consultado el 1 de diciembre de 2015 .
Chi Chen, Tien (julio de 1972). "Cálculo automático de exponenciales, logaritmos, razones y raíces cuadradas" . Revista de investigación y desarrollo de IBM . San José, California, Estados Unidos; Riverton, Nueva Jersey, Estados Unidos: IBM San Jose Research Laboratory ; IBM Corporation . 16 (4): 380–388. doi : 10.1147 / rd.164.0380 . Consultado el 1 de diciembre de 2015 .
Revol, Nathalie ; Yakoubsohn, Jean-Claude (1 de mayo de 2000). "Algoritmos Acelerados Shift-and-Add" (PDF) . Computación confiable . Boston, EE.UU .: Laboratoire d'Analyse Numérique et d'Optimisation (ANO) de la Universidad de Ciencias y Tecnologías de Lille ; Editores académicos de Kluwer . 6 (2): 193-205. doi : 10.1023 / A: 1009921407000 . eISSN 1573-1340 . ISSN 1385-3139 . OCLC 67306353 . S2CID 10716391 . Archivado (PDF) desde el original el 23 de agosto de 2021. Consultado el 23 de agosto de 2021 .(14 páginas) [9]

Este artículo relacionado con el análisis matemático es un fragmento . Puedes ayudar a Wikipedia expandiéndolo .