Blog Zainuddin Nafarin

Ok, pada postingan kali ini saya akan membahas pembuktian Legendre Conjecture dengan teknik komputasi. Legendre Conjecture simpelnya seperti ini (menurut status FB teman saya) :

Selalu ada, paling tidak, 1 buah bilangan prima diantara kuadrat dua bilangan bulat positif yang berurutan…

Nah, sesuai definisi Conjecture, yaitu pernyataan yang masih belum terbukti, kita memang akan sangat sulit membuktikannya secara analitik (menggunakan ilmu-ilmu pure mathematics), dan memang sampai saat ini belum ada manusia yang bisa membuktikannya. Tapi, setidaknya kita bisa membuktikan conjecture ini berlaku sampai suatu batasan bilangan bulat positif tertentu tentunya dengan dibantu komputer.

Dalam percobaan ini batasan bilangan bulat positif yang bisa dicapai adalah 2^32-1 =  4,294,967,295. Ini adalah batasan variabel integer di C++ yang hanya mempunyai 32 bit. Untuk improvement, sebenarnya bisa kita gunakan Integer yang 64 bit atau class integer khusus yang punya digit tak terbatas. Tapi mungkin akan memerlukan kemampuan CPU yang besar dan waktu yang sangat lama untuk mengecek bilangan bulat positif lebih dari 4,2 milyar tsb. Padahal, untuk percobaan ini saja, pengecekan sampai 1 milyar perlu waktu sekitar 1 menit.

Ini adalah kode programnya yang saya potong menjadi beberapa bagian yang berurutan, tujuannya untuk memudahkan penjelasan, Anda dapat menggabungkan potongan2 kode ini menjadi 1 file main.cpp untuk ikut melakukan pengetesan sesuai penjelasan2 saya disini.

#include <iostream>
#include "math.h"
#include <fstream>
#include <string>

using std::cout;

int main(){

// n adalah nilai maksimum bilangan bulat yang akan kita cek
// Untuk pengetesan awal, kita coba n yang kecil
// Nanti, kita dapat ubah n jadi sangat besar (misal : 1,000,000,000)
// limit ini adalah batas pengecekan pada algoritma Sieve di bawah

int n = 120;
int limit = static_cast<int>(sqrt(static_cast<double>(n)));
int i=0, j=0, ik = 0 ;

// c (count)  hanya sebagai info berapa jumlah prima total yang didapatkan
// pc digunakan sebagai info jumlah array P yang akan digunakan di bawah

int c = n-1;
int pc = n/8;

P adalah array dari unsigned byte (8 bit). Setiap bit-nya akan kita gunakan sebagai info apakah suatu bilangan yang sudah kita cek merupakan prima atau bukan. Disini saya memilih menggunakan byte/char dibandingkan hanya menggunakan boolean karena ini akan menghemat memori menjadi 1/8 nya saja daripada menggunakan boolean. Boolean akan tetap menggunakan 1 byte padahal hanya akan menyimpan info true/false. Contoh penggunaannya, bit ke-2 dari P[0] adalah info apakah 2 itu prima? bit ke-3 dari P[0] adalah info apakah 3 itu prima? dst.. bit ke-1 dari P[0] tentunya
adalah info apakah 9 itu prima?

Disini digunakan dynamic variable, karena kita baru tahu size dari array yang akan diperlukan saat runtime. Inisialisasi array ch[] untuk menyimpan 8 tipe byte yang diperlukan untuk proses pengecekan pada array P[]. Byte-byte tersebut : 00000001, 00000010, … , 10000000. Kemudian, Array P[] di-inisialisasi dengan nilai true semua, jadi nilainya 11111111 = 255

unsigned char* P=0;
P = new unsigned char[pc+1];
unsigned char ch[8];

for (i=0; i<=7; i++)
     ch[i] = 1 << i;

for (i=0; i<=pc; i++)
     P[i] = 255;

Sekarang kita akan mencari daftar bilangan prima dari 2 sampai n. Disini digunakan algoritma Sieve of Eratosthenes, simpelnya algoritma ini bekerja dengan mencoret semua bilangan yang merupakan kelipatan bilangan prima. Kita mulai dengan bilangan prima 2, maka kita akan berjalan dari j = ik = 2^2 = 4 untuk mencoret bilangan 4, kemudian 6, 8, 10, dst.. sampai 120. Kemudian akan dilanjutkan dengan bilangan prima berikutnya yaitu i = 3, dan akan dilakukan yang sama. Sampai pada limit, yaitu akar dari n dibulatkan ke bawah. Pada saat berjalan dari i = 2 sampai limit, tentunya akan ada pengecekan apakah i itu prima, pengecekan dilakukan dengan operasi AND : P[i/8] & ch[i%8]. Ini akan mengecek tempat bit disimpannya info apakah i itu prima pada array P[]. Tentang operasi XOR : P[j/8] ^= ch[j%8], adalah untuk mengeset info bit apakah j itu prima, sehingga bit ke j%8 dari P[j/8] menjadi 0 (false) dan bilangan j sudah tercoret dari list bil. prima. Detail tentang algoritma Sieve of Eratosthenes ini bisa didapatkan infonya di wikipedia.

for (i = 2; i <= limit; i++)
{
  if (P[i/8] & ch[i%8]) {
    ik = i*i;
    for (j = ik; j<=n; j+=i)
       if (P[j/8] & ch[j%8]) {
          P[j/8] ^= ch[j%8];
          c--;
       }
   }
}

Nah, sekarang sudah didapatkan info pada P[] tentang bilangan apa saja dari 2 sampai n yang prima. Sekarang kita tinggal menghitung banyaknya bilangan prima yang berada di antara dua bilangan kuadrat. Caranya cukup simple, yaitu dengan berjalan dari angka 2 sampai n, jika kita cek bit info dari 2 adalah prima maka kita akan menambahkannya (increment) ke variabel penghitung (nsqr) banyaknya bilangan prima antara 1^2 & 2^2, kemudian cek bit info 3, sekarang nsqr = 2, cek bit info 4 maka isqr akan di-increment karena kita sudah melewati batas 2^2-1, jadi jumlahnya 2 untuk 1^2 & 2^2. Sekarang cek untuk 2^2 & 3^2, dimulai dengan bit info 5 yang adalah prima sehingga nsqr=1, bit info 6 bukan prima, bit info 7 prima sehingga nsqr=2, bit info 8 bukan prima, dan kita stop saat pengecekan i=9 karena itu adalah 3^2. Jadi banyaknya kembali hanya 2.

int isqr = 2;
int isqr2 = isqr*isqr;
int nsqr = 0;

for (i=2; i<=n; i++)
	  if (P[i/8] & ch[i%8]) {
		  if (i < isqr2) {
			   cout << i << "\n";
				nsqr++;
		  } else {
			   i--;
				cout << nsqr << " up to " << isqr2 << "\n";
				nsqr = 0;
				isqr++;
				isqr2 = isqr*isqr;
		  }
	  }
cout << nsqr << " up to " << isqr2 << "\n";

// Kita hapus dynamic allocation variable yang sudah dibuat pada awal program
delete [] P;

}

