Diberikan bilangan aljabar , saya tertarik untuk menemukan perkiraan ℜ ( e α ) hingga presisi yang diberikan, di mana ℜ ( ) mengacu pada bagian nyata dari bilangan kompleks.
Secara formal, saya ingin menghitung bilangan rasional sehingga | ℜ ( e α ) - r | ≤ 2 - n
diberikan oleh polinomial minimal (standar).
Seberapa cepat kita bisa menyelesaikan masalah ini?
Ketika diberikan sebagai titik mengambang, referensi berikut
R. Brent. Evaluasi multi fungsi presisi cepat yang cepat. JACM, 1976.
sepertinya memberikan jawaban.
Namun, saya tidak yakin dapat digunakan untuk nomor aljabar .
cc.complexity-theory
na.numerical-analysis
computing-over-reals
pengguna22166
sumber
sumber
Jawaban:
Seperti yang ditulis, masalahnya membutuhkan waktu , di mana m adalah panjang input (Anda sayangnya digunakan n untuk sesuatu yang lain). Memang, jika misalnya α adalah bilangan bulat positif (diberikan oleh polinomial minimal x - α ) dan n = 0 , ukuran output eksponensial dalam ukuran input. Batas ini tentu saja optimal, karena ada sejumlah cara bagaimana menghitung hasilnya dalam waktu 2 O ( m ) .2Ω(m) m n α x−α n=0 2O(m)
Biarkan saya mencoba merumuskan kembali pertanyaan itu sehingga lebih masuk akal. Masalah utama adalah bagaimana memilih representasi input dan output, serta gagasan aproksimasi, sehingga eksponensial berpeluang untuk diperhitungkan dalam waktu polinomial.
Salah satu cara disebutkan oleh Kaveh dalam komentar: batasi domain hingga interval terbatas tetap. Meskipun ini berfungsi, itu tidak perlu membatasi; khususnya, tidak ada cara yang baik bagaimana mengubah angka aljabar menjadi angka yang dibatasi sehingga eksponensial mereka ada hubungannya satu sama lain.
Pendekatan yang lebih fleksibel adalah merepresentasikan input sebagai angka titik tetap , dan output sebagai angka titik mengambang . Untuk lebih spesifik, representasi titik tetap adalah string menunjukkan ± ∑ j a j 2 j , di mana a j ∈ { 0 , 1 } , dan representasi titik mengambang adalah ± 2 e ×
Representasi titik tetap dan titik mengambang dari rasional Gaussian diad, dan perkiraan bilangan kompleks, didefinisikan dengan cara yang sama, menggunakan sepasang real. Di mana-mana di bawah ini, menunjukkan ukuran total input.n
Selama kita mematuhi batas waktu menjalankan memenuhi beberapa kondisi keteraturan ringan, dan mengabaikan faktor multiplikasi konstan, kita memiliki:
Ini membagi pertanyaan menjadi dua masalah yang tidak saling berkaitan. Batas atas yang paling dikenal pada eksponensial adalah
Untuk perkiraan akar sebenarnya , Pan dan Tsigaridas memberikan:
Untuk eksponensial rasional yang tepat, kita dapat menghindari masalah:
sumber