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

การประยุกต์ใช้

ขั้นตอนวิธีในรูปแบบพื้นฐานนั้นไม่เหมาะสมในการใช้ในวิทยาการเข้ารหัสลับ (ไม่เหมือนกับ 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) และแบบจำลองทางสถิติอื่นๆเป็นพื้นฐาน เพราะว่านักวิจัยนั้นต้องการตัวเลขที่มีคุณภาพสูง แต่ก็ต้องการประโยชน์จากความเร็วและความสามารถในการนำไปใช้ที่อื่นได้โดยข้อมูลไม่เสียหายและสามารถใช้ได้กับทุกๆที่ด้วย

ทางเลือก

ขั้นตอนวิธีแมร์แซน ทวิสเตอร์ได้รับการวิพากษ์วิจารณ์ในด้านวิทยาการคอมพิวเตอร์ โดยเฉพาะจากจอร์จ มาร์ซากิลา (George Marsaglia) ว่าถึงแม้จะดีในการหาตัวเลขเชิงสุ่มแต่ว่าซับซ้อนในการนำไปใช้งานจริง Marsaglia ได้ยกตัวอย่างของขั้นตอนวิธีสำหรับการหาตัวเลขเชิงสุ่มที่มีความซับซ้อนน้อยกว่าแต่มีช่วงการพิจารณาที่กว้างกว่า ตัวอย่างเช่นขั้นตอนวิธีคูณแบบมีตัวทด (Multiply-with-carry) ซึ่งมีช่วงกว้าง 10³³⁰⁰⁰ ซึ่งเร็วกว่าและมีอัตราการสุ่มเทียบเท่าหรือดีกว่า
อีกหนึ่งประเด็นคือแมร์แซน ทวิสเตอร์ นั้นละเอียดอ่อนมากโดยเฉพาะกับการตั้งค่าเริ่มต้นที่ไม่ดี และแมร์แซน ทวิสเตอร์ยังใช้เวลานานในการแก้ไขจากสถานะเริ่มต้นที่มี 0 มากเกินไปให้อยู่ในสถานะที่มีการสุ่มในเกณฑ์ที่ต้องการ ทางเลือกที่ดีกว่าในการแก้ปัญหานี้ได้แก่ WELL(Well equidistributed long-period linear) ซึ่งสามารถแก้ไขปัญหาสถานะเริ่มต้นที่มี 0 มากเกินไปนี้ได้อย่างรวดเร็ว โดยมีประสิทธิภาพที่เท่ากันหรือดีกว่าและมีอัตราการสุ่มที่เท่ากัน

รหัสเทียม

รหัสเทียมต่อไปนี้ถูกสร้างมาจากการกระจายแบบปกติ (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
        }
    }
}