Programmation Fonctionnelle, TP1

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP1 : Ensemble de Mandelbrot.

Guyslain Naves

L'objectif de ce travail est de réaliser des dessins de fractales, en utilisant le même moteur de calcul sur plusieurs polynômes complexes.

Image without legend

Nous rappelons q'un nombre complexe est de la forme $c = a + i b$, où $a$ est la partie réelle de $c$ et $b$ sa partie imaginaire. Nous coderons les nombres complexes comme des couples de flottants, ainsi, $c = 0.123 + 4.56 i$ sera encodé par la valeur

  1. let c = (0.123, 4.56)

Vous utiliserez les fonctions du module Pervasive de la librairie standard pour manipuler les nombres flottants et accéder aux fonctions mathématiques standards. L'API des modules est disponible sur cette page : la libraire standard.

Convergence d'une suite récursive complexe

Question : Algèbre des complexes

L'addition et la multiplication complexe sont donnés par $(a + i b) + (c + i d) = (a+c) + i (b + d)$ et $(a + i b)* (c + i d) = a*c - b*d + i (b*c + a*d)$. Utiliser cela pour coder l'addition, la multiplication et la puissance par un entier positif de nombres compexes en Ocaml.

Solution :

  1. let add (a,b) (c,d) = (a +. c, b +. d)
  2. let ( +! ) = add (* notation infixe *)

  3. let minus a (r,i) = add a (-.r, -.i)
  4. let ( -! ) = minus (* notation infixe *)

  5. let prod (a,b) (c,d) = (a *. c -. b *. d, a *. d +. b *. c)
  6. let ( *! ) = prod (* notation infixe *)

  7. let rec pow c = function
  8. | 0 -> (1.,0.)
  9. | n -> c *! (pow c (n-1))

  10. (* alternativement, la puissance rapide : *)
  11. let rec pow c = function
  12. | 0 -> (1.,0.)
  13. | n when n mod 2 = 0 -> pow (c *! c) (n/2) (* c^(2p) = (c^2)^p *)
  14. | n (* n impair *) -> c *! (pow (c *! c) (n/2)) (* c^(2p+1) = c * (c^2)^p *)

Question : Module d'un complexe

Le module d'un complexe est sa distance à l'origine dans le plan complexe. Si $c = a + i b$, alors le module de $c$ est $\left|c\right| = \sqrt{a^2 + b^2}$. Coder la fonction module d'un nombre complexe.

Solution :

  1. let norme (a,b) = sqrt (a ** 2. +. b **. 2.)

Question : Indice de divergence

On considère, pour un complexe donné $c$, le polynôme complexe $P_c(z) = z^2 + c$. L'ensemble de Mandelbrot est défini comme l'ensemble des complexes $c$ tels que $u_n = P_c^{(n)}(0)$ converge, avec $P_c^{(n)}(z) = P_c(P_c^{(n-1)}(z))$ si $n \geq 1$ et $P_c^{(0)}(z) = z$. On le voit en noir sur l'image suivante :

Image without legend

Savoir si $u_n$ converge ou diverge est un problème difficile, nous nous contentons d'utiliser une heuristique simple. Nous fixons un rayon $r \geq 2$ réel (par exemple, $r = 10^{10}$), et une borne entière $B$ (par exemple, $B=100$). Si $\left| P^{(n)}_c(0) \right| \geq r$ pour un $n \leq B$, alors $u_n$ diverge certainement. Sinon, on supposera (peut-être à tort) que $u_n$ converge. Autrement dit, nous calculons au plus $B$ itérations de la suite, et dès que nous obtenons un module supérieur à $r$, nous savons que la suite diverge.

