อัลกอริทึมสำหรับการทำงานของตัวสร้างตัวเลขสุ่ม เครื่องกำเนิดตัวเลขสุ่ม วิธีสมภาคเชิงเส้น

ตัวเลขสุ่มเป็นองค์ประกอบง่ายๆ ของการเข้ารหัสที่ได้รับการพูดถึงน้อยที่สุด แต่ก็มีความสำคัญไม่แพ้ส่วนที่เหลือ ระบบรักษาความปลอดภัยคอมพิวเตอร์เกือบทั้งหมดที่ใช้การเข้ารหัสต้องใช้ตัวเลขสุ่ม - สำหรับคีย์ หมายเลขเฉพาะในโปรโตคอล ฯลฯ - และความปลอดภัยของระบบดังกล่าวมักจะขึ้นอยู่กับการสุ่มของ ตัวเลขสุ่ม- หากตัวสร้างตัวเลขสุ่มไม่น่าเชื่อถือ ระบบทั้งหมดจะพัง

การสร้างตัวเลขสุ่มอาจดูเล็กน้อยหรือเป็นไปไม่ได้ ขึ้นอยู่กับว่าคุณคุยกับใคร ตามทฤษฎีแล้วสิ่งนี้เป็นไปไม่ได้ จอห์น ฟอน นอยมันน์ บิดาแห่งคอมพิวเตอร์กล่าวว่า “ใครก็ตามที่เชื่อว่ามีวิธีทางคณิตศาสตร์ในการสร้างตัวเลขสุ่มถือเป็นบาปอย่างแน่นอน” เขาหมายความว่าเป็นไปไม่ได้ที่จะได้อะไรแบบสุ่มเข้ามา ในทุกแง่มุมคำพูดเป็นผลลัพธ์ของสัตว์ร้ายที่กำหนดได้เช่นคอมพิวเตอร์ นี่เป็นเรื่องจริง แต่โชคดีที่มีบางสิ่งที่เราสามารถทำได้ สิ่งที่เราต้องการจากเครื่องสร้างตัวเลขสุ่มไม่ใช่ว่าตัวเลขนั้นสุ่มอย่างแท้จริง แต่ไม่สามารถคาดเดาและทำซ้ำได้ หากเราปฏิบัติตามเงื่อนไขทั้งสองนี้ เราก็สามารถบรรลุความปลอดภัยได้

ในทางกลับกัน ถ้าเราฝ่าฝืนเงื่อนไขทั้งสองนี้ ก็จะไม่มีการรักษาความปลอดภัย ในปี 1994 มีการติดตั้งเครื่องสร้างตัวเลขสุ่มสำหรับลอตเตอรี่ในคาสิโนในมอนทรีออล ผู้เล่นสังเกตการณ์คนหนึ่งที่ใช้เวลาส่วนใหญ่ในคาสิโนสังเกตเห็นว่าหมายเลขที่ชนะจะเท่ากันทุกวัน เขาประสบความสำเร็จในการแจ็กพอตสามรางวัลติดต่อกันและได้รับเงินรางวัล 600,000 ดอลลาร์ (หลังจากบีบมือ ขบเขี้ยวเคี้ยวฟัน และสำรวจทุกอย่าง คาสิโนก็จ่ายเงินรางวัล)

ตัวสร้างตัวเลขสุ่มมีหลายประเภทกว้างๆ บางส่วนขึ้นอยู่กับกระบวนการทางกายภาพซึ่งถือว่าค่อนข้างสุ่ม สำนักงานความมั่นคงแห่งชาติชอบใช้สัญญาณรบกวนทางไฟฟ้าจากไดโอดในอุปกรณ์เพื่อสร้างตัวเลขสุ่ม ความเป็นไปได้อื่นๆ ได้แก่ เครื่องนับไกเกอร์หรือเครื่องรับสัญญาณรบกวนวิทยุ ระบบหนึ่งบนอินเทอร์เน็ตใช้ กล้องดิจิตอลมุ่งเป้าไปที่แสงแฟลชหลายดวง ระบบอื่นๆ ใช้ความปั่นป่วนของอากาศในการขับเคลื่อนหรือกำหนดเวลาของแพ็กเก็ตเครือข่าย

เครื่องกำเนิดตัวเลขสุ่มบางตัวติดตามการเคลื่อนไหวแบบสุ่มของผู้ใช้ โปรแกรมอาจขอให้ผู้ใช้พิมพ์อักขระจำนวนมากบนแป้นพิมพ์ สามารถใช้ลำดับของอักขระหรือแม้แต่เวลาระหว่างการกดแป้นพิมพ์เพื่อสร้างตัวเลขสุ่ม โปรแกรมอื่นสามารถกำหนดให้ผู้ใช้เลื่อนเมาส์ไปมาหรือตะโกนใส่ไมโครโฟนได้อย่างง่ายดาย

ตัวสร้างตัวเลขสุ่มบางตัวใช้ข้อมูลที่ป้อนนี้โดยไม่มีการแก้ไข ในกรณีอื่นๆ จะทำหน้าที่เป็นเมล็ดพันธุ์ (ตัวเลขเริ่มต้น) สำหรับเครื่องกำเนิดตัวเลขสุ่มทางคณิตศาสตร์ เทคนิคนี้จะทำงานได้ดีที่สุดหากระบบต้องการตัวเลขสุ่มมากกว่าที่อินพุตมีให้

ไม่ว่าจุดกำเนิดของการสุ่มจะเป็นอย่างไร ตัวสร้างจะสร้างชุดของบิตสุ่มขึ้นมา จากนั้นสามารถใช้เป็นคีย์เข้ารหัสและสำหรับทุกสิ่งที่ระบบต้องการ

