แมร์แซนทวิสเตอร์

แมร์แซน ทวิสเตอร์ (อังกฤษ: Mersenne twister) เป็นขั้นตอนวิธีหนึ่งของตัวสร้างเลขสุ่มเทียม (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^k -1 ([0,2^k-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 บิต มีคุณสมบัติดังต่อไปนี้

MT19937 มีช่วงที่กว้างมาก (2¹⁹⁹³⁷ − 1) ถึงแม้ว่าช่วงที่กว้างนี้จะไม่สามารถรับประกันคุณภาพของขั้นตอนวิธีสำหรับการสร้างตัวเลขเชิงสุ่ม แต่ช่วงที่แคบ (เช่น 2³² ซึ่งใช้มากในซอฟต์แวร์) อาจเป็นปัญหาได้
MT19937 การกระจาย k (k-distributed) แบบ 32 บิต นั้นมีความแม่นยำทุกๆช่วง 1 ≤ k ≤ 623
MT19937 ผ่านหลายๆการทดสอบสำหรับความสุ่มทางสถิติ รวมถึงการทดสอบ Diehard tests แต่ไม่ได้ผ่านการทดสอบมั้งหมด

การกระจาย k แก้

ลำดับของตัวเลขเชิงสุ่ม x_i ของเลขจำนวนเต็มขนาด w บิต ช่วงกว้าง P จะถูกนิยามว่าเป็นการกระจาย k (k-distributed) ที่มีความแม่นยำได้ v บิต เมื่อต่อไปนี้เป็นจริง

ให้ truncv(x) เป็นตัวเลขที่ถูกสร้างมาจาก v บิตแรกของ x และพิจารณาช่วงกว้าง P ของเวกเตอร์ขนาด kv บิต

จากนั้นการจัดหมู่ที่เป็นไปได้ทั้งหมด 2^kv รูปแบบ จะเกิดขึ้นเป็นจำนวนครั้งที่เท่ากันในช่วงเวลาหนึ่งๆ ยกเว้นแต่การจัดหมู่ที่เป็น 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) ซึ่งมีลักษณะพิเศษดังต่อไปนี้

w: ขนาดของเวิร์ด (จำนวนบิต)
n: ดีกรีของการปรากฏซ้ำ (degree of recurrence)
m: คำกลาง หรือตัวเลขของลำดับแบบขนาน (middle word, or the number of parallel sequences) , 1 ≤ m ≤ n
r: จุดแยกคำหรือจำนวนบิตในบิตมาสก์ระดับต่ำกว่า (separation point of one word, or the number of bits of the lower bitmask) , 0 ≤ r ≤ w - 1
a: สัมประสิทธิ์ของรูปแบบปกติตรรกยะ (rational normal form) จากเมตริกซ์ที่ดัดแปลง (twist matrix)
b, c: TGFSR(R) บิตมาสก์ที่ลดลง (tempering bitmasks)
s, t: TGFSR(R) บิตชิฟท์ที่ลดลง (tempering bit shifts)
u, l: บิตชิฟท์ที่ลดลงเพิ่มเติมของแมร์แซน ทวิสเตอร์ (additional Mersenne Twister tempering bit shifts)

ด้วยข้อจำกัดที่ว่า 2^nw-r -1 เป็นจำนวนเฉพาะแมร์แซน (Mersenne prime) จะช่วยทำให้การทดสอบพื้นฐาน (primitivity test) และการทดสอบการกระจาย k (k-distribution test) ซึ่งจำเป็นในการค้นหาพารามิเตอร์ (parameter search) นั้นง่ายขึ้น

สำหรับ word x ที่มีขนาด w บิตสามารถนำมาเขียนเป็นความสัมพันธ์เวียนเกิดได้ดังนี้

โดย | คือ bitwise or และ คือ bitwise exclusive or (XOR) x^u, x^l เป็น x ที่มีบิตมาสก์ระดับสูงกว่าและต่ำกว่าตามลำดับ การแปลงแบบดัดแปลง (twist transformation) A นั้นถูกนิยามโดยรูปแบบปกติตรรกยะ (rational normal form)

โดย I_n-1 คือเมทริกซ์เอกลักษณ์มีมิติ (n - 1)*(n - 1) (มีความแตกต่างกับการคูณเมทริกซ์แบบปกติคือใช้การดำเนินการ XOR แบบ bitwise แทนการบวก) รูปแบบปกติตรรกยะ (rational normal form) มีประโยชน์ตรงที่สามารถแสดงได้ในรูปแบบดังต่อไปนี้

โดยในการที่จะหาขีดจำกัดบนทางทฤษฎี 2^nw-r-1 ใน TGFSR ได้นั้น φB(t) ต้องเป็นพหุนามแบบพื้นฐาน (Primitive polynomial) และ φB(t) เป็นพหุนามลักษณะเฉพาะ (Characteristic polynomial) ของ

การแปลงแบบดัดแปลง (twist transformation) ช่วยทำให้ GFSR ดีขึ้นได้โดยคุณสมบัติที่สำคัญดังต่อไปนี้

ช่วงของเลขที่จะสุ่มกว้างถึงขีดจำกัดบนทางทฤษฎี 2^nw-r-1 (ยกเว้นกรณีที่เริ่มต้นด้วย 0)
การกระจายที่มีความถี่ในการเกิดเท่ากัน(Equidistribution) ใน n มิติ (เช่น ขั้นตอนวิธีการสร้างความสอดคล้องกันแบบเชิงเส้น (Linear congruential generator) สามารถจัดการได้ถึงแค่การกระจายใน 5 มิติเท่านั้น)

เฉกเช่น 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 ได้แก่

(w, n, m, r) = (32, 624, 397, 31)
a = 9908B0DF₁₆
u = 11
(s, b) = (7, 9D2C5680₁₆)
(t, c) = (15, EFC60000₁₆)
l = 18

รหัสเทียม แก้

รหัสเทียมต่อไปนี้ถูกสร้างมาจากการกระจายแบบปกติ (uniformly distributed) ของเลขจำนวนเต็ม 32 บิตในช่วง [0, 2³² − 1] ด้วย MT19937

// สร้างอาเรย์ขนาด 624 ช่องสำหรับเก็บสถานะของตัวสร้าง
int[0..623] MT
int index = 0

// กำหนดค่าเริ่มต้นของตัวสร้างจากค่าของ seed
function initialize_generator(int seed) {
    MT[0] := seed
    for i from 1 to 623 { //วงวนที่เริ่มตั้งแต่ช่องที่ 1 ของอาเรย์จนถึงช่องสุดท้าย
        MT[i] := 32 บิตสุดท้ายของ (1812433253 * (MT[i-1] xor (ชิฟท์ขวา MT[i-1] ไป 30 บิต)) + i) // 0x6c078965
    }
}

// นำตัวเลขเชิงสุ่มเทียมแบบลดลำดับที่ขึ้นกับค่าดัชนี th ที่ได้ไปใช้
// เรียกใช้ฟังก์ชัน generate_numbers() สำหรับเลขทุกๆ 624 จำนวน
function extract_number() {
    if index == 0 {
        generate_numbers()
    }

    int y := MT[index]
    y := y xor (ชิฟท์ขวา y ไป 11 บิต)
    y := y xor (ชิฟท์ซ้าย y ไป 7 บิต แล้ว and กับ 2636928640) // 0x9d2c5680
    y := y xor (ชิฟท์ซ้าย y ไป 15 บิต แล้ว and กับ 4022730752) // 0xefc60000
    y := y xor (ชิฟท์ขวา y ไป 18 บิต)
    index := (index + 1) mod 624
    return y
}

// สร้างอาเรย์สำหรับเก็บเลขที่ไม่ได้ลดลำดับลงขนาด 624 ช่อง
function generate_numbers() {
    for i from 0 to 623 {
        int y := บิตที่ 32 ของ (MT[i]) + 31 บิตสุดท้ายของ (MT[(i+1) mod 624])
        MT[i] := MT[(i + 397) mod 624] xor (ชิฟท์ขวา y ไป 1 บิต)
        if (y mod 2) != 0 { // y เป็นเลขคี่
            MT[i] := MT[i] xor (2567483615) // 0x9908b0df
        }
    }
}

SFMT แก้

SFMT หรือ แมร์แซน ทวิสเตอร์แบบเร็วที่เน้นกับการใช้ใน SIMD (Single instruction, multiple data : หนึ่งคำสั่งต่อหลายข้อมูล) เป็นแมร์แซน ทวิสเตอร์อีกรูปแบบหนึ่งที่ถูกออกแบบมาเมื่อปี 2006 เพื่อให้สามารถทำงานได้รวดเร็วเมื่อรันบน SIMD ขนาด 128 บิต โดยมีคุณสมบัติดังนี้

เร็วกว่าแมร์แซน ทวิสเตอร์ประมาณ 2 เท่า
มีคุณสมบัติการกระจายที่มีความถี่ในการเกิดเท่ากัน(Equidistribution) ของความแม่นยำขนาด v บิตที่ดีกว่า MT แต่แย่กว่า WELL ("Well Equidistributed Long-period Linear")
สามารถแก้ปัญหาการที่มีจำนวน 0 มากเกินไปในสถานะเริ่มต้นได้เร็วกว่า MT แต่ช้ากว่า WELL
สามารถรองรับช่วงของเลขได้ตั้งแต่ 2⁶⁰⁷ ถึง 2²¹⁶⁰⁹¹-1

อินเทล SSE2 และ PowerPC AltiVec นั้นได้รับการสนับสนุนจาก SFMT นอกจากนี้ SFMT ยังถูกใช้สำหรับอุตสาหกรรมเกม เช่น โปรเซสเซอร์ Cell BE สำหรับเครื่องเล่นเกมเพลย์สเตชัน 3

การนำไปใช้งานในภาษาต่างๆ แก้

Pascal/FreePascal/Delphi เก็บถาวร 2012-02-04 ที่ เวย์แบ็กแมชชีน
Java
The GNU Scientific Library (GSL)
R language
C++0x
C++
C และ C++
C++ เก็บถาวร 2011-10-26 ที่ เวย์แบ็กแมชชีน
C++ เก็บถาวร 2013-03-18 ที่ เวย์แบ็กแมชชีน
C++
Excel addin
Microsoft Excel
Visual Basic
REALbasic
Lisp เก็บถาวร 2010-02-10 ที่ เวย์แบ็กแมชชีน
Euphoria
C# เก็บถาวร 2012-01-09 ที่ เวย์แบ็กแมชชีน
F#
Ada เก็บถาวร 2010-05-08 ที่ เวย์แบ็กแมชชีน
Fortran 95
Lua
Mitrion-C เก็บถาวร 2011-10-01 ที่ เวย์แบ็กแมชชีน
Clean
Linoleum
Perl
Haskell เก็บถาวร 2010-05-20 ที่ เวย์แบ็กแมชชีน
Haskell
Standard ML เก็บถาวร 2008-09-27 ที่ เวย์แบ็กแมชชีน
C++ Sony Cell Broadband Engine เก็บถาวร 2008-12-25 ที่ เวย์แบ็กแมชชีน
ActionScript 1
ActionScript 3.0
Clojure
ABAP
Erlang
SIMUL8 เก็บถาวร 2012-01-28 ที่ เวย์แบ็กแมชชีน
Scala
แมร์แซน ทวิสเตอร์ยังถูกใช้ใน gLib และไลบารี่พื้นฐานของ [en.wikipedia.org/wiki/PHP PHP], Python และ Ruby

อ้างอิง แก้

Matsumoto, M.; Nishimura, T. (1998). "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator". ACM Transactions on Modeling and Computer Simulation 8 (1): 3–30. doi:10.1145/272991.272995
Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo (2005). "Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher"
"10.6. random — Generate pseudo-random numbers" Python v2.6.2 documentation. Retrieved 2009-04-27
"Module: Kernel"Ruby documentation. Retrieved 2010-02-24.
Note: 2¹⁹⁹³⁷is approximately 4.3 × 10⁶⁰⁰¹; this is many orders of magnitude larger than the estimated number of particles in the observable universe, which is 10⁸⁷.
P. L'Ecuyer and R. Simard, TestU01: "A C Library for Empirical Testing of Random Number Generators", ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007.
Marsaglia on Mersenne Twister 2003
Marsaglia on Mersenne Twister 2005
P. L'Ecuyer, ``Uniform Random Number Generators, in International Encyclopedia of Statistical Science, Lovric, Miodrag (Ed.), Springer-Verlag, 2010.
Matsumoto, M.; Kurita, Y. (1992). "Twisted GFSR generators". ACM Transactions on Modeling and Computer Simulation 2 (3): 179–194. doi:10.1145/146382.146383
SIMD-oriented Fast Mersenne Twister (SFMT)
SFMT:Comparison of speed
PLAYSTATION 3 License