Ini adalah tantangan lain tentang angka-angka Fibonacci.
Tujuannya adalah untuk menghitung angka Fibonacii ke- 20'000'000 secepat mungkin. Output desimal sekitar 4 MiB besar; dimulai dengan:
28543982899108793710435526490684533031144309848579
Jumlah MD5 dari output adalah
fa831ff5dd57a830792d8ded4c24c2cb
Anda harus mengirimkan program yang menghitung angka saat berjalan dan menempatkan hasilnya stdout
. Program tercepat, seperti yang diukur pada mesin saya sendiri, menang.
Berikut ini beberapa aturan tambahan:
- Anda harus mengirimkan kode sumber dan runnable biner di Linux x64
- Kode sumber harus lebih pendek dari 1 MiB, dalam hal perakitan juga dapat diterima jika hanya biner yang kecil.
- Anda tidak harus memasukkan nomor yang akan dihitung dalam biner Anda, bahkan dengan cara yang disamarkan. Angka harus dihitung pada saat runtime.
- Komputer saya memiliki dua inti; Anda diizinkan menggunakan paralelisme
Saya mengambil implementasi kecil dari Internet yang berjalan sekitar 4,5 detik. Seharusnya tidak terlalu sulit untuk mengalahkan ini, dengan asumsi bahwa Anda memiliki algoritma yang baik.
fastest-code
fibonacci
FUZxxl
sumber
sumber
phi = (1+sqrt(5))/2
Jawaban:
C dengan GMP, 3.6s
Dewa, tapi GMP membuat kode jelek. Dengan trik ala Karatsuba, saya berhasil mengurangi hingga 2 kali lipat setiap langkah berlipat. Sekarang saya membaca solusi FUZxxl, saya bukan orang pertama yang memiliki ide. Aku punya beberapa trik lagi di lengan bajuku ... mungkin aku akan mencobanya nanti.
Dibangun dengan
gcc -O3 m.c -o m -lgmp
.sumber
Sage
Hmm, Anda tampaknya menganggap bahwa yang tercepat adalah program yang dikompilasi. Tidak ada biner untuk Anda!
Di komputer saya, dibutuhkan 0,10 cpu detik, 0,15 detik dinding.
edit: diberi batas waktu pada konsol, bukan pada notebook
sumber
Haskell
Ini adalah percobaan saya sendiri, walaupun saya tidak menulis algoritma sendiri. Saya lebih suka menyalinnya dari haskell.org dan mengadaptasinya untuk digunakan
Data.Vector
dengan aliran fusi yang terkenal:Ini membutuhkan waktu sekitar 4,5 detik ketika dikompilasi dengan GHC 7.0.3 dan flag-flag berikut:
sumber
enumFromStepN (s-1)
bukanenumFromStepN s
LEMBU
Melenguh! (Butuh beberapa saat. Minum susu ...)
sumber
Mathematica, diartikan:
Jangka waktu:
Dan tentu saja, tidak ada biner.
sumber
stdout
.-batchoutput
, itu hanya mencetak informasi waktu dan bukan angka Fibonacci.curl 'http://www.wolframalpha.com/input/?i=Fibonacci%5B2+10^6%5D' | grep 'Decimal approximation:' | sed ...
Ini berjalan dalam waktu yang konstan sehubungan dengan kecepatan koneksi internet Anda. ;-)Ocaml, 0.856d di laptop saya
Membutuhkan perpustakaan zarith. Saya menggunakan Big_int tapi anjingnya lambat dibandingkan dengan zarith. Butuh 10 menit dengan kode yang sama! Sebagian besar waktu dihabiskan untuk mencetak angka sial (sekitar 9 ½ menit)!
Saya tidak percaya betapa banyak perbedaan yang dibuat perpustakaan!
sumber
Haskell
Di sistem saya, ini berjalan hampir secepat jawaban FUZxxl (~ 18 detik, bukan ~ 17 detik).
sumber
C, algoritma naif
Penasaran, dan saya belum pernah menggunakan gmp sebelumnya ... jadi:
fib (1 juta) membutuhkan waktu sekitar 7 detik ... jadi algoritma ini tidak akan memenangkan perlombaan.
sumber
Saya menerapkan metode penggandaan matriks (dari sicp, http://sicp.org.ua/sicp/Exercise1-19 ) di SBCL tetapi butuh sekitar 30 detik untuk menyelesaikannya. Saya porting ke C menggunakan GMP, dan mengembalikan hasil yang benar dalam waktu sekitar 1,36 detik pada mesin saya. Ini tentang secepat jawaban stan.
sumber
Java: 8 detik untuk menghitung, 18 detik untuk menulis
sumber
Pergilah
Ini sangat lambat. Di komputer saya dibutuhkan kurang dari 3 menit. Ini hanya 120 panggilan rekursif, meskipun (setelah menambahkan cache). Perhatikan bahwa ini mungkin menggunakan banyak memori (seperti 1,4 GiB)!
sumber
kode semu (saya tidak tahu apa yang kalian gunakan)
Komputer saya membutuhkan 56 jam untuk melakukan kedua istilah itu. Komputer saya agak jelek. Saya akan memiliki nomornya di file teks pada 22 Oktober. 1.2 gigs agak besar untuk dibagikan pada koneksi saya.
sumber