Lagged Fibonacci Generator
บทความนี้ต้องการการจัดหน้า จัดหมวดหมู่ ใส่ลิงก์ภายใน หรือเก็บกวาดเนื้อหา ให้มีคุณภาพดีขึ้น คุณสามารถปรับปรุงแก้ไขบทความนี้ได้ และนำป้ายออก พิจารณาใช้ป้ายข้อความอื่นเพื่อชี้ชัดข้อบกพร่อง |
Lagged Fibonacci generator (LFG) เป็นตัวอย่างหนึ่งของ pseudorandom number generator ( ซึ่งเป็นหนึ่งในคลาสของ random number generator ) ในคลาสของ random number generator นั้นมีเป้าหมายเพื่อที่จะ ปรับปรุงและพัฒนาบนพื้นฐานของ linear congruential generator ซึ่งทั้งหมดเหล่านี้ก็อยู่บนพื้นฐานของ ลำดับของ Fibonacci ( Fibonacci Sequence )
ลำดับของ Fibonacci สามารถเขียนอยู่ในรูปแบบ ของความสัมพันธ์แบบเวียนเกิด ( recurrence relation ) ได้ดังนี้
Sn = Sn − 1 + Sn − 2
จากความสัมพันธ์ที่เขียนอยู่ในรูปสมการ ข้างต้นนั้น จะเห็นได้ว่า พจน์ใหม่เกิดขึ้นจาก ผลรวมของสองพจน์ก่อนหน้ในลำดับ ซึ่งเราสามารถทำให้อยู่ในรูปแบบของลำดับทั่วไปได้ดังนี้
Sn = Sn-j * Sn-k ( mod m ), 0<j<k
จากลำดับที่แสดงนี้จะเห็นได้ว่า พจน์ใหม่ที่เกิดขึ้น มาจาก สองพจน์ใดๆก่อนหน้า มากระทำการทางคณิตศาสตร์ อธิบายจากสมการของลำดับทั่วไปด้านบน - m คือตัวแปรที่ โดยส่วนใหญ่จะอยู่ในรูปของ ยกกำลังของ 2 (m = 2m; ตัวอย่างเช่น 232 หรือ 264) - * คือเครื่องหมายตัวกระทำการ ที่ใช้ในระบบของเลขฐานสอง ซึ่งอาจจะเป็นเครื่องหมาย การบวก ,การลบ,การคูณ หรือเครื่องหมายทางตรรกศาสตร์ เช่น XOR ( Exclusive-OR)
จะเห็นได้ว่าจากทฤษฎีนี้ค่อนข้างจะซับซ้อน และ การที่จะเลือกค่าสุ่มของ j และ k ก็ไม่ใช่เรื่องที่ง่ายนัก และยังมีแนวโน้มที่จะเกิดความยุ่งยากได้ง่ายอีกด้วย
ถ้าเครื่องหมาย * เป็นการบวก เราก็จะเรียกว่า Additive Lagged Fibonacci Generator หรือ ALFG ถ้าเครื่องหมาย * เป็นการคูณ เราก็จะเรียกว่า Multiplicative Lagged Fibonacci Generator หรือ MLFG ถ้าเครื่องหมาย * เป็น XOR เราก็จะเรียกว่า Two-tap generalised feedback shift register or GFSR ( ซึ่ง Mersenne twister algorithm ก็ใช้ GFSR ในขั้นตอนของการแก้ปัญหา )
คุณสมบัติของ lagged Fibonacci generators
Lagged Fibonacci generators นั้นมีข้อจำกัดของค่าที่มากที่สุดคือ (2k - 1)*2M-1 ถ้าเป็นในกรณีของการบวก และการลบ และ (2k-1)*k ถ้าเป็นการ XOR กันของค่าใดๆก่อนหน้า ส่วนช่วงของการคูณนั้น คือ (2k - 1)*2M-3 หรือ 1/4 ของการบวกนั่นเอง
เพื่อความง่ายต่อการเข้าใจของค่าสูงสุด สามารถเขียนอยู่ในรูปพหุนามได้ดังนี้
- y = xk + xj + 1
จากสมการพุนามเบื้องต้นต้องเป็นเลขจำนวนเต็มที่ mod ด้วยสอง ส่วนค่าของ j และ k ที่เป็นที่นิยมใช้กันและถูกตีพิมพ์ลงในตำราทางวิชาการ เช่น
- {j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159} [1], {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521}, {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 1279} [2]
จะเห็นได้ว่าจำนวนที่มีขนาดเล็กจะมีช่วงที่สั้น ( จะมีเพียงไม่กี่จำนวนที่เป็นจำนวนทสุ่มที่ถูกสร้างขึ้น ก่อนจำนวนสุ่มตัวแรกที่จะนำมาใช้อีกในลำดับใหม่)
มันเป็นสิ่งที่จำเป็นที่อย่างน้อยหนึ่งค่าของค่า k ตัวแรกที่ถูกเลือกเพื่อเป็นค่าเริ่มต้นเป็นจำนวนคี่
ค่าอัตราส่วนระหว่าง j และ k ที่ควรจะอยู่ในช่วงของ "อัตราส่วนทอง (golden ratio.)"
ปัญหาของ LFGs
การเริ่มต้นของปัญหา LFG นั้นค่อนข้างจะซับซ้อน และช่วงของค่าสูงสุดใดๆของ LFG มีจำนวนของลำดับที่เป็นไปได้ที่แตกต่างกันมากมาย แต่วิธีการทำเช่นนี้อาจจะเป็นผลเสียของผลที่เกิดขึ้นตามมา อีกประการหนึ่งค่าผลลัพธ์ที่เกิดขึ้นของลำดับ LFG ค่อนข้างจะไวต่อเงื่อนไขเริ่มต้น รวมถึงข้อบกพร่องทางสถิติที่อาจเกิดขึ้น แต่ก็เกิดขึ้นเป็นบางช่วงของผลลัพธ์ของลำดับ เว้นแต่จะมีการรองรับที่จะแก้ไขปัญหาที่อาจเกิดขึ้น อีกปัญหาที่อาจเกิดขึ้นกับ LFGs เป็นที่ทฤษฎีทางคณิตศาสตร์ที่ไม่สมบูรณ์ทำให้มันจำเป็นที่จะต้องพึ่งพาการทดสอบทางสถิติมากกว่าประสิทธิภาพทางทฤษฎี ด้วยเหตุผลเหล่านี้ รวมทั้งมี ขั้นตอนวิธีของ Mersenne twister ( Mersenne twister algorithm ) ที่มีประสิทธิภาพจึงมีแนวโน้มที่ขั้นตอนวิธีอื่นที่เหนือกว่าจะถูกเลือก
รหัสเทียมของ LFGs
เป็นตัวอย่างของรหัสในภาษา C++ ;
sub lfib{ my ($m, $r, $k, $op, $seed) = @_; my (@x, $i); srand($seed ||time); #initialise state with rand for (0 .. $r){ push @x, int(rand($m)); } my $fn = "sub { \$i = (\$i + 1) % $r; \$x[\$i] = (\$x[\$i] $op \$x[(\$i-$k) % $r]) % $m; (shift || 1.0) * \$x[\$i] / $m; }\n"; return eval($fn); }
$rand = lfib(2**48, 607, 273, '+'); #additive LFib, period 2 ** 638 $rand2 = lfib(2**64, 1279, 861, '*');#multiplicative LFib, period 2 ** 1340
print &$rand(100) . "\n" . &$rand2() ."\n";
ตัวอย่างของรหัสในภาษาจาวา
public int getRandom(){ Random generator = new Random(); int j = generator.nextInt(90); int k = generator.nextInt(90); int max = Math.max(j, k); int min = Math.min(j, k);
//Fibo is an array that contain Fibonacci's serie long rnd = (fibo[min] + fibo[max])%6 + 1; return (int)rnd; }
การนำไปใช้
- Freeciv ใช้ lagged Fibonacci generator โดยใช้ค่า {j = 24, k = 55} ในการทำ random number generator.
- The Boost library กล่าวถึงการใช้และการดำเนินการของ lagged Fibonacci generator.
- The Oracle Databaseได้นำ LFG ไปใช้ใน DBMS_RANDOM package (available in Oracle 8 and newer versions).
- .NET CLR ได้นำ lagged Fibonacci generator ไปใช้ใน System.Random generator (http://msdn.microsoft.com/en-us/library/system.random.aspx).
แหล่งข้อมูลอื่นๆ
- Linear congruential generator
- Mersenne twister
- FISH (cipher)
- Pike
- VIC cipher
อ้างอิง
- "Uniform random number generators for supercomputers", Richard Brent, Proc. of Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992, pp. 704-706