Perkalian: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.1 |
||
Baris 109:
Metode klasik untuk mengalikan dua bilangan {{math|''n''}} memerlukan digit perkalian {{math|''n''<sup>2</sup>}}. [[Algoritma perkalian]] telah dirancang untuk mengurangi waktu komputasi secara signifikan saat mengalikan bilangan besar. Metode berdasarkan [[Transformasi Fourier diskret#Perkalian bilangan bulat besar|transformasi Fourier diskret]] mengurangi [[kompleksitas komputasi]] menjadi {{math|''O''(''n'' log ''n'' log log ''n'')}}. Baru-baru ini, faktor {{math|log log ''n''}} telah digantikan oleh fungsi yang meningkat jauh lebih lambat meskipun masih tidak konstan (seperti yang diharapkan).<ref>{{Cite journal|last1=Harvey|first1=David|last2=van der Hoeven|first2=Joris|last3=Lecerf|first3=Grégoire|title=Even faster integer multiplication|year=2016|journal=Journal of Complexity|volume=36|pages=1–30|doi=10.1016/j.jco.2016.03.001|issn=0885-064X|arxiv=1407.3360|s2cid=205861906}}</ref>
Pada bulan Maret 2019, David Harvey dan Joris van der Hoeven mengirimkan artikel yang menyajikan algoritma perkalian bilangan bulat dengan kompleksitas diklaim oleh <math>O(n\log n).</math><ref>David Harvey, Joris Van Der Hoeven (2019). [https://hal.archives-ouvertes.fr/hal-02070778 Perkalian bilangan bulat dalam perkalian O(n log n)] {{Webarchive|url=https://web.archive.org/web/20190408180939/https://hal.archives-ouvertes.fr/hal-02070778 |date=2019-04-08 }}</ref> Algoritma juga berdasarkan transformasi Fourier cepat, diperkirakan optimal asimtotik.<ref>{{Cite web|url=https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/|title=Mathematicians Discover the Perfect Way to Multiply|last=Hartnett|first=Kevin|website=Quanta Magazine|language=en|access-date=2020-01-25}}</ref> Algoritma ini tidak dianggap berguna secara praktis, karena keuntungannya hanya muncul ketika mengalikan bilangan besar (memiliki lebih dari {{math|2<sup>1729<sup>12</sup></sup>}} bits).<ref>{{Cite web|url=https://cacm.acm.org/magazines/2020/1/241707-multiplication-hits-the-speed-limit/fulltext|title=Multiplication Hits the Speed Limit|last=Klarreich|first=Erica|website=cacm.acm.org|language=en|access-date=2020-01-25|archive-url=
==Ukuran perkalian==
| |||