La nuit c'est fait pour dormir

Nombres pseudo-aléatoires

samedi 12 juillet 2025

en cours de rédaction

?

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  /* Faisons fonctionner le registre cinq fois. */
  int i ;
  AfficherRegistre() ;
  for(i = 0 ; i < 5 ; i++)
  {
    printf("Bit renvoye : %d\n", ProchainBit()) ;
    AfficherRegistre() ;
  }

  return 0 ;
}

1001011000110110010101101111100101110101010011101011011001110101110110100101100110100001110101110100
Bit renvoye : 0
0010110001101100101011011111001011101010100111010110110011101011101101001011001101000011101011101000
Bit renvoye : 0
0101100011011001010110111110010111010101001110101101100111010111011010010110011010000111010111010000
Bit renvoye : 0
1011000110110010101101111100101110101010011101011011001110101110110100101100110100001110101110100000
Bit renvoye : 1
0110001101100101011011111001011101010100111010110110011101011101101001011001101000011101011101000001
Bit renvoye : 0
1100011011001010110111110010111010101001110101101100111010111011010010110011010000111010111010000010

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

/* Registres à décalage et rétro-action linéaire (R.À.D.E.R.A.L.) */
struct _raderal
{
  int           nb_Bits ;
  int           nb_Cases ; /* égal à 1 + (nb_Bits - 1) / (8 * sizeof(unsigned int)) */
  int           PositionEntrante ; /* égal à (nb_Bits - 1) % (8 * sizeof(unsigned int)) */
  unsigned int *Bits ;
  int           nb_PositionsSpeciales ; /* doit être au moins égal à 2 */
  int          *PositionsSpeciales ;
} ;
typedef struct _raderal raderal ;

/* On définit un générateur pseudo-aléatoire global. */
raderal GPA ;

/* Calcul des positions dans le registre */
void CalculerPosition(int p, int *IndiceCase, int *BitCase)
{
  *IndiceCase = p / (8 * sizeof(unsigned int)) ;
  *BitCase    = p % (8 * sizeof(unsigned int)) ;
}

/* Le fonctionnement : génération du prochain bit sur un ràderal */
int ProchainBit()
{
  /* Calcul du nouveau bit */
  int IndiceCase, BitCase ;
  CalculerPosition(GPA.PositionsSpeciales[0], &IndiceCase, &BitCase) ;
  int bit = (GPA.Bits[IndiceCase] & (1 << BitCase)) >> BitCase ;

  int i ;
  for(i = 1 ; i < GPA.nb_PositionsSpeciales ; i++)
  {
    CalculerPosition(GPA.PositionsSpeciales[i], &IndiceCase, &BitCase) ;
    bit ^= (GPA.Bits[IndiceCase] & (1 << BitCase)) >> BitCase ;
  }

  /* Décalage */
  for(i = 0 ; i < GPA.nb_Cases ; i++)
  {
    GPA.Bits[i] >>= 1 ;
    if(i == GPA.nb_Cases - 1)
    {
      GPA.Bits[i] |= bit << GPA.PositionEntrante ;
    }
    else
    {
      GPA.Bits[i] |= (GPA.Bits[i + 1] & 1) << (8 * sizeof(unsigned int) - 1) ;
    }
  }

  return bit ;
}

/* Affichage (pour voir comment ça marche) */
void AfficherRegistre()
{
  int i, IndiceCase, BitCase ;
  for(i = 0 ; i < GPA.nb_Bits ; i++)
  {
    CalculerPosition(i, &IndiceCase, &BitCase) ;
    printf("%d", (GPA.Bits[IndiceCase] & (1 << BitCase)) >> BitCase) ;
  }
  printf("\n") ;
}