ปรากฏการณ์ทั้งหมดที่เกิดขึ้นกับเรามีสองประเภท - แบบสุ่มและเป็นธรรมชาติ ตัวอย่างเช่น คุณมีเงินไม่เพียงพอที่จะซื้อเครื่องบันทึกเทป และคุณตัดสินใจซื้อเครื่องเล่น - เช่น การกระทำเป็นไปตามตรรกะและคาดหวัง แต่เมื่อเดินไปที่ร้านคุณจะพบจำนวนเงินที่ต้องการซึ่งเปลี่ยนแผนแบบสุ่ม การทำงานของเครื่องสร้างตัวเลขสุ่มนั้นขึ้นอยู่กับกลไกที่ระบุในโอเปอเรเตอร์ ดังนั้นตัวเลขทั้งหมดที่ออกจะเป็นการสุ่มเทียมในเหตุการณ์ปัจจุบัน ผู้ประกอบการที่กลับมา ตัวเลขสุ่มอ้างถึงเวลาคือเวลาของระบบ เหล่านั้น. ทั้งในโลกและในการเขียนโปรแกรมไม่มีอะไรที่ครบถ้วนสมบูรณ์

ฟังก์ชันแรนด์

ในการเขียนโปรแกรม C ตัวดำเนินการในตัวถูกประดิษฐ์ขึ้นเพื่อให้ได้ค่าสุ่ม ซึ่งให้ผลลัพธ์ที่ต้องการแก่เรา ดังนั้นหากต้องการสร้างตัวเลขสุ่มให้ใช้ ฟังก์ชันแรนด์, ที่ ตัวดำเนินการแรนด์ใช้เพื่อรับตัวเลขสุ่มที่ส่งคืนช่วงตั้งแต่ 0 ถึงค่าคงที่ที่แน่นอน นอกจากนี้ ค่าคงที่นี้จะถูกประกาศในคำสั่งของระบบ “stdlib.h” โดยที่ฟังก์ชัน rand นี้ใช้เป็นหลัก ไวยากรณ์ของฟังก์ชันนี้เรียบง่าย: int m= rand(); เหล่านั้น. ส่งคืนจำนวนเต็ม หลังจากทดสอบโอเปอเรเตอร์ในทางปฏิบัติแล้ว คุณจะเห็นว่าตัวเลขที่ปรากฏขึ้นเมื่อเริ่มแอปพลิเคชันนั้นเหมือนกัน การควบคุมดูแลคือตัวดำเนินการ rand ทำงานกับเวลาระบบเดียวกัน ซึ่งได้รับการสงวนไว้ในระหว่างการคอมไพล์ ตัวสร้างตัวเลขสุ่มนี้เชื่อมโยงกับอัลกอริธึมสำหรับการเปลี่ยนเวลาของโปรแกรม แต่ทุกอย่างทำงานไม่ถูกต้อง

ตอนนี้เกี่ยวกับ srand และสุ่ม

สำหรับปัญหานี้ ฟังก์ชันที่จะรีเซ็ตเวลาในตัวให้เป็นศูนย์ทุกครั้งที่มีการเรียกตัวดำเนินการ rand นั้นเป็นสิ่งที่ขาดไม่ได้ และนักพัฒนาซอฟต์แวร์ก็ทำ ฟังก์ชันสแตรนด์- การดำเนินการอนุญาตให้ฟังก์ชัน rand เข้าถึงในแต่ละครั้งไม่ใช่ตัวจับเวลาที่ติดตั้ง แต่เป็นตัวจับเวลาในตัวปัจจุบันซึ่งเปิดโอกาสให้เครื่องกำเนิดทำงานได้อย่างถูกต้อง - เพื่อสร้างค่าสุ่ม เมื่อเร็ว ๆ นี้ในการเขียนโปรแกรม C++ กลไกในการออกตัวเลขสุ่มได้รับการปรับปรุงเนื่องจากมีลักษณะเป็นไมโครวินาที นอกจากนี้ช่วงของค่ายังขยายออกไปและนวัตกรรมปัจจุบันทั้งหมดได้ถูกเปลี่ยนให้เป็นฟังก์ชันแบบสุ่ม

ทุกคนโดยไม่คำนึงถึงระดับของการพนันและการผจญภัย ต้องเผชิญกับแนวคิดเช่นลอตเตอรีไม่ทางใดก็ทางหนึ่ง และมีเพียงไม่กี่คนที่ถามตัวเองว่าการกระจายตัวแบบสุ่มเกิดขึ้นได้อย่างไร ชุดค่าผสมที่ชนะตัวเลข หมายเลขนี้หรือหมายเลขนั้นออกมาได้อย่างไร? อะไรทำให้ระดับทิปไปสู่ผู้ชนะ? ลองดูรายละเอียดนี้กัน

เราทุกคนเคยเจอเหตุการณ์แบบนี้มาก่อนในชีวิต เช่น ลอตเตอรี แต่มีเพียงไม่กี่คนที่คิดหรือจินตนาการว่าระบบนี้ทำงานอย่างไร เครื่องกำเนิดตัวเลขสำหรับลอตเตอรีคืออะไร และหลักการทำงานของมันคืออะไร

แนวคิดของเครื่องกำเนิดตัวเลข

เครื่องสร้างตัวเลขสุ่มสำหรับลอตเตอรีคืออุปกรณ์บางอย่างหรือโปรแกรมที่กำหนดซึ่งสร้างตัวเลขที่อยู่ในช่วงเวลาที่กำหนดในลำดับแบบสุ่ม (ถูกต้องกว่าคือสุ่มหลอก) สำหรับลอตเตอรี่บางประเภท เช่น "Sportloto" จะมีการสร้างตัวเลขที่อยู่ในช่วงตั้งแต่ 1 ถึง 49

