Consignes

Vous devrez soumettre votre travail (un unique fichier Caml valide) en utilisant l'interface TPLab.

Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
la présence de commentaires aux endroits appropriés,
...

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP.
Une exécution du fichier dans Emacs ne devra pas provoquer d'erreur.

Liens utiles

la page du langage Caml
La documentation de Caml, version 3.11 (utilisé en TP) : Documentation and user's manual
le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano Développement d'applications avec Ocaml
brouillon du livre de Jason Hickey sur le langage Caml : Introduction to Objective Caml (anglais)

page de rendu TPLab

1. Générateurs pseudo aléatoires

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. -- John von Neumann

Il n'est pas possible de générer des entiers / flottants / bits réellement aléatoires avec un programme déterministe. On peut par contre simuler l'aléatoire de manière plus ou moins bonne avec de tels programmes. Les générateurs pseudo-aléatoires fonctionnent de la manière suivante :

le générateur possède un état interne,
chaque appel au générateur modifie l'état interne et renvoie une valeur qui dépend uniquement de l'état interne.

Un tels générateur n'est pas vraiment aléatoire car les valeurs générées dépendent uniquement de la valeur initiale de l'état interne. Cet état est aussi appelé graine (seed en anglais) et ne peut en pratique prendre qu'un nombre fini (mais parfois très grand) de valeurs. À cause de ceci, si on génère suffisamment de valeurs pseudo-aléatoires, le générateur se retrouve forcément dans un état déjà visité et les valeurs générées se répètent.

La plupart des langages donnent la possibilité à l'utilisateur de choisir la valeur initiale de l'état, permettant ainsi de regénérer les même valeurs sur des exécutions différentes.

En Caml, il est facile de modéliser un état interne qui évolue en utilisant une référence.

2. Générateurs congruentiels

Les générateurs pseudo-aléatoires les plus simples sont les générateurs congruentiels linéaires :

l'état est simplement un entier (32 bits, 64 bits, ou autre),
si l'état vaut X, la valeur générée est égale à (a X + c) mod m,
l'état est mis à jours en le remplaçant par la valeur générée, à savoir (a X + c) mod m.

Les valeurs a, c et m sont choisies une fois pour toute.

Un mauvais choix de a, c ou m peut rendre le générateur complètement trivial. Par exemple, a=1, c=1 vont générer les valeurs 1, 2, 3, 4, ..., m-1, 0, 1, ...

Il faut donc choisir ces valeurs correctement.

Écrivez une fonction generateur_congruentiel : int -> int -> int -> int -> (unit -> int) qui permet de créer un nouveau générateur congruentiel. Les quatre premiers arguments sont :

m : la valeur qui permet de faire le modulo,
a : la valeur multiplicative,
c : la valeur additive,
x : la valeur initiale de l'état.

On utilisera cette fonction de la manière suivante :

let rng = generateur_congruentiel 10 2 3 1;;
rng : unit -> int = <fun>
let n1 = rng ();;
n1 : int = 5;;
let n2 = rng ();;
n2 : int = 3 ;;
let n3 = rng ();;
n3 : int = 9 ;;
let n4 = rng ();;
n4 : int = 1 ;;
...

Votre fonction generateur_congruentiel devra déclarer une référence locale qui servira d'état.

2.1. Bits aléatoires

Un générateur congruentiel linéaire produit des nombres entre 0 et m-1. Expliquez comment on peut se servir d'un tel générateur pour obtenir des bits aléatoires.

3. Générateurs à registre à rétroaction linéaire

Un autre type de générateur pseudo-aléatoire sont les générateurs à registre à rétroaction linéaire. On conserve en mémoire un certain nombre de valeurs déjà créées, et on utilise une fonction du même type que la fonction de Fibonacci : le nouveau nombre généré est de la forme X_n = (X_n-a + X_n-b) mod m. L'état interne d'un tels générateur consiste toutes les valeurs précédentes nécessaires pour calculer la nouvelle valeurs. Si a=3 et b=31, il faut conserver 31 valeurs dans l'état.

Comme pour les générateurs congruentiels, il faut choisir les valeurs de a, b et m correctement si on veut obtenir de bonne propriétés.

Programmer la fonction element : int -> 'a list -> 'a qui permet de récupérer un élément dans une liste en fonction de son indice (en commençant à 0). Par exemple

