使用 RDRAND 指令确保在一定范围内生成无偏数字

Question

正在进行代码高尔夫挑战，需要使用RDRAND硬件随机数生成器。

示例

将

r12

设置为随机数

[0,255]

rdrand ax
movzx r12,al

将

r8

设置为随机数

[0,1]

rdrand r8
and r8,1

问题

我假设上面的例子是无偏见的？

但是，假设挑战需要生成

[0,N]

范围内的随机数，比如说

N=512

，是否会引入任何偏差？如果是这样，从

[0,N]

生成无偏随机数的正确汇编代码是什么？

更新

基于评论

对于 2 的幂范围，只需屏蔽掉您想要的位即可。

也许这个示例可以通过查看 2^10 范围然后屏蔽位来工作？

    ; Generate a random number until it is in the range [0, 512]
    mov dword[num], 0
retry0:
    rdrand eax
    jnc retry0
    and eax, 1023 ; Limit the range to [0, 1023] to fit into 10 bits
    cmp eax, 512  ; Check if the number is within [0, 512]. (Rejection Sampling)
    ja retry0     ; If above 512, generate again

    mov [num], eax

Answer 1

正如评论部分所建议的，这是我将 Lemire's Method 转换为 Nasm 的尝试。它输出 [0,N] 中的随机 32 位数字。

基本上，采用了这个 C godbolt 示例并将其移植到 Nasm 示例

; Output a random number from [0,N]
;
; Debiased Integer Multiplication — Lemire's Method
;
; uint32_t bounded_rand(rng_t& rng, uint32_t range) {
;     uint32_t t = (-range) % range;
;     do {
;         uint32_t x = rng();
;         uint64_t m = uint64_t(x) * uint64_t(range);
;         uint32_t l = uint32_t(m);
;     } while (l < t);
;     return m >> 32;
; }


section .bss
    num resd 1             
    num_str resb 12       

section .text
global _start

_start:

    ; Generate a random number until it is in the range [0, 8192]
    mov edi, 8192           ; range = EDI

    ; uint32_t t = (-range) % range;
    inc     edi             ; [0, 8193)
    mov     eax, edi        ; 
    neg     eax             ; (-range)
    mov     edx, 0          ; 
    div     edi             ; % range
    mov     ebx, edx        ; t = EBX

.retry:
    rdrand  eax
    jnc     .retry
    mov     ecx, eax        ; uint32_t x = rng(); where x = ECX
    mov     edx, ecx
    mov     eax, edi
    imul    rax, rdx        ; uint64_t m = uint64_t(x) * uint64_t(range); result in RDX:RAX
    mov     rsi, rax        ; m = RSI
    mov     eax, edx        ; Move higher 32 bits of result to EAX (this is 'm >> 32')
    cmp     eax, ebx        ; Compare with t
    jb      .retry          ; while (l < t);
    mov     rax, rsi
    shr     rax, 32         ; m >> 32

    mov [num], eax
    call int_to_ascii
    call print_string
    call exit_program


int_to_ascii:
    mov eax, [num]
    mov rdi, num_str
    add rdi, 10
    mov byte [rdi], 0
    mov ecx, 10
.loop:
    inc rbx
    xor edx, edx
    div ecx
    add dl, '0'
    dec rdi
    mov [rdi], dl
    test eax, eax
    jnz .loop
    mov rsi, rdi
    ret

print_string:
    mov byte[rsi+rbx],0x0A
    inc rbx
    mov rax, 1
    mov rdi, 1
    mov rdx, rbx
    syscall
    ret

exit_program:
    mov rax, 60
    xor rdi, rdi
    syscall

如果有任何明显的错误，请告诉我。谢谢。