Prime Number

minggu lalu waktu kuliah TBD “teknologi Basis Data“, mas poleng (baca : Pak Arif Wibisono ^^) sempat ngobrol sejenak mengenai Java, Sun , Oracle untuk sedikit intermesso di sela kuliah. nah, disitu sempat disinggung “apa cara yang paling cepat menghitung bilangan prima?“, beberapa suara bersautan pelan (pura2 denger ^^ bisikan2 hati biar lebih dramatis) antara membagi bilangan N dengan x = 1~N, ada yang menyaut bilangan N dibagi x = 1~(N/2). kusendiri dulu (dulu banget pas alpro) make yang kedua ^_^

nah, dosen muda SI ini lalu bilang, “N dan n/2 masih kelamaan, jawabnya sqrt(N)” :) persisnya ga ngomong gitu, lebih kocak :D tapi karena pikiran terlanjur memproses sqrt(N) jadi ga inget detail :) jadi ingat kata pak Rully, dan juga mastri (mastery, masih ingatkah kau bilang pake sqrt(N) aja dan jangan kebanyakan make nested conditional waktu di thread programming lautan lama ;) )

nah abis gitu mr dosen nyelotek, coba buktikan. karena awalnya aku rada ga konsen kuliah (berangkat buru2 tuh, datang telat lagi).. so masih skeptis dulu.. baru sampe rumah kepikiran lagi, coba deh liat2 ^_^ dan dan memang terbukti ;)
sekaligus untuk menyegarkan kembali ingatan yang udah lama ngga ngoding dan berhubungan ama algoritma, jadi pengen nulis hasil penalaranku dan bikin codingnya :) he5x kayaknya bakal berguna juga nih buat praktikan alpro 1 (angkatan 2007) saat ini. kali aja keluar (dan biasanya emang keluar ^^)

ke, saatnya mulai. mungkin metodologi pembuktianku lebih agak2 ke arah analogi teoritis di awal kemudian menggunakan pembuktian (aduh apa namanya, di diskrit tuh) tapi ga ku lanjutin pake rumus2nya (membuktikan kasus n berlaku untuk N+1) :) males ja ngitung dan nulis, semua berjalan di RAM (baca : kepala doank) jadi volatile dan ga disimpen :p

as we know, tiap bilangan N memiliki faktor2 yang membentuk pasangan perkalian X dan Y. jumlah X dan Y bisa dikit, bisa banyak banget, tergantung besar nilai N kan :) so, secara umum faktor N adalah X1~Xn dan Y1~Yn. yang mau aku tunjukin disini adalah pola ‘unik’ pasangan faktor tersebut, lanjutannya mending langsung pake contoh aja, faktor 100 adalah :

1×100
2×50
4×25
5×20
10×10
20×5
25×4
50×2
100×1

ehm… bisa ngeliat pola ‘unik’ tersebut ???
oke, gimana kalo disusun kayak gini :

1×100 100×1
2×50 50×2
4×25 25×4
5×20 20×5
10×10

kalo kalian berpikir “X kayak cermin-nya Y“, bener ^_^ kalo nilai2 tersebut diletakkan pada koordinat cartesius (benernya aku mau bikinin grafik cartesiusnya, cuman ga sempat) bakal terlihat bahwa kurva yang dihasilkan simetris (jika dipotong dnegan garis x=y) dengan nilai extrem pada 10×10 (dengan kata lain X=Y).
nah apa hubungannya dengan pendapat diatas mengenai efisiensi penggunaan sqrt(N) sebagai limit perhitungan penentuan bilangan prima ? X*Y=N, (X=Y)=> X2=N => X=sqrt(N) ;)

yah, itu contohnya kan angka 100, angka yang bulat, gampang keliatan, apa teori diatas juag berlaku untuk yang ngga bulat (kotak mungkin ^^)
sepp, pertanyaan bagus, cek mau angka berapa, kita ambil 39 aja gimana :)
faktornya :

1×39 39×1
3×13 13×1

nah loh, ga ada X=Y -nya yah???

^_^ memang keliatannya seperti itu disini, tapi kalo di grafik cartesius bakal ada ko’, tepatnya di nilai 6,244997998…. panjang deh :D tapi, kalo kita bicara mengenai bilangan prima, kita bicara di domain bilangan asli, bilangan yang dimulai dari 1 ~ tak hingga dan BULAT, atau tanpa pecahan. dalam bilangan asli dapat dipastikan floor rounding atau dibulatkan kebawah, sehingga sehingga dapat diasumsikan dengan aman bahwa limit sqrt(N) yang dipakai adalah 6. tidak perlu dilakukan pengecekan modulo dengan pembagi lebih dari 6 (bandingkan dengan mengecek semua 39 pembagi)