มีเครื่องกำเนิดหมายเลขฮาร์ดแวร์และซอฟต์แวร์สำหรับลอตเตอรี่ ภาษาการเขียนโปรแกรมใดๆ มีฟังก์ชัน RAND() ซึ่งมีหน้าที่สร้างตัวเลขสุ่มหลอกในช่วงที่กำหนด

เหตุใดจึงระบุว่าผลลัพธ์ที่ให้มาเป็นการสุ่มหลอกและเครื่องสร้างหมายเลขลอตเตอรีทำงานบนหลักการนี้ทุกประการ

ฟังก์ชัน RAND: แนวคิดและวิธีการใช้งาน

ฟังก์ชัน RAND() คือโปรแกรมหรืออุปกรณ์ที่มีอัลกอริธึมที่กำหนดซึ่งจะแสดงผลลัพธ์เดียวกันอย่างต่อเนื่องภายใต้เงื่อนไขที่ระบุเดียวกัน แต่เพื่อให้เงื่อนไขของลำดับสุ่มที่แท้จริงคงอยู่นั้น จะต้องไม่มีการพึ่งพา เงื่อนไขเริ่มต้นหรือพารามิเตอร์ ดังนั้นเพื่อหลีกเลี่ยง กรณีที่คล้ายกันมีการใช้ขั้นตอน RANDOMIZE พิเศษเพิ่มเติม ซึ่งจะลบความสามารถในการคาดเดาของเงื่อนไขเริ่มต้น และทำให้เป็นแบบสุ่ม

นอกเหนือจากหลักการสร้างที่เราทราบแล้ว ยังมีการใช้เครื่องกำเนิดลอตเตอรีอีกประเภทหนึ่งอีกด้วย ลองดูที่ด้านล่าง

เครื่องกำเนิดตัวเลข 6 จาก 45

เครื่องกำเนิดตัวเลขสำหรับลอตเตอรี 6 จาก 45 - โปรแกรมที่ใช้ในการรับ ตัวเลขนำโชค- ในกรณีนี้สามารถตั้งค่าได้ ตัวเลือกพิเศษเพื่อให้ได้ผลลัพธ์ที่ดีขึ้น

คุณสามารถระบุเกณฑ์การเลือกได้ เช่น:

• ปริมาณ หมายเลขที่ชนะซึ่งจะต้องได้รับในผลลัพธ์สุดท้าย
• ระบุช่วงตัวเลขที่จะทำการคัดเลือก
• ตัวเลขสามารถเรียงลำดับจากน้อยไปหามากหรือจากมากไปหาน้อย
• เลือกประเภทและวิธีการแยก
• ลบรายการที่ซ้ำกันหรือปล่อยส่วนที่เลือกไว้โดยไม่เรียงลำดับ
• คัดลอกลิงก์ไปยังผลลัพธ์และวางไว้บนหน้าใน ในเครือข่ายโซเชียลเพื่อวัตถุประสงค์ในการเผยแพร่ผล

เครื่องกำเนิดตัวเลข: คำแนะนำสำหรับการใช้งาน

• ผลลัพธ์เริ่มต้นคือตัวเลขห้าตัว เมื่อเปลี่ยนการตั้งค่า คุณจะได้รับชุดค่าผสมที่ชนะแบบสุ่มมากถึง 250 ชุด
• เรากำหนดช่วง มาตรฐานคือตั้งแต่ 0 ถึง 36 แต่คุณสามารถระบุได้สูงสุด 9,999,999,999
• เราเลือกการเรียงลำดับที่จำเป็นสำหรับประเภทลอตเตอรี่ของเรา: จากน้อยไปหามาก จากมากไปน้อย หรือวางหมายเลขตามลำดับแบบสุ่ม
• ขั้นตอนต่อไปคือการระบุว่าตัวเลขจะแยกออกจากกันอย่างไร - ลูกน้ำ, จุด, ช่องว่าง, อัฒภาค
• เราจะกำจัดการสุ่มซ้ำที่เกิดขึ้นระหว่างกระบวนการสุ่มตัวอย่าง

ด้วยวิธีนี้ เราจึงได้หมายเลขคุณภาพสูงที่เลือกมา ซึ่งสามารถเป็นหมายเลขที่โชคดีที่สุดและถูกรางวัลได้

โปรดทราบว่าตามหลักการแล้ว เส้นโค้งความหนาแน่นของการแจกแจงของตัวเลขสุ่มจะมีลักษณะดังแสดงในรูปที่ 1 22.3. นั่นคือ ในกรณีที่เหมาะสม แต่ละช่วงเวลาจะรวมไว้ด้วย หมายเลขเดียวกันคะแนน: เอ็น ฉัน = เอ็น/เค , ที่ไหน เอ็น — จำนวนทั้งหมดคะแนน เคจำนวนช่วงเวลา ฉัน= 1, , เค .

ควรจำไว้ว่าการสร้างตัวเลขสุ่มตามอำเภอใจประกอบด้วยสองขั้นตอน:

• การสร้างตัวเลขสุ่มที่ทำให้เป็นมาตรฐาน (นั่นคือ การกระจายอย่างสม่ำเสมอตั้งแต่ 0 ถึง 1)
• การแปลงตัวเลขสุ่มที่ทำให้เป็นมาตรฐาน ร ฉันสู่ตัวเลขสุ่ม x ฉันซึ่งเผยแพร่ตามกฎหมายการแจกจ่าย (โดยพลการ) ที่ผู้ใช้กำหนดหรือตามระยะเวลาที่กำหนด

เครื่องกำเนิดตัวเลขสุ่มตามวิธีการรับตัวเลขแบ่งออกเป็น:

• ทางกายภาพ;
• ตาราง;
• อัลกอริทึม

RNG ทางกายภาพ

