Fonction rand() : séquence aléatoire trop courte ?

Version imprimable

04/12/2010, 18h53
sikin1989

Fonction rand() : séquence aléatoire trop courte ?
Bonjour,

j'ai cherché solution à mon problème, mais je ne trouve rien !
Je dois placer dans un tableau des pions au hasard. Je peux placer "x" pions par case.
Je fais donc un petit :
Code:

1 2 3 4 5 6 7 8 9 10 for (nbpions = 1000; nbpions >0;nbpions--) { int randi = rand() % i; int randj = rand() % j; if (tab[randi][rabdj] < nb_max) tab[randi][randj]++; else nbpions++; }
J'espère donc que des pions vont se placer aléatoirement dans ma grille. La capacité de pion dans ma grille est bcp + grande que mon nombre de pion à placer.
Malheureusement, à partir d'un moment, ma boucle se bloque dans le else. J'ai donc l'impression que le rand() me ressort une trop petite séquence de nombre qui se répète. Si je diminue le nombre de pion à placer à 100, mon programme se termine et marche très bien. Mais pour des nombre trop grand, ca cale ..

Une solution pour régler mon problème please :) !
04/12/2010, 20h22
droggo

Jai,

Combien peuvent valoir i, j et nb_max ?

Tu peux savoir quelle sont les valeurs que rand peut renvoyer : de 0 à RAND_MAX (ou MAX_RAND, j'oublie chaque fois :)), un test rapidement fait te donnera cette valeur.
04/12/2010, 20h28
sikin1989

Comme j'ai dis, la capacité de mon tableau est plus grande que le nombre de pions à placer.
Donc par exemple, i=50, j=50 et nbmax = 6
On a donc une capacité de 15 000 pions. Et j'essaye d'en placer 1000.

Je suis conscient que si j'essaye de placer, par exemple, 10000 pions pour une capacité de 9990 pions, ma fonction risque de tourner longtemps avant de trouver une place pour tout le monde :)
04/12/2010, 21h03
jeroman

Sachant que ton tableau peut contenir au maximum 50*50*6 pions (=15000), si ta boucle tourne sans fin (ie que ton tableau ne peut plus rajouter de pions), c'est que le tableau n'est pas correctement initialisé. Ses 50*50 éléments doivent tous être initialisés par des 0.
04/12/2010, 21h15
sikin1989

Ils le sont ..

Donc je répète : Avec, par exemple, 100 pions à placer, aucun problème ! Mais dés que je veux mettre trop de pion, il boucle infiniment après un certain certain. J'ai donc l'impression que les rand() me sortent toujours les même séquences et que ces séquences sont trop courtes.
04/12/2010, 21h45
matafan

Tu es sous quel OS ? Sur certains systèmes, les bits de poids faible retournés par rand() sont beaucoup moins aléatoires que les bits de poids fort. D'une manière générale, à parti si ton implémentation de rand() précise que ce n'est pas le cas, il faut éviter de faire un modulo pour normaliser les nombres dans l'intervalle voulu. Il vaut mieux faire une division.

Cela dit ton algo de placement est assez naïf ; tu pourrais trouver un moyen de ne t'assurer que tu ne tireras plus jamais de valeurs qui ne sont plus acceptables (je te laisse chercher comment).
04/12/2010, 22h05
sikin1989

Sous linux.

Pour faire un rand() dans un intervalle voulu, je n'ai trouvé que des astuces avec des modulo ..

Et oui, mon algo est un peu naïf mais c'est un peu le rush là ... Et cette histoire n'est qu'une infime partie de ce que je dois faire .. C'est vraiment une bêtise qui me bloque et me fait perdre beaucoup de temps pour pas grand chose :p
Si tu pouvais au moins me diriger vers de la documentation pour créer un algo de ce type ca m'intéresserait parce que je commence à être short niveau temps que pour "perdre" encore du temps sur ce rand() qui ne fonctionne pas comme je le voudrais :p

Merci en tout cas pour ta réponse !
04/12/2010, 22h09
jeroman
Citation:

Ils le sont ..

Pour diagnostiquer un problème, on peut procéder par élimination. Il faut déjà s'assurer de certaines choses.

Juste avant ton code, rajoute cela (le temps d'un test) :
Code:

1 2 3 4 5 6 7 8 9 10 11 { int a,b,compt=0; for (a=0; a<50; a++) { for (b=0; b<50; b++) { compt += (tab[a][b]==0); } } printf("%d\n",compt); }
... et dis-moi si la valeur affichée est bien 2500.

Si c'est le cas, alors le problème peut éventuellement venir de rand.
04/12/2010, 22h10
diogene

Ce programme doit tourner rapidement, SAUF si tu demandes plus de i*j*nb_max (soit 15000 dans l'exemple) pions. Dans ce cas, il tourne indéfiniment puisqu'il n'a pas la possibilité de mettre les derniers.
04/12/2010, 22h22
matafan

Citation:

Envoyé par sikin1989

Si tu pouvais au moins me diriger vers de la documentation pour créer un algo de ce type ca m'intéresserait parce que je commence à être short niveau temps que pour "perdre" encore du temps sur ce rand() qui ne fonctionne pas comme je le voudrais :p

Tu peux allouer un tableau T de N = i*j pointeurs qui te servira à tirer des cases. Tu l'initialises de façon à ce que chaque case pointe vers une case de ta grille. Tu tires un nombre n entre 0 et N-1, et tu vas incrémenter *T[n] (qui est une case de ta grille). Si la nouvelle valeur est nb_max, tu échanges les cases T[N-1] et T[n] (tu fais passer la case que tu ne veux plus tirer en fin de tableau), et tu décrémente N de 1 de façon à ne plus tirer la case que tu viens d'éliminer.

Ca évite de faire des rand() qui ne servent à rien. Evidemment c'est surtout intéressant quand tu as beaucoup de pions à placer par rapport à i*j*nb_max.
04/12/2010, 22h29
diogene

@matafan

Citation:

Evidemment c'est surtout intéressant quand tu as beaucoup de pions à placer par rapport à i*j*nb_max.

Il ne peut pas placer plus de i*j*nb_max pions.
04/12/2010, 22h45
gl

Citation:

Envoyé par sikin1989

Pour faire un rand() dans un intervalle voulu, je n'ai trouvé que des astuces avec des modulo ..

Je te renvoie à la FAQ : Comment obtenir un nombre aléatoire (entier) entre 0 et N ?
04/12/2010, 23h07
sikin1989

Citation:

Envoyé par diogene

@matafan

Il ne peut pas placer plus de i*j*nb_max pions.

Il voulait sûrement dire que c'est intéressant lorsque le nombre de pion à placé s'approche de i*j*nb_max

J'avais pensé à faire ça mais bon .. je trouvais ça trop peu efficace pour le nombre de fois où je vais m'en servir. Le nombre totale de pion à placer n'approchera pas souvent (même peut être jamais) la capacité totale de ma grille. Je vais donc garder mon algo en tentant de le faire marcher.

@jeroman : Oui, ca fait bien 2500 itérations ;)

@gl : Merci, j'avais pas trouvé :)
04/12/2010, 23h14
jeroman

C'est vraiment étonnant que rand renvoie les mêmes séries. 8O
05/12/2010, 16h03
kruller
Citation:
Envoyé par sikin1989

Bonjour,

j'ai cherché solution à mon problème, mais je ne trouve rien !
Je dois placer dans un tableau des pions au hasard. Je peux placer "x" pions par case.
Je fais donc un petit :

Code:

1 2 3 4 5 6 7 8 9 10 for (nbpions = 1000; nbpions >0;nbpions--) { int randi = rand() % i; int randj = rand() % j; if (tab[randi][rabdj] < nb_max) tab[randi][randj]++; else nbpions++; }

J'espère donc que des pions vont se placer aléatoirement dans ma grille. La capacité de pion dans ma grille est bcp + grande que mon nombre de pion à placer.
Malheureusement, à partir d'un moment, ma boucle se bloque dans le else. J'ai donc l'impression que le rand() me ressort une trop petite séquence de nombre qui se répète. Si je diminue le nombre de pion à placer à 100, mon programme se termine et marche très bien. Mais pour des nombre trop grand, ca cale ..

Une solution pour régler mon problème please :) !
Il y a la fonction int random() de la stdlib bien plus aléatoire. Elle est fournie avec int RAND_MAX ;)
05/12/2010, 18h07
gl

