ตัวสร้างตัวเลขสุ่มเทียมใหม่ที่เรียกว่า LoopMix128 ได้จุดประกายให้เกิดการสนทนาทางเทคนิคที่น่าสนใจในหมู่ผู้เชี่ยวชาญด้านอัลกอริทึม โดยจุดเริ่มต้นของผู้สร้างมาจากแหล่งที่ไม่คาดคิด: คำถามของผู้ใช้เกี่ยวกับวิธีการสุ่มของแอปโป๊กเกอร์
อัลกอริทึมนี้ถูกออกแบบมาสำหรับการใช้งานที่ไม่เกี่ยวกับการเข้ารหัสลับ ซึ่งความเร็วและคุณภาพทางสถิติเป็นสิ่งสำคัญสูงสุด มีคุณสมบัติที่น่าประทับใจรวมถึงการรับประกันคาบของ 2^128 การพิสูจน์ความเป็น injective และผ่านการทดสอบทั้งชุดทดสอบ BigCrush และ PractRand ไปจนถึงข้อมูล 32TB
การอ้างสิทธิ์ด้านประสิทธิภาพและการวิเคราะห์จากผู้เชี่ยวชาญ
LoopMix128 อ้างว่ามีข้อได้เปรียบด้านประสิทธิภาพที่สำคัญ โดยรายงานว่าทำงานเร็วกว่าการใช้งาน random ของ Java 8.75 เท่า และมีประสิทธิภาพเหนือกว่า PRNG ความเร็วสูงสมัยใหม่อื่นๆ เช่น xoroshiro128++ และ PCG64 อย่างไรก็ตาม การอ้างสิทธิ์เหล่านี้ได้กระตุ้นให้เกิดการตรวจสอบทางเทคนิคจากผู้เชี่ยวชาญด้านอัลกอริทึม รวมถึงผู้สร้าง MurmurHash
ผู้เชี่ยวชาญคนหนึ่งแสดงความประหลาดใจที่อัลกอริทึมผ่านการทดสอบทางสถิติที่เข้มงวด ทั้งๆ ที่มีการออกแบบที่ค่อนข้างเรียบง่าย โดยสังเกตว่าฟังก์ชันการอัปเดตสถานะแทบจะไม่เป็นเชิงเส้น และการสร้างเอาต์พุตเป็นเชิงเส้น สิ่งนี้จุดประกายให้เกิดการแลกเปลี่ยนทางเทคนิคเกี่ยวกับทางเลือกการออกแบบอัลกอริทึม โดยผู้สร้างได้อธิบายถึงวิธีการเลือกค่าการหมุนอย่างระมัดระวังผ่านการทดสอบอย่างกว้างขวางเพื่อเพิ่มประสิทธิภาพคุณภาพความสุ่ม
While I don't doubt this passes BigCrush etc, I do find it very surprising that it does. The state update function is effectively a = rotate(a, constant) + b; b = rotate(b, constant) + constant; and the output derivation is output = (a + b) * constant.
คุณสมบัติหลักของ LoopMix128
- ประสิทธิภาพ: เร็วกว่า Java random 8.75 เท่า, เร็วกว่า Java xoroshiro128++ 21%, เร็วกว่า C xoroshiro128++ และ PCG64 98%
- คุณภาพทางสถิติ: ผ่านชุดทดสอบ BigCrush ของ TestU01 และ PractRand (สูงถึง 32TB) โดยไม่พบความผิดปกติใดๆ
- คาบ: รับประกันความยาวคาบขั้นต่ำที่ 2^128
- ขนาดสถานะ: สถานะขนาด 192 บิตพร้อมการพิสูจน์ความเป็น injective
- การเปรียบเทียบ PractRand (1000 รอบจาก 256M ถึง 8GB ด้วยค่าเริ่มต้นที่หลากหลาย):
- LoopMix128: 0 ความล้มเหลว, 24 น่าสงสัย
- xoroshiro256++: 0 ความล้มเหลว, 27 น่าสงสัย
- xoroshiro128++: 0 ความล้มเหลว, 28 น่าสงสัย
- wyrand: 0 ความล้มเหลว, 32 น่าสงสัย
- /dev/urandom: 0 ความล้มเหลว, 37 น่าสงสัย
ขนาดสถานะและคุณภาพทางสถิติ
เกิดการสนทนาที่น่าสนใจเกี่ยวกับการวิเคราะห์ความจุของขนาดสถานะ โดยผู้แสดงความคิดเห็นคนหนึ่งแนะนำว่าสถานะ 192 บิตของอัลกอริทึมอาจมีขนาดใหญ่เกินความจำเป็น พวกเขาชี้ให้เห็นว่าแม้แต่อัลกอริทึมที่รู้กันว่าไม่ดีเช่น middle square ก็สามารถผ่านการทดสอบทางสถิติด้วยสถานะขนาดใหญ่เช่นนั้น โดยอ้างอิงถึงวิธีการวิเคราะห์ของ PCG ในการลดขนาดสถานะจนกว่าจะล้มเหลวเพื่อกำหนดว่าอัลกอริทึมมีระยะปลอดภัยมากเพียงใด
ผู้สร้างตอบสนองเชิงบวกต่อข้อเสนอนี้ และต่อมารายงานว่าเวอร์ชันที่ลดลงโดยใช้ตัวแปร 32 บิตเท่านั้น (สำหรับสถานะ 64 บิต) ยังคงผ่าน PractRand ไปจนถึง 256GB โดยมีผลลัพธ์ที่ผิดปกติเพียงครั้งเดียว ซึ่งบ่งชี้ว่าอัลกอริทึมมีความทนทานอย่างมากแม้จะมีสถานะที่ลดลงอย่างมีนัยสำคัญ
การประยุกต์ใช้ในโลกแห่งความเป็นจริง
การสนทนาในชุมชนเผยให้เห็นการประยุกต์ใช้งานที่ปฏิบัติได้จริงหลายอย่างสำหรับ PRNG ประสิทธิภาพสูง การเขียนโปรแกรมกราฟิกและเสียงถูกเน้นย้ำว่าเป็นโดเมนที่ประสิทธิภาพของ PRNG สามารถเป็นสัดส่วนที่วัดได้ของประสิทธิภาพโปรแกรมทั้งหมดโดยไม่มีข้อจำกัดด้านความปลอดภัย เมื่อสร้างเสียงรบกวนสำหรับทุกตัวอย่างเสียงหรือพิกเซล อัลกอริทึมที่เร็วมากให้ประโยชน์ที่จับต้องได้ การจำลอง Monte Carlo ก็ถูกกล่าวถึงว่าเป็นกรณีการใช้งานที่เห็นได้ชัด
การเดินทางของผู้สร้างในการพัฒนา PRNG เริ่มต้นด้วยคำถามง่ายๆ เกี่ยวกับการสุ่มในแอปโป๊กเกอร์ แสดงให้เห็นว่าการสำรวจที่ขับเคลื่อนด้วยความอยากรู้อยากเห็นสามารถนำไปสู่การมีส่วนร่วมทางเทคนิคที่มีความหมายได้อย่างไร ในขณะที่บางคนสงสัยว่าทำไมผู้สร้างไม่ใช้อัลกอริทึมการเข้ารหัสลับที่มีอยู่แล้วเช่น ChaCha สำหรับแอปพลิเคชันโป๊กเกอร์ การศึกษาเชิงลึกที่เกิดขึ้นได้สร้างอัลกอริทึมที่มีศักยภาพในการประยุกต์ใช้นอกเหนือจากบริบทดั้งเดิม
เมื่อการประมวลผลพึ่งพาเทคนิคการสุ่มมากขึ้นในโดเมนต่างๆ ตั้งแต่เกมไปจนถึงการจำลองทางวิทยาศาสตร์ การปรับปรุง PRNG อย่าง LoopMix128 อย่างต่อเนื่องถือเป็นพื้นที่สำคัญของการพัฒนาอัลกอริทึมที่แม้แต่การปรับปรุงเพียงเล็กน้อยก็สามารถมีผลกระทบอย่างกว้างขวาง