Sehingga pada akhirnya di dapatkan daftar seperti ini pada output :

Jika n diubah menjadi 1 milyar atau lebih, kita dapat menyimpan hasilnya dalam format text atau file binary, yang kemudian dapat kita analisis hasilnya pada software lain (misalnya : Excel). Dari hasil analisis saya sampai bilangan 100,000,000, terbukti bahwa selalu ada bilangan prima di antara 2 bilangan bulat positif yang berurutan. Dan, info yang paling penting adala semakin besar 2 bilangan bulat positif berurutan, semakin banyak jumlah bilangan prima yang berada diantara kuadrat 2 bilangan tersebut. Tapi ini belum bisa membuktikan secara general conjecture tsb, karena pada bilangan bulat yang sangat besar sekali yang tidak mungkin dicek oleh komputasi, mungkin saja conjecture ini salah.  Demikian artikel singkat saya, ditunggu komentarnya

Algoritma Euclidean adalah salah satu algoritma tercepat untuk menghitung FPB (Faktor Persekutuan terBesar) / GCD (Greatest Common Divisor). FPB dari 2 angka adalah angka terbesar yang habis membagi 2 angka tersebut. Prinsip dari algoritma Euclidean ini adalah dari kenyataan bahwa FPB dari 2 angka tidak akan berubah jika angka terbesar dikurangi angka terkecil. Sebagai contoh, 22 adalah FPB dari 198 dan 110 (198 = 22 x 9; 110 = 22 x 5), 198 – 110 = 88 dan 110 tetap mempunyai FPB 22. Proses ini bisa terus di-ulang sampai salah satu dari angka tersebut adalah 0, sehingga angka yang lainnya adalah FPB dari 2 angka paling awal. Jika dilihat langkah – langkahnya sampai selesai :

(198, 110) -> (110, 88) -> (88, 22) -> (22, 0)

Dapat juga dituliskan secara prosedural :
198 = 110 x 1 + 88
110 = 88 x 1 + 22
88 = 22 x 4 + 0

Berdasarkan prosedur di atas, sekarang akan dibuat implementasinya di 4 bahasa pemrograman (C/C++, Assembly, Pascal, dan BASIC). Implementasinya akan berbentuk fungsi FPB dengan input 2 bilangan bulat (integer) 32-bit, dan output juga integer. Berikut ini adalah kode-kode fungsi FPB algoritma Euclidean di 4 bahasa tersebut :

C/C++

int FPB(int a, int b)
{
    if (a < b)
       {int t = a; a = b; b = t;} // Tukar a dan b jika a < b

    int r = 0;

    do
    {
        r = a % b;
        a = b;
        b = r;
    } while (r); // Teruskan loop hanya jika r tidak 0 

    return a;
}

Assembly

FPB PROC
; Fungsi : FPB(a,b)
; Input  : (a,b) -> (eax, ebx)
; Output : FPB -> eax

	pushad              ; Simpan semua register
	cmp	eax, ebx    ; Bandingkan eax dan ebx
	ja	startloop   ; Jika  a > b, langsung ke startloop
	xchg    eax, ebx    ; Jika tidak, tukar isi eax dan ebx
startloop:
	xor	edx, edx    ; edx = 0
	div	ebx         ; eax / edx, sisanya akan disimpan di edx
	cmp	edx, 0      ; Bandingkan edx dan 0
	je	endloop     ; Jika edx = 0, hentikan loop ke endloop
	mov	eax, ebx    ; eax = ebx
	mov	ebx, edx    ; ebx = edx
	jmp	startloop   ; Mulai lagi loop
endloop:
	popad               ; Kembalikan semua register ke asal
	mov eax, ebx        ; Simpan nilai FPB di eax
	ret                 ; Kembali ke pemanggil

FPB ENDP

Pascal

Function FPB(a, b : Integer) : Integer;

Var t, r : Integer;

Begin
 If (a < b) Then
    Begin
      t := a; a := b; b := t
    End;

 Repeat
    r := a Mod b;
    a := b;
    b := r
 Until r = 0;

 FPB := a;
End;

BASIC

Function FPB(ByVal a As Long, ByVal b As Long) As Long

    Dim t As Long, r As Long

    If a < b Then t = a: a = b: b = t

    Do
        r = a Mod b
        a = b
        b = r
    Loop Until r = 0

    FPB = a

End Function