lsBN979- 8012- 95- X
P
KOW ILMU PENGEIAHUAN NASIONALVI Jakarta,11 - 15 September1995
BI.iKU II MAKALAH SIDANG.SIDANG DIMENSI
LEMBAGA ILMU PENGETAHUANINDONESIA bekerjasamadengan PIBE4TORAT JENDERALPENbIDIKAN TINGGI, DEPARTEMENPENDIDIKAN DAN KEBUDAYAAN
FORUMO*"O*"I3I PROFESI ILMIAH
STTJDIKOMPARATM TERtrADAP' BEBERAPA STIBRTTIINPEMBANGKIT BII./INGAI\ ACAK Bd[ Seilco],Yazlz
llsrmr; pltonof
ABSTRAK
membangkitkanbilangan acak yang terdistribusi secaraseraganrdengan persentase deviasirata-rata3 7o. ABSTRACT A comparativestudy for various subroutinesof randomnumber
uniformly in the relatedinterval with more or less3% percentage deviation. PENDAHI.JLUAN
* PusalPengkajian TeknologiNuklir, Batan,Jakarta
50r
bilanganacakdapatdinyatakan Sejumlahmetodeuntukmenciptakan khusus;(2) (1) tabelterkonstruksi menarik sampel dari dalamtiga kategori: (3) kalkulasi proses fisis; dan memantauoutput bebqrapaperanti atau demikian tertentu(bilangan-bilangan suatualgoritmamatematis menggunakan ''acak-semu").Kategori ketiga mungkin agak sering disebut bilangan acak!Kategori bilangan-bilangan karenaproduksideterministik paradoksikal ini dalam yang saat digunakan ketiga ini mengandungmetodautalna Penjelasannya multiplikatifkongruensial). bilanganacak(metoda menciptakan praktispenggunaan bilanganacak. eratdenganaspek-aspek berhubungan utamaterjadidalamhalpembangkit Akantetapi,salahsatukesukaran Dapatterjadibahwasetelahsuatubilangantertentudari bilanganacak-semu. dirinya unsur-unsuryangberbedatelahdihasilkan,barisanmulaimengulangi yangdihasilkanolehpembangkit bilangan sendiri;jumlahunsuryangberbeda acak-semukemudiandisebutperiodanya.Jika periodasuatubarisansangat tak tertentuadalatr bilanganacak-semu besar,makasifatperiodispembangkit praktis. memiliki kegunaan PEMBANGKITAN BILANGAN ACAK acak yang terdistribusiseragam Pembangkitanbilangan-bilangan merupakanoperasi komputer yang mendasarisetiap penanganansuatu distribusiyang lebih rumit. Ada beberapametodauntuk melakukantugas dengan dasarini dan untuk mencekbahwahasil-hasilmemangberhubungan yang paling bilanganacak seragamyang diinginkan.Salahsatualgoritma lazim adalahmetoda"kongruensiallinear', yang "menumbuhkan"seluruh barisanbilanganacakdari suatubilangan"bibit". Angotaterbarudari barisan dikalikandengansuatubilangan"magik" pertama,diinkremenolehbilangan magik kedua,dan kemudianjumlahannyadimodulooleh bilanganmagik olehhubungan berikut ketiga,yangQinyatakan xi+r: @x,* c)modm,
(l\
bilangan di manai adalahlabelbarisandana, c danm adalahmasing-masing sangatbesar,dengannilai-nilaipresisinya magik. Yang terakhirkadangkala bergantungpadapanjangkata komputeryang digunakan,Catatanbahwa4 "acak" sebagaimana munculdari bibit dalamyang telah tidak benar-benar tentusaja,duabarisanyangtumbuhdari terdefinisi,algoritmadeterministik; bibit yangsamaadalahidentik.Karenaalasanini, merekaseringdiistilahkan "acak-semu". Meskipundemikian,untukbanyaktujuanpraktisbilanganacakmereka dengancaraini dapatdigunakanseolah-olah semuyangdibangkitkan
502
benar-benar acak. Pembangkit Bilangan Acak pasokan-sistem ' Komputer biasanyamemiliki suatu rutin pustakayang dinamakan pembangkit bilanganacak,RAN. Biasanya diawalidengants'Ego untuknilai seblang sebelumperramakali bekerjake RAN. Tiap mengawalinilai secara tipikal akan kembali ke barisanacak subsequenbirbeda, atau sekurang_ kurangnyasubsequen berbedadari beberapabarisansangatpanjang.Namun, nilai awal ISEED yang samaakanseralumengembalikan bariian acakyang sama. RAN pasokan-sistem hampirselaluberupapembangkit kongruensial linear,yangmembangkitkan suatubarisanbilangan-bilangan burat xt,x2.x3, ..., tiap antara0 danm-I (bildnganbesar)oleh hubung"n,-.ku..nri persamaan (1).Rekurensi akhirnyaakanmengulang dirinyasendi.i,dengansuatuperioda yang besar dari m. Jikam, a, dan c dipilih se.rr^ benai,maka -tak-lebih periodaakanmemiliki panjangmaksimal.yaitu panjangn. Dalamhal itu, semuabilanganbulat yangmungkinantara0 danm-.l tirjadi padabeberapa titik, sehingga setiappilihan "bibit" awalxradalahsebaikyrng lrin, barisan hanyaberanjakdari titik itu. Bilanganrealantara0 dan I y^nglit.rbalikan adalahumumnyax,*,/tn, sehinggaharuskurangdari l, tapi kaoang-kadang secaraeksaksamadengannol. ISEED dikembarikan sebagai .r,*r, sehinggi dapatdigunakanpadapanggilanberikutnyauntuk membarigkitkan x,*r, dan seterusnya. Kelebihanmetodakongruensiallinear adalahoperasinyayang sangatcepar.Tapi kelemahannya adalahtidak bebaskorelasiiekuensialpada panggilan-panggilan berentetan. Korelasi ruang adalahbukan satu-satunyakelemahanpembangkit kongruensial linear. Pembangkitini seringmempunyaibit-bit orde reniah yangjauh kurangacakdari padabit-bit orde tingginya.Usahaminimum adalahmengusahakan pengacaktambahanyang mengacakbilangan yang dibangkitkanoleh Mf, yaitu menggantinya dingan naNo. narisanyang dikembalikan olehRAN0secara efektifbebasdari ktrelasisekuensiat. Output RAN0 harusberkualitasuntuksemuatujuan,meskipuncenderung masihteiap mencurigaibit-bit ordeterendahnya. PembangkitBilangan Acak portabel seringdiinginkansuatupembangkit bilanganacakportabelyangdapat diprogramdalambahasa tingkattinggi,danyang m..brngkitkan bariian acakyangsama(dari bibit tertentu)padasemua"k"n mesin.Dapatdibedakandua kelaspenggunaan untukrutin-rutinportabelsepertiitu: peitama,diinginkan pembangkityang benar-benar andal,sekurangnya sekualitas RAN0 di atas. untuk ini, danjuga portabilitas,harusditerimakenyataan: rutin-rutinakan
503
bekerjaagaklebih lambatdari padaRAN0. Kedua,seringkalidiinginkan suatu pembangkitcepatuntuk ditambahkan dalamprogramhanyauntuk mengacak apasaja.Sekarang pertama kembalikepenggunaan daripembangkit bilanganacakponabel. yaituuntukmembangkitkan bilangan-bilangan acak yangberkualitas. Adatigarutinyangdisajikan di sini,perrama adalahRANI yang didasarkan padatiga pembangkit kongruensial lineardari suatutabel yang menyertai.Satu pembangkitdigunakanuntuk bagianyang paling signifikandari bilanganoutput,keduauntukbagiankurangsignifikan,dan yang ketigaunrukmengontrol suaturutin pengocok.Rutinpengocokyang digunakan adalahtidaksamasepertiyangdilukiskan dalamRANO.Tentusaja, jauh RANI sangat lebihbaikdaripada masing-masing daritigapembangkitnya secaraindividual:periodanya adalah(untuksemuatujuanpraktis)takhingga, yangnyata.Pilihanyangmana dan ia harustak memilikikorelasisekuensial konstanta-konstanta dalamtabel yang menyertaiadalahsebarang,sebagaipengocokan. manapanjangpengaturan PeriodaRAN2adalahjuga tak hingga,Keterbatasan utamanya adalatr bahwa ia membalikkan satudari hanya714025nilai-nilaiyang mungkin, dibuatberjarak samasepertisebuah"sisir" dalaminterval[0,1]. Akhirnya. suaturutin portabel,RAN3, yang samasekali tidak didasarkanpadametodakongruensial linear,tapi padametodasubtraktif. Kelemahannya.kalau ada, adalah karenakarakter-karakter yang sangat berbedadari kelemahan-kelernahan RANI di atasjika ada.Rutin-rutinyang dibicarakandapatdilihatdalamLampiranA. PERHITI,JNGAAI,HASIL DAN PEMBAHASAN Setiapkumpulan bilanganacakharusmemilikisifat,sifatberilott: I. Bilangan-bilangan harusterdistribusiseragam di arasrangeyangditetapkan; ii. Koefisien-koefisien autokorelasi antarabilangan-bilangan berurutandan bertetangga harussekecilmungkin;idealnyaharusnol: iii. Waktu yang diperlukanuntuk membangkitkan bilangan-bilangan harus minimum.dan iv. Barisanacakharusberperioda sebesar mungkin. Di sini disajikankinerja pembangkit-pembangkit bilanganacak terhadapkriteriayangdisebutkan di atas. Distribusi Frekuensi TabelI menyajikan distribusifrekuensi bilangan-bilangan acakdalam jatuh dalamrentang range0 sampai1. Frekuensi bilanganacakdiharapkan 504
interval0,1 adalah5.0@untuk 50.000bilangan. Tabel l. Distribusi frekuensipada tiap interval (Jumlahyangdiharapkan5.000) SUBRUTIN
JUlvl-AHBIL@
EIfiTNC-TNTER-fr{I-
tr-.I
)-
45
J.
o-
-6
6-
1
RANT)
496/.
5058
4 8l 0
5048
lyJ
6 KAN
)uol
5012
4913
t
r+yo
5067
6 RANI
4961
5040
-5026
)u4
5067
494
)u0 I
5044
4U)
4992
J
8
5tJ2
4yo
4992
RAN3
5041
502E
4991
4887
5034
494
5r30
7
500tt
8 RAN2
v-t
.9
f lu
4936
499
4968
') I
4y) 4Uy
5054
)uz
5058
9 )u4
_5
)
49J
)047
3 5t0
:rUl
494't
6 4EE9
4*t
5056
5
Distribusifrekuensibilanganacak yang dinyatakandalam bentuk grafik ditunjukkandalam Gambarl. sesuai yang diharapkanbahwajatuhnya bilangan-bilangan acakdalamrenrangintervaiyangoipitihharusterdistribusi secarameraradalam rentanginterval-intervalyang yang bersangkutan. semakin besarjumrah bilangan acak yang dihasilkan ,i"k, oinr.apkan 'distribusi frekuensi akanmentbentuk suatudiJtribusidatar.persentase deviasi dalamdistribusidataruntuklima rutindiprotdaramGambar2. Diamati bahwa deviasidalamdistribusidataradalahleblhkurang3%.
a|Ial^|OaqrtI(rr
5
.O
I
D
T
I a
'at
.raa
aru
g
.g
llra
nt
ota
*
u
s05
al
it
,-
aa
tf
r!llltttlr tsrrr.-arr.rt T -l
--r---.tOO
it;
tt
I
n
a
71t
I I t I I I r
tla--irI-
-
-
-_q-
1r
E
-t
-
-
r
F F aaa let tt I
I'IITTSIII iftjtrif
-t,c,t
--!!
rtttttltlr 506
a.trrtFr-
3'
'r',-
Gambar 1. Gralik distribusi frekumsi bilangan acak h|b.nl|'tthrDp
--r-!i-rlr-
507
mrlIr-al|fIJa
m-r-r:lar,
Ganbar 2. Grrtik persentscdeviasiuntuk 51t.000 qrI| iL
at rl at
ra bilangantt
50E
lrr
I;
-
t
t
I
o
r
-
I
ra
.a +tl
DT.
rl'tl-
nfa-l
cri i
l.ri
I *1 I
||L
TEO
l)-ttnr-
tlrr-
"i I ar{ I I
o,ffffi;ion-
509
-J
ft{raad
'i
Gambar 3. Distribui ternormalisasi
Koefisien Autokorelasi Karakteristiklain yang terpentingdari rutin bilanganacak adalah yang memiliki suatu bahwa ia harus membangkitkan bilangan-bilangan yang koefrsienautokorelasiyang sangatrendahuntuk bilangan-bilangan persanuan bertetangga. Koefisienautokorelasi dihitungmenggunakan
(2\ di mana1 adalahkoefisien autokorelasi untukbilangan-bilangan tetangga ke7 dalambarisan,.x,adalah bilangan acakke-idalambarisandanr adalahratajumlahbilangan ratayangdalamlimit cenderung ke 0,5. N adalah acakyang dibangkitkanyang dalam kajian ini adalah50.000.Koefisien-koefisien autokorelasi untukT= l, 2,3 diberikandalamTabel2.
510
Tabel2. Kmfisien Autokorelasi dan waktu pembangkitan waKu Pembangkitan (dalamdetik)
Kootrsren Aotokorelasi
subrutrn
J=z rJ.4U5't4L t62E.{J2
-u.lu46ujz /)b01 0.198746403E-O2
RAND
0.E857750E08{3
ITAN
o.z5z64LE3ZE-tJ',l -u.422J661| lE-UJ -0.460895 l97E-02 0.935554504E-03 0 . 5 4 1l 2 5 7 l 5 E - 0 3 0.234096055E-02 o.E9Z3Z4466E-O2 u.342)6) lTUE-UZ -0.553 -(J.269 l4Zl24E42 l2E9l5E-02 - u .t 6 z t I o w S E -
RANI
RAN2 RAN3
0.1 0.054
0.124 o.o14
0.024
02
Walrtu Pembangkitan sejumlahbesar fisismemerlukan Karenasetiapsimulasiproses-proses bilanganacak menjadi bilanganacak, maka waktu untuk membangkitkan faktor penting.Tabel 2 juga memberikanwaktu yang diperlukandalam bilanganacakolehberbagairutin. milidetikuntukmembangkitkan
KESIMPULAN Diperolehbahwa semuapembangkitbilanganacak adalahsama untukmengeksekusi-studiKarenaKomputerPC tidakdiharapkan bagusnya. studi simulasi skala besar, maka waktu lebih yang diperlukanuntuk masalahserius. bilanganacaktunggaltidakmerupakan membangkitkan
DAFTAR PUSTAKA Press,William H., et.al., NumericalRecipes,Press Syndicateof the Universityof Cambridge,New York, 1987. Raeside,D. E., An Introductionto Monte Carlo Methods.AJP Volume 42, 1974. A Random Rajagopal,V., B. Danalakshmiand C. R. Gopalakrishnan, NurnberRoutinefor PersonalComputersand a ComparativeStudyof Random Routines, Indira Gandhi Centre for Atomic Research, Kalpakkam,1987
5ll
LAMPIRAN A. DAFTARPROGRAMSUBRUTINPEMBANGKITBILANGANACAK RAN. MNO, RANI, RAN2, DAN RAN3 RAN functionran(ran) ia= 1366 ic= 1508E9 m=714025 rm= l./float(m) jran= mod(ran*ia* ic,m) oat(m) ran= fl oat(iran)/fl retum end RANO functionran0(idum) dimensionv(97) dataiff/01 if (idum.lt.0.or.iff.eq.0)then iff= I iseed=abs(idum) idum=l doll j=l'97 dum=ran(iseed) continue ll d o 1 2i = 1 ' 9 7 v0) =ran(iseed) continue 12 Y: ran(iseed) endif j=l+int(9+y) l) pause if (. gt.97.or.j.lt. y=v(i) rar{)=y v(i) =ran(iseed) retum end
RAt{I furction ranl(idum) dimensionr(97) = l./ml) (mI =259fi),ial =7 l4l,icl = 54773,rml parameter l,nr0= I'hr0\ parameter(m2= 134456,ia2=8l2l,ic2=2841 =456l,ic3 = 5I 349) parameter(m3=243000,ia3
312
a
dataiifi0/ if (idum.lt0 or ilT.eq0) then ix1=mod(icl-idum'ml) i x l = m o d ( i a 1 * i x+i i c 1 ' m l ) ix2=mod(ixl,m2) l i cl . m l ) i x l = m o d ( i a l * i x+ ix3=mod(ixl,m3) doIl j=1'97 i x l = m o d ( i a+l i x l + i c l . m l ) i x2 = mod(ia2*i x2 + ic?'nQ) r() = (fl oat(ixl) * fl oat(ix2)*rm2)*rml contlnue t
ll
c
endif i 1 1= 6 e d ( i a 1 * i x+l i c l , m l ) i x2= nrod(ia2+i xZ+ icL,nQ) + ic3,m3) ix3=mod(ia3+ix3 j = I +(97*ix3)/m3 i f ( . g t . 9 7 . o r . j . l t ' lP) a u s e ranl = r(i) rfi) = (float(ix1)*fl oat(ix2)*nn2)+rm1 return end
RAN2 functionran2(idum) dimensionir(97) = = parameter(m=7l4Q25,ia=1366,ic 150889'rm I /m)
=284| L'rnL= |' I nO) = i.rut.,., i"A = nUSA,iA 8i2l,iO
dataiff/0i then if (idumlt.0.oriff.eg.0) iff= I idum=mod(ic-idum,m) d o1 l j = l ' 9 ? + ic,m) idum= mod(ia+idum ir() = 16un' contlnue ll * ic'm) idum=mod(ia*idum iY= idum endif j = I +(97+iy)/m if (.gt.97.or.j.lt.l) Pause c iy = ir(i) ran2= iy*rm + ic'm) i4um= rnod(ia*idum ir()=i6ut retum end
513
RAN3 functionran3(idum) parameter(mbig= 1000000000. = I 6I g0339g, mseed mz= 0.fac= I ./mbig) dimensionma(55) dataiff/Ot if (idum.lt.0.or.iff.eq.0) then iff= I mj =mseed-iabs(idum) mj=mod(mj,mbig) ma(55)=mj mk=l doll i=1.54 ii=mod(21*i,55) ma(ii)=61 mk=mj-mk if (mk.lt.mz) mk=mk*mbig. mj=ma(ii) ll continue d o 1 3k = 1 , 4 d o 1 2i = 1 , 5 5 ma(i)= 631;1-^a( I +mod(i+30,5$) if (ma(i). lr.mz)ma(i)=rnx1;; a 11t!t, 12 continue 13 continue inext=0 inextP=31 idum=I endif inext=inext*I if (inext.eq.56) inext=I inextp:;ng1pr.1 if (inextp.eq.56) inextp=1 mj = ma(inext)-ma(inextp) if (mj.lt.mz)mj:mj +mbig rn(inext)=6j ran3:mj*fac relum end
514
