Algoritmus BKM - BKM algorithm

BKM algoritmus je shift-and-add algoritmus pro výpočet elementárních funkcí , nejprve publikoval v roce 1994 Jean-Claude Bajard, Sylvanus KLA, a Jean-Michel Muller. BKM je založen na výpočtu komplexních logaritmů ( režim L ) a exponenciálů ( režim E ) pomocí metody podobné algoritmu, který Henry Briggs používá k výpočtu logaritmů. Pomocí předpočítané tabulky logaritmů záporných mocnin dvou vypočítá algoritmus BKM elementární funkce pomocí pouze celočíselných operací sčítání, posouvání a porovnávání.

BKM je podobný CORDIC , ale používá spíše tabulku logaritmů než tabulku arktangentů . Při každé iteraci je výběr koeficientu proveden ze sady devíti komplexních čísel, 1, 0, −1, i, −i, 1+i, 1 − i, −1+i, −1 − i, spíše než pouze −1 nebo +1, jak je používá CORDIC. BKM poskytuje jednodušší způsob výpočtu některých elementárních funkcí a na rozdíl od CORDIC nepotřebuje BKM žádný faktor škálování výsledků. Míra konvergence BKM je přibližně jeden bit na iteraci, jako CORDIC, ale BKM vyžaduje více předpočítaných prvků tabulky pro stejnou přesnost, protože tabulka ukládá logaritmy komplexních operandů.

Stejně jako u jiných algoritmů ve třídě shift-and-add je BKM obzvláště vhodný pro implementaci hardwaru. Relativní výkon implementace softwarové BKM ve srovnání s jinými metodami, jako jsou polynomické nebo racionální aproximace, bude záviset na dostupnosti rychlých vícebitových posunů (tj. Barelový posunovač ) nebo hardwarové aritmetice s pohyblivou řádovou čárkou.

Reference

Další čtení

Stub ikona

Tento článek související s matematickou analýzou je útržek . Wikipedii můžete pomoci jejím rozšířením .