Apa algoritma yang paling efisien untuk Divisibilitas?

12

$a$ $b$ $a$ $b$ $a$ $b$ $O(m\log m\log\log m)$ $m$ $\max\{a,b\}$ $\Omega(m\log m\log\log m)$ batas bawah dari masalah ini?

Terima kasih dan salam, dan maaf jika ini pertanyaan naif.

time-complexity lower-bounds nt.number-theory primes Leandro Zatesko
sumber

AFAIK tidak ada batas bawah non-sepele yang diketahui. Saya percaya penggandaan dan pembagian diketahui memiliki kompleksitas yang pada dasarnya sama (meskipun mungkin bisa sampai ke faktor log log?) Melalui metode Newton, dan karena tidak ada batas bawah nonlinier yang diketahui pada perkalian maka saya pikir ada batas bawah bentuk Anda menyatakan akan menjadi hasil utama.

Steven Stadnicki

(Sebenarnya, melihatnya sekarang saya pikir faktor log log hilang karena saat Anda melakukan jumlah perkalian yang tidak konstan, mereka tidak semuanya sama panjangnya, sehingga faktor-faktor superlinear dapat diserap dengan cara yang sama seperti itu, misal, masih linier dalam meskipun memiliki sejumlah faktor 'linear' yang tidak konstan.)

\sum_{k = 1}^{⌊ \lg n ⌋} \frac{n}{2^{k}}

$\sum_{k=1}^{\lfloor\lg n\rfloor} \frac{n}{2^k}$

n

$n$

Steven Stadnicki

4

Membagi-bagi komentar saya menjadi sebuah jawaban: karena keterbagian (secara sepele) dapat direduksi menjadi divisi, dan karena pembagian (dapat direduksi) direduksi menjadi multiplikasi melalui pendekatan seperti metode Newton, maka masalah Anda harus memiliki kompleksitas waktu yang sama dengan multiplikasi integer. AFAIK, tidak ada batas yang diketahui lebih rendah untuk perkalian lebih baik daripada yang linier sepele, jadi hal yang sama harus berlaku untuk masalah Anda - dan khususnya, karena perkalian diketahui memiliki (pada dasarnya) algoritma, harapan Anda untuk batas bawah hampir pasti sia-sia. $O(n\log n\log^* n)$ $n\log n\log\log n$

Alasan pembagian itu justru mengurangi kerumitan menjadi multiplikasi - seperti yang saya pahami - adalah bahwa metode Newton akan melakukan serangkaian perkalian dengan ukuran eskalasi yang berbeda; ini berarti bahwa jika ada algoritma untuk perkalian dengan kompleksitas maka kompleksitas dari algoritma pembagian menggunakan algoritma perkalian ini sebagai langkah perantara akan berada di sepanjang garis - dan untuk semua kelas kompleksitas yang dibahas ini hanya . $\Theta(f(n))$ $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ $\Theta(f(n))$

Steven Stadnicki
sumber

2

Nitpick: Saya tidak melihat bagaimana Anda mendapatkan batasan yang lebih rendah dari jenis penalaran ini, bahkan jika kita berasumsi tidak ada algoritma yang lebih baik untuk perkalian daripada yang terbaik saat ini. Pengurangan Anda menyiratkan bahwa pembagian tidak lebih sulit daripada perkalian. Tetapi masih ada kemungkinan bahwa pembagian dapat lebih mudah daripada pembagian dan lebih mudah daripada multiplikasi, karena pembagian hanya memerlukan jawaban ya / tidak sebagai ganti angka. (Setidaknya, pengurangan yang Anda sebutkan tampaknya tidak mengesampingkan hal itu.)

DW

2

@DW Setuju, dan itu poin yang bagus; tapi aku tidak berusaha untuk mendapatkan batas bawah. Sebaliknya, intinya adalah bahwa setiap batas bawah pada keterpisahan menyiratkan batas bawah terkait pada perkalian, dan karena tidak ada batas yang diketahui di luar batas linier sepele, maka mendapatkan batas bawah yang dapat dibedakan lebih baik dari linier (yang merupakan bagian dari apa OP meminta) tidak mungkin.

Steven Stadnicki

@ WD Saya tidak akan sepenuhnya terkejut mengetahui batas atas linier pada keterbagian, dan seperti yang Anda katakan bahwa tidak secara khusus menyiratkan apa pun tentang batas atas pada perkalian, tetapi tidak ada hasil khusus ke arah itu AFAIK.

Steven Stadnicki

-2

Saya pikir ada jenis retas Veda untuk beberapa angka yang berakhir dengan 3,7 dll. Atau pembagi basis 2 ^ n ...

Tetapi secara umum, algoritma pembagian tercepat tampaknya menjadi norma.

Yang terbaik yang saya tahu tanpa melihat adalah Algoritma D dari metode seminar Knuth ... Namun tidak pernah memeriksa kebenarannya. Ini berjalan di lebih atau kurang O (mn-n ^ 2) di mana m dan n adalah dividen dan pembagi ... tanpa memperhitungkan kompleksitas multiplikasi ...

Namun batas bawah bisa jadi surpringly karena pertanyaan Anda hanya menyangkut masalah keputusan.

Phil
sumber

Apa algoritma yang paling efisien untuk Divisibilitas?

Jawaban: