🎼 🎐 ◾️ Memilah miliaran angka sederhana lebih cepat dari Wikipedia 🙆🏼 👆🏽 🤰

( Sumber Gambar )

Telah diketahui bahwa Saringan Eratosthenes (RE) adalah salah satu algoritma tertua yang muncul jauh sebelum penemuan komputer. Oleh karena itu, Anda mungkin berpikir bahwa selama berabad-abad algoritma ini telah dipelajari naik turun dan tidak ada yang dapat ditambahkan ke dalamnya. Jika Anda melihat Wikipedia, ada banyak referensi ke sumber-sumber resmi di mana Anda dapat dengan mudah tenggelam. Karena itu, saya terkejut ketika saya tidak sengaja menemukan bahwa opsi yang disajikan secara optimal di Wikipedia dapat dioptimalkan secara signifikan.

Seperti itu. Dalam diskusi tentang artikel tentang pemrograman fungsional (FP), ia mengajukan pertanyaan : bagaimana menulis RE dalam paradigma ini. Memiliki lebih dari pengetahuan FP yang sedikit, saya tidak berani menilai jawabannya, tetapi peserta lain dalam diskusi menolak beberapa solusi yang diajukan segera, menunjukkan bahwa alih-alih kompleksitas teoretis

$O (n \ log \ log n)$ (1)

implementasi yang diusulkan akan memiliki kompleksitas komputasi

$O (n ^ 2 / \ log n)$ (2)

dan dengan kompleksitas seperti itu Anda tidak bisa menunggu ketika, misalnya, 10 juta angka disaring. Saya menjadi tertarik dan saya mencoba untuk mengimplementasikan versi optimal menurut Wikipedia, menggunakan pemrograman prosedural yang biasa. Di Delphi-7, saya mendapat kode berikut:

Listing 1

program EratosthenesSieve; // Sieve of Eratosthenes {$APPTYPE CONSOLE} uses SysUtils, DateUtils,Math; const version ='1.0.1d1'; N = 1000000000; // number of primes var sieve : array [2..N] of boolean; // false if prime t0, t1,dt : TDateTime; O,C : Extended; procedure init; var i : integer; begin for i:=2 to n do sieve [i] := false; end; //init procedure calc (start : integer); var prime, i : integer; breakLoop, exitProc : Boolean; begin prime := start; exitProc := false; repeat // find next prime prime := prime+1; while (prime<N) and sieve[prime] do inc (prime); i:= sqr(prime); // delete if i<= N then begin breakLoop := false; repeat if i<= N then begin sieve [i] := true; inc (i,prime); end else // if i<= N breakLoop := true; until breakLoop; end else // if prime+prime<= N exitProc := true; until exitProc; end; //calc procedure print; var i :integer; found : integer; begin found := 0; for i:=2 to N do if not sieve [i] then begin // write (i,', '); inc(found); end; writeln; writeln ('Found ',found,' primes.'); end; // begin // program body writeln ('Sieve of Eratosthenes version ', version); writeln('N= ',N); init; t0 := now; writeln('Program started ',DateTimeToStr(t0)); t0 := now; calc (1); t1 := now; writeln('Program finished ',DateTimeToStr(t1)); dt := SecondSpan(t1,t0); writeln ('Time is ',FloatToStr(dt),' sec.'); O := N* ln(ln(N)); C := dt/O; writeln ('O(N ln ln N)= ',O,' C=',C); O := sqr(N)/ln(N); C := dt/O; writeln ('O(N*N/ln N)= ',O,' C=',C); print; writeln ('Press Enter to stop...'); readln; end.

RE diwakili oleh array Boolean saringan dengan nilai terbalik - jika bilangan prima, ini diindikasikan sebagai false, yang mengurangi jumlah operasi negasi (bukan) selama pengayakan. Ada 3 prosedur dalam program: inisialisasi RE - init, perhitungan (pengayakan dan pencabutan angka dalam RE) - kalk, dan pencetakan bilangan prima yang ditemukan sebagai hasil - cetak, dan jumlah angka yang ditemukan dihitung. Saya terutama akan menarik perhatian pada keluaran komentar bilangan prima dalam prosedur cetak: untuk pengujian pada N = 1000, komentar dihapus.

Di sini, di prosedur kalk, saya menggunakan rekomendasi Wikipedia: untuk nomor utama i berikutnya, hapus angka dari RE

$i ^ 2, i ^ 2 + i, i ^ 2 + 2i, ...$

Program ini menembus angka satu miliar dalam 17,6 detik. pada PC saya (3,4 GHz Intel Core i7 CPU).
Setelah membuat program ini, saya tiba-tiba teringat sifat-sifat nomor genap dan ganjil yang terkenal .

Lemma 1. 1) odd + odd = even; 2) ganjil + genap = ganjil; 3) even + even = even.

Bukti

1)

$(2n + 1) + (2m + 1) = 2n + 2m + 2$ habis dibagi 2. TCD.
2)

$(2n + 1) + (2m) = 2n + 2m + 1$ tidak habis dibagi 2 tanpa sisa. Chtd.
3)

$(2n) + (2m) = 2n + 2m$ habis dibagi 2. TCD.

Lemma 2. Kuadrat dari angka ganjil adalah angka ganjil.
Bukti.

$(2n + 1) ^ {2} = 4n ^ {2} + 4n + 1$ tidak habis dibagi 2 tanpa sisa. Chtd.

Komentar. Angka prima yang lebih besar dari 2 adalah ganjil.

Karena itu, Anda hanya dapat menghapus angka ganjil:

$i ^ 2, i ^ 2 + 2i, i ^ 2 + 4i, ...$ (3)

Tetapi pertama-tama Anda harus mencoret semua angka genap. Ini dilakukan oleh prosedur inisialisasi init yang dimodifikasi.

Listing 2

 program EratosthenesSieve; // Sieve of Eratosthenes {$APPTYPE CONSOLE} uses SysUtils, DateUtils,Math; const version ='1.0.1d1'; N = 1000000000; // number of primes var sieve : array [2..N] of boolean; // false if prime t0, t1,dt : TDateTime; O,C : Extended; procedure init; var i : integer; begin for i:=2 to n do sieve [i] := not odd(i); end; //init procedure calc (start : integer); var prime,prime2, i : integer; breakLoop, exitProc : Boolean; begin prime := start; exitProc := false; repeat // find next prime prime := prime+1; while (prime<N) and sieve[prime] do inc (prime); // i:= prime*prime; i:= sqr(prime); prime2 := prime+prime; // delete if i<= N then begin breakLoop := false; repeat if i<= N then begin sieve [i] := true; inc (i,prime2); end else // if i<= N breakLoop := true; until breakLoop; end else // if prime+prime<= N exitProc := true; until exitProc; sieve [2] := false; end; //calc procedure print; var i :integer; found : integer; begin found := 0; for i:=2 to N do if not sieve [i] then begin // write (i,', '); inc(found); end; writeln; writeln ('Found ',found,' primes.'); end; // begin // program body writeln ('Sieve of Eratosthenes version ', version); writeln('N= ',N); init; t0 := now; writeln('Program started ',DateTimeToStr(t0)); t0 := now; calc (2); t1 := now; writeln('Program finished ',DateTimeToStr(t1)); dt := SecondSpan(t1,t0); writeln ('Time is ',FloatToStr(dt),' sec.'); O := N* ln(ln(N)); C := dt/O; writeln ('O(N ln ln N)= ',O,' C=',C); O := sqr(N)/ln(N); C := dt/O; writeln ('O(N*N/ln N)= ',O,' C=',C); print; writeln ('Press Enter to stop...'); readln; end.

Program ini bekerja selama 9,9 detik. - Hampir dua kali lebih cepat.

Untuk menilai korespondensi operasi real-time dari program dengan teori, saya menyarankan itu

$dt = C * O,$

dimana

$dt$ - waktu operasi yang diukur;

$C$ - konstan dengan dimensi waktu;

$O$ - penilaian teoritis.

Dihitung dari sini

$C$ untuk mengevaluasi (1) dan (2). Untuk

$N = 10 ^ 6$ dan kurang

$dt$ mendekati nol. Karena itu, saya membawa data pada program pertama untuk besar

$N.$

$N$	(1)	(2)
$10 ^ 7$	$1,69 \ cdot 10 ^ {- 9}$	$2,74 \ cdot 10 ^ {- 9}$
$10 ^ 8$	$5,14 \ cdot 10 ^ {- 9}$	$1,47 \ cdot 10 ^ {- 8}$
$10 ^ 9$	$5,80 \ cdot 10 ^ {- 9}$	$1.29 \ cdot 10 ^ {- 7}$

Seperti yang kita lihat, perkiraan (1) jauh lebih dekat dengan hasil nyata. Untuk program kedua, gambar serupa diamati. Saya sangat ragu bahwa saya menemukan Amerika menggunakan urutan (3) dan saya akan sangat berterima kasih atas hubungan dengan pekerjaan di mana pendekatan ini diterapkan. Kemungkinan besar, penulis Wikipedia sendiri tenggelam dalam lautan informasi tentang perang elektronik dan melewatkan pekerjaan ini.

PS Untuk algoritma Wikipedia dengan “linear runtime” lihat

Memilah miliaran angka sederhana lebih cepat dari Wikipedia

More articles: