Sujet

Le projet est à réaliser individuellement et devra être rendu d'ici la fin du semestre.

Objectifs

Les deux objectifs du projet sont les suivants :

calculer une valeur approximative de π à l'aide d'une simulation de Monte-Carlo ;
générer une image animée représentant la simulation comme ci-dessous.

Image animée

Pour calculer une approximation de π à l'aide d'une simulation de Monte-Carlo en tirant n points aléatoires (comme au casino), un algorithme simple est le suivant :

initialiser un compteur à 0 ;
pour i allant de 1 à n :
- générer un point aléatoire (x,y) dans un carré de longueur 2 et de centre (0,0). Pour cela il suffit de générer x dans [-1,1] et y dans [-1,1] ;
- si le point est dans le cercle de centre (0,0) et de rayon 1, ajouter 1 au compteur ;
l'estimation de π/4 est la valeur du compteur divisée par le nombre n.

Pour en savoir plus sur le sujet, nous nous référerons au très clair billet de Bruno Tuffin sur le site interstices.info.

Pour la création de l'image animée, nous générerons des images au format PPM puis nous les agrégerons comme expliqué dans la prochaine section.

Travail à réaliser

Le travail à réaliser se décompose en deux parties.

Première partie : simulation

La première partie du projet consiste à écrire un module Python simulator.py qui sera le coeur de notre simulation. Autrement dit, ce module se charge uniquement du travail en lien avec le calcul d'une approximation de π sans se préoccuper des questions de visualisation sous forme d'image.

Il est demandé que le module simulator.py soit également un programme exécutable permettant de donner une approximation de π en utilisant un nombre de points donné sur la ligne de commande tel qu'illustré ci-dessous :

[selvama@ensipc215 projet_bpi]$ ./simulator.py 100000000
3.14152532

Deuxième partie : génération d'images `PPM`

Nous allons maintenant utiliser simulator.py comme un module pour passer aux choses sérieuses, c'est à dire à la génération de notre image animée représentant une simulation. Le travail demandé consiste à écrire un programme Python approximate_pi.py qui :

reçoit 3 arguments dans l'ordre suivant depuis la ligne de commande :
- la taille de l'image en pixels (qui est carrée, donc un seul entier) ;
- le nombre de point n à utiliser dans la simulation ;
- le nombre de chiffres après la virgule à utiliser dans l'affichage de la valeur approximative de π.
implémente une fonction generate_ppm_file(...) qui génère une image au format PPM. L'image doit montrer les points qui sont à l'intérieur du cercle d'une certaine couleur, les points qui sont à l'extérieur du cercle d'une autre couleur et la valeur approchée de π comme l'illustre l'image animée ci-dessus. Le nom de l'image doit être au format img0_3-13776.ppm : 0 indique le numéro de l'image dans la simulation totale (0 en l'occurrence, donc la première image) et 3-13776 correspond à l'approximation courante de π en utilisant le nombre de chiffres après la virgule spécifié sur la ligne de commande (5 en l'occurrence). La signature de la fonction n'est volontairement pas donnée pour que chacun puisse réaliser sa propre solution ;
génère une image PPM, en utilisant la fonction generate_ppm_file, représentant l'état courant de la simulation à chaque fois qu'un dixième du nombre total de points a été tiré. Dix images seront donc générées ;
utilise le programme convert pour créer une image animée au format GIF à partir des dix images PPM.

Évaluation

Critères d'évaluation

L'évaluation du projet se fera sur la base des critères suivants :

justesse du code : le programme réalise bien ce qui est demandé ;
qualité du code : utilisation d'au moins deux modules tel que demandé ci-dessus et utilisation de pylint. Le fichier de configuration pour pylint est disponible ici. Ce fichier doit être placé à la racine de votre répertoire personnel et doit être nommé .pylintrc;
performance du programme en fonction des entrées ;
utilisation mémoire du programme en fonction des entrées ;
le poids des images PPM générées (c'est à dire le nombre d'octets sur le disque dur) ;
respect des consignes ci-dessous.

À titre d'information, le programme qui a généré l'image animée ci-dessus correspondant a une simulation avec un million de point a pris environ 9 secondes (sur un ordinateur portable récent assez haut de gamme) et a utilisé un maximum de 205 mégaoctets de mémoire à un instant donné. Les dix images PPM générées, d'une taille de 800 x 800, pèsent 1,9 mégaoctets chacune.

Des tests automatiques seront utilisés sur votre code afin d'évaluer ces critères.

Rendu

À la fin du projet, vous devez rendre :

votre code, c'est à dire uniquement vos fichiers Python ;
un rapport de deux pages maximum.

Dans le rapport vous présenterez, en argumentant, l'état de votre programme vis à vis des critères ci-dessus. Comme le rapport est limité à deux pages, il ne faut surtout pas reprendre le sujet mais présenter directement vos arguments.

Consignes à respecter

Il est demandé de respecter les consignes suivantes dans votre code :

lancer une exception sans l'attraper si une ou plusieurs entrées incorrectes sont données par l'utilisateur sur la ligne de commande. Autrement dit, si l'utilisateur lance le programme avec ./approximate_pi.py tutu 10000 4 ou avec ./approximate_pi.py -800 100000 4 il doit voir dans son terminal une erreur indiquant l'exception qui a été lancée ainsi que la pile d'appels. L'interpréteur se charge de tout cet affichage pour nous quand on lance une exception et que celle-ci n'est jamais attrapée et donc remonte jusqu'au sommet de la pile d'appels ;
utiliser des f-string quand cela est pertinent ;
utiliser le module subprocess pour générer l'image animée GIF à partir des images PPM ;

Résumé des consignes et précisions apportées au fil du projet sur le salon général BPI

