Tujuannya sederhana: hitung fungsi totient untuk sebanyak mungkin angka dalam 10 detik dan jumlahkan jumlahnya.
Anda harus mencetak hasil Anda di akhir dan Anda harus benar-benar menghitungnya. Tidak ada fungsi totient otomatis yang diizinkan, tetapi perpustakaan bignum diperbolehkan. Anda harus mulai dari 1 dan menghitung semua bilangan bulat secara berurutan. Anda tidak diizinkan melewati angka.
Skor Anda adalah berapa banyak angka yang dapat dihitung program Anda di mesin Anda / berapa banyak program saya yang bisa dihitung di mesin Anda . Kode saya adalah program sederhana dalam C ++ (optimisasi tidak aktif), semoga Anda dapat menjalankannya.
Properti penting yang dapat Anda gunakan!
- jika
gcd(m,n) = 1, phi(mn) = phi(m) * phi(n)
- jika
p
prima,phi(p) = p - 1
(untukp < 10^20
) - jika
n
genap,phi(2n) = 2 phi(n)
- yang lain tercantum di tautan pertama
Kode saya
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
while (b != 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}
int phi(int n)
{
int x = 0;
for (int i=1; i<=n; i++)
{
if (gcd(n, i) == 1)
x++;
}
return x;
}
int main()
{
unsigned int sum = 0;
for (int i=1; i<19000; i++) // Change this so it runs in 10 seconds
{
sum += phi(i);
}
cout << sum << endl;
return 0;
}
fastest-code
qwr
sumber
sumber
1, 3, 5, 2, 4
atau sejenisnya?Jawaban:
Nimrod: ~ 38.667 (580.000.000 / 15.000)
Jawaban ini menggunakan pendekatan yang cukup sederhana. Kode ini menggunakan ayakan bilangan prima sederhana yang menyimpan bilangan prima dari bilangan prima terkecil di setiap slot untuk bilangan komposit (nol untuk bilangan prima), kemudian menggunakan pemrograman dinamis untuk membangun fungsi totient pada rentang yang sama, kemudian menjumlahkan hasilnya. Program menghabiskan hampir seluruh waktunya untuk membuat ayakan, kemudian menghitung fungsi total dalam waktu yang singkat. Sepertinya itu turun untuk membangun saringan yang efisien (dengan sedikit twist yang satu juga harus dapat mengekstrak faktor utama untuk nomor komposit dari hasil dan harus menjaga penggunaan memori pada tingkat yang masuk akal).
Pembaruan: Peningkatan kinerja dengan mengurangi jejak memori dan meningkatkan perilaku cache. Dimungkinkan untuk memeras kinerja 5% -10% lebih banyak, tetapi peningkatan kompleksitas kode tidak sepadan. Pada akhirnya, algoritma ini terutama melatih bottleneck von Neumann dari CPU, dan ada sangat sedikit penyesuaian algoritme yang dapat mengatasi itu.
Juga memperbarui pembagi kinerja karena kode C ++ tidak dimaksudkan untuk dikompilasi dengan semua optimasi dan tidak ada orang lain yang melakukannya. :)
Pembaruan 2: Operasi ayakan yang dioptimalkan untuk peningkatan akses memori. Sekarang menangani bilangan prima kecil dalam jumlah besar melalui memcpy () (~ 5% speedup) dan melompati kelipatan 2, 3, dan 5 saat menyaring bilangan prima yang lebih besar (~ 10% speedup).
Kode C ++: 9,9 detik (dengan g ++ 4,9)
Kode Nimrod: 9,9 detik (dengan -d: rilis, backend gcc 4,9)
sumber
Java, skor ~ 24.000 (360.000.000 / 15.000)
Kode java di bawah ini melakukan perhitungan fungsi totient dan ayakan utama secara bersamaan. Perhatikan bahwa tergantung pada mesin Anda, Anda harus meningkatkan ukuran tumpukan awal / maksimum (pada laptop saya yang agak lambat saya harus naik ke
-Xmx3g -Xms3g
).sumber
Nimrod: ~ 2.333.333 (42.000.000.000 / 18.000)
Ini menggunakan pendekatan yang sama sekali berbeda dari jawaban saya sebelumnya. Lihat komentar untuk detailnya. The
longint
modul dapat ditemukan di sini .sumber
2*sqrt(n)
) yang menghasilkan skor yang jauh lebih rendah.C #: 49.000 (980.000.000 / 20.000)
/codegolf//a/26800 "kode Howard".
Tetapi dimodifikasi, nilai phi dihitung untuk bilangan bulat ganjil.
Skor baru: 61.000 (1.220.000.000 / 20.000)
Di "App.config" Saya harus menambahkan "gcAllowVeryLargeObjects enabled = true".
sumber
Python 3: ~ 24000 (335.000.000 / 14.000)
Versi saya adalah port Python dari algoritma Howard . Fungsi asli saya adalah modifikasi dari algoritma yang diperkenalkan di blogpost ini .
Saya menggunakan modul Numpy dan Numba untuk mempercepat waktu eksekusi. Perhatikan bahwa biasanya Anda tidak perlu mendeklarasikan jenis variabel lokal (saat menggunakan Numba), tetapi dalam hal ini saya ingin memeras waktu eksekusi sebanyak mungkin.
Sunting: fungsi constructsieve dan summarum gabungan menjadi satu fungsi.
C ++: 9.99s (n = 14.000); Python 3: 9.94s (n = 335.000.000)
sumber
Berikut ini adalah implementasi Python saya yang tampaknya mampu mengeluarkan ~ 60000 angka dalam 10 detik. Saya memfaktorkan angka menggunakan algoritma pollard rho dan menggunakan uji primitif Rabin miller.
sumber
φ (2 n ) = 2 n - 1
Σ φ (2 i ) = 2 i - 1 untuk saya dari 1 hingga n
Pertama, sesuatu untuk menemukan waktu:
Untuk kode referensi, bagi saya, itu:
Sekarang, Haskell:
Itu membuat sesuatu dengan 2525224 digit dalam 0,718 detik. Dan sekarang saya hanya memperhatikan komentar @ Howard.
sumber
Matlab: 1464 = 26355867/18000
Saya tidak dapat menguji kode Anda, jadi saya membagi 18.000 karena mewakili komputer tercepat dari mereka yang diuji. Saya sampai pada skor menggunakan properti ini:
Saya sebagian besar suka itu adalah satu liner:
sumber
phi(p)
semua yang bukan perdanap
?Python 2.7: 10.999 (165975/15090)
Pypy 2.3.1: 28.496 (430000/15090)
Beberapa metode menarik yang saya gunakan:
Rabin-Miller Strong Pseudoprime Test - Tes primality yang menyediakan algoritma probabilistik yang efisien untuk menentukan apakah angka yang diberikan adalah prima
Formula produk Euler - Produk melebihi bilangan prima yang berbeda yang membagi n
Kode:
sumber