algoritmo BKM

Algoritmo de cambio y suma

El algoritmo BKM es un algoritmo de desplazamiento 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 utilizar una tabla precalculada de logaritmos de potencias negativas de dos, el algoritmo BKM calcula funciones elementales utilizando únicamente operaciones de suma, desplazamiento y comparación de enteros.

BKM es similar a CORDIC , pero utiliza una tabla de logaritmos en lugar de una tabla de arcotangentes . En cada iteración, se elige un coeficiente a partir 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 sencillo 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 de desplazamiento y suma, 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 las aproximaciones polinómicas o racionales , dependerá de la disponibilidad de desplazamientos rápidos de varios bits (es decir, un desplazador de barril ) o aritmética de punto flotante de hardware.

Descripción general

Para resolver la ecuación

${\displaystyle \ln(x)=y}$

el algoritmo BKM aprovecha una propiedad básica de los logaritmos

${\displaystyle \ln(ab)=\ln(a)+\ln(b)}$

Usando la notación Pi , esta identidad se generaliza a

${\displaystyle \ln \left(\prod _{k=0}^{n}a_{k}\right)=\sum _{k=0}^{n}\ln(a_{k})}$

Debido a que cualquier número puede representarse mediante un producto, esto nos permite elegir cualquier conjunto de valores que se multiplican para dar el valor con el que comenzamos. En los sistemas informáticos, es mucho más rápido multiplicar y dividir por múltiplos de 2, pero como no todos los números son múltiplos de 2, usar es una mejor opción que una elección más simple de . Dado que queremos comenzar con cambios grandes y ser más precisos a medida que aumentamos, podemos usar más específicamente , permitiendo que el producto se acerque a cualquier valor entre 1 y ~4,768, dependiendo de qué subconjunto usemos en el producto final. En este punto, la ecuación anterior se ve así: ${\displaystyle a_{k}}$ ${\displaystyle a_{k}=1+2^{m}}$ ${\displaystyle a_{k}=2^{m}}$ ${\displaystyle k}$ ${\displaystyle a_{k}=1+2^{-k}}$ ${\displaystyle a_{k}}$

${\displaystyle \ln \left(\prod _{k\in K\subset \mathbb {Z} _{0}^{+}}1+2^{-k}\right)=\sum _{k\in K\subset \mathbb {Z} _{0}^{+}}\ln(1+2^{-k})}$

Esta elección reduce la complejidad computacional del producto desde la multiplicación repetida hasta la simple suma y el desplazamiento de bits según la implementación. Finalmente, al almacenar los valores en una tabla, calcular la solución también es una simple cuestión de suma. Iterativamente, esto nos da dos secuencias separadas. Una secuencia se acerca al valor de entrada mientras que la otra se acerca al valor de salida : ${\displaystyle a_{k}}$ ${\displaystyle \ln(1+2^{-k})}$ ${\displaystyle x}$ ${\displaystyle \ln(x)=y}$

$${\displaystyle x_{k}={\begin{cases}1&{\text{if }}k=0\\x_{k-1}\cdot (1+2^{-k})&{\text{if }}x_{k}{\text{ would be}}\leq x\\x_{k-1}&{\text{otherwise}}\end{cases}}}$$

Dada esta definición recursiva y debido a que es estrictamente creciente, se puede demostrar por inducción y convergencia que ${\displaystyle x_{k}}$

${\displaystyle \lim _{k\to \infty }x_{k}=x}$

para cualquier . Para calcular el resultado, primero creamos la tabla de referencia. ${\displaystyle 1\leq x\lesssim 4.768}$

${\displaystyle A_{k}=\ln(1+2^{-k})}$

Luego, la salida se calcula iterativamente según la definición.

$${\displaystyle y_{k}={\begin{cases}0&{\text{if }}k=0\\y_{k-1}+A_{k}&{\text{if }}x_{k}{\text{ would be}}\leq x\\y_{k-1}&{\text{otherwise}}\end{cases}}}$$

${\displaystyle \lim _{k\to \infty }y_{k}=y}$

para cualquier . ${\displaystyle 0\leq y\lesssim 1.562}$

Debido a que el algoritmo anterior calcula tanto la entrada como la salida simultáneamente, es posible modificarlo ligeramente para que sea el valor conocido y el valor que queremos calcular, calculando así el exponencial en lugar del logaritmo. Dado que x se convierte en una incógnita en este caso, el condicional cambia de ${\displaystyle y}$ ${\displaystyle x}$

${\displaystyle \dots {\text{if }}x_{k}{\text{ would be}}\leq x}$

a

${\displaystyle \dots {\text{if }}y_{k}{\text{ would be}}\leq y}$

función logaritmo

Para calcular la función logaritmo (modo L), el algoritmo en cada iteración prueba si . Si es así, calcula y . Después de las iteraciones se conoce el valor de la función con un error de . ${\displaystyle x_{n}\cdot (1+2^{-n})\leq x}$ ${\displaystyle x_{n+1}}$ ${\displaystyle y_{n+1}}$ ${\displaystyle N}$ ${\displaystyle \Delta \ln(x)\leq 2^{-N}}$