$r = 2$ suffit pour être sûr que la suite diverge. En prenant une grande valeur de $r$, nous obtenons une meilleure précision sur la vitesse à laquelle la suite diverge (au prix d'un temps de calcul plus long).

Écrire une fonction récursive, qui étant donné $r$, $B$ et $P_c$, détermine le plus petit $n$ tel que $\left| P^{(n)}_c(0) \right| \geq r$, ou renvoie $B+1$ s'il n'existe pas de tel $n$.

Solution :

  1. let divergence radius bound poly =
  2. (* [terme_i] prend pour argument [i] et [z_i],
  3. avec [z] la suite complexe définie par [z_{i+1} = poly z_i], [z_0 = (0.,0.)] *)
  4. let rec terme_i i z_i =
  5. if (norme z_i > radius) || (i >= bound) then i (* || est le 'ou' booleen *)
  6. else terme_i (i+1) (poly z_i)
  7. in
  8. terme_i 0 (0.,0.)

Rendu graphique

On utilise la librairie Graphics, que l'on charge avec le code suivant :

  1. #load "graphics.cma";;
  2. open Graphics
  3. let _ = open_graph ""
  4. let _ = resize_window 400 400

Question : Itération sur un intervalle.

Écrire une fonction récursive iter_range de type (int -> unit) -> int -> int -> unit, telle que iter_range f mini maxi applique $f$ sur tous les entiers de l'intervalle $[\text{mini},\text{maxi}]$.

Solution :

  1. let rec iter_range f mini maxi =
  2. if not (mini > maxi) then
  3. begin
  4. f mini;
  5. iter_range f (mini+1) maxi
  6. end

Nous disposons donc maintenant de l'équivalent d'une boucle for, qui permet d'exécuter un calcul sur tous les éléments d'un intervalle. Par exemple,

  1. let () = iter_range (fun v -> Printf.printf "%i\n" v) 1 100

provoque à l'exécution l'impression en sortie standard des 100 premiers entiers strictement positifs.

Question : Itération sur un rectangle d'entier.

En déduire une fonction iter_rectangle de type (int -> unit) -> int -> int -> int -> int -> unit, telle que iter_rectangle f min_row max_row min_column max_column applique f row column pour tout row $\in$ [min_row,max_row] et tout column $\in$ [min_column, max_column].

Solution :

  1. let iter_rectangle f min_row max_row min_column max_column =
  2. let iter_one_row row = iter_range (fun column -> f row column) min_column max_column in
  3. iter_range iter_one_row min_row max_row

Question : Affichage d'une fonction sur le plan.

À un nombre complexe $a + i b$, on associe le point du plan $(a,b)$.

Écrire une fonction pour afficher une image, de type :

  1. val display : (float * float -> Graphics.color) -> (float * float) -> float -> float -> unit

Le premier argument est une fonction color_of_complex qui associe une couleur à chaque nombre complexe. Le second argument est le complexe au centre de l'image. Les deux arguments suivants précisent la largeur et la hauteur du rectangle du plan complexe à afficher.

L'effet de cette fonction sera donc d'afficher pour chaque pixel de la fenêtre graphique la couleur d'un point du plan calculé avec color_of_complex, en cohérence avec les arguments de centre et de dimension.

Vous utiliserez les fonctions size_x et size_y de la librairie Graphics pour connaître la taille de la fenêtre d'affichage.

Vous pouvez découper cette question comme suit.

  1. Écrire une fonction, prenant en argument le centre de l'image (un complexe $c$), la longueur et la hauteur de l'image affichée (notées $l$ et $h$), et un pixel de coordonnées $a,b$, et calculant un point complexe $z$ correspondant à ce pixel. La formule pour trouver $z$ est $z = c - (\frac{l}{2} + i \frac{h}{2}) + (\frac{l \cdot a}{x} + i \frac{h \cdot b}{y})$, avec $(x,y)$ la taille de la fenêtre graphique.
  2. En déduire une fonction qui affiche un pixel, étant donné ses coordonnées.
  3. Utiliser iter_rectangle pour afficher tous les pixels.

Solution :

  1. (* transforme un pixel en coordonnée complexe *)
  2. let complex_of_pixel c l h =
  3. let x = float_of_int (size_x ()) in
  4. let y = float_of_int (size_y ()) in
  5. (fun a b -> c -! (l /. 2., h /. 2.) +! (l *. (float_of_int a) /. x, h *. (float_of_int b) /. y))
  6. (* Subtilité : je vais calculer une fois pour toutes les valeurs de [x] et [y],
  7. j'obtiens ensuite une fonction qui prend deux entiers [a] et [b],
  8. et c'est cette fonction que j'appellerai plusieurs fois.
  9. *)


  10. (* je prends en argument la fonction calculant le complexe, et celle calculant la couleur du complexe *)
  11. let display_pixel complex_of_pixel color_of_complex a b =
  12. set_color (color_of_complex (complex_of_pixel a b));
  13. plot a b

  14. let display color_of_complex c l h =
  15. let () = clear_graph () in (* efface la fenêtre graphique *)
  16. let col_of_pix = complex_of_pixel c l h in
  17. iter_rectangle
  18. (display_pixel col_of_pix color_of_complex) (* affiche le pixel (a,b) *)
  19. 0 (size_x ()) (* pour a dans [0,size_x ()] *)
  20. 0 (size_y ()) (* et b dans [0,size_y ()] *)


  21. (* un petit test pour vérifier que tout va bien jusque là *)
  22. let _ = display (fun c -> rgb (10 * (int_of_float (norme c /. 10.)) mod 255) 0 0) (0.,0.) 600. 600.
  23. (* doit afficher des cercles concentriques dans les tons rouges *)

Question : calcul de la couleur d'un point.

Étant donné $P_c$, la couleur attribuée au point $c$ est le noir si l'indice de divergence est $B+1$. Sinon, la couleur attribuée est fonction de l'indice de divergence. Les choix possibles de couleurs sont infinis. Une idée générale est d'attribuer deux couleurs d'autant plus proches que les indices de divergence sont eux-mêmes proches, afin d'obtenir des gradients de couleurs. Coder différentes fonctions de type float -> Graphics.color transformant un indice de divergence (converti en flottant pour rester cohérent avec la suite du TP) en couleur.

Solution possible :

  1. (* un gradient simple en nuance de gris *)
  2. (* [scaling_factor] permettra de régler la vitesse à laquelle les couleurs changent *)
  3. let grey_of_float scaling_factor f =
  4. let i = 255 - (abs (255 - (int_of_float (f *. scaling_factor) mod 511))) in
  5. rgb i i i

  6. (* du code plus complexe, proposant une autre solution *)
  7. let median a b x = int_of_float (255. *. ((1. -. x) *. a +. x *. b))

  8. let gradient low high (ra,ga,ba) (rb,gb,bb) otherwise x =
  9. if low <= x && x < high then
  10. let lambda = (x -. low) /. (high -. low) in
  11. rgb (median ra rb lambda) (median ga gb lambda) (median ba bb lambda)
  12. else otherwise x

  13. (* un gradient défini sur trois intervalles *)
  14. let white = (1.,1.,1.)
  15. let grey = (0.5,0.5,0.5)
  16. let blue = (0.2,0.2,1.)
  17. let yellow = (0.8,0.8,0.)
  18. let complicated_gradient =
  19. gradient 0. 15. white grey
  20. (gradient 15. 40. grey blue
  21. (gradient 40. 100. blue yellow
  22. (fun x -> black)
  23. ))

Question : rendu d'une fractale

Combiner les résultats des précédentes questions pour obtenir un dessin de fractale, en utilisant $P_c(z) = z^2 + c$.

Solution :

  1. let p c z = z *! z +! c

  2. let mandelbrot c = float_of_int (divergence 10. 100 (p c))
  3. let _= display (fun c -> grey_of_float 30. (mandelbrot c)) (0.,0.) 6. 6.
  4. let _= display (fun c -> complicated_gradient (mandelbrot c)) (0.,0.) 6. 6.
  5. let _= display (fun c -> complicated_gradient (mandelbrot c)) (-0.82,-0.19) 0.038 0.038

Amélioration de l'image

L'indice de divergence étant entier, les images font apparaitre des zones uniformes de couleurs qui nuisent à leur aspect esthétique. Cette partie propose un amélioration pour lisser les couleurs. Pour cela, il faut raffiner le calcul de l'indice de divergence. Notons $d$ le degré du polynome $P_c$ utilisé (pour l'instant, $d = 2$).

Image without legend

Désormais, l'indice de divergence est donné par la formule:

$$ n - \frac{\log \frac{\log |z|}{\log r}}{\log d}$$

avec :

  • $n$ le plus petit entier tel que $\left| P_c^{(n)}(0) \right| \geq r$,
  • $z = P_c^{(n)}(0)$

Utiliser cette formule pour améliorer le rendu.

Solution :

  1. let divergence r b p d =
  2. let rec terme_i i z_i =
  3. if (norme z_i > r) || (i >= b) then (i,z_i)
  4. else terme_i (i+1) (p z_i)
  5. in
  6. let (n,z) = terme_i 0 (0.,0.) in
  7. (float_of_int n) -. log ( (log (norme z)) /. (log r)) /. (log d)

  8. let mandelbrot c = divergence 10e10 200 (p c) 2.
  9. let _ = display (fun c -> grey_of_float 30. (mandelbrot c)) (0.,0.) 6. 6.
  10. let _ = display (fun c -> complicated_gradient (mandelbrot c)) (0.,0.) 6. 6.
  11. let _ = display (fun c -> complicated_gradient (mandelbrot c)) (-0.82,-0.18) 0.3 0.3
  12. let _ = display (fun c -> complicated_gradient (mandelbrot c)) (-0.82,-0.19) 0.038 0.038

À vous de jouer...

Essayer de tracer d'autres fractales, en utilisant des polynomes différents, par exemple $z \rightarrow z^3 + c$, en testant des fonctions de colorations plus subtiles et en zoomant sur des points intéressants du plan.

  1. let red = (1.,0.2,0.2)
  2. let green= (0.4,0.8,0.4)
  3. let flashy_green = (0.3,1.,0.3)
  4. let complicated_gradient_2 x =
  5. gradient 0. 75. white grey
  6. (gradient 75. 80. grey red
  7. (gradient 80. 100. red yellow
  8. (gradient 100. 120. yellow green
  9. (gradient 120. 200. green flashy_green
  10. (fun x -> black)))))
  11. (x -. 20.)
  12. let _ = display (fun c -> complicated_gradient_2 (mandelbrot c))
  13. (0.001643721971153,0.822467633298876) 0.0000003 0.0000003
Image without legend
  1. let comp (a,b) = (a,-.b)
  2. let tricorn c = divergence 10e10 200 (fun z -> pow (comp z) 2 +! c) 2.
  3. let _ = display (fun c -> grey_of_float 30. (tricorn c)) (0.,0.) 6. 6.
  4. let _ = display (fun c -> complicated_gradient (tricorn c +. 10.)) (0.,0.) 6. 6.
Image without legend