ตัวอย่างของ RNG ทางกายภาพอาจเป็น: เหรียญ (“หัว” 1, “ก้อย” 0); ลูกเต๋า- กลองที่มีลูกศรแบ่งออกเป็นภาคที่มีตัวเลข เครื่องกำเนิดสัญญาณรบกวนฮาร์ดแวร์ (HS) ซึ่งใช้อุปกรณ์ระบายความร้อนที่มีเสียงดังเช่นทรานซิสเตอร์ (รูปที่ 22.422.5)

RNG แบบตาราง

RNG แบบตารางใช้ตารางที่คอมไพล์เป็นพิเศษซึ่งมีการตรวจสอบแล้วว่าไม่เกี่ยวข้องกัน กล่าวคือ ตัวเลขเป็นแหล่งของตัวเลขสุ่มโดยไม่ขึ้นอยู่กับกันและกัน ในตาราง รูปที่ 22.1 แสดงส่วนเล็กๆ ของตารางดังกล่าว เมื่อสำรวจตารางจากซ้ายไปขวาจากบนลงล่าง คุณจะได้ตัวเลขสุ่มที่กระจายเท่าๆ กันตั้งแต่ 0 ถึง 1 โดยมีจำนวนตำแหน่งทศนิยมที่ต้องการ (ในตัวอย่างของเรา เราใช้ทศนิยมสามตำแหน่งสำหรับแต่ละหมายเลข) เนื่องจากตัวเลขในตารางไม่ได้ขึ้นอยู่กับแต่ละอื่น ๆ จึงสามารถข้ามตารางได้ วิธีทางที่แตกต่างเช่น จากบนลงล่าง หรือจากขวาไปซ้าย หรือพูดว่า คุณสามารถเลือกตัวเลขที่อยู่ในตำแหน่งคู่ได้

ศักดิ์ศรี วิธีนี้คือมันสร้างตัวเลขสุ่มอย่างแท้จริงเนื่องจากตารางมีตัวเลขที่ไม่สัมพันธ์กันซึ่งตรวจสอบแล้ว ข้อเสียของวิธีการ: สำหรับการจัดเก็บ ปริมาณมากตัวเลขต้องใช้หน่วยความจำมาก การสร้างและตรวจสอบตารางประเภทนี้เป็นเรื่องยากมาก การทำซ้ำเมื่อใช้ตารางไม่รับประกันความสุ่มของลำดับตัวเลขอีกต่อไป และความน่าเชื่อถือของผลลัพธ์ด้วย

มีตารางที่ประกอบด้วยตัวเลขที่ตรวจสอบแบบสุ่มอย่างแน่นอน 500 ตัว (นำมาจากหนังสือของ I. G. Venetsky, V. I. Venetskaya "แนวคิดและสูตรทางคณิตศาสตร์และสถิติพื้นฐานในการวิเคราะห์ทางเศรษฐศาสตร์")

อัลกอริทึม RNG

ตัวเลขที่สร้างโดย RNG เหล่านี้จะเป็นการสุ่มหลอกเสมอ (หรือกึ่งสุ่ม) กล่าวคือ แต่ละหมายเลขที่สร้างขึ้นในภายหลังจะขึ้นอยู่กับตัวเลขก่อนหน้า:

ร ฉัน + 1 = ฉ(ร ฉัน) .

ลำดับที่ประกอบด้วยตัวเลขดังกล่าวจะก่อให้เกิดการวนซ้ำ กล่าวคือ จำเป็นต้องมีวงจรที่ซ้ำกัน จำนวนอนันต์ครั้งหนึ่ง. วงจรที่เกิดซ้ำเรียกว่าช่วงเวลา

ข้อดีของ RNG เหล่านี้คือความเร็ว เครื่องกำเนิดไฟฟ้าแทบไม่ต้องใช้ทรัพยากรหน่วยความจำและมีขนาดกะทัดรัด ข้อเสีย: ตัวเลขไม่สามารถเรียกว่าสุ่มได้ทั้งหมด เนื่องจากมีการพึ่งพากันระหว่างตัวเลขเหล่านั้น เช่นเดียวกับการมีจุดในลำดับของตัวเลขกึ่งสุ่ม

ลองพิจารณาวิธีการอัลกอริทึมหลายวิธีในการรับ RNG:

• วิธีหาค่ามัธยฐานกำลังสอง
• วิธีการผลิตภัณฑ์ขั้นกลาง
• วิธีการกวน
• วิธีสมภาคเชิงเส้น

วิธีมิดสแควร์

มีเลขสี่หลักอยู่บ้าง ร 0 . หมายเลขนี้ถูกยกกำลังสองและป้อนเข้าไป ร 1. ต่อไปจาก ร 1 นำตัวเลขสุ่มตัวใหม่ที่อยู่ตรงกลาง (สี่หลักกลาง) มาเขียนลงไป ร 0 . จากนั้นให้ทำซ้ำขั้นตอนนี้ (ดูรูปที่ 22.6) โปรดทราบว่าในความเป็นจริงคุณไม่จำเป็นต้องใช้ตัวเลขสุ่ม กิจ, ก 0.กิจโดยมีศูนย์และจุดทศนิยมบวกทางด้านซ้าย ข้อเท็จจริงนี้สะท้อนให้เห็นดังในรูป 22.6 และในตัวเลขที่คล้ายกันถัดๆ ไป

ข้อเสียของวิธีการ: 1) หากมีการวนซ้ำตัวเลข ร 0 จะเท่ากับศูนย์ จากนั้นตัวกำเนิดจะเสื่อมลง ดังนั้นการเลือกค่าเริ่มต้นที่ถูกต้องจึงเป็นสิ่งสำคัญ ร 0 ; 2) เครื่องกำเนิดจะทำซ้ำลำดับผ่าน ม nขั้นตอน (ใน สถานการณ์กรณีที่ดีที่สุด), ที่ไหน nตัวเลขหลัก ร 0 , มฐานของระบบตัวเลข