let l = [3; 17; -1; 42];;
val l : int list = [3; 17; -1; 42]
let x = element 2 l;;
x : int = -1

Programmez une fonction generateur_retroaction : int -> int -> int -> int list -> (unit -> int) qui permet d'initialiser un tel générateur à partir de m, a, b et des valeurs initiales:

let rng = generateur_retroaction 2 1 3 [1;1;1];;
let b1 = rng ()
b1 : int = 0
let b2 = rng ()
b2 : int = 1
let b3 = rng ()
b3 : int = 0
let b4 = rng ()
b4 : int = 0
...

Attention : il ne faut pas conserver toutes les valeurs précédentes, mais seulement celles qui sont nécessaires pour calculer les nouvelles valeurs.

Vous pouvez également supposer que a < b et que la liste pour initialiser l'état a exactement b éléments.

3.1. Amélioration : utilisation de files

Lorsque l'on utilise un générateur à registre à rétroaction linéaire avec a=3 et b=31, il faut conserver 31 valeurs dans l'état. À chaque étape, on rajoute une nouvelle valeur au début de la liste et on supprime la dernière valeur de la liste (ou inversement).

Dans tous les cas, on doit parcourir toute la liste de l'état à chaque génération de nouvelle valeur. C'est inefficace !

Pour améliorer ceci, il faudrait utiliser une file (FIFO : "first in, first out") plus efficace qu'une simple liste.

Dans une file, les élément rentrent toujours par le début, et sortent toujours par la fin. Comme les opérations sur la tête d'une liste sont beaucoup plus rapide que les opérations sur la fin des listes, on va essayer d'avoir :

une liste à l'endroit pour pouvoir ajouter des nouveaux éléments rapidement,
une liste à l'envers pour pouvoir enlever les anciens éléments rapidement.

Autrement dit, une file sera donnée par une paire de liste :

si on ajoute la valeur 7 dans ([6;5;4] , [1;2;3]), on obtient ([7;6;5;4] , [1;2;3])
si on enlève un élément dans ([7;6;5;4] , [1;2;3]), on récupère 1, et la file devient ([7;6;5;4] , [2;3]).

On peut toujours ajouter un élément dans la première liste, mais il peut arriver que la seconde liste deviennent vide. Dans ce cas, il faudrait prendre le dernier élément de la première liste. On va faire mieux : on va transférer tous les éléments de la première liste dans la seconde liste, en les renversant ! De cette façon, si on essaie d'enlever un autre élément, il sera déjà dans la seconde liste...

si on enlève un élément dans ([7;6;5;4] , []), on récupère 4, et la file devient ([] , [5;6;7])
si on enlève un élément dans ([] , []), il y a une exception...

On définit le type 'a fifo de la manière suivante :

type 'a fifo = ('a list * 'a list) ref

Écrivez la fonction add : 'a -> 'a fifo -> unit qui modifie une file en ajoutant un élément au début,
écrivez la fonction pop : 'a fifo -> 'a qui récupère le dernier élément d'une file en modifiant la file en question.

On peut maintenant reprogrammer les générateurs à registre à rétroaction linéaire en utilisant deux files :

la file des a dernières valeurs,
la file des b dernières valeurs.

De cette manière, à chaque génération, il suffit d'enlever le dernier élément de chaque file, et d'ajouter le nouvel élément dans les deux files.

Définissez une nouvelle fonction generateur_retroaction_fifo : int -> int -> int -> int list -> (unit -> int) en utilisant des files.

Essayer de comparer les vitesse de génération d'entiers pseudo-aléatoires avec les deux versions, en expliquant votre méthode et vos résultats.

3.2. Amélioration : opérations bit à bit (Bonus)

On peut utiliser un générateur à registre à rétroaction linéaire pour générer des bits : on utilise simplement m=2. Lorsque a et b ne sont pas trop grand, on peut encore simplifier l'état : un entier Caml est stocké sur 31 (ou 63). On peut donc représenter une suite de 31 ou 63 bits par un unique entier !

Pour récupérer des bits particuliers, on peut utiliser des opérations bit à bit qui sont très rapides !

le "et", "ou" ou "xor" bit à bit (land, lor et lxor en Caml)
les décalages à droite ou à gauche (lsr et lsl en Caml)

Toutes ces opérations se notent de manière infixe :

