Algoritmo BKM

El algoritmo BKM es un algoritmo de suma y desplazamiento para calcular funciones elementales , publicado por primera vez en 1994 por Jean-Claude Bajard, Sylvanus Kla y Jean-Michel Muller . BKM se basa en el cálculo de logaritmos complejos ( modo L ) y exponenciales ( modo E ) mediante 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 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 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 usa CORDIC. BKM proporciona un método más sencillo para calcular algunas funciones elementales y, a diferencia de CORDIC, no necesita un factor de escala para los resultados. La tasa de convergencia de BKM es aproximadamente de 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 otros algoritmos de la clase de desplazamiento y suma, BKM es particularmente adecuado para la implementación en hardware. El rendimiento relativo de la implementación de BKM por software en comparación con otros métodos, como las aproximaciones polinómicas o racionales, dependerá de la disponibilidad de desplazamientos multibit rápidos (es decir, un desplazador de barril ) o aritmética de punto flotante por hardware.

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)}$

Utilizando 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})}$

Dado que cualquier número puede representarse mediante un producto, esto nos permite elegir cualquier conjunto de valores.${\displaystyle a_{k}}$que se multiplican para dar el valor con el que empezamos. 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${\displaystyle a_{k}=1+2^{m}}$es una mejor opción que una elección más simple de${\displaystyle a_{k}=2^{m}}$. Dado que queremos comenzar con grandes cambios y obtener mayor precisión${\displaystyle k}$aumenta, podemos usar más específicamente${\displaystyle a_{k}=1+2^{-k}}$, permitiendo que el producto se aproxime a cualquier valor entre 1 y ~4,768, dependiendo de qué subconjunto de${\displaystyle a_{k}}$lo utilizamos en el producto final. En este punto, la ecuación anterior se ve así:

${\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 de${\displaystyle a_{k}}$reduce la complejidad computacional del producto de multiplicación repetida a simple suma y desplazamiento de bits dependiendo de la implementación. Finalmente, al almacenar los valores${\displaystyle \ln(1+2^{-k})}$En una tabla, calcular la solución también es una simple suma. De forma iterativa, esto nos da dos secuencias separadas. Una secuencia se aproxima al valor de entrada.${\displaystyle x}$mientras que el otro se aproxima al valor de salida${\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 porque${\displaystyle x_{k}}$es estrictamente creciente, se puede demostrar por inducción y convergencia que

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

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

${\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}}}$$ Las condiciones en esta iteración son las mismas que las condiciones para la entrada. De manera similar a la entrada, esta secuencia también es estrictamente creciente, por lo que se puede demostrar que