ตัวอย่างเช่นในรูป 22.6: ถ้าเป็นตัวเลข ร 0 จะแสดงในระบบเลขฐานสอง ตามด้วยลำดับ ตัวเลขสุ่มเทียมทำซ้ำใน 2 4 = 16 ขั้นตอน โปรดทราบว่าการทำซ้ำของลำดับอาจเกิดขึ้นเร็วกว่านี้หากเลือกหมายเลขเริ่มต้นได้ไม่ดี

วิธีการที่อธิบายไว้ข้างต้นเสนอโดย John von Neumann และมีอายุย้อนไปถึงปี 1946 เนื่องจากวิธีนี้ไม่น่าเชื่อถือ จึงถูกละทิ้งอย่างรวดเร็ว

วิธีการกลางผลิตภัณฑ์

ตัวเลข ร 0 คูณด้วย ร 1 จากผลลัพธ์ที่ได้รับ ร 2 ตรงกลางถูกดึงออกมา ร 2 * (นี่คือตัวเลขสุ่มอีกตัวหนึ่ง) แล้วคูณด้วย ร 1. ตัวเลขสุ่มที่ตามมาทั้งหมดคำนวณโดยใช้รูปแบบนี้ (ดูรูปที่ 22.7)

วิธีการกวน

วิธีการสุ่มใช้การดำเนินการเพื่อเลื่อนเนื้อหาของเซลล์ไปทางซ้ายและขวาแบบวนรอบ แนวคิดของวิธีการมีดังนี้ ให้เซลล์เก็บหมายเลขเริ่มต้น ร 0 . เลื่อนเนื้อหาของเซลล์ไปทางซ้ายแบบวนรอบ 1/4 ของความยาวเซลล์เราจะได้ตัวเลขใหม่ ร 0 * . ในทำนองเดียวกัน หมุนเวียนเนื้อหาของเซลล์ ร 0 ไปทางขวาคูณ 1/4 ของความยาวเซลล์ เราจะได้เลขตัวที่สอง ร 0**. ผลรวมของตัวเลข ร 0* และ ร 0** ให้ตัวเลขสุ่มใหม่ ร 1. ไกลออกไป รเข้ามาแล้ว 1 อัน ร 0 และทำซ้ำลำดับการทำงานทั้งหมด (ดูรูปที่ 22.8)

โปรดทราบว่าตัวเลขที่เกิดจากผลรวม ร 0* และ ร 0 ** อาจไม่พอดีกับเซลล์ทั้งหมด ร 1. ในกรณีนี้ จะต้องละทิ้งตัวเลขพิเศษออกจากตัวเลขผลลัพธ์ ให้เราอธิบายเรื่องนี้ในรูป 22.8 โดยที่เซลล์ทั้งหมดจะแสดงด้วยเลขฐานสองแปดหลัก อนุญาต ร 0 * = 10010001 2 = 145 10 , ร 0 ** = 10100001 2 = 161 10 , แล้ว ร 0 * + ร 0 ** = 100110010 2 = 306 10 - อย่างที่คุณเห็นตัวเลข 306 นั้นมี 9 หลัก (ในระบบเลขฐานสอง) และเซลล์ ร 1 (เช่นเดียวกับ ร 0) สามารถมีได้สูงสุด 8 บิต ดังนั้นก่อนจะใส่ค่าเข้าไป ร 1 จำเป็นต้องลบ "พิเศษ" หนึ่งบิตซ้ายสุดออกจากหมายเลข 306 ผลลัพธ์ที่ได้ ร 1 จะไม่ไปที่ 306 อีกต่อไป แต่เป็น 00110010 2 = 50 10 โปรดทราบว่าในภาษาเช่นปาสคาล "การตัด" บิตพิเศษเมื่อเซลล์ล้นจะดำเนินการโดยอัตโนมัติตามประเภทของตัวแปรที่ระบุ

วิธีสมภาคเชิงเส้น

วิธีการสมภาคเชิงเส้นเป็นหนึ่งในขั้นตอนที่ง่ายที่สุดและใช้กันมากที่สุดในปัจจุบันในการจำลองตัวเลขสุ่ม วิธีการนี้ใช้ mod( x, ย) ซึ่งส่งคืนส่วนที่เหลือเมื่ออาร์กิวเมนต์แรกถูกหารด้วยวินาที จำนวนสุ่มที่ตามมาแต่ละตัวจะคำนวณตามจำนวนสุ่มก่อนหน้าโดยใช้สูตรต่อไปนี้:

ร ฉัน+ 1 = ม็อด( เค · ร ฉัน + ข, ม) .

ลำดับของตัวเลขสุ่มที่ได้รับโดยใช้สูตรนี้เรียกว่า ลำดับที่สอดคล้องกันเชิงเส้น- ผู้เขียนหลายคนเรียกลำดับที่สอดคล้องกันเชิงเส้นเมื่อ ข = 0 วิธีคูณที่เท่ากันทุกประการ, และเมื่อ ข ≠ 0 — วิธีผสมที่สอดคล้องกัน.

สำหรับเครื่องกำเนิดไฟฟ้าคุณภาพสูงจำเป็นต้องเลือกค่าสัมประสิทธิ์ที่เหมาะสม จำเป็นต้องมีจำนวนนั้น มมีขนาดค่อนข้างใหญ่เนื่องจากช่วงเวลานั้นไม่สามารถมีได้อีกต่อไป มองค์ประกอบ ในทางกลับกัน การแบ่งที่ใช้ในวิธีนี้เป็นการดำเนินการที่ค่อนข้างช้า ดังนั้นสำหรับคอมพิวเตอร์ไบนารี่ ตัวเลือกเชิงตรรกะจะเป็น ม = 2 เอ็นเนื่องจากในกรณีนี้ การค้นหาส่วนที่เหลือของการหารจะลดลงภายในคอมพิวเตอร์เป็นการดำเนินการทางตรรกะแบบไบนารี "AND" การเลือกจำนวนเฉพาะที่ใหญ่ที่สุดก็เป็นเรื่องปกติเช่นกัน มน้อยกว่า 2 เอ็น: ในวรรณกรรมเฉพาะทางได้รับการพิสูจน์แล้วว่าในกรณีนี้ตัวเลขลำดับต่ำของตัวเลขสุ่มผลลัพธ์ ร ฉัน+ 1 มีพฤติกรรมสุ่มเหมือนกับรุ่นเก่า ซึ่งส่งผลเชิงบวกต่อลำดับตัวเลขสุ่มโดยรวม ยกตัวอย่างหนึ่งใน ตัวเลขเมอร์เซนเท่ากับ 2 31 1 ดังนั้น ม= 2 31 1 .

