Discussion :

[moooona]

Bonjour,
j'ai développé une méthode qui permet de créer une valeur aléatoirement.
voilà cette fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
int random(int x_min, int x_max)
{
	return( (rand()%x_max) + x_min);
}

je veux modifier cette fonction comme suit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
double random(double val_min, double val_max)
{
	return( (rand()%val_max) + val_min);
}

car je veux par exemple avoir des valeur entre -0,5 et 0.5 ou bien entre deux autres doubles.
Comment je peux faire ça?

[r0d]

Bonjour,

quelque chose du style:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
double random(double val_min, double val_max)
{
	double diff = val_max - val_min;
	return(  ( (double) rand() ) / diff + val_min );
}

[Emmanuel Deloget]

De manière générale, il faut éviter de faire un modulo sur le résultat de rand(), car on perd certaines propriétés.

Il faut normalement faire quelque chose du style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
double my_rand(double minval, double maxval)
{
  // r est entre 0 et 1
  double r = (double)rand() / (double)(RAND_MAX + 1);
  return (maxval - minval) * r + minval;
}

cf. http://www.thinkage.ca/english/gcos/.../lib/rand.html pour davantage d'informations.

[Jean-Marc.Bourguet]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
double my_rand(double minval, double maxval)
{
  // r est entre 0 et 1
  double r = (double)rand() / ((double)(RAND_MAX) + 1);
  return (maxval - minval) * r + minval;
}

RAND_MAX+1 peut faire un overflow.

Le +1 empèche -- sauf arrondi pour compliquer les choses -- d'atteindre maxval.

[Emmanuel Deloget]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
double my_rand(double minval, double maxval)
{
  // r est entre 0 et 1
  double r = (double)rand() / ((double)(RAND_MAX) + 1);
  return (maxval - minval) * r + minval;
}

RAND_MAX+1 peut faire un overflow.

Le +1 empèche -- sauf arrondi pour compliquer les choses -- d'atteindre maxval.

Dans la pratique, RAND_MAX excède rarement 32767 - parce qu'un générateur du type de rand() cycle très rapidement sur les bits de poids faibles (et du coup renvoie généralement les bits de poids fort), si j'ai bien tout compris à la théorie. MSVC par exemple ne considère que les 16 bits de poids fort.

Ceci dit, en théorie un overflow reste possible.

[Jean-Marc.Bourguet]

Dans la pratique, RAND_MAX excède rarement 32767

Au moins Linux, OpenBSD, FreeBSD, NetBSD ont RAND_MAX==INT_MAX.

parce qu'un générateur du type de rand() cycle très rapidement sur les bits de poids faibles (et du coup renvoie généralement les bits de poids fort), si j'ai bien tout compris à la théorie. MSVC par exemple ne considère que les 16 bits de poids fort.

Rien n'oblige à avoir un générateur à congruence linéaire pour rand.

[Emmanuel Deloget]

Au moins Linux, OpenBSD, FreeBSD, NetBSD ont RAND_MAX==INT_MAX.

Je viens de vérifier l'implémentation de la glibc, et c'est vrai. Par contre, c'est quand même un générateur linéaire. Je suppose qu'ils ont correctement choisi les constantes à la base - j'aimerais bien savoir s'il y a un document qui explicite ce choix.

Du coup, effectivement, on peut effectivement avoir un overflow avec le code que j'ai proposé. Je bats ma coulpe.

Rien n'oblige à avoir un générateur à congruence linéaire pour rand.

C'est vrai aussi, mais pour le coup, je ne connais pas d'implémentation qui ait pris le risque de proposer une version de rand() qui soit basée sur autre chose ; le coût au runtime est censé rester faible.

[Jean-Marc.Bourguet]

Je viens de vérifier l'implémentation de la glibc, et c'est vrai. Par contre, c'est quand même un générateur linéaire.

J'avais regarde une fois et ils n'utilisaient pas un generateur lineaire (je suis a peu pres certain) mais (je suis moins certain) un des generateurs de George Marsaglia qui combinait deux ou trois types de generateurs differents.

Je suppose qu'ils ont correctement choisi les constantes à la base - j'aimerais bien savoir s'il y a un document qui explicite ce choix.

Quand tu as un modulo qui est une puissance de 2, le bit de poid faible a un cycle de 2, le 2ieme bit un cycle de 4, le 3ieme un cycle de 8 et le seul moyen de l'eviter c'est d'utiliser un autre type de generateur. Tu as ce genre de probleme des que le modulo est compose.

Du coup, effectivement, on peut effectivement avoir un overflow avec le code que j'ai proposé. Je bats ma coulpe.

Ayant commence sur des machines 16 bits, j'ai pris l'habitude de faire attention a ca.

C'est vrai aussi, mais pour le coup, je ne connais pas d'implémentation qui ait pris le risque de proposer une version de rand() qui soit basée sur autre chose ; le coût au runtime est censé rester faible.

Les generateurs de George Marsaglia ne sont pas beaucoup plus couteux (il en a qui n'utilisent pas de multiplication par exemple).

[Emmanuel Deloget]

J'avais regarde une fois et ils n'utilisaient pas un generateur lineaire (je suis a peu pres certain) mais (je suis moins certain) un des generateurs de George Marsaglia qui combinait deux ou trois types de generateurs differents.

J'ai dit que j'avais vérifié avant

En mode standard, c'est à dire si tu n'as pas appelé initstate_r(), rand() appelle rand_r() qui appelle random_r() qui utilise le RNG type 0, qui est un LCG :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
  if (buf->rand_type == TYPE_0)
    {
      int32_t val = state[0];
      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
      state[0] = val;
      *result = val;
    }

Le commentaire de la fonction explique un peu ce qui se passe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
   congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
   same in all the other cases due to all the global variables that have been
   set up.  The basic operation is to add the number at the rear pointer into
   the one at the front pointer.  Then both pointers are advanced to the next
   location cyclically in the table.  The value returned is the sum generated,
   reduced to 31 bits by throwing away the "least random" low bit.
   Note: The code takes advantage of the fact that both the front and
   rear pointers can't wrap on the same call by not testing the rear
   pointer if the front one has wrapped.  Returns a 31-bit random number.  */

Par contre, je viens de regarder les RNG de Marsaglias - ils sont effectivement très léger, et relativement bien expliqués.

[Jean-Marc.Bourguet]

J'ai dit que j'avais vérifié avant

J'ai parle au passe volontairement. J'aurais du ajouter que je me demandais pourquoi ils avaient change.

Mais je viens d'aller voir, le probleme est que ftp.gnu, toutes les glibc (depuis 2.0.1 qui est a coup sur anterieure au moment ou j'ai regarde) que j'ai vu utilise le code que tu montres et qui n'est pas celui dont je me souviens. Est-ce qu'alors j'aurais regarde celui d'une distrib specifique qui aurait change le generateur?

[moooona]

Merci pour tous.
C'est bien résolu