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

ตัวสร้างความสอดคล้องแบบเชิงเส้น () เป็นหนึ่งในขั้นตอนวิธีที่นิยมใช้งานของตัวสร้างเลขสุ่มเทียม (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 ของรหัสเป็นรหัสในส่วนที่ใช้สร้างตัวเลขสุ่มแบบการสร้างความสอดคล้องแบบเชิงเส้นดังที่ได้กล่าวไว้ในหัวข้อรหัสเทียมแล้ว

ซึ่งไม่ได้มีเพียงภาษาจาวาเท่านั้น ภาษาคอมพิวเตอร์อื่น ๆ ก็นำเอาขั้นตอนวิธีการสร้างความสอดคล้องแบบเชิงเส้นนี้ไปใช้ด้วยเช่นกัน

 อ้างอิง 


 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.


Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods, 2nd edition , Springer, ISBN 0-387-00178-6.
  (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

หมวดหมู่:เลขคณิตมอดุลาร์
หมวดหมู่:ตัวสร้างเลขสุ่มเทียม