Tantangan ini adalah untuk menulis kode cepat yang dapat melakukan jumlah tak terbatas yang sulit secara komputasi.
Memasukkan
Sebuah n
oleh n
matriks P
dengan entri bilangan bulat yang lebih kecil dari 100
nilai absolut. Saat menguji, saya senang memberikan input ke kode Anda dalam format apa pun yang diinginkan oleh kode Anda. Standarnya adalah satu baris per baris dari matriks, dipisahkan oleh ruang dan disediakan pada input standar.
P
akan pasti positif yang menyiratkan itu akan selalu simetris. Selain itu Anda tidak benar-benar perlu tahu apa arti positif yang pasti untuk menjawab tantangan. Namun itu berarti bahwa sebenarnya akan ada jawaban untuk jumlah yang didefinisikan di bawah ini.
Namun Anda perlu tahu apa produk vektor-matriks .
Keluaran
Kode Anda harus menghitung jumlah tak terbatas:
ke dalam plus atau minus 0,0001 dari jawaban yang benar. Berikut Z
adalah himpunan bilangan bulat dan Z^n
semua mungkin vektor dengan n
elemen integer dan e
adalah konstanta matematika yang terkenal bahwa sekitar sama dengan 2,71828. Perhatikan bahwa nilai dalam eksponen hanyalah angka. Lihat di bawah untuk contoh eksplisit.
Bagaimana ini berhubungan dengan fungsi Riemann Theta?
Dalam notasi makalah ini tentang perkiraan fungsi Riemann Theta kami mencoba untuk menghitung . Masalah kami adalah kasus khusus untuk setidaknya dua alasan.
- Kami mengatur parameter awal yang disebut
z
di kertas tertaut ke 0. - Kami membuat matriks
P
sedemikian rupa sehingga ukuran minimum nilai eigen adalah1
. (Lihat di bawah untuk mengetahui bagaimana matriks dibuat.)
Contohnya
P = [[ 5., 2., 0., 0.],
[ 2., 5., 2., -2.],
[ 0., 2., 5., 0.],
[ 0., -2., 0., 5.]]
Output: 1.07551411208
Secara lebih rinci, mari kita lihat hanya satu istilah dalam jumlah untuk P. Ambil contoh hanya satu istilah dalam jumlah:
dan x^T P x = 30
. Perhatikan bahwa e^(-30)
ini tentang 10^(-14)
dan tidak mungkin menjadi penting untuk mendapatkan jawaban yang benar hingga toleransi yang diberikan. Ingat bahwa jumlah tak terbatas sebenarnya akan menggunakan setiap kemungkinan vektor dengan panjang 4 di mana elemen-elemennya adalah bilangan bulat. Saya hanya memilih satu untuk memberikan contoh eksplisit.
P = [[ 5., 2., 2., 2.],
[ 2., 5., 4., 4.],
[ 2., 4., 5., 4.],
[ 2., 4., 4., 5.]]
Output = 1.91841190706
P = [[ 6., -3., 3., -3., 3.],
[-3., 6., -5., 5., -5.],
[ 3., -5., 6., -5., 5.],
[-3., 5., -5., 6., -5.],
[ 3., -5., 5., -5., 6.]]
Output = 2.87091065342
P = [[6., -1., -3., 1., 3., -1., -3., 1., 3.],
[-1., 6., -1., -5., 1., 5., -1., -5., 1.],
[-3., -1., 6., 1., -5., -1., 5., 1., -5.],
[1., -5., 1., 6., -1., -5., 1., 5., -1.],
[3., 1., -5., -1., 6., 1., -5., -1., 5.],
[-1., 5., -1., -5., 1., 6., -1., -5., 1.],
[-3., -1., 5., 1., -5., -1., 6., 1., -5.],
[1., -5., 1., 5., -1., -5., 1., 6., -1.],
[3., 1., -5., -1., 5., 1., -5., -1., 6.]]
Output: 8.1443647932
P = [[ 7., 2., 0., 0., 6., 2., 0., 0., 6.],
[ 2., 7., 0., 0., 2., 6., 0., 0., 2.],
[ 0., 0., 7., -2., 0., 0., 6., -2., 0.],
[ 0., 0., -2., 7., 0., 0., -2., 6., 0.],
[ 6., 2., 0., 0., 7., 2., 0., 0., 6.],
[ 2., 6., 0., 0., 2., 7., 0., 0., 2.],
[ 0., 0., 6., -2., 0., 0., 7., -2., 0.],
[ 0., 0., -2., 6., 0., 0., -2., 7., 0.],
[ 6., 2., 0., 0., 6., 2., 0., 0., 7.]]
Output = 3.80639191181
Skor
Saya akan menguji kode Anda pada matriks P yang dipilih secara acak dari ukuran yang meningkat.
Skor Anda hanyalah yang terbesar di n
mana saya mendapatkan jawaban yang benar dalam waktu kurang dari 30 detik ketika rata-rata lebih dari 5 berjalan dengan matriks yang dipilih secara acak P
dari ukuran itu.
Bagaimana dengan dasi?
Jika ada seri, pemenang akan menjadi orang yang kodenya paling cepat berjalan rata-rata lebih dari 5 kali. Jika waktu itu juga sama, pemenangnya adalah jawaban pertama.
Bagaimana input acak akan dibuat?
- Misalkan M adalah matriks acak m demi n dengan m <= n dan entri yang -1 atau 1. Dengan Python / numpy
M = np.random.choice([0,1], size = (m,n))*2-1
. Dalam praktiknya saya akan mengaturm
tentangn/2
. - Biarkan P menjadi matriks identitas + M ^ T M. Dengan Python / numpy
P =np.identity(n)+np.dot(M.T,M)
. Kami sekarang dijaminP
pasti positif dan entri dalam kisaran yang sesuai.
Perhatikan bahwa ini berarti bahwa semua nilai eigen P setidaknya 1, membuat masalah berpotensi lebih mudah daripada masalah umum perkiraan fungsi Riemann Theta.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa atau pustaka yang Anda suka. Namun, untuk keperluan penilaian saya akan menjalankan kode Anda di mesin saya jadi tolong berikan instruksi yang jelas untuk bagaimana menjalankannya di Ubuntu.
Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi standar Ubuntu pada Prosesor Delapan-Core AMD 8GB 8GB AMD. Ini juga berarti saya harus dapat menjalankan kode Anda.
Memimpin jawaban
n = 47
dalam C ++ oleh Ton Hospeln = 8
dalam Python oleh Maltysen
sumber
x
dari[-1,0,2,1]
. Bisakah Anda menguraikan ini? (Petunjuk: Saya bukan guru matematika)Jawaban:
C ++
Tidak ada pendekatan yang lebih naif. Hanya evaluasi di dalam ellipsoid.
Menggunakan perpustakaan armadillo, ntl, gsl dan pthread. Instal menggunakan
Kompilasi program menggunakan sesuatu seperti:
Pada beberapa sistem Anda mungkin perlu menambahkan
-lgslcblas
setelah-lgsl
.Jalankan dengan ukuran matriks diikuti oleh elemen-elemen di STDIN:
matrix.txt
:Atau untuk mencoba ketelitian 1e-5:
infinity.cpp
:sumber
-lgslcblas
flag untuk dikompilasi. Omong-omong jawaban yang luar biasa!Python 3
12 detik n = 8 di komputer saya, ubuntu 4 core.
Benar-benar naif, tidak tahu apa yang saya lakukan.
Ini akan terus meningkatkan rentang
Z
yang digunakan sampai mendapat jawaban yang cukup baik. Saya menulis perkalian matriks saya sendiri, prolly harus menggunakan numpy.sumber