Bonjour 🙂

J'aimerais savoir svp, comment expliquer la construction de la fonction "(rand() % (MAX − MIN + 1)) + MIN; " se trouvant dans l'exemple suivant :

 #include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main ( )
{
int mysteriousNumber = 0, inputNumber = 0;
const int MAX = 100, MIN = 1;
// Generation of random number
srand(time(NULL));
mysteriousNumber = (rand() % (MAX − MIN + 1)) + MIN;

do
 {
// We request the number
printf(”What’s the number? ”);
scanf(”%d”, &inputNumber );
// We compare between inputNumber and mysteriousNumber
if (mysteriousNumber > inputNumber )
{
printf(”Greater !\n\n”);
}
else if (mysteriousNumber < inputNumber )
{
printf(”Lesser !\n\n”);
}
else
{
printf (”Bravo, you have found the mysterious number !!!\n\n”);
} while (inputNumber != mysteriousNumber);
return 0;
}

Je vous remercie infiniment 🙏🙏🙏

Salut,

rand() sort un entier pseudo aléatoire entre 0 et RAND_MAX. Il s'agît là de borner le résultat pour réduire cette valeur entre MIN et MAX.

Bonne continuation.

Les nombres entiers entre MIN et MAX, il y en a MAX-MIN+1 différents .  Exemple 3 entre 5 et 7.

Autant que de restes possibles quand on divise par ce nombre.

PierrotLeFou a écrit:

Noter que RAND_MAX vaut 32767
Si on veut des nombres aléatoires plus grand, c'est moins évident.
J'ai déjà essayé rand()*rand()

Ce n'est qu'une garantie de minimum, il peut être différent d'un environnement à l'autre.

Du coup un autre façon de faire est d'utiliser le fait que (en flottant) 0 ≤ rand()/RAND_MAX ≤ 1 et du coup  min ≤ min + (max-min)*rand()/RAND_MAX ≤ max.

Une implémentation quick and dirty pourrait donner :

int rand_between(int min, int max) {
    return min + (int)( ((double)rand())/RAND_MAX*(max-min) );
}

Je ne suis pas sûr que le produit conduise à une distribution uniforme.

Le produit de 2 nombres modulo n est entre 0 et (n-1)^2,  et 0 est obtenu de  2n-1 façons différentes.

A la place, je construirai plutôt un grand nombre aléatoire par juxtaposition de "tranches de bits" (moins de 15 a la fois, puisque limitation a 32K)

> Je ne suis pas sûr que le produit conduise à une distribution uniforme.
Moi non plus ...
Si on veut utiliser les long long, il y a fort à parier qu'on pourrait trouver un nombre premier de l'ordre de 2^42 et un multiplicateur de l'ordre de 2^14 à 2^21
(par ex. 4398046511093)
Pour une fonction random à modulo tel que  s' = s * m % p
où p est un nombre premier et m est un multiplicateur et s est la semence suivante.
et tels qu'on retourne à la semence initiale en p-1 itérations.
Je n'ai pas essayé de trouver le multiplicateur ...  2^42 nano-secondes, ça risque d'être long.

Edit: c'est pour tester un seul multiplicateur (et je suis optimiste dans mes évaluations)
Bah, à peine 4096 secondes ...

Voici des valeurs plus modestes:
long long p = 3037000493;
long long m = 28276;

-
Edité par PierrotLeFou 21 février 2022 à 7:22:04

Après m'être rendormi et réveillé, j'ai pondu le code pour une fonction qui fabrique un nombre aléatoire long par tranches (de 8 bits)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

unsigned long long ull_rand(void)
{
    union {
        unsigned long long number;
        char bytes[sizeof(unsigned long long)];
    } u;

    for (size_t i = 0; i < sizeof(unsigned long long); i++) {
        u.bytes[i] = rand();
    }
    return u.number;
}

int main()
{
    // initialiser le générateur
    srand(time(NULL));

    printf("# Génération aléatoire de nombres entiers longs :"
           " unsigned long long\n");
    for(int i = 0; i < 10; i++) {
        printf("%20llx\n", ull_rand());
    }
}

Résultat, avec affichage en hexa, pour qu'on voie bien que les octets changent d'un appel à l'autre

# Génération aléatoire de nombres entiers longs : unsigned long long
     798d08843962d12
    fda99fd08c658cce
    23a4caae3121f185
    a0bc368e89ffbcdb
    f1f37c23ece45263
    7dd626f7d97d5809
    9de952c2c6aef818
    823de31f9c27e90e
    a64a619d596e2136
     52e56edb180c7b9

Pour ce qui est de la distribution dans le cas de rand()*rand(), j'ai réfléchi. L'effet principal c'est que je me suis rendormi, mais accessoirement :

• la seule façon de retourner 1, c'est d'obtenir deux tirages à 1 consécutifs
• par contre il y a 64000 façons d'obtenir 0
• un nombre premier s'obtient de deux façons, si il est plus petit que 32K. Aucune sinon.
• un nombre de la forme  p^k (avec p premier) s'obtient à peu près de k+1 façons différentes si il est plus petit que 32K

-
Edité par michelbillaud 21 février 2022 à 10:46:31

«Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.»
John von Neumann.

Les plateformes modernes proposent en général un accès à un «vrai» rng si le besoin s'en fait ressentir. Maintenant il y a une tonne de littérature qui explique comment créer un prng avec des propriétés précises.

Quel rand() ? sur quelle plateforme ? quel environnement ? quelles options de compilations de la libc ?
Il n'y a même pas de contraintes dans la norme sur ce que rand() doit réellement fournir … on y lit même en footnote : «There are no guarantees as to the quality of the random sequence produced and some implementations are known to produce sequences with distressingly non-random low-order bits. Applications with particular requirements should use a generator that is known to be sufficient for their needs.»

On n'est même pas obligé de passer par rand(), par exemple sous linux il y a les /dev/random et /dev/urandom … les systèmes POSIX proposent d'autres interfaces …

Si on a des besoins spécifiques il faut généralement faire appel à autre chose que rand() qui est a priori même limite pour un fisher yates sur un jeu de cartes (si on pousse le bouchon).

Est-ce que "Guess a number" est un besoin spécifique ?  :-=

C'était plus dans le sens que la discussion prenait entre toi et Pierrot, à dire le besoin spécifique de dépasser le minimum normatif de la norme. Je ne me serais pas permis d'intervenir ainsi pour un simple guess my number.

Si j'ai bien compris, je m'achête une série de compteurs 8 bits que je monte en séquence avec un oscillateur qui pousse le circuit à la limite.
Il faut ensuite juste écrire le driver et espérer que l'ordi pourra y accéder ...
Petite note sur rand()
Si je prend une semence et que j'appelle rand() jusqu'à ce que je retrouve cette première semence, je n'ai jamais le même nombre d'ittérations.

Avec un générateur à modulo avec p=65537 et m=75, j'ai un cycle de 65536 itérations.

-
Edité par PierrotLeFou 21 février 2022 à 16:00:48

ou si tu en as besoin tu utilises RDRAND/RDSEED sur les x86 pas trop anciens ;

ou des bibliothèques qui proposent des prng avec des propriétés précises ;

ou tu regardes ce que ton OS propose ;

…

Edit:

PierrotLeFou a écrit:

[...]
Avec un générateur à modulo avec p=65537 et m=75, j'ai un cycle de 65536 itérations.

-
Edité par PierrotLeFou il y a 2 minutes

-
Edité par White Crow 21 février 2022 à 16:06:12

Le code de michel, m'a fait penser à BCryptGenRandom de Windows qui rempli un buffer :

#include <stdio.h>
#include <windows.h>
#include <bcrypt.h>

int main(void)
{
    union
    {
        unsigned long long number;
        BYTE bytes[sizeof(unsigned long long)];
    } u;

    for(size_t j=0; j<20; j++)
    {
        BCryptGenRandom(NULL, u.bytes, sizeof(unsigned long long),
                                               BCRYPT_USE_SYSTEM_PREFERRED_RNG);
        printf("\n%24llu",u.number );
    }
    printf("\n");

    return 0;
}

White Crow a écrit:
> Ce qui est insuffisant pour avoir un fisher yates sur un tableau de 9 éléments ou plus qui donnerait toutes les permutations suivant une loi uniforme.
Je n'ai pas mentionné qu'on retourne s-1 au programme. Donc 0 <= s-1 < p-1
Si j'utilisais ton truc:
(double)(s-1)/(p-1) * longueur_de_l'intervalle avec un nombre p assez grand, est-ce que ça serait mieux?

L'intervalle des nombres réels est infiniment dense, mais ça n'est pas possible d'avoir ça dans un ordi.

-
Edité par PierrotLeFou 21 février 2022 à 18:57:56

rouIoude a écrit:

Le code de michel, m'a fait penser à BCryptGenRandom de Windows qui rempli un buffer :

comme quoi

• c'est difficile d'être original (*)
• j'ai peut être un jumeau (malfaisant) chez microsoft du mauvais côté de la force

unsigned long long ull_rand(void)
{
    char bytes[sizeof(unsigned long long)];
 
    for (size_t i = 0; i < sizeof(unsigned long long); i++) {
        bytes[i] = rand();
    }
    return * (unsigned long long *) bytes;
}

unsigned long long r = 0;

for (.....) {
    r = (r << 15) ^ rand();   // xor, plus, or ?
}

return r;

-
Edité par michelbillaud 21 février 2022 à 19:52:05

PierrotLeFou a écrit:

White Crow a écrit:
> Ce qui est insuffisant pour avoir un fisher yates sur un tableau de 9 éléments ou plus qui donnerait toutes les permutations suivant une loi uniforme.
Je n'ai pas mentionné qu'on retourne s-1 au programme. Donc 0 <= s-1 < p-1
Si j'utilisais ton truc:
(double)(s-1)/(p-1) * longueur_de_l'intervalle avec un nombre p assez grand, est-ce que ça serait mieux?

L'intervalle des nombres réels est infiniment dense, mais ça n'est pas possible d'avoir ça dans un ordi.

-
Edité par PierrotLeFou il y a environ 1 heure

Ah ben non, ça n'aurait pas été mieux … 

Si tu veux pouvoir choisir au hasard (en suivant une loi uniforme) une des n! permutations de ⟦0, n-1⟧ il te faut au moins un prng dont le cycle est supérieur à log2(n!). Dans l'exemple dont je poussais le bouchon un peu loin, un fisher yates sur un jeu de 52 cartes il te faut au moins log2(52!) = 225.8 ⇒ 226 bits.