วิธีที่มีประสิทธิภาพในการเลือกดัชนีอาร์เรย์โดยใช้ a พูด ตัวเลขสุ่ม 64 บิต

พูดว่าฉันมี uint64_t rand = <ตัวเลขสุ่ม>, และ อาร์เรย์ถ่าน [20] = .... เป้าหมายของฉันคือการเลือกองค์ประกอบใน อาร์เรย์ โดยอิงจากเนื้อหาของ แรนด์.

1. วิธีหนึ่งที่ช้าคือใช้ส่วนที่เหลือ: size_t i = แรนด์ % 20 จากนั้นเลือกองค์ประกอบตาม อาร์เรย์[i].
2. อีกทางหนึ่งซึ่ง ฉันคิดว่า เร็วกว่าคือ ฉัน = แรนด์/UINT64_MAX * 20. หรือเพื่อหลีกเลี่ยงความจำเป็นในการดำเนินการแบบลอยตัว ส่วนที่ผกผัน 20/(UINT64_MAX/แรนด์).
3. วิธีที่ 3 คือการใช้บิตสุ่มเพื่อแยกย่อยไปยังดัชนีเหมือนต้นไม้ (แต่พลาดทุกหมายเลขที่ 5):

size_t total_bytes = 20;
size_t มาสก์ = 1;
size_t ฉัน = 0;
ในขณะที่ (total_bytes) {
  ถ้า (แรนด์ & มาสก์) ฉัน += total_bytes / 2; // สาขาขวา
  อื่น ฉัน += 0; //สาขาซ้าย
  หน้ากาก <<= 1;
  total_bytes /= 2;
}

มีวิธีที่เร็วกว่าสำหรับฮาร์ดแวร์ทั่วไปหรือไม่? เช่น. แล็ปท็อป / เดสก์ท็อปพีซี?

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

ภาษาเป้าหมายคือ C

แรนด์ % 20 สร้างผลลัพธ์ใน $\{0,1,\ldots,18,19\}$ นั่นคือ เกือบ ชุดยูนิฟอร์ม(สมมุติ แรนด์ เป็น): $\Pr(19)/\Pr(0)=1-1/922337203685477581$. นั่นเป็นอคติที่ยอมรับได้

บน "แล็ปท็อป/เดสก์ท็อปพีซี" ที่มี CPU 64 บิตที่ทันสมัย แรนด์ % 20 มีความรวดเร็วพอสมควร และมีจุดเด่นที่สำคัญ คือ ถูกต้อง เรียบง่าย และปรับเปลี่ยนได้ง่าย อย่างไรก็ตาม อย่างน้อยก็บ่อยครั้ง (ดู ความคิดเห็น) เป็นไปได้ที่จะใช้เร็วขึ้น

(แรนด์-((แรนด์-(แรนด์>>2))>>1))>>59

ซึ่งมีอัตราส่วน (ที่เหมาะสมที่สุด) เท่ากันระหว่างผลลัพธ์ที่น้อยที่สุดและเป็นไปได้มากที่สุด ในขณะที่ใช้การดำเนินการกะและเพิ่มเท่านั้น ฉันมั่นใจมากขึ้นว่ารหัสที่สร้างขึ้นนั้นเป็นเวลาคงที่ ซึ่งอาจมีความสำคัญในแอปพลิเคชันการเข้ารหัสลับ และค่าเฉลี่ยจะใกล้เคียงกับ $19/2$.

สำหรับสัญชาตญาณว่าสูตรนั้นทำงานอย่างไร: สำหรับใดๆ $x\in\mathbb R$ มันถือ $(x-(x-x\,2^{-2})\,2^{-1})\,2^{-59}=20\,x\,2^{-64}$ดังนั้นเราจึงจำเป็นต้องประเมินสิ่งที่แสดงออก (uint64_t)ชั้น(แรนด์*(20/(UINT64_MAX+1.))) หรือ (uint64_t)((แรนด์*(uint128_t)20)>>64) พยายามประเมิน โปรดสังเกตว่าสำหรับบางค่ารวมถึง แรนด์=0xCCCCCCCCCCCCCCCC สูตรต่อมาไม่ตรงกับสูตรที่ผมเสนอ แต่การกระจายที่ทำได้โดยทั้งสองนั้นมีความสม่ำเสมออย่างเหมาะสมที่สุด