# 3 lsl 2;;
- : int = 12
# 12 lsr 2;;
- : int = 3
# 3 land 1;;
- : int = 1
# 7 lxor 2;;
- : int = 5

Programmez la fonction generateur_retroaction_binaire : int -> int -> int -> (unit -> int) qui prend en argument : a, b et x (état initial donné comme un entier).

Comparez les vitesses de génération pour des générateurs binaires avec les trois variantes. (Utilisez par exemple a=3, b=31 et x=1.)

4. Générateur de von Neumann

Un des premiers générateurs pseudo-aléatoire était la méthode des carrés, due à John von Neumann : l'état est un entier sur 10 chiffres, et l'entier généré est obtenu de la manière suivante :

on calcule le carré de l'état : c'est un nombre sur 20 chiffres,
on récupère les 10 chiffres du milieu : c'est le nombre généré, et le nouvel état.

Comme les entiers positifs de Caml sont stockés sur 30 (ou 62) bits, on la taille des calculs ne peuvent pas dépasser 30 bits (ou 62 bits). L'état ne doit donc pas avoir plus de 15 bits (ou 31 bits) si on ne veut pas que son carré provoque un dépassement de capacité.

Écrivez une fonction generateur_von_neumann : int -> (unit -> int) qui génère des nombres pseudo-aléatoires en utilisant 15 ou 31 bits selon votre machine...

(Vous pouvez soit utiliser la méthode en base 10 comme décrit si dessus, soit utiliser la méthode directement en base 2 en utilisant les opérations bit à bit.)

5. Période et prépériode

Au bout d'un certain nombre de générations, l'état reprend forcément une valeur déjà utilisée, et le générateur boucle. Si un générateur produit les valeurs 3, 7, 5, 21, 4, 10, 12, 4, 10, 12, 4, 10, 12, 4, ... on dit qu'il a :

une prépériode de 4 (c'est le nombre de valeurs initiales avant la répétitions : 3, 7, 5 et 21),
une période de 3 (c'est le nombre de valeurs qui se répètent : 14, 10 et 12).

Si f est une fonction sur des états (donné par un type fini), et x est un état initial, on aimerait calculer une prépériode q et une période p :

lorsque n > q, on a iter f n x = iter f (n+p) x
p est minimal,
q est minimal.

Rappel : la fonction iter est donné par

let rec iter f n x =
  if n = 0
  then x
  else iter f (n-1) (f x)

Pour calculer la période et la prépériode, la méthode naïve consiste à sauvegarder toute les valeurs de l'état, et à regarder quand on retrouve un état déjà rencontré. C'est assez inefficace, en particulier lorsque la période ou la prépériode est longue.

On peut utiliser la méthode suivante :

on cherche le plus petit nombre n0 tels que iter f n0 x = iter f (2*n0) x
on calcule la période en cherchant le plus petit p qui vérifie iter f n0 x = iter f (n0+p) x
on calcule la prépériode en cherchant le plus grand q qui vérifie iter f q x <> iter f (q+p) x.

Attention : il s'agit d'une description formelle de l'algorithme. Pour le programmer, il faut réfléchir pour faire le moins de calculs possible ! En particulier, la fonction suivante est une mauvaise version de la première partie :

let borne f x =
  let rec aux n =
    if iter f n x = iter f (2*n) x
    then n
    else aux (n+1)
  in
  aux 1

Cette fonction est très mauvaise car elle recalcule iter f n x à chaque fois !

Écrivez, en minimisant la quantité de calculs faits, les fonctions permettant de calculer la période et la prépériode d'une fonction.

Vous finirez par une fonction pperiode : ('a -> 'a) -> 'a -> int*int qui prend une fonction f, un état initial x et qui renvoie une paire d'entier donnant la prépériode et la période correspondante.

Calculez les périodes et prépériodes de quelques fonctions utilisés pour des générateurs pseudo-aléatoires :

fun x -> (a*x + c) mod m pour différentes valeurs de a, c et m,
fun x -> milieu (x*x) pour la méthode des carrés, où milieu donne les bits (ou les chiffres) du milieu d'un nombre,
la fonction des générateurs à registre à rétroaction linéaire.
... `

TP4 : générateurs pseudo-aléatoires

info-421 : programmation fonctionnelle (Caml)

année 2012-2013