ในโลกของการคำนวณ การสร้างตัวเลขสุ่มได้วิวัฒนาการจากวงล้อรูเล็ตทางกายภาพไปสู่อัลกอริทึมอันซับซ้อนที่สามารถบรรจุอยู่ในโค้ดเพียงไม่กี่บรรทัด การอภิปรายล่าสุดเกี่ยวกับ Rust crate oorandom ได้จุดประกายความสนใจอีกครั้งในเรื่องวิธีการสร้างตัวเลขสุ่มเทียม (pseudorandom numbers) และเหตุใดอัลกอริทึมบางชนิดจึงได้รับความนิยม ในขณะที่บางชนิดเลือนหายไป
สถานะปัจจุบันของการสร้างตัวเลขสุ่ม
ขณะนี้ชุมชนนักเขียนโปรแกรมแตกออกเป็นหลายฝ่ายที่แข่งขันระหว่างอัลกอริทึมตัวสร้างตัวเลขสุ่มเทียม (PRNG) หลายตัว โดย Permuted Congruential Generators (PCG) กำลังปรากฏขึ้นเป็นคู่แข่งสำคัญที่ท้าทายตัวเก่งอย่างเช่น xorshift variants PCG เป็นตัวแทนของสิ่งที่ผู้แสดงความคิดเห็นรายหนึ่งอธิบายว่าเป็นการนำ LCG เก่าแก่มาอัดสเตอรอยด์ – เป็นเวอร์ชันที่ทรงพลังยิ่งขึ้นของ Linear Congruential Generator แบบดั้งเดิม ซึ่งแก้จุดอ่อนทางประวัติศาสตร์หลายประการของมัน อัลกอริทึมนี้รวมการดำเนินการทางคณิตศาสตร์อย่างง่ายกับฟังก์ชันการเรียงสับเปลี่ยน (permutation) เพื่อผลิตความสุ่มคุณภาพสูง ในขณะที่ยังคงรักษาลักษณะประสิทธิภาพการทำงานที่ยอดเยี่ยมไว้
PCG ดีกว่า xorshift และอัลกอริทึมที่เกี่ยวข้องในตระกูลเดียวกัน... PCG-RXS-M-XS (ที่มีเอาต์พุต 32 บิต) ผ่านการทดสอบ BigCrush ด้วยสถานะขนาด 36 บิต (ซึ่งเป็นขนาดที่เล็กที่สุดที่เป็นไปได้)
ประสิทธิภาพในการผ่านการทดสอบทางสถิติที่เข้มงวดด้วยขนาดสถานะที่น้อยนี้ เป็นตัวแทนของความก้าวหน้าที่สำคัญในปรัชญาการออกแบบ PRNG
การเปรียบเทียบอัลกอริทึม PRNG สมัยใหม่:
- PCG (Permuted Congruential Generator): รวม LCG เข้ากับการดำเนินการเรียงสับเปลี่ยน ต้องการ state 36-49 บิตเพื่อผ่านการทดสอบ BigCrush
- Xorshift variants: ใช้การเลื่อนบิตและการดำเนินการ XOR ถูกใช้โดยเว็บเบราว์เซอร์หลักๆ ณ ปี 2025
- Mersenne Twister: อัลกอริทึมรุ่นเก่าที่ต้องการ state 19937 บิต ไม่ผ่านการทดสอบทางสtatisticsบางอย่างแม้จะมีขนาด state ที่ใหญ่
- Middle Square Weyl Sequence: วิธีการในอดีตที่ได้รับการฟื้นฟูด้วยการปรับปรุงสมัยใหม่ มีการใช้งานที่เรียบง่าย
บริบททางประวัติศาสตร์และสงครามทางอัลกอริทึม
ประวัติศาสตร์ของการสร้างตัวเลขสุ่มอ่านแล้วคล้ายกับการแข่งขันทางเทคโนโลยีแบบถอนหายใจเฮือกใหญ่ มันเริ่มต้นจากวงล้อรูเล็ตและลูกบิงโกที่เป็นของจริง ก้าวหน้าผ่าน Linear Congruential Generators (LCGs) ในยุคทศวรรษ 1960, เห็นการขึ้นมาของ Linear Feedback Shift Registers (LFSRs) สำหรับการใช้งานทางฮาร์ดแวร์, เป็นพยานถึงการครองตำแหน่งของ Mersenne Twister ในช่วงปลายทศวรรษ 1990 และปัจจุบันมีตระกูลอัลกอริทึมที่แข่งขันกันเช่น xorshift derivatives และ PCG สิ่งที่น่าสนใจเป็นพิเศษคือความเข้าใจของชุมชนเกี่ยวกับสิ่งที่ถือว่าเป็นความสุ่มที่ ดีพอ ได้วิวัฒนาการไปพร้อมๆ กับความก้าวหน้าทางเทคโนโลยีเหล่านี้อย่างไร
ผู้แสดงความคิดเห็นรายหนึ่งระบุว่าผลงานของ George Marsaglia ซึ่งรวมถึง multiply-with-carry, xorshift ดั้งเดิม และตัวสร้าง KISS generator มีบทบาทสำคัญในวิวัฒนาการนี้ ความจริงที่ว่าแม้แต่วิธีการโบราณอย่าง middle square method สามารถฟื้นคืนชีพด้วยการปรับปรุงสมัยใหม่ แสดงให้เห็นว่าความเข้าใจของเราเกี่ยวกับความสุ่มยังคงลึกซึ้งยิ่งขึ้นเรื่อยๆ ตัวอย่างเช่น middle square Weyl sequence PRNG เป็นตัวแทนของส่วนผสมอันน่าหลงใหลระหว่างเทคนิคทางประวัติศาสตร์กับความเข้าใจทางคณิตศาสตร์สมัยใหม่
การนำไปปฏิบัติจริงและการยอมรับจากชุมชน
แม้ PCG จะมีข้อได้เปรียบทางเทคนิค การยอมรับในโครงการซอฟต์แวร์ใหญ่ๆ กลับมีความหลากหลาย ดังที่สมาชิกชุมชนหนึ่งสังเกตว่า ผมไม่ทราบว่าโครงการระดับสูงหลายโครงการหันมาใช้ PCG เป็นค่าเริ่มต้น ณ ปี 2025 นี้ รันไทม์ระดับสูงหลายตัว (รวมถึงเบราว์เซอร์หลักทั้งหมด) ใช้ xorshift variants ช่องว่างระหว่างความเหนือกว่าในทางทฤษฎีกับการยอมรับในทางปฏิบัตินี้ ชี้ให้เห็นว่าการตัดสินใจทางวิศวกรรมในโลกจริงมักเกี่ยวข้องกับปัจจัยอื่นๆ นอกเหนือจากประสิทธิภาพของอัลกอริทึมล้วนๆ – รวมถึงความซับซ้อนในการนำไปใช้, แนวทางปฏิบัติเดิม, และข้อกังวลเกี่ยวกับความเข้ากันได้
การอภิปรายเกี่ยวกับ oorandom เทียบกับทางเลือกอื่นๆ เช่น randomize, nanorand และ fastrand แสดงให้เห็นว่าการเลือกอัลกอริทึมเหล่านี้แปลเป็นการออกแบบไลบรารีในทางปฏิบัติอย่างไร นักพัฒนาต้องบาลานซ์ปัจจัยต่างๆ เช่น ขนาดโค้ด, เวลาในการคอมไพล์, ความเสถียรของ API, และความเหมาะสมสำหรับการเข้ารหัสลับ เมื่อเลือกโซลูชัน PRNG สำหรับกรณีใช้เฉพาะของพวกเขา สำหรับแอปพลิเคชันจำนวนมาก ความแตกต่างระหว่าง PRNG สมัยใหม่นั้นมีน้อยมาก ทำให้ความเรียบง่ายและความง่ายต่อการใช้งานเป็นข้อกังวลหลัก
มาตรฐานการทดสอบ PRNG ที่สำคัญ:
- BigCrush: เป็นส่วนหนึ่งของชุดทดสอบ TestU01 ตรวจสอบข้อมูลจำนวนมากเพียงพอที่จะตรวจจับรอบระยะเวลาได้ถึง 2^35
- Dieharder: ชุดทดสอบทางสtatisticsที่ครอบคลุมสำหรับตัวสร้างตัวเลขสุ่ม
- ขนาด state ขั้นต่ำ: เป็นตัววัดคุณภาพของอัลกอริทึม - state ที่มีขนาดเล็กกว่าแต่ผ่านการทดสอบแสดงถึงประสิทธิภาพที่ดีกว่า
มิติเชิงปรัชญาของความสุ่ม
เหนือไปจากข้อกำหนดทางเทคนิค คือคำถามที่ลึกซึ้งยิ่งขึ้นเกี่ยวกับธรรมชาติของความสุ่มเอง ดังที่ผู้แสดงความคิดเห็นรายหนึ่งครุ่นคิดว่า ความสุ่มนั้นลึกซึ้งกว่าที่มันปรากฏแก่ตาเรามาก มันอาจจะไม่ได้เป็นส่วนหนึ่งของโลก (ที่เป็นวัตถุ) จริงๆ ด้วยซ้ำ มุมมองเชิงปรัชนานี้เตือนเราว่าสิ่งที่เราเรียกว่าความสุ่มในการคำนวณนั้นเป็นเพียงความสุ่มเทียม (pseudorandom) เสมอ – นั่นคือลำดับที่กำหนดได้ (deterministic) ที่เพียงแต่ดูสุ่มตามการทดสอบทางสถิติเฉพาะบางอย่างเท่านั้น การแสวงหาอย่างต่อเนื่องเพื่อหา PRNG ที่ดีขึ้นเป็นตัวแทนของความพยายามของเราในการเชื่อมช่องว่างระหว่างอุดมคติทางคณิตศาสตร์กับการคำนวณในทางปฏิบัติ
วิวัฒนาการยังคงดำเนินต่อไปในขณะที่นักวิจัยพัฒนาอัลกอริทึมใหม่และปรับปรุงอัลกอริทึมที่มีอยู่ สิ่งที่ทำให้ยุคปัจจุบันน่าตื่นเต้นเป็นพิเศษคือการเข้าถึงเครื่องมือเหล่านี้ได้ง่าย – ในอดีตคุณอาจต้องการตารางตัวเลขสุ่มที่คำนวณล่วงหน้าขนาดยักษ์หรือฮาร์ดแวร์เฉพาะทาง แต่ในปัจจุบันความสุ่มคุณภาพสูงสามารถเข้าถึงได้ผ่านไลบรารีที่ย่อส่วนและมีเอกสารประกอบดีๆ อย่าง oorandom ปัญหานี้อาจไม่เคยได้รับการแก้ไขอย่างสมบูรณ์ แต่เราได้ก้าวมาไกลมากแล้วนับตั้งแต่วงล้อรูเล็ตของ Edith
อ้างอิง: oorandom v11.1.5