Algorisme BKM

L'algorisme BKM és un algorisme shift-and-add per a la computació de funcions elementals, publicat per primera vegada el 1994 per J.C. Bajard, S. Kla, i J.M. Muller. BKM es basa en el càlcul d'algoritmes complex i exponencials utilitzant un mètode similar a l'algoritme CORDIC de Henry Briggs utilitzat per calcular logaritmes. Mitjançant l'ús d'una taula precalculada de logaritmes de les potències negatives de dos, l'algorisme BKM calcula utilitzant només funcions elementals per a enters, suma, desplaçament i comparació.

BKM és similar a CORDIC, però utilitza una taula de logaritmes en lloc d'una taula d'arctangents. A cada iteració, es fa una elecció de coeficient a partir d'un conjunt de nou nombres complexos, 1, 0, -1, i,-i, 1 + i, 1-i, -1 + i,-1-i, en lloc de només -1 o +1, com s'usa per CORDIC. BKM proporciona un mètode senzill de calcular algunes funcions elementals, a diferència de CORDIC, BKM no necessita aplicar un factor d'escala al resultat. La taxa de convergència de BKM és d'aproximadament un bit per iteració, com CORDIC, però BKM requereix més elements a la taula precalculada per aconseguir la mateixa precisió logaritmes d'operands complexos.

Igual que amb altres algoritmes a la classe de desplaçament i suma, BKM és particularment adequat per a la implementació en maquinari més que en programari. El rendiment relatiu en programari de l'algorisme BKM en comparació amb altres mètodes, com ara s aproximacions basades en polinomis o funcions racionals depèn de la disponibilitat de registres per a efectuar manipulacions bit a bit (és a dir, un desplaçador) o maquinari amb aritmètica de coma flotant.

Referències

• J.C. Bajard, S. Kla, and J.M. Muller. BKM: A new hardware algorithm for complex elementary functions. IEEE Transactions on Computers, 43(8): 955-963, August 1994, (anglès)
• J.M. Muller, Elementary Functions: Algorithms and Implementation, 2nd Ed. Birkhauser 2006, (anglès)