BKM algoritması - BKM algorithm
BKM algoritması a, kaydırma ve ekleme algoritması hesaplanması için temel fonksiyonlar ilk Jean-Claude Bajard, Sylvanus kla, Jean Michel Muller tarafından 1994 yılında yayınlanan,. BKM, Henry Briggs'in logaritmaları hesaplamak için kullandığı algoritmaya benzer bir yöntem kullanarak karmaşık logaritmaların ( L-mode ) ve üstellerin ( E-mode ) hesaplanmasına dayanır . İkinin negatif kuvvetlerinin önceden hesaplanmış bir logaritma tablosunu kullanarak, BKM algoritması yalnızca tamsayı toplama, kaydırma ve karşılaştırma işlemlerini kullanarak temel işlevleri hesaplar.
BKM, CORDIC'e benzer , ancak bir arktanjant tablosu yerine bir logaritma tablosu kullanır . Her yinelemede, 1, 0, -1, i, −i, 1+i, 1−i, -1+i, −1−i olmak üzere dokuz karmaşık sayıdan oluşan bir kümeden bir katsayı seçimi yapılır. CORDIC tarafından kullanıldığı gibi sadece -1 veya +1. BKM, bazı temel işlevleri hesaplamak için daha basit bir yöntem sağlar ve CORDIC'in aksine, BKM'nin sonuç ölçeklendirme faktörüne ihtiyacı yoktur. BKM'nin yakınsama hızı, CORDIC gibi yineleme başına yaklaşık bir bittir, ancak BKM, aynı kesinlik için daha fazla önceden hesaplanmış tablo öğesi gerektirir, çünkü tablo karmaşık işlenenlerin logaritmasını depolar.
Kaydır ve ekle sınıfındaki diğer algoritmalarda olduğu gibi, BKM özellikle donanım uygulaması için çok uygundur. Yazılım BKM uygulamasının polinom veya rasyonel yaklaşımlar gibi diğer yöntemlerle karşılaştırıldığında göreceli performansı, hızlı çok bitli kaydırmaların (yani bir varil kaydırıcı ) veya donanım kayan nokta aritmetiğinin mevcudiyetine bağlı olacaktır .
Referanslar
- Bajard, Jean-Claude; Kla, Sylvanus; Müller, Jean-Michel (Ağustos 1994). "BKM: Karmaşık temel işlevler için yeni bir donanım algoritması" (PDF) . Bilgisayarlarda IEEE İşlemleri . 43 (8): 955-963. doi : 10.1109/12.295857 . ISSN 0018-9340 . Zbl 1073.68501 . Orijinalinden 2018-11-03 tarihinde arşivlendi (PDF) . 2017-12-21 alındı .
- Skaf, Ali; Müller, Jean-Michel; Guyot, Alain (20-22 Eylül 1994). Karmaşık Üstel ve Logaritma için Çevrimiçi Donanım Uygulaması . ESSCIRC '94: Twientieth Avrupa Katı Hal Devreleri Konferansı. Ulm, Almanya CiteSeerX 10.1.1.47.7521 . ISBN'si 2-86332-160-9. 2021-08-23 alındı .(5 sayfa) [1] [2]
- Bajard, Jean-Claude; Imbert, Laurent (1999-11-02). Luk, Franklin T. (ed.). "Karmaşık Temel Fonksiyonların Değerlendirilmesi: BKM'nin Yeni Bir Versiyonu" (PDF) . SPIE Proceedings, Gelişmiş Sinyal İşleme Algoritmaları, Mimariler ve Uygulamalar IX . Gelişmiş Sinyal İşleme Algoritmaları, Mimarileri ve Uygulamaları IX. Foto-Optik Enstrümantasyon Mühendisleri Derneği (SPIE). 3807 : 2–9. Bibcode : 1999SPIE.3807....2B . doi : 10.1117/12.367631 . 2020-06-09 tarihinde orijinalinden arşivlendi (PDF) . 2020-06-09 alındı .(8 sayfa) [3]
- Imbert, Laurent; Müller, Jean-Michel; Rico, Fabien (2006-05-24) [2000-06-01, Eylül 1999]. "Cep Bilgisayarlarında Transandantallerin Hesaplanması için Radix-10 BKM Algoritması" . VLSI Sinyal İşleme Dergisi (Araştırma raporu). Kluwer Academic Publishers / Institut National de recherche en informatique et en automatique (INRIA). 25 (2): 179–186. doi : 10.1023/A:1008127208220 . ISSN 0922-5773 . S2CID 392036 . RR-3754. INRIA-00072908. Tema 2 ISSN 0249-6399 . 2018-07-11 tarihinde kaynağından arşivlendi . 2018-07-11 alındı .(1+15 sayfa) [4] [5] [6]
- Didier, Laurent-Stéphane; Rico, Fabien (2002-01-21). "Yuvarlama Yoluyla Seçimli Yüksek Tabanlı BKM algoritması" (PDF) . S2CID 17750192 . dudak6.2002.009. hal-02545612. Orijinalinden 2021-08-23 tarihinde arşivlendi (PDF) . 2021-08-23 alındı . [7] (1+11 sayfa)
- Didier, Laurent-Stéphane; Riko, Fabien (2004-12-01). "Yüksek Radix BKM Algoritması" . Sayısal Algoritmalar . SCAN'2002 Uluslararası Konferansı. Springer Bilim+İş Medyası, LLC . 37 (1–4 [4]): 113–125. doi : 10.1023/B:NUMA.0000049459.69390.ff . eISSN 1572-9265 . ISSN 1017-1398 . S2CID 2761452 . [8]
- Müller, Jean-Michel (2006). Temel Fonksiyonlar: Algoritmalar ve Uygulama (2 ed.). Boston, MA, ABD: Birkhäuser . ISBN'si 978-0-8176-4372-0. LCCN 2005048094 .
- Müller, Jean-Michel (2016-12-12). Temel Fonksiyonlar: Algoritmalar ve Uygulama (3 ed.). Boston, MA, ABD: Birkhäuser . ISBN'si 978-1-4899-7981-0. ISBN 1-4899-7981-6 .
daha fazla okuma
- Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik (Almanca) (1 ed.). Berlin, Almanya: VEB Verlag Technik . s. 280–282. ISBN'si 334100515-3. ISBN 978-3-34100515-6 . EAN 9783341005156 . MPN 5539165. Lisans 201.370/4/89 . 2015-12-01 alındı .
- Meggitt, John E. (1961-08-29). "Sözde Bölme ve Sözde Çarpma İşlemleri" . IBM Araştırma ve Geliştirme Dergisi . Riverton, New Jersey, ABD: IBM Corporation (Nisan 1962'de yayınlandı). 6 (2): 210–226, 287. doi : 10.1147/rd.62.0210 . 2015-12-01 alındı .
- Chi Chen, Tien (Temmuz 1972). "Üssellerin, logaritmaların, oranların ve kareköklerin otomatik hesaplanması" . IBM Araştırma ve Geliştirme Dergisi . San Jose, Kaliforniya, ABD; Riverton, New Jersey, ABD: IBM San Jose Araştırma Laboratuvarı ; IBM Şirketi . 16 (4): 380–388. doi : 10.1147/rd.164.0380 . 2015-12-01 alındı .
- Revol, Nathalie ; Yakoubsohn, Jean-Claude (2000-05-01). "Hızlandırılmış Kaydırma ve Ekleme algoritmaları" (PDF) . Güvenilir Bilgi İşlem . Boston, ABD: Laboratoire d'Analyse Numerique et d'Optimisation (ANO) de l' Université des Sciences et Technologies de Lille ; Kluwer Akademik Yayıncılar . 6 (2): 193–205. doi : 10.1023/A:1009921407000 . eISSN 1573-1340 . ISSN 1385-3139 . OCLC 67306353 . S2CID 10716391 . Orijinalinden 2021-08-23 tarihinde arşivlendi (PDF) . 2021-08-23 alındı .(14 sayfa) [9]