ข้อกำหนดประการหนึ่งสำหรับลำดับที่สอดคล้องกันเชิงเส้นคือความยาวของคาบต้องยาวที่สุดเท่าที่จะเป็นไปได้ ความยาวของช่วงเวลาขึ้นอยู่กับค่า ม , เคและ ข- ทฤษฎีบทที่เรานำเสนอด้านล่างนี้ช่วยให้เราสามารถระบุได้ว่าเป็นไปได้หรือไม่ที่จะบรรลุช่วงเวลาดังกล่าว ความยาวสูงสุดสำหรับค่าเฉพาะ ม , เคและ ข .

ทฤษฎีบท- ลำดับสมภาคเชิงเส้นที่กำหนดโดยตัวเลข ม , เค , ขและ ร 0 มีคาบความยาว มหากและหาก:

• ตัวเลข ขและ มค่อนข้างง่าย
• เค 1 ครั้ง พีสำหรับทุก ๆ ไพรม์ พีซึ่งเป็นตัวหาร ม ;
• เค 1 เป็นผลคูณของ 4 ถ้า มหลายเท่าของ 4

สุดท้าย เราจะสรุปด้วยตัวอย่างการใช้วิธีสมภาคเชิงเส้นเพื่อสร้างตัวเลขสุ่ม

มีการพิจารณาว่าชุดตัวเลขสุ่มหลอกที่สร้างขึ้นจากข้อมูลจากตัวอย่างที่ 1 จะถูกทำซ้ำทุกๆ ม/4 หมายเลข. ตัวเลข ถามถูกตั้งค่าโดยพลการก่อนเริ่มการคำนวณ อย่างไรก็ตาม โปรดทราบว่าซีรีส์นี้ให้ความรู้สึกของการสุ่มในวงกว้าง เค(และดังนั้นจึง ถาม- ผลลัพธ์สามารถปรับปรุงได้บ้างถ้า ขแปลกและ เค= 1 + 4 · ถาม ในกรณีนี้ แถวจะซ้ำกันทุกแถว มตัวเลข หลังจากค้นหามานาน เคนักวิจัยตัดสินด้วยค่า 69069 และ 71365

เครื่องสร้างตัวเลขสุ่มโดยใช้ข้อมูลจากตัวอย่างที่ 2 จะสร้างตัวเลขสุ่มที่ไม่ซ้ำกันด้วยคาบ 7 ล้าน

วิธีการคูณเพื่อสร้างตัวเลขสุ่มเทียมเสนอโดย D. H. Lehmer ในปี 1949

ตรวจสอบคุณภาพของเครื่องกำเนิดไฟฟ้า

คุณภาพของทั้งระบบและความแม่นยำของผลลัพธ์ขึ้นอยู่กับคุณภาพของ RNG ดังนั้นลำดับสุ่มที่สร้างโดย RNG จะต้องเป็นไปตามเกณฑ์หลายประการ

การตรวจสอบที่ดำเนินการมีสองประเภท:

• ตรวจสอบความสม่ำเสมอของการกระจาย
• การทดสอบความเป็นอิสระทางสถิติ

ตรวจสอบความสม่ำเสมอของการกระจายตัว

1) RNG ควรสร้างค่าใกล้เคียงกับค่าพารามิเตอร์ทางสถิติที่มีลักษณะเฉพาะของกฎสุ่มที่สม่ำเสมอ:

2) การทดสอบความถี่

การทดสอบความถี่ช่วยให้คุณทราบว่ามีตัวเลขจำนวนเท่าใดที่อยู่ในช่วงหนึ่งๆ (ม ร – σ ร ; ม ร + σ ร) นั่นคือ (0.5 0.2887; 0.5 + 0.2887) หรือท้ายที่สุดคือ (0.2113; 0.7887) เนื่องจาก 0.7887 0.2113 = 0.5774 เราสรุปได้ว่าใน RNG ที่ดี ประมาณ 57.7% ของตัวเลขสุ่มที่สุ่มออกมาทั้งหมดควรอยู่ในช่วงนี้ (ดูรูปที่ 22.9)

นอกจากนี้ยังจำเป็นต้องคำนึงว่าจำนวนตัวเลขที่อยู่ในช่วง (0; 0.5) ควรเท่ากับจำนวนตัวเลขที่อยู่ในช่วงโดยประมาณ (0.5; 1)

3) การทดสอบไคสแควร์

การทดสอบไคสแควร์ (การทดสอบ χ 2) เป็นหนึ่งในการทดสอบทางสถิติที่รู้จักกันดีที่สุด เป็นวิธีหลักที่ใช้ร่วมกับเกณฑ์อื่นๆ การทดสอบไคสแควร์เสนอในปี 1900 โดยคาร์ล เพียร์สัน ผลงานอันโดดเด่นของเขาถือเป็นรากฐานของสถิติทางคณิตศาสตร์สมัยใหม่