${\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${\displaystyle y}$es el valor conocido y${\displaystyle x}$es el valor que queremos calcular, calculando así la exponencial en lugar del logaritmo. Dado que x se convierte en una incógnita en este caso, la condición cambia de

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

a

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

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

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

double log_e ( const double argument , const int bits = 53 ) // 1 <= argument <= 4.768462058 { double x = 1.0 , y = 0.0 , s = 1.0 ;for ( int k = 0 ; k < bits ; k ++ ) { double const z = x + x * s ; if ( z <= argument ) { x = z ; y += A_e [ k ]; } s *= 0.5 ; } return y ; }

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

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

double log_2 ( const double argument , const int bits = 53 ) // 1 <= argument <= 4.768462058 { double x = 1.0 , y = 0.0 , s = 1.0 ;for ( int k = 0 ; k < bits ; k ++ ) { double const z = x + x * s ; if ( z <= argument ) { x = z ; y += A_2 [ k ]; } s *= 0.5 ; } return y ; }

El rango de argumentos permitido es el mismo para ambos ejemplos (1  ≤ ≤ 4,768462058...). En el caso del logaritmo en base 2, el exponente se puede separar de antemano (para obtener la parte entera) de modo que el algoritmo se pueda aplicar al resto (entre 1 y 2). Como el argumento es menor que 2,384231..., la iteración de k puede comenzar con 1. Trabajando en cualquiera de las bases, la multiplicación por s se puede reemplazar con la modificación directa del exponente de punto flotante, restándole 1 en cada iteración. Esto hace que el algoritmo utilice solo suma y no multiplicación. Argument  

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

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

double exp ( const double argument , const int bits = 54 ) // 0 <= argument <= 1.5620238332 { double x = 1.0 , y = 0.0 , s = 1.0 ;for ( int k = 0 ; k < bits ; k ++ ) { double const z = y + A_e [ k ]; if ( z <= argument ) { y = z ; x = x + x * s ; } s *= 0.5 ; } return x ; }

• Bajard, Jean-Claude; Kla, Sylvanus; Muller, Jean-Michel (agosto de 1994). "BKM: Un nuevo algoritmo de hardware para funciones elementales complejas" (PDF) . IEEE Transactions on Computers . 43 (8): 955– 963. doi : 10.1109/12.295857 . ISSN 0018-9340 . Zbl 1073.68501 . Archivado (PDF) del original el 3 de noviembre de 2018. Recuperado el 21 de diciembre de 2017 .  
• Skaf, Ali; Muller, Jean-Michel; Guyot, Alain (20–22 de septiembre de 1994). Implementación de hardware en línea para exponenciales y logaritmos complejos . ESSCIRC '94: Vigésima Conferencia Europea 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)
• Bajard, Jean-Claude; Imbert, Laurent (1999-11-02). "Evaluación de funciones elementales complejas: una nueva versión de BKM" (PDF) . En Luk, Franklin T. (ed.). Algoritmos, arquitecturas e implementaciones avanzadas de procesamiento de señales IX . Actas de SPIE. Vol.  3807. Sociedad de Ingenieros de Instrumentación Fotoóptica (SPIE). pp. 2– 9. Bibcode : 1999SPIE.3807....2B . doi : 10.1117/12.367631 . S2CID 121001818. Archivado (PDF) del original el 2020-06-09 . Recuperado el 2020-06-09 .  (8 páginas)
• 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 del original el 11/07/2018 . Consultado el 11/07/2018 .   (1+15 páginas)
• Didier, Laurent-Stéphane; Rico, Fabien (2002-01-21). "Algoritmo BKM de base alta con selección por redondeo" (PDF) . S2CID 17750192. lip6.2002.009. hal-02545612. Archivado (PDF) del original el 23-08-2021 . Recuperado el 23-08-2021 . (1+11 páginas)
• Didier, Laurent-Stéphane; Rico, Fabien (2004-12-01). "Algoritmo BKM de alta base" . Algoritmos numéricos . Conferencia internacional SCAN'2002. 37 (1–4 [4]). Springer Science+Business Media, LLC : 113–125 . Bibcode : 2004NuAlg..37..113D . doi : 10.1023/B:NUMA.0000049459.69390.ff . eISSN 1572-9265 . ISSN 1017-1398 . S2CID 2761452 .   
• 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-0ISBN​ 1-4899-7981-6.

• 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-3ISBN​ 978-3-34100515-6EAN 9783341005156. MPN 5539165. Licencia 201.370/4/89 . Consultado el 1 de diciembre de 2015 . 
• Meggitt, John E. (1961-08-29). "Procesos de pseudodivisión y pseudomultiplicación" . IBM Journal of Research and Development . 6 (2). Riverton, Nueva Jersey, EE. UU.: IBM Corporation (publicado en abril de 1962): 210–226 , 287. doi : 10.1147/rd.62.0210 . Recuperado el 1 de diciembre de 2015 .
• Chi Chen, Tien (julio de 1972). "Cálculo automático de exponenciales, logaritmos, razones y raíces cuadradas" . IBM Journal of Research and Development . 16 (4). San José, California, EE. UU.; Riverton, Nueva Jersey, EE. UU.: IBM San Jose Research Laboratory ; IBM Corporation : 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)