วิธีการไม่จำกัดเฉพาะค่าคงที่ $m=20$ สำหรับขนาดอาร์เรย์ มันทำให้ทุกคน คงที่ $m$ มีน้ำหนักแฮมมิ่งปานกลาง การคำนวณกะที่เหมาะสมจากค่าคงที่นั้นไม่สำคัญ ฉันอ้างถึงสิ่งนี้ คำตอบที่น่าอัศจรรย์ (หมายเหตุ: จำนวนกะสุดท้ายที่กำหนดจะต้องเพิ่มขึ้น 32 ในกรณีที่มีอยู่) สำหรับบางสิ่งที่ใช้งานได้ แต่ก็ไม่ได้ดีที่สุดเสมอไป ฉันไม่มีข้อมูลอ้างอิงอื่นใดสำหรับวิธีการที่ฉันคิดค้นขึ้นใหม่สำหรับ ARM Cortex-M0 ซึ่งพิสูจน์แล้วว่ามีประโยชน์ จริงๆ แล้วฉันพบสูตรเชิงประจักษ์สำหรับค่าคงที่ไม่กี่ค่าที่เหมาะกับความต้องการของฉันเท่านั้น และ Anders Kaseorg ให้ความสำคัญกับวิธีสร้างสูตรอย่างเป็นระบบ

หากเราเต็มใจที่จะสูญเสียความสม่ำเสมอเล็กน้อยและรับประกันว่ารหัสนั้นเป็นเวลาคงที่ เราสามารถใช้

((แรนด์>>3)*5)>>59

ซึ่งง่ายกว่า เร็วกว่า และง่ายกว่าที่จะปรับให้เข้ากับค่าคงที่อื่นๆ $m$ ค่อนข้างมากกว่า $20$: พวกเราเขียน $m$ เช่น $r\,2^i$ กับ $i$ จำนวนเต็มและ $r$ เลขคี่ดีกว่า แล้วหาจำนวนเต็ม $เจ$ กับ $2^{j-1}\le r<2^j$. เราใช้ ((แรนด์>>j)*r)>>(64+i-j). ปัญหาคือด้านล่าง $เจ$ บิตของ แรนด์ ไม่ได้ใช้ และความสม่ำเสมอของผลลัพธ์จะลดลงตามลำดับ (ยกเว้นในกรณีที่ $m$ เป็นกำลังสอง)

เมื่อไร $m$ เป็น $2^j$ สำหรับจำนวนเต็ม $เจ$, เราสามารถใช้ แรนด์>>(64-j) หรือ แรนด์&(m-1). ภายหลังจะสังเกตเห็นใน คำตอบอื่น ๆ. วิธีการเหล่านี้ไม่สูญเสียความสม่ำเสมอ หากบิตทั้งหมด แรนด์ มีความสม่ำเสมอและเป็นอิสระ

ถ้า $m$ การเปลี่ยนแปลงที่รันไทม์ด้วย $m<2^j$ สำหรับค่าคงที่ที่รู้จัก $เจ$, เราสามารถใช้

((แรนด์>>ญ)*ม)>>(64-ญ)

อย่างไรก็ตาม $เจ$ บิตที่ต่ำกว่าของ แรนด์ จะหายไปและทำให้ความสม่ำเสมอของผลลัพธ์ลดลง (ยกเว้นในกรณีที่ $m$ เป็นกำลังสอง)

นอกหัวข้อ:

• (uint64_t)(ชั้น(แรนด์*(20/(UINT64_MAX+1.)))) จะไม่เป็นไรหากไม่มีข้อผิดพลาดในการปัดเศษ แต่เนื่องจากสิ่งเหล่านี้มีอยู่จริง จึงยากที่จะบอกได้ว่าสามารถให้ผลได้หรือไม่ 20 สำหรับการป้อนข้อมูลบางอย่าง นอกจากนี้ในคอมไพเลอร์หลายตัวก็ไม่เหมือนกันอย่างเหมาะสม
• (uint64_t)((แรนด์*(uint128_t)20)>>64) มีความถูกต้องทางคณิตศาสตร์และใกล้เคียงกับที่เราประเมินมาก แต่ uint128_t เป็นคุณลักษณะ C ที่เป็นทางเลือกและยังคงรองรับเล็กน้อย
• คำถาม แรนด์/UINT64_MAX * 20 เอาท์พุทใน $\{0,20\}$ จึงไม่เหมาะ ปัญหาคือการหารปัดเศษลงเป็นจำนวนเต็ม และ (ไม่ขึ้นกับ) สิ่งนั้น แรนด์ เป็นไปได้ UINT64_MAX.
• คำถาม 20/(UINT64_MAX/แรนด์) เอาท์พุทใน $\{0,1,2,3,4,5,6,10,20\}$ และทำให้เกิดการหารด้วยศูนย์ได้ จึงไม่เหมาะ ปัญหาคือการหารปัดเศษลงเป็นจำนวนเต็ม และ (ไม่ขึ้นกับ) สิ่งนั้น แรนด์ เป็นไปได้ 0.
• ส่วนของรหัสคำถาม 3 มีเสมอ ฉัน%5 != 4 บนเอาต์พุตจึงไม่เหมาะ ปัญหาคือผลลัพธ์ ผม ถูกสร้างขึ้นเป็น 10+5+2+1 โดยลบคำศัพท์บางคำออกไป

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

อาร์เรย์ถ่าน [0x40];
uint64_t แรนด์;
...
ถ่าน c = อาร์เรย์ [แรนด์ & 0x3f];