สำหรับกรณีของเรา การทดสอบโดยใช้เกณฑ์ไคสแควร์จะช่วยให้เราทราบว่ามีค่าเท่าใด จริง RNG อยู่ใกล้แล้ว มาตรฐานอาร์เอ็นจีนั่นคือไม่ว่าจะเป็นไปตามข้อกำหนดของการกระจายแบบสม่ำเสมอหรือไม่ก็ตาม

แผนภาพความถี่ อ้างอิง RNG จะแสดงในรูป 22.10. เนื่องจากกฎการกระจายของ RNG อ้างอิงมีความสม่ำเสมอ ความน่าจะเป็น (ตามทฤษฎี) พี ฉันการรับตัวเลขเข้ามา ฉันช่วงเวลาที่ (ช่วงเวลาทั้งหมดนี้ เค) เท่ากับ พี ฉัน = 1/เค - และด้วยเหตุนี้ในแต่ละ เคช่วงเวลาจะตี เรียบโดย พี ฉัน · เอ็น ตัวเลข ( เอ็นจำนวนตัวเลขทั้งหมดที่สร้างขึ้น)

RNG จริงจะสร้างตัวเลขที่กระจาย (และไม่จำเป็นต้องเท่ากัน!) เคช่วงเวลาและแต่ละช่วงจะมี n ฉันตัวเลข (รวม n 1 + n 2 + + n เค = เอ็น - เราจะทราบได้อย่างไรว่า RNG ที่กำลังทดสอบนั้นดีแค่ไหน และใกล้กับข้อมูลอ้างอิงมากน้อยเพียงใด การพิจารณาความแตกต่างกำลังสองระหว่างจำนวนผลลัพธ์ของตัวเลขค่อนข้างสมเหตุสมผล n ฉันและ "การอ้างอิง" พี ฉัน · เอ็น - มาบวกกันและผลลัพธ์คือ:

χ 2 ประสบการณ์ - n 1 พี 1 · เอ็น) 2 + (n 2 พี 2 · เอ็น) 2 + + ( n เค – พี เค · เอ็น) 2 .

จากสูตรนี้จะตามมาว่ายิ่งความแตกต่างในแต่ละเงื่อนไขน้อยลง (และด้วยเหตุนี้ มูลค่าน้อยลงχ 2 ประสบการณ์ ) ยิ่งกฎการกระจายตัวเลขสุ่มที่สร้างโดย RNG จริงมีความสม่ำเสมอมากขึ้นเท่าใด ก็จะมีความสม่ำเสมอมากขึ้นเท่านั้น

ในนิพจน์ที่แล้ว แต่ละเงื่อนไขถูกกำหนดให้มีน้ำหนักเท่ากัน (เท่ากับ 1) ซึ่งอันที่จริงอาจไม่เป็นความจริง ดังนั้นสำหรับสถิติไคสแควร์ จึงจำเป็นต้องทำให้แต่ละรายการเป็นมาตรฐาน ฉันเทอมที่ 3 หารด้วย พี ฉัน · เอ็น :

สุดท้ายนี้ มาเขียนนิพจน์ผลลัพธ์ให้กระชับยิ่งขึ้นและทำให้ง่ายขึ้น:

เราได้รับค่าทดสอบไคสแควร์สำหรับ ทดลองข้อมูล.

ในตาราง ให้ 22.2 ตามทฤษฎีค่าไคสแควร์ (χ 2 ตามทฤษฎี) โดยที่ ν = เอ็น 1 คือจำนวนระดับความเป็นอิสระ พีนี่คือระดับความเชื่อมั่นที่ผู้ใช้ระบุซึ่งบ่งชี้ว่า RNG ควรตอบสนองความต้องการของการกระจายแบบสม่ำเสมอมากน้อยเพียงใด หรือ พี — คือความน่าจะเป็นที่ค่าทดลองของ χ 2 exp จะน้อยกว่าตาราง (เชิงทฤษฎี) χ 2 ตามทฤษฎี หรือเท่ากับมัน.

ถือว่ายอมรับได้ พี จาก 10% ถึง 90%.

ถ้า χ 2 ประสบการณ์ มากกว่าทฤษฎี χ 2 มาก (นั่นคือ พีมีขนาดใหญ่) จากนั้นเครื่องกำเนิดไฟฟ้า ไม่พอใจข้อกำหนดของการแจกแจงแบบสม่ำเสมอเนื่องจากค่าที่สังเกตได้ n ฉันไปไกลจากทฤษฎีมากเกินไป พี ฉัน · เอ็น และไม่สามารถถือเป็นการสุ่มได้ กล่าวอีกนัยหนึ่งคือมีการติดตั้งขนาดใหญ่มาก ช่วงความมั่นใจว่าข้อจำกัดด้านตัวเลขเริ่มหลวมมาก ข้อกำหนดด้านตัวเลขเริ่มอ่อนแอ ในกรณีนี้จะสังเกตเห็นข้อผิดพลาดสัมบูรณ์ที่มีขนาดใหญ่มาก

แม้แต่ D. Knuth ในหนังสือของเขาเรื่อง "The Art of Programming" ยังตั้งข้อสังเกตว่าการมี χ 2 exp. โดยทั่วไปสำหรับคนตัวเล็กมันก็ไม่ดีเช่นกันแม้ว่าเมื่อมองแวบแรกจะดูยอดเยี่ยมจากมุมมองของความสม่ำเสมอ จริงๆ แล้วใช้ชุดตัวเลข 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6 ซึ่งเหมาะอย่างยิ่งจากมุมมองของความสม่ำเสมอและ χ ประสบการณ์ 2 ครั้ง จะเป็นศูนย์ในทางปฏิบัติ แต่คุณไม่น่าจะจดจำพวกมันเป็นการสุ่มได้