so ngapain nyari lagi modulo dengan x (pembagi perhitungan) > sqrt(N), karena perkalian dengan nilai diatas itu PASTI merupakan ‘cermin’ dari perkalian faktor sebelumnya yang telah dihitung, lebih baik menghemat waktu kan ^_^ 100 sih masih enak, coba kalo ngitung apakah 100000000 itu prima, kan menghabiskan waktu.
oke, 100000000 emang bukan prima, udah dilihat juga tau ^_^ tapi coba cek 98165512531247, tes prima pa bukan :D

nah cukup segitu aja pembuktiannya ala tyo yang ngga jelas tersebut ^_^

coba rubah aja code limit menjadi N atau (N/2) kalo mau ngetes, bandingkan hasil bilangan yang ditampilkan ;) pengecekan silahkan sampe berapa suku bilangan prima deh, 1 juta juga gpp, makin banyak makin menegaskan kalo yang ditampilkan sama berarti bener kan :) dan perbedaan kecepatan bakal kerasa, yang lebih cepat tentu dengan menggunakan sqrt(N) ;)

NB : kalo ada yang keliru atau salah mohon kritik dan sarannya ;)

App jadinya :

Free Image Hosting at www.ImageShack.us

Advertisements

Brief History of JAVA

“Tak kenal maka tak sayang”, begitulah orang bijak bilang ^_^
so bagi mahasiswa SI (termausk aku yah), rasanya ga lengkap rasanya kalo sehari-hari makai JAVA tapi ngga tau sejarah JAVA. kenapa ko’ namanya gitu, cikal bakal lahir java gimana sih, ultahnay kapan, makanan favoritnya apa, suka musik yang gimana. (doh mulai ngelantur ^_^)
anyway, perkembangan microprocessor memiliki dampak yang cukup besar pada alat-alat elektronik ‘pintar’ pada masa itu (lama banget bo’, 80-90an lah, blom kepikiran ngoding kali yah, masih maenan ayunan). melihat adanya kesempatan, Sun Mcirosystems, pada tahun 1991 mendanai proyek penelitian perusahaan yang memiliki kode “Gren”. proyek ini menghasilkan sebuah bahasa pemrograman yang berdasarkan dari C++, James Gosling, penciptanya, menamainya ‘Oak’ terinspirasi dari pohon oak yang ada disamping jendela kantornya di Sun. tapi kemudian diketahui, bahwa bahasa pemrograman bernama Oak sudah ada, so mau ga mau harus ganti lah. saat sekelompok (daripada dibilang gerombolan), karyawan Sun mengunjungi ‘warkop’ (cuman lebih berkelas dari warkop di indo), nama ‘JAVA’ nyantol dikepala dan kemudian dipake.
tetapi, ga ada jalan yang ngga berlubang (macam jalan di indo), Project Green mendapati beberapa kesulitan. pangsa pasar perangkat elektronik pintar tidak terlalu berkembang di awal 1990, paling tidka tidak secepat harapan Sun. proyek ini terancam dibatalkan. dengan sedikit keberuntungan, World Wide Web (WWW) menjadi populer di tahun 1993, Sun melihat adanya potensi penggunaan JAVA untuk mebambah konten dinamis (interaktifitas, animasi, dan sebagainya ^_^) pada halaman web. hal ini meniupkan nafas baru pada Project Green.
Sun memperkenalkan JAVA secara resmi pada tahun 1995. JAVA dengan cepat menimbulkan ketertarikan dunia bisnis dakrena sukses fenomenal dari WWW. JAVA sekarang digunakan untuk mengembangkan aplikasi perusahaan berskala besar, menambah fungsionalitas web-server (komputer yang menyediakan ‘isi’ yang kita lihat di web browser, kali aja ga paham maksudnya server ^_^), deretan aplikasi untuk peralatan elektronik konsumen (seperti telepon selular, pager, dan PDA) dan untuk tujuan-tujuan lainnya. Versi terbaru dari C++. seperti Microsoft® Visual C++® .NET dan Borland® C++Builder™, menawarkan kemampuan yang mirip. ada pula C# yang menggabungkan kekuatan C++, produktifitas Visual Basic, dan JAVA yang elegan dalam satu bahasa pemrograman baru ^_^ *dah nyoba dikit, syntax-nya mirip banget ama java*

nah setelah beberap tahun pengembangan (wuih, udah 18an tahun yah) jadilah JAVA seperti yang kita kenal yang kita cintai di SI ini :)

Machine Languages, Assembly Languages and High-Level Languages

