ตัวสร้างความสอดคล้องแบบเชิงเส้น

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

ตัวสร้างความสอดคล้องแบบเชิงเส้น (อังกฤษ: 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) ก็ต่อเมื่อ

  1. c และ m ไม่มีตัวร่วมร่วมกัน
  2. ตัวประกอบที่เป็นจำนวนเฉพาะทุกตัวของ m จะสามารถหาร a-1 ได้ลงตัว
  3. 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". Communications of the ACM. 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". Mathematics of Computation. 68 (225): 249&ndash, 260. doi:10.1090/S0025-5718-99-00996-5.
  • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 7.1.1. Some History", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
  • 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". Journal of the ACM. 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).

แหล่งข้อมูลอื่น[แก้]