เมนูนำทาง
แมร์แซนทวิสเตอร์ รายละเอียดของขั้นตอนวิธีขั้นตอนวิธีแมร์แซน ทวิสเตอร์นั้นคือวิธีชิฟท์รีจิสเตอร์ป้อนกลับแบบทั่วไป (Generalised feedback shift register) ซึ่งผ่านการดัดแปลง (twisted GFSR หรือ TGFSR) ของรูปแบบปกติตรรกยะ (rational normal form) (TGFSR(R)) ที่มีสถานะการสะท้อนและลดลงของบิต (state bit reflection and tempering) ซึ่งมีลักษณะพิเศษดังต่อไปนี้
ด้วยข้อจำกัดที่ว่า 2nw-r -1 เป็นจำนวนเฉพาะแมร์แซน (Mersenne prime) จะช่วยทำให้การทดสอบพื้นฐาน (primitivity test) และการทดสอบการกระจาย k (k-distribution test) ซึ่งจำเป็นในการค้นหาพารามิเตอร์ (parameter search) นั้นง่ายขึ้น
สำหรับ word x ที่มีขนาด w บิตสามารถนำมาเขียนเป็นความสัมพันธ์เวียนเกิดได้ดังนี้
โดย | คือ bitwise or และ คือ bitwise exclusive or (XOR) xu, xl เป็น x ที่มีบิตมาสก์ระดับสูงกว่าและต่ำกว่าตามลำดับ การแปลงแบบดัดแปลง (twist transformation) A นั้นถูกนิยามโดยรูปแบบปกติตรรกยะ (rational normal form)
โดย In-1 คือเมทริกซ์เอกลักษณ์มีมิติ (n - 1)*(n - 1) (มีความแตกต่างกับการคูณเมทริกซ์แบบปกติคือใช้การดำเนินการ XOR แบบ bitwise แทนการบวก) รูปแบบปกติตรรกยะ (rational normal form) มีประโยชน์ตรงที่สามารถแสดงได้ในรูปแบบดังต่อไปนี้
โดยในการที่จะหาขีดจำกัดบนทางทฤษฎี 2nw-r-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 = T-1RT โดยสามารถหาตัวผกผันของ T (T-1) ได้ การแปลงที่ลดลงนั้นถูกกำหนดไว้ในกรณีของแมร์แซน ทวิสเตอร์ ดังนี้
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 ได้แก่
เมนูนำทาง
แมร์แซนทวิสเตอร์ รายละเอียดของขั้นตอนวิธีใกล้เคียง
แมร์แซนทวิสเตอร์ แมร์แยม มีร์ซอฆอนี แมร์แยม อีมอนีเยฮ์ แมร์แนปทาห์ แอร์แคนาดา แมร์ฮัยแรนิค แฌร์แม็ง กาต็องกา แอร์แบร์ที่ 2 เคานต์แห่งแวร์ม็องดัว แฮร์แบร์ท ฟ็อน คารายัน แมรีแห่งโมดีนาแหล่งที่มา
WikiPedia: แมร์แซนทวิสเตอร์ http://www.tecgraf.puc-rio.br/~lhf/ftp/lua/ http://www.iro.umontreal.ca/~lecuyer/myftp/papers/... http://adrianhoe.com/adrianhoe/projects/adamt19937... http://cybertiggyr.com/gene/jmt/ http://groups.google.com/group/comp.lang.c/browse_... http://groups.google.com/group/sci.crypt/browse_th... http://www.hackinghat.com/index.php/lisp/mersenne-... http://archive.msdn.microsoft.com/MersenneTwister http://www.mitrionics.com/?page=mersenne http://www.ntrand.com/