Fürer'in algoritması - Fürer's algorithm

Fürer'in algoritması , çok düşük asimptotik karmaşıklığa sahip son derece büyük tamsayılar için bir tamsayı çarpma algoritmasıdır . 2007'de Pennsylvania Eyalet Üniversitesi'nden İsviçreli matematikçi Martin Fürer tarafından, çok bantlı bir Turing makinesinde analiz edildiğinde, kendinden önceki Schönhage–Strassen algoritmasından asimptotik olarak daha hızlı bir algoritma olarak yayınlandı . Temel Polinom Cebir Alt Programları (BPAS) açık kaynak kitaplığında kullanılır.

Arka plan

Schönhage–Strassen algoritması, tamsayılı ürünleri zamanında hesaplamak için hızlı Fourier dönüşümünü (FFT) kullanır ve yazarları Arnold Schönhage ve Volker Strassen , . Fürer'in algoritması bu iki sınır arasındaki boşluğu azaltır. Bu uzunluk çarpın tamsayılar için kullanılabilir zamanında nerede log * n ise tekrarlanan logaritma . Karmaşıklık açısından ve terimleri arasındaki fark , asimptotik olarak, Fürer'in 'den büyük tamsayılar için algoritmasının avantajındadır . Ancak gerçekçi değerler için bu terimler arasındaki fark çok küçüktür. ${\displaystyle O(n\log n\cdot\log\log n)}$${\displaystyle \Omega (n\log n)}$${\görüntüleme stili n}$${\displaystyle O\sol(n\log n\\cdot 2^{O(\log ^{*}n)}\sağ)}$${\displaystyle \log \log n}$${\ Displaystyle 2^{\log ^{*}n}}$${\ Displaystyle 2^{2^{64}}}$${\görüntüleme stili n}$

Geliştirilmiş algoritmalar

2008'de De ve diğerleri , aslında aynı çalışma süresini elde etmek için karmaşık aritmetik yerine modüler aritmetiğe dayanan benzer bir algoritma verdi . uzunluğunu aşan girdiler için Schönhage-Strassen'den daha hızlı olduğu tahmin edilmektedir . ${\ Displaystyle 10^{10^{4796}}}$

2015'te Harvey, Joris van der Hoeven ve Lecerf, üsteldeki ima edilen sabiti açık hale getirmek için bir çalışma süresi elde eden yeni bir algoritma verdiler . Ayrıca algoritmalarının , Mersenne asallarının dağılımına ilişkin standart varsayımları başaran, ancak geçerliliği bu varsayımlara dayanan bir varyantı önerdiler . ${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$${\ Displaystyle O(\log ^{*}n)}$${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$

2015'te Covanov ve Thomé, Fürer'in algoritmasında aynı çalışma süresini sağlayan başka bir değişiklik sağladı. Bununla birlikte, bu algoritmanın diğer tüm uygulamaları kadar pratik değildir.

2016'da Covanov ve Thomé, Fermat asallarının genelleştirilmesine dayanan ve varsayımsal olarak . Bu, Harvey, van der Hoeven ve Lecerf'in 2015 koşullu sonucuyla eşleşir ancak farklı bir algoritma kullanır ve farklı bir varsayıma dayanır. ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$

2018 Harvey ve Hoeven der van tarafından garanti kısa kafes vektörlerin varlığına dayalı bir yaklaşım kullanılan Minkowski'nin teoremi sınırı koşulsuz karmaşıklığı kanıtlamak için . ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$

Mart 2019'da Harvey ve van der Hoeven , asimptotik olarak optimal olduğu tahmin edilen, uzun zamandır aranan bir tamsayı çarpma algoritması yayınladı . Schönhage ve Strassen, n  log( n )'nin 'mümkün olan en iyi' sonuç olduğunu öngördükleri için Harvey şunları söyledi: “...işimizin bu sorun için yolun sonu olması bekleniyor, ancak henüz nasıl kanıtlayacağımızı bilmiyoruz. bu şiddetle." ${\ Displaystyle O(n\log n)}$

Ayrıca bakınız

• galaktik algoritma
• Sayı-teorik dönüşüm

Referanslar