แมร์แซนทวิสเตอร์
แมร์แซน ทวิสเตอร์ () เป็นขั้นตอนวิธีหนึ่งของตัวสร้างเลขสุ่มเทียม (pseudorandom number generator) ถูกพัฒนาขึ้นในปี 1997 โดยมาโคโตะ มัตซูโมโตะ (Makoto Matsumoto) และทาคูจิ นิชิมูระ (Takuji Nishimura) มีพื้นฐานมาจากความสัมพันธ์เวียนเกิดเชิงเส้นของเมทริกซ์ (Matrix linear recurrence) ของฟิลด์เลขฐานสอง F (binary field) ขั้นตอนวิธีเมอแซนน์ ทวิสเตอร์นี้สามารถหาตัวเลขเชิงสุ่มเทียม (pseudorandom numbers) ได้อย่างรวดเร็วและมีประสิทธิภาพ โดยได้รับการออกแบบมาโดยเฉพาะเพื่อแก้ไขข้อบกพร่องหลายอย่างที่พบในขั้นตอนวิธีเก่า
ชื่อแมร์แซน ทวิสเตอร์ นั้นมาจากช่วงของเลขที่จะสุ่มซึ่งเลือกมาจาก จำนวนเฉพาะแมร์แซน (Mersenne prime) มีแมร์แซน ทวิสเตอร์อย่างน้อย 2 แบบ ที่ใช้กันอย่างแพร่หลาย แตกต่างกันที่ขนาดของจำนวนเฉพาะแมร์แซนที่ใช้เท่านั้น แมร์แซน ทวิสเตอร์แบบที่ใหม่กว่าและนิยมใช้มากกว่าคือแมร์แซน ทวิสเตอร์ MT19937 มีขนาด 32 บิตเวิร์ด นอกจากนี้ยังมี MT19937-64 ซึ่งเป็นแมร์แซน ทวิสเตอร์อีกรูปแบบหนึ่งซึ่งมีความยาวขนาด 64 บิตเวิร์ด สำหรับการหาลำดับที่แตกต่างออกไป
แมร์แซน ทวิสเตอร์สำหรับจำนวนเฉพาะแมร์แซนขนาด k บิตเวิร์ดหาตัวเลขแบบเชิงสุ่มได้ในรูปแบบใกล้เคียงกับการกระจายอย่างสม่ำเสมอ (Uniform distribution) ในช่วง 0 ถึง 2 -1 ([0,2-1])
ขั้นตอนวิธีในรูปแบบพื้นฐานนั้นไม่เหมาะสมในการใช้ในวิทยาการเข้ารหัสลับ (ไม่เหมือนกับ Blum Blum Shub) จากการสังเกตตัวเลขซ้ำๆจำนวนหนึ่ง (624 ในกรณีของ MT19937) สามารถทำให้สามารถคาดเดาตัวเลขซ้ำๆเหล่านี้ในอนาคตได้ มาโคโตะ มัตซูโมโตะอ้างว่าการเข้ารหัสลับโดยอาศัยแมร์แซน ทวิสเตอร์นั้นมีความเร็ว 1.5 ถึง 2 เท่าของมาตรฐานการเข้ารหัสขั้นสูง (Advanced Encryption Standard) ใน counter mode
อีกหนึ่งปัญหาคือเวลาที่นานในการแปลงสถานะเริ่มต้นที่ไม่ใช่แบบเชิงสุ่ม(เช่นกรณีที่มี 0 หลายตัว) ให้เป็นผลลัพธ์ที่ผ่านการตรวจสอบความสุ่ม (Randomness tests) ขั้นตอนวิธีการสร้างเลขฟิโบนัชชีแบบล้าหลัง (Lagged Fibonacci generator) หรือขั้นตอนวิธีการสร้างความสอดคล้องกันแบบเชิงเส้น (Linear congruential generator) มักจะถูกใช้ในการทำให้แมร์แซน ทวิสเตอร์นั้นมีค่าเริ่มต้นแบบสุ่ม
สำหรับหลายๆโปรแกรมประยุกต์ การใช้งานแมร์แซน ทวิสเตอร์มักจะเป็นตัวเลือกที่ดีตัวเลือกหนึ่งในการเลือกใช้ขั้นตอนวิธีสำหรับการสร้างตัวเลขเชิงสุ่ม
แมร์แซน ทวิสเตอร์นั้นถูกออกแบบมาโดยใช้หลักการของขั้นตอนวิธีแบบมอนติคาร์โล (Monte Carlo method) และแบบจำลองทางสถิติอื่นๆเป็นพื้นฐาน เพราะว่านักวิจัยนั้นต้องการตัวเลขที่มีคุณภาพสูง แต่ก็ต้องการประโยชน์จากความเร็วและความสามารถในการนำไปใช้ที่อื่นได้โดยข้อมูลไม่เสียหายและสามารถใช้ได้กับทุกๆที่ด้วย
แมร์แซน ทวิสเตอร์ที่มีการนิยมใช้กันมาก หรือ MT19937 ซึ่งสร้างลำดับของเลขจำนวนเต็มขนาด 32 บิต มีคุณสมบัติดังต่อไปนี้ลำดับของตัวเลขเชิงสุ่ม x ของเลขจำนวนเต็มขนาด w บิต ช่วงกว้าง P จะถูกนิยามว่าเป็นการกระจาย k (k-distributed) ที่มีความแม่นยำได้ v บิต เมื่อต่อไปนี้เป็นจริง
ให้ truncv(x) เป็นตัวเลขที่ถูกสร้างมาจาก v บิตแรกของ x และพิจารณาช่วงกว้าง P ของเวกเตอร์ขนาด kv บิต
จากนั้นการจัดหมู่ที่เป็นไปได้ทั้งหมด 2 รูปแบบ จะเกิดขึ้นเป็นจำนวนครั้งที่เท่ากันในช่วงเวลาหนึ่งๆ ยกเว้นแต่การจัดหมู่ที่เป็น 0 ทั้งหมดซึ่งมีโอกาสเกิดขึ้นน้อยมาก
ขั้นตอนวิธีแมร์แซน ทวิสเตอร์ได้รับการวิพากษ์วิจารณ์ในด้านวิทยาการคอมพิวเตอร์ โดยเฉพาะจากจอร์จ มาร์ซากิลา (George Marsaglia) ว่าถึงแม้จะดีในการหาตัวเลขเชิงสุ่มแต่ว่าซับซ้อนในการนำไปใช้งานจริง Marsaglia ได้ยกตัวอย่างของขั้นตอนวิธีสำหรับการหาตัวเลขเชิงสุ่มที่มีความซับซ้อนน้อยกว่าแต่มีช่วงการพิจารณาที่กว้างกว่า ตัวอย่างเช่นขั้นตอนวิธีคูณแบบมีตัวทด (Multiply-with-carry) ซึ่งมีช่วงกว้าง 10 ซึ่งเร็วกว่าและมีอัตราการสุ่มเทียบเท่าหรือดีกว่า
อีกหนึ่งประเด็นคือแมร์แซน ทวิสเตอร์ นั้นละเอียดอ่อนมากโดยเฉพาะกับการตั้งค่าเริ่มต้นที่ไม่ดี และแมร์แซน ทวิสเตอร์ยังใช้เวลานานในการแก้ไขจากสถานะเริ่มต้นที่มี 0 มากเกินไปให้อยู่ในสถานะที่มีการสุ่มในเกณฑ์ที่ต้องการ ทางเลือกที่ดีกว่าในการแก้ปัญหานี้ได้แก่ WELL(Well equidistributed long-period linear) ซึ่งสามารถแก้ไขปัญหาสถานะเริ่มต้นที่มี 0 มากเกินไปนี้ได้อย่างรวดเร็ว โดยมีประสิทธิภาพที่เท่ากันหรือดีกว่าและมีอัตราการสุ่มที่เท่ากัน
ขั้นตอนวิธีแมร์แซน ทวิสเตอร์นั้นคือวิธีชิฟท์รีจิสเตอร์ป้อนกลับแบบทั่วไป (Generalised feedback shift register) ซึ่งผ่านการดัดแปลง (twisted GFSR หรือ TGFSR) ของรูปแบบปกติตรรกยะ (rational normal form) (TGFSR(R)) ที่มีสถานะการสะท้อนและลดลงของบิต (state bit reflection and tempering) ซึ่งมีลักษณะพิเศษดังต่อไปนี้ด้วยข้อจำกัดที่ว่า 2 -1 เป็นจำนวนเฉพาะแมร์แซน (Mersenne prime) จะช่วยทำให้การทดสอบพื้นฐาน (primitivity test) และการทดสอบการกระจาย k (k-distribution test) ซึ่งจำเป็นในการค้นหาพารามิเตอร์ (parameter search) นั้นง่ายขึ้น
สำหรับ word x ที่มีขนาด w บิตสามารถนำมาเขียนเป็นความสัมพันธ์เวียนเกิดได้ดังนี้
โดย | คือ bitwise or และ คือ bitwise exclusive or (XOR) x, x เป็น x ที่มีบิตมาสก์ระดับสูงกว่าและต่ำกว่าตามลำดับ การแปลงแบบดัดแปลง (twist transformation) A นั้นถูกนิยามโดยรูปแบบปกติตรรกยะ (rational normal form)
โดย I คือเมทริกซ์เอกลักษณ์มีมิติ (n - 1)*(n - 1) (มีความแตกต่างกับการคูณเมทริกซ์แบบปกติคือใช้การดำเนินการ XOR แบบ bitwise แทนการบวก) รูปแบบปกติตรรกยะ (rational normal form) มีประโยชน์ตรงที่สามารถแสดงได้ในรูปแบบดังต่อไปนี้
โดย
ในการที่จะหาขีดจำกัดบนทางทฤษฎี 2-1 ใน TGFSR ได้นั้น φB(t) ต้องเป็นพหุนามแบบพื้นฐาน (Primitive polynomial) และ φB(t) เป็นพหุนามลักษณะเฉพาะ (Characteristic polynomial) ของ
การแปลงแบบดัดแปลง (twist transformation) ช่วยทำให้ GFSR ดีขึ้นได้โดยคุณสมบัติที่สำคัญดังต่อไปนี้เฉกเช่น TGFSR(R) แมร์แซน ทวิสเตอร์ ถูกลดหลั่นด้วยการแปลงที่ลดลง (tempering transform) เพื่อชดเชยการลดมิติของการกระจายที่มีความถี่ในการเกิดเท่ากัน(Equidistribution) (เพราะว่า A อยู่ในรูปแบบปกติตรรกยะ(rational normal form)) ซึ่งจะสมมูลกับการแปลง A = R → A = TRT โดยสามารถหาตัวผกผันของ T (T) ได้ การแปลงที่ลดลงนั้นถูกกำหนดไว้ในกรณีของแมร์แซน ทวิสเตอร์ ดังนี้
y := x ⊕ (x » u)
y := :y ⊕ ((y « s) & b)
y := :y ⊕ ((y « t) & c)
z := y ⊕ (y » l)
โดย « และ » เป็นการชิฟท์ซ้ายแบบ bitwise และชิฟท์ขวาแบบ bitwise ตามลำดับ และ & เป็นการดำเนินการ bitwise and การแปลงในบรรทัดแรกและบรรทัดสุดท้ายถูกเพิ่มมาเพื่อเพิ่มประสิทธิภาพของการกระจายที่มีความถี่ในการเกิดเท่ากัน (Equidistribution) ในบิตล่าง ซึ่งเป็นคุณลักษณะของ TGFSR มีความจำเป็นในการที่จะไปให้ถึงขีดจำกัดบนของการกระจายที่มีความถี่ในการเกิดเท่ากัน สำหรับบิตบน
ค่าสัมประสิทธ์สำหรับ MT19937 ได้แก่
รหัสเทียมต่อไปนี้ถูกสร้างมาจากการกระจายแบบปกติ (uniformly distributed) ของเลขจำนวนเต็ม 32 บิตในช่วง [0, 2 − 1] ด้วย MT19937
SFMT หรือ แมร์แซน ทวิสเตอร์แบบเร็วที่เน้นกับการใช้ใน SIMD (Single instruction, multiple data : หนึ่งคำสั่งต่อหลายข้อมูล) เป็นแมร์แซน ทวิสเตอร์อีกรูปแบบหนึ่งที่ถูกออกแบบมาเมื่อปี 2006 เพื่อให้สามารถทำงานได้รวดเร็วเมื่อรันบน SIMD ขนาด 128 บิต โดยมีคุณสมบัติดังนี้อินเทล SSE2 และ PowerPC AltiVec นั้นได้รับการสนับสนุนจาก SFMT นอกจากนี้ SFMT ยังถูกใช้สำหรับอุตสาหกรรมเกม เช่น โปรเซสเซอร์ Cell BE สำหรับเครื่องเล่นเกมเพลย์สเตชัน 3