Programa de ejemplo para logaritmo natural en C++ (ver A_etabla):

 double log_e ( const double Argumento , const int Bits = 53 ) // 1 <= Argumento <= 4.768462058 { double x = 1.0 , y = 0.0 , s = 1.0 ;                      for ( int k = 0 ; k < Bits ; k ++ ) { doble const z = x + x * s ; si ( z <= Argumento ) { x = z ; y += A_e [ k ]; } s *= 0,5 ; } devolver y ; }                                   

Los logaritmos para bases distintas de e se pueden calcular con un esfuerzo similar.

Programa de ejemplo para logaritmo binario en C++ (ver A_2tabla):

 double log_2 ( const double Argumento , const int Bits = 53 ) // 1 <= Argumento <= 4.768462058 { double x = 1.0 , y = 0.0 , s = 1.0 ;                      for ( int k = 0 ; k < Bits ; k ++ ) { doble const z = x + x * s ; si ( z <= Argumento ) { x = z ; y += A_2 [ k ]; } s *= 0,5 ; } devolver y ; }                                   

El rango de argumentos permitido es el mismo para ambos ejemplos (1 ≤  Argument ≤ 4,768462058…). En el caso del logaritmo de base 2, el exponente se puede dividir por adelantado (para obtener la parte entera) para que el algoritmo se pueda aplicar al resto (entre 1 y 2). Dado que el argumento es menor que 2,384231…, la iteración de k puede comenzar con 1. Trabajando en cualquier base, la multiplicación por s se puede reemplazar con una modificación directa del exponente de coma flotante, restándole 1 durante cada iteración. Esto da como resultado que el algoritmo utilice solo la suma y no la multiplicación.

Funcion exponencial

Para calcular la función exponencial (modo E), el algoritmo en cada iteración prueba si . Si es así, calcula y . Después de las iteraciones se conoce el valor de la función con un error de . ${\displaystyle y_{n}+\ln(1+2^{-n})\leq y}$ ${\displaystyle x_{n+1}}$ ${\displaystyle y_{n+1}}$ ${\displaystyle N}$ ${\displaystyle \Delta \exp(x)\leq 2^{-N}}$

Programa de ejemplo en C++ (ver A_etabla):

 double exp ( const double Argumento , const int Bits = 54 ) // 0 <= Argumento <= 1.5620238332 { double x = 1.0 , y = 0.0 , s = 1.0 ;                     for ( int k = 0 ; k < Bits ; k ++ ) { doble const z = y + A_e [ k ]; si ( z <= Argumento ) { y = z ; x = x + x * s ; } s *= 0,5 ; } devolver x ; }                                     

Tablas para ejemplos

Notas

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; Müller, Jean-Michel; Guyot, Alain (20 a 22 de septiembre de 1994). Implementación de Hardware en Línea para Exponenciales y Logaritmos Complejos. ESSCIRC '94: Vigésima Conferencia Europea sobre 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 de SPIE, algoritmos avanzados de procesamiento de señales, arquitecturas e implementaciones IX . Algoritmos, arquitecturas e implementaciones avanzadas de procesamiento de señales IX. 3807 . Sociedad de Ingenieros de Instrumentación Fotoóptica (SPIE): 2–9. Código Bib : 1999SPIE.3807....2B. doi :10.1117/12.367631. S2CID  121001818. Archivado (PDF) desde el original el 9 de junio de 2020 . Consultado el 9 de junio de 2020 .(8 páginas) [3]
• Imbert, Laurent; Müller, Jean-Michel; Rico, Fabien (24 de mayo de 2006) [1 de junio de 2000, septiembre de 1999]. "Algoritmo Radix-10 BKM para calcular trascendentales en computadoras de bolsillo". Journal of VLSI Signal Processing (informe de investigación). 25 (2). Kluwer Academic Publishers / Institut national de recherche en informatique et en automatique (INRIA): 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 . Consultado el 11 de julio de 2018 .(1+15 páginas) [4][5][6]
• Didier, Laurent-Stéphane; Rico, Fabián (21 de enero de 2002). "Algoritmo BKM de base alta con selección por redondeo" (PDF) . S2CID  17750192. lip6.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, Fabián (1 de diciembre de 2004). "Algoritmo BKM de alta base". Algoritmos Numéricos . Conferencia Internacional SCAN'2002. 37 (1–4 [4]). Springer Science + Business Media, LLC : 113–125. Código Bib : 2004NuAlg..37..113D. doi :10.1023/B:NUMA.0000049459.69390.ff. eISSN  1572-9265. ISSN  1017-1398. S2CID  2761452.[8]
• Müller, Jean-Michel (2006). Funciones elementales: algoritmos e implementación (2 ed.). Boston, MA, Estados Unidos: Birkhäuser . ISBN 978-0-8176-4372-0. LCCN  2005048094.
• Müller, 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, Norberto (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 pseudodivisión y pseudomultiplicación". Revista IBM de investigación y desarrollo . 6 (2). Riverton, Nueva Jersey, EE. UU.: IBM Corporation (publicado en abril de 1962): 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 IBM de investigación y desarrollo . 16 (4). San José, California, Estados Unidos; Riverton, Nueva Jersey, EE.UU.: Laboratorio de Investigación IBM San José ; Corporación IBM : 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 de cambio y adición" (PDF) . Computación confiable . 6 (2). Boston, EE.UU.: Laboratoire d'Analyse Numérique et d'Optimisation (ANO) de la Université des Sciences et Technologies de Lille ; Editores académicos de Kluwer : 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]