สร้างจำนวนเต็มสุ่มใด ๆ
ฉันขออภัยล่วงหน้าเนื่องจากฉันไม่ค่อยมีประสบการณ์กับความคิดที่เป็นทางการเกี่ยวกับการสุ่ม
หัวเรื่องกล่าวถึงส่วนใหญ่: ฉันต้องการสร้างจำนวนเต็มแบบสุ่มภายในเวลาที่เหมาะสมซึ่งทุกจำนวนเต็มสามารถปรากฏได้ไม่ว่าจะมีความถี่เท่ากันหรือไม่ก็ไม่สำคัญ ในฐานะที่เป็นส่วนเสริมหน่วยความจำคอมพิวเตอร์ไม่ใช่ปัญหาแม้ว่าจะมีพื้นที่หน่วยความจำไม่ จำกัด ในการจัดเก็บตัวเลขที่สร้างขึ้นเหล่านี้ แต่ก็ไม่ชัดเจนว่าจะทำได้อย่างไร ฉันยังไม่ได้ดำเนินการใด ๆ ในการหาอัลกอริทึมที่เหมาะสม แต่นี่คือข้อสังเกตของฉัน
หากคุณสามารถสร้างจำนวนจริงแบบสุ่มคุณสามารถใช้ฟังก์ชันเช่นฟังก์ชันพื้นเพื่อสร้างจำนวนเต็มใด ๆ หากคุณสามารถสุ่มสร้างจำนวนจริงระหว่างช่วงเวลาใดก็ได้$[a,b]$จากนั้นคุณสามารถใช้ฟังก์ชัน asymptotic เช่น $\tan$ เพื่อสร้างจำนวนจริงใด ๆ
โดยทั่วไปถ้าฉันมีเซต S ซึ่งมีคาร์ดินาลลิตี้มากกว่าหรือเท่ากับจำนวนเต็มและฉันสามารถสร้างองค์ประกอบภายใน S แบบสุ่มฉันสามารถสุ่มสร้างจำนวนเต็มใดก็ได้โดยการแมปสมาชิกของ S ลงบนจำนวนเต็ม
ฉันรู้ว่ามีลำดับเช่นลำดับช่องว่างเฉพาะซึ่งเป็นแบบสุ่มและมีจำนวนเต็มขนาดใหญ่ตามอำเภอใจ แต่ไม่สามารถคำนวณได้อย่างง่ายดาย
อย่างไรก็ตามเรื่องนี้เกี่ยวกับสิ่งที่ฉันคิดได้ ฉันจะไม่แปลกใจเลยถ้าไม่มีวิธีแก้ปัญหาง่ายๆ แต่ถ้าใครมีเหตุผลว่าทำไมถึงทำไม่ได้ฉันก็อยากฟังเช่นกัน
คำตอบ
ขนาดตามอำเภอใจไม่มีความหมายเนื่องจากการคำนวณไม่สามารถหยุดได้!
พิจารณาว่าคุณโยนเหรียญสำหรับทุกบิตของจำนวนเต็มแบบสุ่มจากนั้นคุณจะเห็นว่าการโยนเหรียญนั้นไม่มีวันสิ้นสุด
หนึ่งควรระมัดระวังเมื่อเล่นกับขนาดโดยพลการ ในทางคณิตศาสตร์คุณสามารถพูดได้ว่าให้$x$ เป็นจำนวนเต็มแบบสุ่มเช่น $x \stackrel{R}{\leftarrow} \mathbb Z$อย่างไรก็ตามเมื่อคุณพยายามหาคุณค่าของสิ่งนี้คุณจะต้องเผชิญกับการสร้างของมัน หากคุณต้องการจำนวนเต็มสุ่มสม่ำเสมอแน่นอนว่ามันจะล้มเหลว!
ตอนนี้สมมติว่าคุณมีขีด จำกัด เช่น $0\color{red}{<} x \leq 2^L$จากนั้นคุณสามารถใช้LFSRเพื่อสร้างตัวเลขสุ่มในช่วง ถ้า LFSR ที่มีขนาด$L$ เป็นค่าสูงสุดจากนั้นจะเป็นระยะและมีช่วงเวลา $2^L-1$. ในช่วงนี้จะเข้าชมทั้งหมดที่เป็นไปได้$L$ตัวเลขบิตยกเว้นสถานะศูนย์ทั้งหมด คุณสามารถรับเมล็ดพันธุ์จากเวลาและเริ่มใช้งานได้
โปรดทราบว่า LFSR อยู่ห่างไกลจากการเป็นตัวสร้าง Pseudo แบบสุ่มที่ปลอดภัยด้วยการเข้ารหัสลับ (CSPRNG) มีเพียง$2L$ เอาต์พุตบิตจาก LFSR เพียงพอที่จะกำหนดบิตถัดไปเนื่องจากอัลกอริทึม Berlakamp-Massay และที่จริงแล้วการกำจัด Gaussian ก็เพียงพอแล้วอย่างไรก็ตาม BM เร็วกว่ามาก -