Citation:

Envoyé par kruller

Il y a la fonction int random() de la stdlib bien plus aléatoire. Elle est fournie avec int RAND_MAX ;)

Attention, la fonction random() n'est pas une fonction standard (c'est du BSD d'après la page man).

Et au passage, rand() fournie déjà un nombre entre 0 et RAND_MAX.
05/12/2010, 20h16
diogene

- @jeroman

Citation:

C'est vraiment étonnant que rand renvoie les mêmes séries.

je ne crois pas non plus que la fonction rand() fournie avec un compilateur puisse être si mauvaise qu'elle ne puisse remplir les 50*50*6 = 15000 pions.

- le biais introduit par l'utilisation des modulos avec des valeurs de i et j aussi faibles (50) doit être négligeable (pour un RAND_MAX supérieur ou égal à 32767)

- même si on veut mettre 15000 pions, le remplissage sera rapide : pour donner une idée, si on a déjà placé 14999 pions, il reste une seule case possible pour le 15000 ième. A chaque boucle, on sélectionne une case du tableau et on a une probabilité de 1/2500 de toucher la case disponible et de terminer au premier essai. On a 50% chances de la remplir en moins de 1700 essais , 80% en moins de 4000, 90% en moins de 6000 et 98% en moins de 10000. Ce ne sont pas des chiffres gigantesques sur une machine moderne.