Cách hiệu quả để chọn một chỉ mục mảng bằng cách sử dụng một số ngẫu nhiên 64 bit?

Nói, tôi có uint64_t rand = <số ngẫu nhiên>, và mảng char[20] = .... Mục tiêu của tôi là chọn một phần tử trong mảng dựa vào nội dung của rand.

1. Một cách chậm là sử dụng phần còn lại: size_t i = rand% 20 sau đó chọn phần tử theo mảng[i].
2. Một cách khác, mà tôi đoán nhanh hơn, là tôi = rand/UINT64_MAX * 20. Hoặc, để tránh cần các hoạt động thả nổi, bộ đếm nghịch đảo của nó 20/(UINT64_MAX/rand).
3. Cách thứ 3 là sử dụng các bit ngẫu nhiên để phân nhánh thành chỉ mục giống như một cái cây (nhưng bỏ lỡ mọi số thứ 5):

size_t tổng_byte = 20;
size_t mặt nạ = 1;
size_t tôi = 0;
trong khi (total_byte) {
  if (rand & mask) i += total_bytes / 2; // rẽ phải
  khác tôi += 0; // nhánh trái
  mặt nạ <<= 1;
  tổng_byte /= 2;
}

Có cách nào nhanh hơn trên phần cứng phổ biến không? Ví dụ. máy tính xách tay/máy tính để bàn?

Lý do tôi quan tâm: Tôi đang triển khai chức năng dẫn xuất khóa cứng bộ nhớ và tại một số điểm, tôi cần chọn một phần tử mảng dựa trên nội dung của bản mã được tính toán. Số ngẫu nhiên là 64 bit.

Ngôn ngữ đích là C.

đồng % 20 tạo ra một kết quả trong $\{0,1,\ldots,18,19\}$ đó là Gần đồng phục (giả sử rand Là): $\Pr(19)/\Pr(0)=1-1/922337203685477581$. Đó thường là một sự thiên vị chấp nhận được.

Trên "máy tính xách tay/máy tính để bàn" có CPU 64 bit hiện đại, đồng % 20 tương đối nhanh và có những ưu điểm quan trọng là chính xác, đơn giản và dễ thích nghi. Tuy nhiên nó ít nhất là thường xuyên (xem bình luận) có thể nhanh hơn bằng cách sử dụng

(rand-((rand-(rand>>2))>>1))>>59

có cùng tỷ lệ (tối ưu) giữa kết quả ít nhất và có thể xảy ra nhất, trong khi chỉ sử dụng các phép toán thay đổi và thêm. Tôi tự tin hơn rằng mã được tạo là liên tục, điều này có thể quan trọng trong các ứng dụng tiền điện tử. Và giá trị trung bình gần với $19/2$.

Để có trực giác về cách thức hoạt động của công thức đó: đối với bất kỳ $x\in\mathbb R$ nó giữ $(x-(x-x\,2^{-2})\,2^{-1})\,2^{-59}=20\,x\,2^{-64}$, do đó về cơ bản chúng tôi đánh giá những gì các biểu thức (uint64_t)sàn(rand*(20/(UINT64_MAX+1.))) hoặc (uint64_t)((rand*(uint128_t)20)>>64) cố gắng đánh giá. Lưu ý rằng đối với một số giá trị bao gồm rand=0xCCCCCCCCCCCCCCCC công thức sau không hoàn toàn trùng khớp với công thức tôi đề xuất; nhưng phân phối đạt được bởi cả hai là đồng nhất tối ưu.