ถ้า χ 2 ประสบการณ์ น้อยกว่าทฤษฎี χ 2 มาก (นั่นคือ พีเล็ก) จากนั้นเครื่องกำเนิด ไม่พอใจข้อกำหนดของการแจกแจงแบบสม่ำเสมอแบบสุ่ม เนื่องจากค่าที่สังเกตได้ n ฉันใกล้เคียงกับทฤษฎีมากเกินไป พี ฉัน · เอ็น และไม่สามารถถือเป็นการสุ่มได้

แต่ถ้า χ 2 ประสบการณ์ อยู่ในช่วงที่แน่นอนระหว่างค่าสองค่าของทฤษฎี χ 2 หรือ ซึ่งสอดคล้องกัน เช่น พี= 25% และ พี= 50% จากนั้นเราสามารถสรุปได้ว่าค่าตัวเลขสุ่มที่สร้างโดยเซ็นเซอร์นั้นเป็นการสุ่มโดยสมบูรณ์

นอกจากนี้ควรคำนึงถึงคุณค่าทั้งหมดด้วย พี ฉัน · เอ็น ต้องมีขนาดใหญ่เพียงพอ เช่น มากกว่า 5 (พบโดยเชิงประจักษ์) เมื่อถึงเวลานั้น (ด้วยตัวอย่างทางสถิติที่มีขนาดใหญ่เพียงพอ) เท่านั้นจึงจะถือว่าเงื่อนไขการทดลองเป็นที่น่าพอใจ

ดังนั้นขั้นตอนการตรวจสอบจึงเป็นดังนี้

ทดสอบความเป็นอิสระทางสถิติ

1) การตรวจสอบความถี่ของการเกิดตัวเลขในลำดับ

ลองดูตัวอย่าง หมายเลขสุ่ม 0.2463389991 ประกอบด้วยตัวเลข 2463389991 และหมายเลข 0.5467766618 ประกอบด้วยตัวเลข 5467766618 การเชื่อมต่อลำดับของตัวเลขเรามี: 24633899915467766618

เป็นที่ชัดเจนว่าความน่าจะเป็นทางทฤษฎี พี ฉันการสูญเสีย ฉันหลักที่ (ตั้งแต่ 0 ถึง 9) เท่ากับ 0.1

2) การตรวจสอบลักษณะของชุดตัวเลขที่เหมือนกัน

ให้เราแสดงโดย n ลจำนวนชุดของตัวเลขที่เหมือนกันในแถวความยาว ล- ทุกอย่างจะต้องมีการตรวจสอบ ลตั้งแต่ 1 ถึง ม, ที่ไหน มนี่คือหมายเลขที่ผู้ใช้ระบุ: จำนวนสูงสุดที่เกิดขึ้นของหลักที่เหมือนกันในชุด

ในตัวอย่าง “24633899915467766618” พบ 2 ชุดความยาว 2 (33 และ 77) นั่นคือ n 2 = 2 และ 2 อนุกรมความยาว 3 (999 และ 666) นั่นคือ n 3 = 2 .

ความน่าจะเป็นที่อนุกรมของความยาวจะเกิดขึ้น ลเท่ากับ: พี ล= 9 10 ล (ตามทฤษฎี) นั่นคือ ความน่าจะเป็นที่ซีรีส์หนึ่งจะมีความยาวอักขระเท่ากับ: พี 1 = 0.9 (ตามทฤษฎี) ความน่าจะเป็นที่จะมีอักขระสองตัวปรากฏเป็นชุดคือ: พี 2 = 0.09 (ตามทฤษฎี) ความน่าจะเป็นที่จะมีอักขระสามตัวปรากฏเป็นชุดคือ: พี 3 = 0.009 (ตามทฤษฎี)

ตัวอย่างเช่น ความน่าจะเป็นที่ซีรีส์หนึ่งจะมีความยาวหนึ่งอักขระ พี ล= 0.9 เนื่องจากสามารถมีได้เพียงสัญลักษณ์เดียวจาก 10 และมีทั้งหมด 9 สัญลักษณ์ (ศูนย์ไม่นับ) และความน่าจะเป็นที่สัญลักษณ์ “XX” ที่เหมือนกันสองตัวจะปรากฏเรียงกันเป็น 0.1 · 0.1 · 9 นั่นคือความน่าจะเป็นที่ 0.1 ที่สัญลักษณ์ “X” จะปรากฏในตำแหน่งแรกคูณด้วยความน่าจะเป็นที่ 0.1 ที่ สัญลักษณ์เดียวกันจะปรากฏในตำแหน่งที่สอง “X” และคูณด้วยจำนวนชุดดังกล่าว 9

ความถี่ของการเกิดอนุกรมคำนวณโดยใช้สูตรไคสแควร์ที่เราพูดถึงก่อนหน้านี้โดยใช้ค่าต่างๆ พี ล .

หมายเหตุ: ตัวสร้างสามารถทดสอบได้หลายครั้ง แต่การทดสอบจะไม่สมบูรณ์และไม่รับประกันว่าตัวสร้างจะสร้างตัวเลขสุ่ม ตัวอย่างเช่น เครื่องกำเนิดไฟฟ้าที่สร้างลำดับ 12345678912345 จะถือว่าเหมาะสมที่สุดในระหว่างการทดสอบ ซึ่งเห็นได้ชัดว่าไม่เป็นความจริงทั้งหมด

โดยสรุป เราสังเกตว่าบทที่สามของหนังสือ The Art of Programming (เล่ม 2) ของ Donald E. Knuth เน้นไปที่การศึกษาตัวเลขสุ่มโดยเฉพาะ มันเรียน วิธีการต่างๆการสร้างตัวเลขสุ่ม การทดสอบความสุ่มทางสถิติ และการแปลงตัวเลขสุ่มแบบกระจายสม่ำเสมอไปเป็นรูปแบบอื่น ตัวแปรสุ่ม- มีมากกว่าสองร้อยหน้าสำหรับการนำเสนอเนื้อหานี้