programmer menulis instruksi dan perintah dalam berbagai jenis bahasa pemrograman, beberapa dapat dimengerti secara langsung oleh komputer, dan beberapa yang laen membutuhkan ‘media’ penengah untuk penerjemah. dari ratusan bahasa pemrograman yang ada saat ini, secara garis besar dapat dikelompokkan dalam 3 kategori berikut :

  • Machine languages
  • Assembly languages
  • High-level languages

tiap komputer dapat secara langsung mengerti HANYA bahasa mesin-nya sendiri. bahasa mesin (Machine Language) adalah ‘bahasa alami’ dari sebuah komputer dan bahasa tersebut didefinisikan oleh manufaktur/desain hardware yang bersangkutan. [Catatan: bahasa mesin sering di sebut sebagai object code. istilah ini muncul jauh sebelum istilah “object-oriented programming.” penggunaan kedua “object” dalam istilah tersebut tidak berhubungan.] bahasa mesin pada umumnya terdiri dari deretan angka-angka (tepatnya 1 dan 0, basis binari) yang membeirkan instruksi kepada komputer untuk melakukan operasi dasar komputer. bhasa mesin bersifat dependent (satu jenis bhasa mesin hanya dapat digunakan pada satu jenis mesin/komputer tersebut, sebagai contoh bahasa mesin untuk proc intel x86 tentu tidak sama dengan bahasa mesin yang diaplikasikan pada pro ARM atau RISC). bahasa yang demikian akan terlihat membingungkan bagi manusia, seperti diilustrasikan dibawah, berikut adalah potongan kode bahasa mesin untuk menambahkan gaji lembur ke gaji pokok dan menambahkan keduanya dalam gaji total :

+1300042774
+1400593419
+1200274027

membuat instruksi dalam bahasa mesin akan menyita waktu, cukup melelahkan dan rentan terhadap kesalahan bagi kebanyakan programmer. sebagai alternatif terhadap bahasa tersebut, untuk mempermudah, programmer mulai menggunakan singkatan (yang lebih sering berasal dari bahasa inggris) untuk mewakili operasi dasar. singkatan-singkatan ini membentuk dasar dari bahasa assembly. program translasi yang disebut assemblers dikembangkan untuk melakukan konversi program yang dibuat dengan menggunakan bahasa assembly (pada masa pengembangan awal) menjadi bahasa mesin dengan memanfaatkan kemampuan komputer. berikut ini adalah kode dalam bahasa assembly yang menambahkan gaji lembur ke gaji pokok dan menyimpan nilai dalam gaji total :

load gajipokok
add gajilembur
store gajitotal

meski kode tersebut sudah tampak lebih jelas bagi manusia, isntruksi tersebut tidak dapat dipahami oleh komputer sebelum diterjemahkan ke bahasa mesin
penggunaan komputer meningkat dengan pesan seiring dengan perkembangan bahasa assembly, tetapi programmer masih harus menggunakan banyak instruksi untuk dapat mencapai, bahkan tugas yang cukup sederhana. untuk memeprcepat proses pemrograman, bahasa tingkat tinggi (high-level language) dikembangkan dimana pernyataan tunggal dapat digunakan untuk menyelesaikan tugas yang substansial.

program penerjemah disebut dengan compiler menerjemahkan program engan bahasa tingkat tingi menjadi bahasa mesin. bahasa tingkat tinggi memungkinkan programmer untuk menulis instruksi yang terlihat hampir seperti bhasa sehari-hari (english tentunya, kecuali nar mau bikin bahasa pemrograman pake bahasa indonesia ^_^ )dan berisi notasi umum matematika. program pengjaian yang sama dengan kedua contoh diatas dapat dituliskan dengan bahasa tingkat tinggi menjadi kurang lebih seperti ini :

gajiTotal = gajiPokok + gajiLembur;

dari sudut pandang programmer, tentu saja, bahasa tingkat tinggi lebih dipilih dibandingkan bahasa mesin dan bahasa assembly. C, C++, Microsoft .NET Platform (contoh, Visual Basic .NET, Visual C++ .NET and C#) dan Java adalah diantara beberapa bahasa tingkat tinggi yang sering digunakan.

proses merubah (compile) program dengan bahasa tingkat tinggi menjadi bahasa mesin membutuhkan waktu computer (computer time, clock) yang cukup banyak. program interpreter dikembangkan untuk melakukan eksekusi program yang dibuat dengan bahasa tingkat tinggi secara langsung, meski dengan waktu eksekusi yang lebih lama dan lambat. nterpreter lebih sering digunakan dalam lingkungan pengembangan program, dimana fitur-fitur baru ditambahkan dan error/kesalahan dikoreksi. setelah aplikasi selesai dikembangkan, versi bahasa mesin dapat dibuat (compile) agar aplikasi dapat berjalan lebih efisien.

Source : Deitel “how to program” series