O modalitate eficientă de a alege un index de matrice utilizând, să zicem, un număr aleator de 64 de biți?

Spune, am uint64_t rand = <un număr aleatoriu>, și matrice de caractere[20] =.... Scopul meu este să aleg un element matrice pe baza continutului de rand.

1. O modalitate lentă este să folosești restul: size_t i = rand % 20 apoi alegeți elementul de matrice[i].
2. Un alt mod, care Cred este mai rapid, este i = rand/UINT64_MAX * 20. Sau, pentru a evita necesitatea operațiunilor flotante, partea sa inversă 20/(UINT64_MAX/rand).
3. O a treia modalitate este de a folosi biții aleatori pentru a se ramifica la index ca un copac (dar ratează fiecare al 5-lea număr):

size_t total_bytes = 20;
size_t mask = 1;
dimensiunea_t i = 0;
while (total_bytes) {
  if (rand & mask) i += total_bytes / 2; // ramură dreapta
  altfel i += 0; // ramură stângă
  masca <<= 1;
  total_octeți /= 2;
}

Există vreo modalitate mai rapidă pe hardware-ul comun? De exemplu. PC-uri laptop/desktop?

Motivul pentru care îmi pasă: implementez o funcție de derivare a tastei de memorie și, la un moment dat, trebuie să aleg un element de matrice bazat pe conținutul textului cifrat calculat. Numărul aleatoriu este de 64 de biți.

Limba țintă este C.

rand % 20 generează un rezultat în $\{0,1,\ldots,18,19\}$ acesta este aproape uniformă (presupunând rand este): $\Pr(19)/\Pr(0)=1-1/922337203685477581$. Aceasta este adesea o părtinire tolerabilă.

Pe un „laptop/desktop PC” cu un procesor modern pe 64 de biți, rand % 20 este destul de rapid și are virtuțile importante de a fi corect, simplu și ușor de adaptat. Cu toate acestea, este cel puțin des (vezi cometariu) posibil să fie mai rapid folosind

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

care are același raport (optim) între cele mai puțin și cele mai probabile rezultate, utilizând în același timp doar operațiunile de schimbare și adăugare. Sunt mai încrezător că codul generat este în timp constant, ceea ce poate fi important în aplicațiile cripto. Și media este mai aproape de $19/2$.

Pentru o intuiție a modului în care funcționează această formulă: pentru orice $x\in\mathbb R$ tine $(x-(x-x\,2^{-2})\,2^{-1})\,2^{-59}=20\,x\,2^{-64}$, astfel evaluăm în mod esențial care sunt expresiile (uint64_t)floor(rand*(20/(UINT64_MAX+1.))) sau (uint64_t)((rand*(uint128_t)20)>>64) încercarea de a evalua. Observați că pentru unele valori, inclusiv rand=0xCCCCCCCCCCCCCCCCCC formula ulterioară nu coincide tocmai cu formula pe care o propun; totuși distribuția realizată de ambii este optim uniformă.

Metoda nu se limitează la constantă $m=20$ pentru dimensiunea matricei. Se generalizează la oricare constant $m$ cu greutate Hamming moderată. Calcularea numărătorilor de deplasări adecvate din constante este netrivială. Ma refer la asta răspuns minunat (notă: numărul ultimului schimb dat acolo trebuie crescut cu 32 în cazul în cauză) pentru ceva care funcționează, dar nu este întotdeauna optim. Nu am altă referință pentru metoda, pe care am (re-?)inventat-o ​​pentru un ARM Cortex-M0, unde s-a dovedit utilă. De fapt, am găsit doar empiric formule pentru câteva constante care se potrivesc nevoilor mele, iar Anders Kaseorg își asumă toată meritul pentru modul de a genera formule în mod sistematic.

Dacă suntem dispuși să pierdem puțină uniformitate și siguranța că codul este în timp constant, putem folosi

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

care este mai simplu, probabil mai rapid și mai ușor de adaptat la alte constante $m$ Decat $20$: noi scriem $m$ la fel de $r\,2^i$ cu $i$ un număr întreg și $r$ de preferință impar, apoi găsiți numărul întreg $j$ cu $2^{j-1}\le r<2^j$. Folosim ((rand>>j)*r)>>(64+i-j). Problema este, mai jos $j$ bucăți de rand nu sunt utilizate, iar uniformitatea rezultatului este redusă în mod corespunzător (cu excepția cazului în care $m$ este o putere a doi).

Când $m$ este $2^j$ pentru un număr întreg $j$, putem folosi rand>>(64-j) sau rand&(m-1). Cel mai târziu este observat în celălalt răspuns. Aceste metode nu pierd nicio uniformitate, dacă toate părțile rand sunt uniforme și independente.

Dacă $m$ modificări în timpul rulării cu $m<2^j$ pentru o constantă cunoscută $j$, putem folosi

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

Însă $j$ biți mai mici de rand sunt pierdute și care reduce uniformitatea rezultatului (cu excepția cazului în care $m$ este o putere a doi).

Pe langa subiect:

• (uint64_t)(etaj (rand*(20/(UINT64_MAX+1.)))) ar fi OK dacă nu ar exista o eroare de rotunjire, dar pentru că acestea există, este greu de spus dacă poate da rezultate 20 pentru unele intrări; de asemenea, pe multe compilatoare nu este uniform uniform.
• (uint64_t)((rand*(uint128_t)20)>>64) este corect din punct de vedere matematic și foarte aproape de ceea ce evaluăm noi, dar uint128_t este o caracteristică C opțională și încă suportată marginal.
• Întrebarea e rand/UINT64_MAX * 20 iesiri in $\{0,20\}$ deci este nepotrivit. Problemele sunt împărțirea rotunjite în jos la întreg și (independent) asta rand poate fi UINT64_MAX.
• Întrebarea e 20/(UINT64_MAX/rand) iesiri in $\{0,1,2,3,4,5,6,10,20\}$ și poate provoca o împărțire la zero, deci este nepotrivit. Problemele sunt împărțirea rotunjite în jos la întreg și (independent) asta rand poate fi 0.
• Fragmentul de cod al întrebării 3 are întotdeauna i%5 != 4 la ieșire, deci este nepotrivit. Problema este că ieșirea i este construit ca 10+5+2+1 cu unii termeni eliminati.

De obicei, s-ar strădui să facă dimensiunea matricei o putere de 2. Apoi indicele poate fi calculat prin ȘI pe biți:

matrice de caractere[0x40];
uint64_t rand;
...
char c = matrice[rand & 0x3f];