Nombre aléatoire à temps constant dans la plage

Question

J'ai un générateur de nombres aléatoires qui fonctionne en temps constant.

Le prototype de cette fonction est la suivante:

uint8_t rand(); 

Ce que je veux être en mesure de faire est de créer une fonction qui renvoie au hasard un uint8_t de telle sorte que la sortie est comprise entre 0 et max où max est la nombre maximum à renvoyer. Le prototype d'une telle fonction est le suivant:

uint8_t randi(uint8_t max); 

Il existe des algorithmes en ligne pour ce faire et en cas de débordement de pile. Par exemple, https://stackoverflow.com/a/6852396/1444313. Mais mon problème est que je veux y parvenir à temps constant. Je ne peux trouver aucune méthode qui fait cela à temps constant.

De plus, je cours sur un ARM Cortex-m0 sans division matérielle donc l'utilisation de l'opérateur% n'est pas possible.

Quelqu'un at-il des suggestions ou des indications sur la façon dont j'y arriverais en temps constant?

Merci

Answer 1

Pour aider à clarifier OP » dilemme ci-dessous sont 2 solution simple qui ne répondent pas aux objectifs de OP.

Qu'est-ce pas travail:

distribution non uniforme à moins max +1 est une puissance de 2.

uint8_t randi_fail1(uint8_t max) { 
    return rand()%(max + 1); 
} 

Distribution uniforme, mais pas le temps uniforme.

uint8_t randi_fail2(uint8_t max) { 
    unsigned n = (256/(max+1))*(max+1); 
    unsigned r; 
    do { 
    r = rand(); // 0 - 255 
    } while (r >= n); 
    return r/(max+1); 
} 

Answer 2

Voici une solution qui répond à vos besoins, mais peut ne pas aimer!

255 Faire des tableaux de 256 ou 65536 valeurs aléatoires, appelez uint8_t randval[255][256];

Maintenant, chaque randval[N][M] <= N; en d'autres termes, les sous-matrices sont spécialisées pour le paramètre randimax.

uint8_t randi(uint8_t max) 
{ 
    return (max == 0u) ? 0u : randval[max - 1][rand()]; 
} 

Notez que randval peut être construit au moment de la compilation, ou peut être mis à jour en arrière-plan comme suggéré par @Realtime Rik. Bien sûr, si construit au moment de la compilation, il peut être const, et stocké en flash.

Answer 3

L'entrée et la sortie sont des octets de 8 bits, alors pourquoi ne pas obtenir votre valeur aléatoire, multiplier par votre 'max', et passer à droite par 8 pour diviser par 256? Je l'ai fait pour choisir une lettre au hasard en obtenant une valeur de 0-25 (aléatoire de 8 bits, multiplier par 26, prendre l'octet supérieur).