ne pas mettre son nom ni dans le rapport ni dans les fichiers Python (c'est pour corriger de façon anonyme) ;
des valeurs raisonnables, disons entre 1 et 7, seront utilisées pour le paramètre nombre de décimales ;
l'archive ne doit contenir que vos fichiers Python et votre rapport, rien d'autre ;
vous pouvez utiliser des modules externes comme numpy, même si ce n'est pas du tout nécessaire ;
vous pouvez utiliser PIL ou autre chose pour rajouter le texte de π par dessus votre image, même si l'objectif premier était de le coder à la main en pensant à l'afficheur 7 segments de votre gadget électronique préféré ;
le temps d'exécution absolu de votre programme sur des entrées particulières n'est pas très important. Ce qui compte surtout, c'est l'évolution du temps en fonction des entrées, c'est à dire la complexité ;
idem pour l'utilisation mémoire ;
le module simulator.py doit fournir à minima les points aléatoires au programme approximate_pi.py ainsi que la fonction indiquant si un point est dans le cercle unitaire ou non ;
idéalement, la taille du texte de π par dessus votre image s'adapte à la taille de l'image ;
aucun problème si votre programme est capable de prendre des arguments optionnels en plus des 3 arguments obligatoires ;
respecter scrupuleusement les noms des fichiers Python et image indiqués sur cette page un peu plus haut ;

Cliquez ici pour révéler la correction.

Correction

Voici ci-dessous deux propositions de correction. D'autres solutions faisant des choix différents impliquant éventuellement des complexité mémoire et temps de calcul différentes, néanmoins toutes aussi raisonnables sont possibles. On peut notamment citer une autre solution consistant à stocker toute l'image en mémoire via une list ou un bytearray et "écrire les pixels" directement au bon endroit dans cette list ou ce bytearray. N'hésitez pas à contacter vos enseignants si vous voulez discuter d'une solution particulière.

`simulator.py`

Les points clés sont les suivants :

la fonction génératrice simulate_iterator(nb_point) renvoie un itérateur permettant de tirer aléatoirement nb_point points (x, y) avec x dans [-1, 1] et y dans [-1, 1]. En plus du point courant, l'itérateur renvoie un booléen indiquant si le point courant est dans le cercle ou non ainsi que le nombre de points déjà tirés appartenant au cercle ;
lorsque simulator.py est utilisé comme programme principal, on crée simplement un itérateur avec la fonction génératrice simulate_iterator(nb_point) puis on le parcours entièrement sans rien faire juste pour récupérer le nombre total de points dans le cercle. Avec cette valeur on calcul l'approximation de π. La complexité mémoire du programme est donc constante et la complexité en temps de calcul est une fonction linéaire du nombre de points.

#!/usr/bin/env python3


"""Heart of the simulation.

This module provides:

- a Point type made of two integers called x and y
- a function to fix the randomness of point generation
- a function to generate a random point
- a function to approximate the value of PI from points
"""

import math

import random
import collections
import sys

# A point in a square of size 2.
# Hence point.x ∈ [-1, 1] and point.y ∈ [-1, 1]
Point = collections.namedtuple("Point", ["x", "y"])

def fix_random_from(number):
    """Fix the random number generation for reproductibility

    The generated sequence of points must be same every time
    this function is called with the same number before the
    first call to create_random_point.
    """
    random.seed(number)

def create_random_point():
    """Return a new random point between (0, 0) and (max_val, max_val)"""
    x_coord = random.uniform(-1, 1)
    y_coord = random.uniform(-1, 1)
    return Point(x_coord, y_coord)

def simulate_iterator(nb_points):
    """Generator for the simulation"""
    nb_points_in_circle = 0
    for _ in range(nb_points):
        point = create_random_point()
        in_circle = is_in_circle(point)
        nb_points_in_circle += int(in_circle)
        yield point, in_circle, nb_points_in_circle

def simulate_quadratic_with_list(nb_points):
    """Simulation using a list.

    For testing auto tests only.
    Linear in memory, quadratic in time
    """
    nb_points_in_circle = 0
    points = []
    for _ in range(nb_points):
        for i, _ in enumerate(range(nb_points)):
            if i == 0:
                point = create_random_point()
                points.append(points)
                in_circle = is_in_circle(point)
                nb_points_in_circle += int(in_circle)
    return (points, in_circle, nb_points_in_circle)

def is_in_circle(point):
    """Return True if the point is in the unit circle and False otherwise"""
    dist_from_center = math.sqrt((point.x - 0.0)**2 + (point.y - 0.0)**2)
    return dist_from_center <= 1

def main():
    """Program's entry point"""

    # Program's inputs is given on the command line
    if len(sys.argv) != 2:
        print("utilisation ./simulator.py nb_points")
    nb_points = int(sys.argv[1])
    if nb_points <= 0:
        raise ValueError("all parameters must be integers "
                         "strictly greater than 0")

    # Fix random in the simulator
    fix_random_from(42)

    # Main simulation loop using generator function
    for last in simulate_iterator(nb_points):
        pass
    # pylint: disable=undefined-loop-variable
    _, _, nb_points_in_circle = last

    # Main simulation loop using list
    # For testing the automatic test only
    # i.e to have LINEAR memory complexity
    # instead of CONSTANT and quadratic
    # in time instead of linear
    # _, _, nb_points_in_circle = simulate_quadratic_with_list(nb_points)

    # Approximate the value of PI from the points
    # Nous on sait que nb_points > 0, donc on le dit à pylint
    pi_approx = 4 * nb_points_in_circle / nb_points
    print(pi_approx)

if __name__ == "__main__":
    main()

`approximate_pi.py`