Apa algoritma tercepat untuk perkalian dua angka n-digit?

21

Saya ingin tahu algoritma mana yang tercepat untuk perkalian dua angka n-digit? Kompleksitas ruang bisa santai di sini!

Andy
sumber
1
Apakah Anda tertarik pada pertanyaan teoretis atau pada pertanyaan praktis?
Yuval Filmus
Keduanya, tetapi lebih condong ke arah yang praktis!
Andy
1
Untuk pertanyaan praktis, saya sarankan menggunakan GMP. Jika Anda penasaran dengan apa yang mereka gunakan, lihat dokumentasi atau kode sumbernya.
Yuval Filmus
Tidak ada yang tahu. Kami belum menemukannya.
JeffE

Jawaban:

22

Sampai sekarang algoritma Fürer oleh Martin Fürer memiliki kompleksitas waktu yang menggunakan transformasi Fourier atas bilangan kompleks. Algoritma-nya sebenarnya didasarkan pada algoritma Schönhage dan Strassen yang memiliki kompleksitas waktu Θ ( n log ( n ) log ( log ( n ) ) )nlog(n)2Θ(lHaig(n))Θ(nlog(n)log(log(n)))

Algoritma lain yang lebih cepat daripada algoritma Multiplikasi Sekolah Tingkat adalah perkalian Karatsuba yang memiliki kompleksitas waktu HAI(nlog23)HAI(n1.585) dan algoritma Toom 3 yang memiliki kompleksitas waktu dari Θ(n1.465)

Perhatikan bahwa ini adalah algoritma cepat. Menemukan algoritma tercepat untuk perkalian adalah masalah terbuka dalam Ilmu Komputer.

Referensi :

  1. Algoritma Fürer
  2. Multiplikasi berbasis FFT dalam jumlah besar
  3. Transformasi Fourier Cepat
  4. Perbanyakan Toom – Cook
  5. Algoritma Schönhage – Strassen
  6. Algoritma Karatsuba
avi
sumber
Perhatikan makalah terbaru oleh D. Harvey dan J. van der Hoeven (Maret 2019) yang menggambarkan algoritme dengan kompleksitas . HAI(ndalamn)
Hardmath
9

Perhatikan bahwa algoritma FFT yang dicantumkan oleh avi menambahkan konstanta besar, menjadikannya tidak praktis untuk angka yang kurang dari ribuan + bit.

Selain daftar itu, ada beberapa algoritma menarik lainnya, dan pertanyaan terbuka:

  • Penggandaan waktu linier pada model RAM (dengan prakomputasi)
  • Perkalian dengan sebuah Konstanta adalah Sublinear ( PDF ) - ini berarti jumlah tambahan sublinear yang didapat untuk totalkompleksitas. Ini pada dasarnya setara dengan perkalian panjang (di mana Anda menggeser / menambah berdasarkan angkas di angka yang lebih rendah), yaitu, tetapi denganPercepatan.1O(n2)O(logn)HAI(n2logn)1HAI(n2)HAI(logn)
  • Sistem angka residu dan representasi angka lainnya; perkalian adalah waktu yang hampir linier. Kelemahannya adalah, perkaliannya adalah modular dan {deteksi meluap, paritas, perbandingan magnitudo} semuanya sekeras atau hampir sekeras mengubah angka kembali ke representasi biner atau serupa dan melakukan perbandingan tradisional; konversi ini setidaknya sama buruknya dengan perkalian tradisional (saat ini, AFAIK).
    • Representasi lain:
      • [ Representasi logaritmik ]: multiplikasi adalah penambahan representasi logaritmik. Contoh:
        16×32=2log216+log232=24+5=29
        • Kelemahannya adalah konversi ke dan dari representasi logaritmik bisa sekeras penggandaan atau lebih sulit, representasi juga bisa fraksional / irasional / perkiraan dll. Operasi lain (tambahan?) Cenderung lebih sulit.
      • Representasi kanonik : mewakili angka sebagai eksponen faktorisasi utama. Perkalian adalah penambahan eksponen. Contoh:
        36×48=3251×223141=22324151
      • Kelemahannya adalah, membutuhkan faktor, atau faktorisasi, masalah yang jauh lebih sulit daripada perkalian. Operasi lain seperti penambahan kemungkinan sangat sulit.
Realz Slaw
sumber
1
Saya percaya residu / pendekatan Teorema berbasis Sisa Cina dengan moduli yang tepat dapat menyebabkan percepatan atas perkalian tradisional bahkan dengan konversi kembali; pada titik tertentu ini ada di bab 4 TAOCP, setidaknya sebagai catatan kaki. (Masih belum mendekati metode berbasis FFT, tapi ini adalah catatan sejarah yang menarik)
Steven Stadnicki
@ StevenStadnicki oh keren, saya perlu melihat itu kalau begitu; apakah Anda tahu kompleksitasnya?
Realz Slaw