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 :)

Comments No Comments »

Cara mempresentasikan bilangan desimal ke bilangan biner terbagi menjadi 2, Unsigned & Signed number. Panjang bit dari bilangan biner harus sudah ditentukan dan tidak berubah. Unsigned number hanya untuk bilangan positif. Contohnya Unsigned number yang terdiri dari 4 bit dapat mempresentasikan bilangan desimal 0 sampai 15. Namun, kalau kita juga ingin menuliskan bilangan negatif kita harus menggunakan Signed Number.

Signed Number adalah bilangan biner yang dapat mempresentasikan bilangan negatif. Ada banyak tipe Signed Number. Tapi yang akan kita bahas disini hanya 3 tipe saja yaitu sign-and-magnitude, one’s complement, two’s complement.

Sign-and-magnitude adalah cara yang paling mudah, kita tinggal menambahkan sign bit di bit terdepan (Most Significant Bit). Sign bit untuk bilangan positif adalah 0, negatif 1. Contohnya untuk 4 bit, dapat mempresentasikan angka 1111 (-7) sampai 0111 (7). Tapi, konsekuensinya ada dua tipe angka 0 yaitu 0000 (0) dan 1000 (-0). Cara ini digunakan komputer biner zaman dulu (misalnya IBM 7090), dan sudah jarang digunakan komputer saat ini.

One’s complement, untuk mempresentasikan angka negatif, kita meng-invers angka positifnya. Contohnya untuk 4 bit, 7 = 0111, inversnya adalah -7 = 1000. Sama seperti Sign-and-magnitude, akan ada dua tipe angka 0 yaitu 0000 (0) dan 1111 (-0). Untuk operasi penambahan, misalnya -3 + 5 :
1100 = -3
0101 = 5
—— +
0001    <– belum benar
0001    <– harus ditambah 1
—— +
0010 = 2

Two’s complement adalah cara yang paling banyak digunakan komputer sekarang. Hampir sama dengan One’s complement, bedanya setelah meng-invers kita harus menambahkan hasilnya dengan 1. Contohnya untuk 4 bit, 7 = 0111, negatifnya adalah -7 = 1000 + 1 = 1001. Kelebihannya, hanya akan ada satu tipe angka 0 yaitu 0000 (0), karena jika -0 = 1111 + 1 = 10000 = 0000. 1 yang paling depan bisa diabaikan karena kita hanya menggunakan 4 bit.  Untuk operasi penambahan dapat langsung mendapatkan hasil, misalnya -3 + 5 :
1101 = -3
0101 = 5
—— +
0010 = 2  <– sudah benar

 

Cukup sampai disini pembahasan tentang bilangan biner.  :D Tunggu artikel berikutnya yang akan membahas lebih lanjut tentang :

- representasi pecahan desimal dalam floating point binary

- penggunaan bilangan biner pada programming .

Comments 1 Comment »

Coba-coba LaTex

 

 \sqrt{\frac{x_{1}^{2}+\cdots+x_{n}^{2}}{n}}\ge\frac{x_{1}+\cdots+x_{n}}{n}\ge\sqrt[n]{x_{1}\cdots x_{n}}\ge\frac{n}{\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}}

Test :
i\hbar\frac{\partial}{\partial t}\left|\Psi(t)\right>=H\left|\Psi(t)\right>

Comments 1 Comment »

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

Comments 1 Comment »

Hello World, Hello Bro, Halo Dunia.

Blog ini saya buat untuk mempublikasikan beberapa percobaan (riset) yang sedang/telah/akan saya pelajari di bidang Computer Science. Jika tidak saya publish disini mungkin percobaan-percobaan tersebut mungkin akan hilang dan saya lupakan, karena saya memang jarang menyimpan catatan/coretan di kampus dengan rapi. Jadi, alangkah lebih baik jika saya publikasikan dan simpan di blog ini saja, mungkin juga bisa menginspirasi pembaca-pembaca lainnya yang tertarik di topik yang sama.

Khusus untuk contoh-contoh kode (source code), saya akan usahakan membuatnya minimal di 4 bahasa pemrograman (Assembly, BASIC, C/C++, dan Pascal). Saya anggap 4 bahasa ini sudah mewakili sebagian besar bahasa pemrograman yang populer saat ini. Dan ada kemungkinan bertambah lagi jika nanti saya sudah mempelajari beberapa bahasa yang lain, seperti ML, Haskell, F#.

Ini adalah contoh program Hello World di 4 bahasa, coba tebak sendiri masing-masing bahasanya :)

int main() { printf("Hello World!"); } 
Sub main(): MsgBox "Hello World!": End Sub 
Begin Writeln('Hello World !');  End. 
MODEL Small
    .STACK 100h
    .DATA
   msg db 'Hello, world!$'
    .CODE
  start:
  mov ah, 09h
  lea dx, msg
  int 21h
  mov ax,4C00h
  int 21h
  end start

Comments 5 Comments »