/* Initialisation du ràderal */
void InitialiserGenerateur(int nb_Bits,
                           int nb_PositionsSpeciales, int *PositionsSpeciales,
                           unsigned int Graine)
{
  /* Initialisation des différents champs */
  GPA.nb_Bits               = nb_Bits ;
  GPA.nb_Cases              = 1 + (nb_Bits - 1) / (8 * sizeof(unsigned int)) ;
  GPA.PositionEntrante      = (nb_Bits - 1) % (8 * sizeof(unsigned int)) ;
  GPA.Bits                  = malloc(GPA.nb_Cases * sizeof(unsigned int)) ;
  GPA.nb_PositionsSpeciales = nb_PositionsSpeciales ;
  GPA.PositionsSpeciales    = PositionsSpeciales ;

  /* Initialisation */
  int i ;
  for(i = 0 ; i < GPA.nb_Cases ; i++)
  {
    /* On met alternativement 000....0 ou 111....1 dans les cases */
    GPA.Bits[i] = -(i % 2) ;
  }
  GPA.Bits[0] = Graine ;

  /* On fait « tourner » le générateur trois fois sur tous ses bits */
  for(i = 0 ; i < 3 * nb_Bits ; i++) {ProchainBit() ;}
}

/* Initialisation du ràderal */
void InitialiserGenerateur(int nb_Bits,
                           int nb_PositionsSpeciales, int *PositionsSpeciales,
                           unsigned int Graine)
{
  ...

  for(i = 0 ; i < GPA.nb_Cases ; i++)
  {
    /* On met alternativement 000....0 ou 111....1 dans les cases */
    GPA.Bits[i] = -(i % 2) ;
  }
  AfficherRegistre() ;
  GPA.Bits[0] = Graine ;
  AfficherRegistre() ;

  ...
}

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  return 0 ;
}

0000000000000000000000000000000011111111111111111111111111111111000000000000000000000000000000001111
0101010000000000000000000000000011111111111111111111111111111111000000000000000000000000000000001111

/* Entier aléatoire entre 0 et 2**K - 1 */
int EntierPleinAlea(int K)
{
  int i, x = 0 ;
  for(i = 0 ; i < K ; i++)
  {
    x <<= 1 ;
    x |= ProchainBit() ;
  }
  return x ;
}

/* Entier aléatoire dans {a, ..., b} */
int EntierAlea(int a, int b)
{
  /* On cherche la plus petite puissance de deux */
     au moins égale au nombre de valeurs distinctes possibles */
  int d = b - a + 1 ;
  int K = 0, p = 1 ; /* p représente 2**K */
  while(p < d) {K++ ; p *= 2 ;}

  /* Méthode de rejet : par le choix de K, on « rate » en moyenne au plus une fois. */
  int x = EntierPleinAlea(K) ;
  while(x >= d) {x = EntierPleinAlea(K) ;}

  return a + x ;
}

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  /* Test visuel pour des entiers */
  int i ;
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", EntierAlea(1, 6)) ;
  }

  return 0 ;
}

1 5 2 3 6 6 4 4 4 6 2 4 4 1 5 6 1 2 6 4 1 5 4 4 1 3 4 1 4 1

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  /* Test statistique pour des entiers */
  int i ;
  int Effectifs[7] = {-1, 0, 0, 0, 0, 0, 0} ;
  for(i = 0 ; i < 10000000 ; i++)
  {
    Effectifs[EntierAlea(1, 6)]++ ;
  }
  printf("Repartition statistique des valeurs de 1 a 6\n") ;
  for(i = 1 ; i <= 6 ; i++)
  {
    printf("%d : %d\n", i, Effectifs[i]) ;
  }

  return 0 ;
}

Repartition statistique des valeurs de 1 a 6
1 : 1665765
2 : 1667844
3 : 1665744
4 : 1667611
5 : 1664795
6 : 1668241

/* Réel aléatoire dans [0 ; 1[ */
#define DEUX_PUISSANCE_CINQUANTE_DEUX 4.503599627370496e+15
double Alea()
{
  /* On génère un entier long sur 52 bits */
  long int X = 0L ;
  int i ;
  for(i = 0 ; i < 52 ; i++)
  {
    X <<= 1 ;
    X  |= ProchainBit() ;
  }

  /* Puis on le divise par 2**52 */
  double x = (double)X ;
  x /= DEUX_PUISSANCE_CINQUANTE_DEUX ;
  return x ;
}

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  /* Test visuel pour des flottants */
  int i ;
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%.15g\n", Alea()) ;
  }

  return 0 ;
}

