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. Ceci nous amènera à définir des fonctions simples, à apprendre à faire des sortes de boucles à partir de récursion, et aussi à écrire quelques fonctions d'ordre supérieur.
Nous rappelons qu'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 pouvons aussi le représenter comme un vecteur du plan 2-dimensionel $(a,b)$. Nous coderons les nombres complexes comme des couples de flottants, ainsi, $c = 0.123 + 4.56 i$ sera encodé par la valeur (notez comment sont construits les couples)
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.
Consulter le sommaire du cours pour mettre en place votre environnement de travail. Vous trouverez aussi une aide contenant des exemples de syntaxe.
Avant de vous lancer dans le TP, prenez le temps de découvrir l'éditeur que vous utilisez et l'interprèteur Ocaml. Vous pouvez reprendre les exercices du TD et les compiler par exemple pour vous familiariser avec ce nouvel environnement.
L'addition et la multiplication complexes sont donnés par $(a + i b) + (c + i d) = (a+c) + i (b + d)$ et $(a + i b) \times (c + i d) = ac - bd + i (bc + ad)$. Utilisez cela pour coder l'addition, la multiplication et la puissance par un entier positif de nombres compexes en Ocaml.
Pour la puissance, utilisez une définition récursive, en utilisant le mot-clé rec.
Utilisez la boucle d'interaction pour tester vos fonctions.
Ensuite, vous pouvez définir des opérateurs infixes pour utiliser ces fonctions :
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.
Pour la racine carrée, la fonction idoine est définie dans la librairie standard, dont vous pouvez voir la documentation ici.
Une suite récursive est une séquence infinie de valeurs définies par une relation de récurrence, par exemple par $u_{n+1} = f(u_{n}), u_0 = c$. Étant donné la fonction $f$ et la constante $c$, nous voulons calculer les valeurs de cette suite.
Nous représentons la $n$e valeur de la suite par une paire $(u_n,n)$. Écrire une fonction next qui étant donné $f$ et la $n$e valeur, calcule la $(n+1)$e valeur.
Nous allons écrire une version fonctionnelle de la boucle for. Le principe d'un for est de faire $n$ fois la même opération. Étant données une fonction $f$ et une valeur $v$, nous voulons donc calculer $f (f (f \ldots (f v)\ldots ))$, avec $n$ appels à $f$.
Définissez une fonction récursive repeat pour effectuer ce calcul.
Ainsi, pour calculer le $n$e terme, il suffit de faire :
Utilisez repeat pour afficher "Hello world!" dix fois.
Passons à l'équivalent fonctionnel du while. En s'inspirant de repeat, écrivez une fonction qui applique $f$ jusqu'à ce que le résultat soit supérieur ou égal à 100 :
Ensuite, remplacez la condition au moins 100 par un prédicat sur la valeur $v$ que la fonction prend en argument :
On peut alors redéfinir :
Soit la suite d'entiers définie par la fonction collatz :
Calculez à l'aide de repeat_until le plus petit indice $n$ tel que le $n$e terme de la suite de Collatz soit 1 .
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 la suite $u_n$ générée par $P_c$ avec $u_0 = 0$ converge. On le voit en noir sur l'image suivante :
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).
Écrivez une fonction utilisant repeat_until, 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 $n > B$. On traduit ensuite cet entier en flottant (via la fonction float_of_int), qui est négatif si $n > B$.
La valeur du nombre d'itérations effectuées sera plus tard traduite en couleur pour donner la couleur du point de coordonnée $c$.
On utilise la librairie Graphics, que l'on charge avec le code suivant :
Si tout s'est passé correctement, une fenêtre blanche devrait s'être ouverte, dans laquelle nous allons dessiner.
Écrivez une fonction récursive iter_interval, telle que iter_interval ~f ~min ~max applique $f$ sur tous les entiers de l'intervalle $[\text{min},\text{max}]$.
Nous disposons donc maintenant d'une autre version de la boucle for, qui permet d'exécuter un calcul sur tous les éléments d'un intervalle. Par exemple,
provoque à l'exécution l'impression en sortie standard des 100 premiers entiers strictement positifs.
En déduire une fonction iter_rectangle telle que iter_rectangle ~f ~xmin ~xmax ~ymin ~ymax applique f x y pour tout x $\in$ [xmin,xmax] et tout y $\in$ [ymin, ymax].
Ceci nous donne donc une sorte de boucle for en deux dimensions. Utilisez-la pour calculer les tables de multiplications jusqu'à 9 .
À un nombre complexe $a + i b$, on associe le point du plan $(a,b)$.
Complétez la fonction suivante, qui affiche une image selon les arguments :
Nous avons déjà écrit la fonction qui transforme un pixel en une couleur, et celle qui remplit un pixel. Il suffit donc d'appeller draw_pixel pour tous les pixels de la fenêtre graphique.
Testez votre code avec cet appel. Le résultat obtenu est-il celui auquel vous vous attendiez ?
Étant donné $P_c$, la couleur attribuée au point $c$ est le noir si l'indice de divergence est supérieur à la borne sur le nombre d'itération. Sinon, la couleur attribuée est fonction du nombre d'itération. Les choix possibles de couleurs sont illimités. 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. Nous allons coder des gradients de couleurs. On commence par faire un dessin en noir et blanc.
Définissez le polynome complexe $P_c(z) = z^2 + c$ comme une fonction de $c$ et $z$. Puis codez une fonction qui étant donné $c$, calcule l'indice de divergence de $P_c$ en appelan la fonction divergence et retourne une couleur, blanc ou noir, selon que le nombre d'itérations dépasse ou non la borne. Enfin, affichez le résultat avec la fonction display :
On représente les couleurs par des triplets de flottants compris entre 0 et 1 en notation RGB. On souhaite faire un mélange de couleurs avec différentes proportions. Par exemple 2 unités de bleu avec 3 unités de jaune. Il s'agit donc de calculer une moyenne pondérée de deux couleurs, un barycentre.
Nous utilisons la fonction élémentaire suivante pour calculer le barycentre de deux flottants :
Nous pouvons ensuite l'utiliser pour écrire une fonction pour les triplets de flottants. De façon générale, il est toujours possible de prendre un opérateur sur les flottants et d'en faire un opérateur sur les triplets de flottants. C'est ce que fait la fonction suivante :
Utiliser ces deux fonctions pour coder le mélange de deux couleurs :
Nous devons transformer un flottant en couleur. Nous fixons deux flottants min et max et deux couleurs associées, ce sont les limites du gradient. Si la valeur value dont on cherche la couleur est entre min et max, on calcule le barycentre des deux couleurs avec les coefficients max -. value et value -. min, et cela crée un gradient linéaire.
Si value n'est pas dans les bornes, on utilise une autre fonction appelée otherwise pour calculer la couleur associée.
Implémentez cette idée en complétant la fonction suivante :
Créez un gradient simple et ajoutez des couleurs à l'image précédemment en noir et blanc.
La valeur de divergence étant entière, 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 cette valeur. Notons $d$ le degré du polynome $P_c$ utilisé (pour l'instant, $d = 2$). Utilisez la formule suivante :
$$ n - \frac{\log \frac{\log |z_n|}{\log r}}{\log d}$$
avec :
En utilisant un seul gradient linéaire entre $0$ et $100$, nous obtenons une image assez décevante parce que beaucoup plus de points sont proches de $0$ que de $100$, et donc la linéarité du gradient est contre-effective.
De plus, une seul gradient ne permet pas d'avoir d'aussi jolies couleurs qu'avec trois ou quatre gradients qui se partagent l'ensemble des flottants possibles.
Créez des schémas de couleurs utilisant plusieurs gradients se partageant l'ensemble des flottants compris entre $0$ et $100$.
Quelques points intéressants sur lesquels zoomer :
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.
