Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ตัวสร้างความสอดคล้องแบบเชิงเส้น (อังกฤษ: Linear Congruential Generators : LCG) เป็นหนึ่งในขั้นตอนวิธีที่นิยมใช้งานของตัวสร้างเลขสุ่มเทียม (pseudorandom number generator: PRNG) ซึ่งเป็นการสร้างตัวสุ่มโดยใช้ (Recurrence Relation) ที่มีความสัมพันธ์ดังนี้
- "Xn+1 = (aXn + c) mod m" โดยที่
- Xn เป็นลำดับของตัวเลขสุ่ม
- n คือลำดับของตัวเลขสุ่มซึ่งเป็นจำนวนนับ (n = 0 ถือว่าเป็นค่าเริ่มต้น)
- m คือตัวที่นำไปหาเศษ เป็นจำนวนเต็มที่มีค่ามากกว่า 0
- a คือตัวคูณ เป็นจำนวนเต็มที่มีค่ามากกว่า 0 แต่น้อยกว่า m
- c คือตัวบวก เป็นจำนวนเต็มที่มีค่ามากกว่าเท่ากับ 0 แต่น้อยกว่า m
- X0 คือ ค่าเริ่มต้น (seed) มีค่ามากกว่า 0 แต่น้อยกว่า m
- หมายเหตุ y mod m จะมีค่าเท่ากับเศษที่ได้จากการหาร y ด้วย m ยกตัวอย่างเช่น 13 mod 3 จะมีค่าเท่ากับ 1 เพราะ 13 หาร 3 ไม่ลงตัว แต่เหลือเศษอยู่ 1
การใช้งาน
ตัวเลขสุ่มที่ได้จากความสัมพันธ์ข้างต้น คือค่าของ Xn+1 ซึ่งเป็นผลที่ได้มาจากค่าของตัวเลขสุ่มลำดับก่อนหน้า (Xn) แสดงว่าทุกตัวเลขสุ่มที่สุ่มได้ออกมานั้นเป็นผลลัพธ์ที่ได้จากเลขสุ่มตัวก่อนหน้าเสมอ ดังนั้น X1 คือเลขสุ่มตัวแรกที่ได้ออกมาจากความสัมพันธ์นี้โดยที่มีค่าเริ่มต้นคือ (X0)
จากข้อสังเกตข้างต้นจะสรุปได้ว่าถ้าเริ่มต้นด้วยค่าเริ่มต้นเดียวกัน ลำดับของตัวเลขสุ่มที่มาจาก ความสัมพันธ์นี้ที่มีค่า X0, a, c และ m เป็นตัวเลขชุดเดียวกันจะมีลำดับเหมือนกันเสมอ
ซึ่งถ้าดูจากความสัมพันธ์ Xn+1 = (aXn + c) mod m แล้ว จะเห็นว่าเป็นความสัมพันธ์ที่ทำความข้าใจได้ง่าย ไม่ซับซ้อน และสามารถเขียนรหัสได้ง่ายจึงเป็นนิยมใช้กันอย่างแพร่หลาย
ขนาดของคาบ
คาบ (ในที่นี้หมายถึงค่าสูงสุด) ของตัวสร้างความสอดคล้องแบบเชิงเส้นจะมีค่าได้สูงสุดเกือบเท่ากับ m(ขอเรียกว่า คาบแบบสูง) แต่ก็มีบางส่วนที่มีค่าต่ำกว่านั้นมาก ถ้ากำหนดให้ c เป็นจำนวนเต็มที่มีค่ามากกว่า 0 แล้ว ตัวสร้างความสอดคล้องแบบเชิงเส้น จะมีคาบแบบสูงในทุก ๆ ค่าเริ่มต้น (seed) ก็ต่อเมื่อ
- c และ m ไม่มีตัวร่วมร่วมกัน
- ตัวประกอบที่เป็นจำนวนเฉพาะทุกตัวของ m จะสามารถหาร a-1 ได้ลงตัว
- a จะเป็นพหุคูณของ 4 ถ้า m เป็นพหุคูณของ 4 ด้วย
ถึงแม้ว่าตัวสร้างความสอดคล้องแบบเชิงเส้นจะมีความสามารถในการสร้างตัวเลขสุ่มเทียมได้เป็นอย่างดี แต่ว่ามันก็มีความละเอียดอ่อนมากในการเลือกค่าของ a, c และ m ดังนั้นจึงต้องเลือกค่าต่าง ๆ ดังกล่าวให้ดี เพื่อให้ตัวสร้างความสอดคล้องแบบเชิงเส้นทำงานได้ดีตามที่ต้องการ
ตัวอย่างค่าของ a, c และ m ที่ใช้กันทั่วไป
โดยมาก ค่าของ m ที่ใช้ในการสร้างตัวสร้างความสอดคล้องแบบเชิงเส้นจะมีค่าเปนค่าที่เป็นค่า 2 ยกกำลังซึ่งส่วนใหญ่เป็นค่า 232 หรือ 264 เพราะสามารถคำนวณผ่านคอมพิวเตอร์ได้โดยการชิฟขวาไป 32 หรือ 64 บิตตามลำดับ ตารางด้านล่างนี้จะแสดงถึงค่าที่ใช้กันโดยทั่วไป รวมทั้งค่าที่อยู่ในรันไทม์ไลบราลี่ (Runtime Libraries) ของคอมไพเลอร์ต่าง ๆ
| ที่มา | ค่า m | ค่า a | ค่า c | บิตผลลัพธ์ของค่าเริ่มต้น |
|---|---|---|---|---|
| Borland สำหรับภาษาซีและซีพลัสพลัส | 232 | 22695477 | 1 | บิตที่ 30 ถึง 16 ในฟังก์ชัน rand() และ บิตที่ 30 ถึง 0 ในฟังก์ชัน lrand() |
| glib (ใช้ใน GCC ) | 232 | 1103515245 | 12345 | บิตที่ 30 ถึง 0 |
| Borland สำหรับภาษาเดลฟี | 232 | 134775813 | 1 | บิตที่ 63 ถึง 32 ของค่าเริ่มต้น |
| Apple Carbonlib | 231 - 1 | 16807 | 7 | |
| Microsoft Visual Basic (รุ่น 6 หรือก่อนหน้า) | 224 | 1140671485 | 12820163 |
รหัสเทียม
เนื่องจากตัวสร้างความสอดคล้องแบบเชิงเส้นนั้นเกิดจากความสัมพันธ์ในรูปแบบที่เข้าใจได้ง่าย ดังนั้นรหัสเทียมที่เขียนจึงมีเพิ่มขึ้นมาเพียงกำหนดค่าให้กับ a, c และ m เท่านั้นซึ่งมีรหัสเทียมดังนี้
//รหัสเทียมในส่วนของตัวสร้างความสอดคล้องแบบเชิงเส้นที่ใช้ในคลาส Random ในภาษาจาวา seed = (seed * 0x5DEECE66DL + 0xBL) mod ((1L << 48) - 1); //ซึ่งใช้ a = 0x5DEECE66D (เลขฐานสิบ คือ 25214903917) // c = 0xB (เลขฐานสิบ คือ 11) // m = 1L << 48 คือการเลื่อนบิตของเลข 1 ไปทางซ้ายเป็นจำนวน 48 บิตซึ่งได้เป็นเลขฐานสิบคือ 248
ตัวอย่างการใช้งาน
ดังที่ได้กล่าวในหัวข้อรหัสเทียมแล้ว ตัวสร้างความสอดคล้องแบบเชิงเส้นใช้ในการทำงานของ เมท้อด next ในคลาส Random ในภาษาจาวา ซึ่งรหัสของเมท้อดดังกล่าวเป็นดังนี้
synchronized protected int next(int bits) { seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); return (int)(seed >>> (48 - bits)); } จะเห็นว่าในบรรทัดที่ 2 ของรหัสเป็นรหัสในส่วนที่ใช้สร้างตัวเลขสุ่มแบบการสร้างความสอดคล้องแบบเชิงเส้นดังที่ได้กล่าวไว้ในหัวข้อรหัสเทียมแล้ว
ซึ่งไม่ได้มีเพียงภาษาจาวาเท่านั้น ภาษาคอมพิวเตอร์อื่น ๆ ก็นำเอาขั้นตอนวิธีการสร้างความสอดคล้องแบบเชิงเส้นนี้ไปใช้ด้วยเช่นกัน
อ้างอิง
- S.K. Park and K.W. Miller (1988). "Random Number Generators: Good Ones Are Hard To Find". . 31 (10): 1192–1201. doi:10.1145/63039.63042.
- D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. . Section 3.2.1: The Linear Congruential Method, pp. 10–26.
- P. L'Ecuyer (1999). "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure". . 68 (225): 249–260. doi:10.1090/S0025-5718-99-00996-5.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), , Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN , คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-08-11, สืบค้นเมื่อ 2011-09-28
- Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods, 2nd edition , Springer, .
- Joan Boyar (1989). "Inferring sequences produced by pseudo-random number generators". . 36 (1): 129–141. doi:10.1145/58562.59305. (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).
แหล่งข้อมูลอื่น
- http://www.bloggang.com/viewblog.php?id=zkaru&date=04-10-2008&group=3&gblog=4
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
twsrangkhwamsxdkhlxngaebbechingesn xngkvs Linear Congruential Generators LCG epnhnunginkhntxnwithithiniymichngankhxngtwsrangelkhsumethiym pseudorandom number generator PRNG sungepnkarsrangtwsumodyich Recurrence Relation thimikhwamsmphnthdngni Xn 1 aXn c mod m odythi dd Xn epnladbkhxngtwelkhsum n khuxladbkhxngtwelkhsumsungepncanwnnb n 0 thuxwaepnkhaerimtn m khuxtwthinaiphaess epncanwnetmthimikhamakkwa 0 a khuxtwkhun epncanwnetmthimikhamakkwa 0 aetnxykwa m c khuxtwbwk epncanwnetmthimikhamakkwaethakb 0 aetnxykwa m X0 khux khaerimtn seed mikhamakkwa 0 aetnxykwa m dd hmayehtu y mod m camikhaethakbessthiidcakkarhar y dwy m yktwxyangechn 13 mod 3 camikhaethakb 1 ephraa 13 har 3 imlngtw aetehluxessxyu 1 dd karichngantwelkhsumthiidcakkhwamsmphnthkhangtn khuxkhakhxng Xn 1 sungepnphlthiidmacakkhakhxngtwelkhsumladbkxnhna Xn aesdngwathuktwelkhsumthisumidxxkmannepnphllphththiidcakelkhsumtwkxnhnaesmx dngnn X1 khuxelkhsumtwaerkthiidxxkmacakkhwamsmphnthniodythimikhaerimtnkhux X0 cakkhxsngektkhangtncasrupidwathaerimtndwykhaerimtnediywkn ladbkhxngtwelkhsumthimacak khwamsmphnthnithimikha X0 a c aela m epntwelkhchudediywkncamiladbehmuxnknesmx sungthaducakkhwamsmphnth Xn 1 aXn c mod m aelw caehnwaepnkhwamsmphnththithakhwamkhaicidngay imsbsxn aelasamarthekhiynrhsidngaycungepnniymichknxyangaephrhlaykhnadkhxngkhabkhab inthinihmaythungkhasungsud khxngtwsrangkhwamsxdkhlxngaebbechingesncamikhaidsungsudekuxbethakb m khxeriykwa khabaebbsung aetkmibangswnthimikhatakwannmak thakahndih c epncanwnetmthimikhamakkwa 0 aelw twsrangkhwamsxdkhlxngaebbechingesn camikhabaebbsunginthuk khaerimtn seed ktxemux c aela m immitwrwmrwmkn twprakxbthiepncanwnechphaathuktwkhxng m casamarthhar a 1 idlngtw a caepnphhukhunkhxng 4 tha m epnphhukhunkhxng 4 dwy dd thungaemwatwsrangkhwamsxdkhlxngaebbechingesncamikhwamsamarthinkarsrangtwelkhsumethiymidepnxyangdi aetwamnkmikhwamlaexiydxxnmakinkareluxkkhakhxng a c aela m dngnncungtxngeluxkkhatang dngklawihdi ephuxihtwsrangkhwamsxdkhlxngaebbechingesnthanganidditamthitxngkartwxyangkhakhxng a c aela m thiichknthwipodymak khakhxng m thiichinkarsrangtwsrangkhwamsxdkhlxngaebbechingesncamikhaepnkhathiepnkha 2 ykkalngsungswnihyepnkha 232 hrux 264 ephraasamarthkhanwnphankhxmphiwetxridodykarchifkhwaip 32 hrux 64 bittamladb tarangdanlangnicaaesdngthungkhathiichknodythwip rwmthngkhathixyuinrnithmilbrali Runtime Libraries khxngkhxmiphelxrtang thima kha m kha a kha c bitphllphthkhxngkhaerimtnBorland sahrbphasasiaelasiphlsphls 232 22695477 1 bitthi 30 thung 16 infngkchn rand aela bitthi 30 thung 0 infngkchn lrand glib ichin GCC 232 1103515245 12345 bitthi 30 thung 0Borland sahrbphasaedlfi 232 134775813 1 bitthi 63 thung 32 khxngkhaerimtnApple Carbonlib 231 1 16807 7Microsoft Visual Basic run 6 hruxkxnhna 224 1140671485 12820163rhsethiymenuxngcaktwsrangkhwamsxdkhlxngaebbechingesnnnekidcakkhwamsmphnthinrupaebbthiekhaicidngay dngnnrhsethiymthiekhiyncungmiephimkhunmaephiyngkahndkhaihkb a c aela m ethannsungmirhsethiymdngni rhsethiyminswnkhxngtwsrangkhwamsxdkhlxngaebbechingesnthiichinkhlas Random inphasacawa seed seed 0x5DEECE66DL 0xBL mod 1L lt lt 48 1 sungich a 0x5DEECE66D elkhthansib khux 25214903917 c 0xB elkhthansib khux 11 m 1L lt lt 48 khuxkareluxnbitkhxngelkh 1 ipthangsayepncanwn 48 bitsungidepnelkhthansibkhux 248twxyangkarichngandngthiidklawinhwkhxrhsethiymaelw twsrangkhwamsxdkhlxngaebbechingesnichinkarthangankhxng emthxd next inkhlas Random inphasacawa sungrhskhxngemthxddngklawepndngni synchronized protected int next int bits seed seed 0x5DEECE66DL 0xBL amp 1L lt lt 48 1 return int seed gt gt gt 48 bits caehnwainbrrthdthi 2 khxngrhsepnrhsinswnthiichsrangtwelkhsumaebbkarsrangkhwamsxdkhlxngaebbechingesndngthiidklawiwinhwkhxrhsethiymaelw sungimidmiephiyngphasacawaethann phasakhxmphiwetxrxun knaexakhntxnwithikarsrangkhwamsxdkhlxngaebbechingesnniipichdwyechnknxangxingS K Park and K W Miller 1988 Random Number Generators Good Ones Are Hard To Find 31 10 1192 1201 doi 10 1145 63039 63042 D E Knuth The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition Addison Wesley 1997 ISBN 0 201 89684 2 Section 3 2 1 The Linear Congruential Method pp 10 26 P L Ecuyer 1999 Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure 68 225 249 260 doi 10 1090 S0025 5718 99 00996 5 Press WH Teukolsky SA Vetterling WT Flannery BP 2007 Numerical Recipes The Art of Scientific Computing 3rd ed New York Cambridge University Press ISBN 978 0 521 88068 8 khlngkhxmulekaekbcakaehlngedimemux 2011 08 11 subkhnemux 2011 09 28 Gentle James E 2003 Random Number Generation and Monte Carlo Methods 2nd edition Springer ISBN 0 387 00178 6 Joan Boyar 1989 Inferring sequences produced by pseudo random number generators 36 1 129 141 doi 10 1145 58562 59305 in this paper efficient algorithms are given for inferring sequences produced by certain pseudo random number generators aehlngkhxmulxunhttp www bloggang com viewblog php id zkaru amp date 04 10 2008 amp group 3 amp gblog 4