0.0651232859494235
0.150894126114274
0.893613949182188
0.704242795138858
0.126652606955983
0.19436179689397
0.827781302493979
0.168071698532625
0.352386774667715
0.975439404570722

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  /* Test statistique pour des flottants */
  int i, k ;
  int Effectifs[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} ;
  double x ;
  for(i = 0 ; i < 10000000 ; i++)
  {
    x = Alea() ;
    k = (int)(x / 0.1) ;
    Effectifs[k]++ ;
  }
  printf("Repartition statistique des valeurs\n") ;
  for(i = 0 ; i < 10 ; i++)
  {
    if(i < 9)
    {
      printf("[0.%d ; 0.%d[ : %d\n", i, i + 1, Effectifs[i]) ;
    }
    else
    {
      printf("[0.9 ; 1.0[ : %d\n", Effectifs[i]) ;
    }
  }

  return 0 ;
}

Repartition statistique des valeurs
[0.0 ; 0.1[ : 1000410
[0.1 ; 0.2[ : 999245
[0.2 ; 0.3[ : 1001244
[0.3 ; 0.4[ : 999376
[0.4 ; 0.5[ : 998718
[0.5 ; 0.6[ : 1001066
[0.6 ; 0.7[ : 1000578
[0.7 ; 0.8[ : 999899
[0.8 ; 0.9[ : 1000025
[0.9 ; 1.0[ : 999439

/* Épreuve de Bernoulli de paramètre p dans [0 ; 1[ */
#define VRAI 1
#define FAUX 0
typedef int bool ;
bool Bernoulli(double p)
{
  return Alea() < p ;
}

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  /* Test statistique pour l'épreuve de Bernoulli */
  int nb_succes ;
  double p = 0.047 ;
  for(i = 0 ; i < 10000000 ; i++)
  {
    if(Bernoulli(p)) {nb_succes++ ;}
  }
  printf("Repartition statistique des resultats\n") ;
  printf("pour un parametre p = %.15g\n", p) ;
  printf("Succes : %d\n", nb_succes) ;
  printf("Echecs : %d\n", 10000000 - nb_succes) ;

  return 0 ;
}

Repartition statistique des resultats
pour un parametre p = 0.047
Succes : 469683
Echecs : 9530317

/* Mélange d'un tableau */
void Melanger(int nb_elts, void *T[])
{
  int i, j ;
  void *tmp ;
  int nb_elts_moins_un = nb_elts - 1 ;
  for(i = 0 ; i < nb_elts_moins_un ; i++)
  {
    j = EntierAlea(i + 1, nb_elts_moins_un) ;
    tmp = T[i] ; T[i] = T[j] ; T[j] = tmp ;
  }
}

int main()
{
  /* Il faut initialiser le générateur */
  int nb_Bits = 100 ;
  int PositionsSpeciales[] = {3, 4, 19, 25, 82} ;
  int nb_PositionsSpeciales = 5 ;
  int Graine = 42 ;
  InitialiserGenerateur(nb_Bits,
                        nb_PositionsSpeciales, PositionsSpeciales,
                        Graine) ;

  /* Test de mélange d'un tableau */
  int i, nb_elts = 20 ;
  void *T[nb_elts] ;
  int *x = NULL ;
  for(i = 0 ; i < nb_elts ; i++)
  {
    x = malloc(sizeof(int)) ; *x = i + 1 ; T[i] = x ;
  }

  /* Affichage avant */
  for(i = 0 ; i < nb_elts ; i++)
  {
    x = T[i] ;
    printf("%d ; ", *x) ;
  }
  printf("\n") ;

  Melanger(nb_elts, T) ;

  /* Affichage après */
  for(i = 0 ; i < nb_elts ; i++)
  {
    x = T[i] ;
    printf("%d ; ", *x) ;
  }
  printf("\n") ;

  return 0 ;
}

1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ; 10 ; 11 ; 12 ; 13 ; 14 ; 15 ; 16 ; 17 ; 18 ; 19 ; 20 ;
4 ; 5 ; 15 ; 19 ; 18 ; 11 ; 12 ; 10 ; 6 ; 14 ; 1 ; 9 ; 3 ; 7 ; 20 ; 13 ; 2 ; 8 ; 16 ; 17 ;