Phương pháp này không giới hạn ở hằng số $m=20$ cho kích thước mảng. Nó khái quát hóa cho bất kỳ hằng số $m$ với trọng lượng Hamming vừa phải. Tính toán số ca thích hợp từ các hằng số là không cần thiết. tôi đề cập đến điều này câu trả lời tuyệt vời (lưu ý: số ca làm việc cuối cùng được đưa ra phải tăng thêm 32 trong trường hợp hiện tại) đối với thứ gì đó hoạt động, nhưng không phải lúc nào cũng tối ưu. Tôi không có tài liệu tham khảo nào khác cho phương pháp mà tôi (lại-?)đã phát minh ra cho ARM Cortex-M0, nơi nó tỏ ra hữu ích. Trên thực tế, theo kinh nghiệm, tôi chỉ tìm thấy các công thức cho một vài hằng số phù hợp với nhu cầu của mình và Anders Kaseorg hoàn toàn tin tưởng vào cách tạo công thức một cách có hệ thống.

Nếu chúng tôi sẵn sàng mất một chút tính đồng nhất và đảm bảo rằng mã là thời gian không đổi, chúng tôi có thể sử dụng

((rand>>3)*5)>>59

cái nào đơn giản hơn, có khả năng nhanh hơn và dễ dàng thích ứng với các hằng số khác $m$ còn hơn là $20$: chúng tôi viết $m$ như $r\,2^i$ với $i$ một số nguyên và $r$ tốt nhất là lẻ, sau đó tìm số nguyên $j$ với $2^{j-1}\le r<2^j$. Chúng tôi sử dụng ((rand>>j)*r)>>(64+i-j). Vấn đề là, càng thấp $j$ bit của rand không được sử dụng và tính đồng nhất của kết quả bị giảm tương ứng (ngoại trừ nếu $m$ là lũy thừa của hai).

Khi nào $m$ Là $2^j$ cho một số nguyên $j$, chúng ta có thể sử dụng rand>>(64-j) hoặc rand&(m-1). Cái sau được chú ý trong câu trả lời khác. Các phương pháp này không mất tính đồng nhất, nếu tất cả các bit của rand là thống nhất và độc lập.

Nếu $m$ thay đổi trong thời gian chạy với $m<2^j$ cho một số hằng số đã biết $j$, chúng ta có thể sử dụng

((rand>>j)*m)>>(64-j)

tuy nhiên $j$ bit thấp hơn của rand bị mất và điều đó làm giảm tính đồng nhất của kết quả (ngoại trừ nếu $m$ là lũy thừa của hai).

Đề ra:

• (uint64_t)(sàn(rand*(20/(UINT64_MAX+1.)))) sẽ ổn nếu không có lỗi làm tròn, nhưng vì những lỗi này tồn tại nên khó biết liệu nó có mang lại kết quả hay không 20 cho một số đầu vào; cũng trên nhiều trình biên dịch, nó không thống nhất tối ưu.
• (uint64_t)((rand*(uint128_t)20)>>64) đúng về mặt toán học và rất gần với những gì chúng tôi đánh giá, nhưng uint128_t là một tính năng C tùy chọn và vẫn được hỗ trợ một chút.
• câu hỏi là rand/UINT64_MAX * 20 đầu ra trong $\{0,20\}$ như vậy là không phù hợp. Các vấn đề là phép chia làm tròn xuống số nguyên và (độc lập) rằng rand có thể UINT64_MAX.
• câu hỏi là 20/(UINT64_MAX/rand) đầu ra trong $\{0,1,2,3,4,5,6,10,20\}$ và có thể gây ra phép chia cho 0, do đó không phù hợp. Các vấn đề là phép chia làm tròn xuống số nguyên và (độc lập) rằng rand có thể 0.
• Đoạn mã 3 của câu hỏi luôn có i%5 != 4 trên đầu ra, do đó là không phù hợp. Vấn đề là đầu ra tôi được xây dựng như 10+5+2+1 với một số điều khoản bị loại bỏ.

Thông thường, người ta sẽ cố gắng làm cho kích thước mảng có lũy thừa bằng 2. Sau đó, chỉ số có thể được tính theo bit AND:

mảng ký tự [0x40];
uint64_t rand;
...
char c = mảng[rand & 0x3f];