Algoritmus BKM - BKM algorithm

The Algoritmus BKM je algoritmus shift-and-add pro výpočet základní funkce, poprvé publikovali v roce 1994 Jean-Claude Bajard, Sylvanus Kla a Jean-Michel Muller. BKM je založen na výpočetním komplexu logaritmy (Režim L) a exponenciály (E-režim) pomocí metody podobné algoritmu Henry Briggs slouží k výpočtu logaritmů. Použitím předpočítané tabulky logaritmů záporných sil dvou vypočítá algoritmus BKM elementární funkce pouze pomocí operací přidání, posunutí a porovnání celého čísla.

BKM je podobný CORDIC, ale používá tabulku logaritmy spíše než tabulku arktangenty. Při každé iteraci se volí koeficient 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šší metodu výpočtu některých základních funkcí a na rozdíl od CORDIC nepotřebuje BKM žádný faktor měřítka 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 se 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 zvláště vhodný pro implementaci hardwaru. Relativní výkon implementace softwarového BKM ve srovnání s jinými metodami, jako je polynomiální nebo Racionální aproximace budou záviset na dostupnosti rychlých vícebitových posunů (tj. a řadicí páka ) nebo hardware plovoucí bod aritmetický.

Reference

  • Bajard, Jean-Claude; Kla, Sylvanus; Muller, Jean-Michel (srpen 1994). „BKM: Nový hardwarový algoritmus pro složité základní funkce“ (PDF). Transakce IEEE na počítačích. 43 (8): 955–963. doi:10.1109/12.295857. ISSN  0018-9340. Archivováno (PDF) od originálu 21. 12. 2017. Citováno 2017-12-21.
  • Bajard, Jean-Claude; Imbert, Laurent (11.02.1999). Luk, Franklin T. (ed.). „Hodnocení složitých základních funkcí: nová verze BKM“ (PDF). SPIE řízení, pokročilé algoritmy zpracování signálu, architektury a implementace IX. Pokročilé algoritmy, architektury a implementace zpracování signálu IX. Společnost techniků fotooptické instrumentace (SPIE). 3807: 2–9. Bibcode:1999SPIE.3807 .... 2B. doi:10.1117/12.367631. Citováno 2020-06-09. [1]
  • Imbert, Laurent; Muller, Jean-Michel; Rico, Fabien (2006-05-24) [2000-06-01, září 1999]. „Algoritmus Radix-10 BKM pro výpočet transcendentálů na kapesních počítačích“. Journal of VLSI Signal Processing (Zpráva o výzkumu). Kluwer Academic Publishers / Institucionální národní odborný časopis informativní a automatický (INRIA). 25 (2): 179–186. doi:10.1023 / A: 1008127208220. ISSN  0922-5773. RR-3754. INRIA-00072908. Téma 2. Archivováno od originálu 11. 7. 2018. Citováno 2018-07-11. [2] [3]
  • Muller, Jean-Michel (2006). Základní funkce: Algoritmy a implementace (2. vyd.). Boston, MA, USA: Birkhäuser. ISBN  978-0-8176-4372-0. LCCN  2005048094.
  • Muller, Jean-Michel (12. 12. 2016). Základní funkce: Algoritmy a implementace (3. vyd.). Boston, MA, USA: Birkhäuser. ISBN  978-1-4899-7981-0.

Další čtení

externí odkazy