Architecture des ordinateurs
TP Noté

Crible d’Ératosthène

ESIPE - INFO 1 2024 –2025

Le but de ce TP noté est de réaliser un programme assembleur implantant le crible d’Ératosthène. Ce TP demande l’application de toutes les techniques et éléments vus au cours des séances précédentes.

1 Consignes générales

  • Le cours ainsi que toutes les ressources de la page du cours sont autorisés. Les notes personnelles sur papier sont également autorisées.

  • Les appareils numériques sont interdits.

  • Vous devez travailler dans le répertoire EXAM de votre répertoire personnel. Tout document hors de ce dossier ne sera pas évalué.

  • Les fichiers nécessaires pour travailler sont les suivants : Fichiers.zip

  • Vous disposez d’un script Compile.sh pour compiler le programme à compléter. Ce dernier produit également un exécutable ./testeur qui teste les fonctions de votre programme. Si le programme complet est attendu, le testeur teste sur quelques cas le bon fonctionnement de vos fonctions même si vous ne les avez pas toutes écrites, profitez en.

  • Un programme complet doit passer tous les tests du testeur.

  • Le code réalisé doit être commenté.Z

2 Algorithme

L’algorithme du crible d’Ératosthène permet de calculer tous les nombres premiers inférieurs à un nombre \(n\) fixé. Il procède ainsi :

  1. on commence par générer une liste d’entiers \(L := [2, 3, 4, \dots, n]\). Chaque entier de cette liste possède un état : il peut être marqué ou bien non marqué. Initialement, tous les entiers de \(L\) sont non marqués ;

  2. ensuite, tant qu’il existe des nombres non marqués dans la liste \(L\) :

    1. on marque le plus petit nombre \(k\) de \(L\) non encore marqué ;

    2. pour tout nombre \(\ell > k\) de la liste \(L\) :

      • si \(k\) est un diviseur de \(\ell\), alors on supprime l’élément \(\ell\) de la liste ;

  3. la liste \(L\) — qui contient maintenant exclusivement des nombres marqués — est la liste des nombres premiers inférieurs à \(n\).

Par exemple, si on applique cet algorithme pour \(n := 30\), on obtient successivement les valeurs de \(L\) suivantes (les nombres marqués sont soulignés) :

      2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
      2 3   5   7   9    11    13    15    17    19    21    23    25    27    29
      2 3   5   7        11    13          17    19          23    25          29
      2 3   5   7        11    13          17    19          23                29
      2 3   5   7        11    13          17    19          23                29
      2 3   5   7        11    13          17    19          23                29
      2 3   5   7        11    13          17    19          23                29
      2 3   5   7        11    13          17    19          23                29
      2 3   5   7        11    13          17    19          23                29
      2 3   5   7        11    13          17    19          23                29
      2 3   5   7        11    13          17    19          23                29

3 Implantation

On peut se servir de la bibliothèque asm_io.inc pour gérer les entrées/sorties. Le programme doit définir une constante N de valeur 128. Ceci est réalisé par la déclaration

%define N 128

Le programme doit également réserver N-1 octets à partir d’une adresse tab et un octet à l’adresse pgm. Ceci est réalisé par les déclarations

tab : resb N-1
pgm : resb 1

à disposer dans la section .bss.

La suite de N octets tab peut être vue comme un tableau. Celui-ci est utilisé pour mémoriser les nombres effacés pendant l’exécution de l’algorithme. Pour cela, l’octet à l’adresse tab + i - 2 vaut 1 si le nombre i n’est pas effacé et 0 s’il est effacé.

Il s’agit pour débuter de bien comprendre l’adresse spécifée par la formule précédente. En effet, comme la liste des entiers à considérer commence par \(2\) (car aucun nombre strictement inférieur à \(2\) n’est premier), l’octet à l’adresse tab + 2 - 2 = tab est dédié à coder la présence/absence de 2. En poursuivant le raisonnement, c’est bien l’octet à l’adresse tab + 3 - 2 = tab + 1 qui est dédié à coder la présence/absence de 3. Et ainsi de suite, ce qui explique la formule générale.

Par ailleurs, en plus de tout cela, la variable à l’adresse pgm contient la valeur du plus grand nombre marqué (c’est-à-dire donc le dernier nombre marqué).

Important 1.

  1. Toutes les fonctions implantées par la suite doivent respecter la convention d’appel du C.

  2. Chaque fonction implantée doit être documentée en mentionnant son rôle, ses arguments attendus et son renvoi.

  3. On utilisera le fichier Squelette.asm qui contient un squelette du code a fournir. Il suffit de le remplir ses parties manquantes conformément aux questions suivantes.

Exercice 1.

  1. \(\blacksquare\) Écrire une fonction effacer qui prend en argument un nombre i et positionne la case correspondante du tableau tab à 0, signifiant que le nombre i est effacé.

    Note : il se peut que la réponse à cette question figure déjà dans le fichier Squelette.asm. Il est important de bien la comprendre avant d’aller plus loin.

  2. \(\blacksquare\) Écrire une fonction ajouter qui prend en argument un nombre i et positionne la case correspondante du tableau tab à 1, signifiant que le nombre i n’est pas effacé.

  3. \(\blacksquare\) Écrire une fonction lire qui prend en argument un nombre i et renvoie dans eax la valeur de la case correspondante dans le tableau tab.

    Dorénavant, on utilisera uniquement les trois fonctions précédentes pour accéder au tableau tab, que ce soit en lecture ou en écriture.

  4. \(\blacksquare\) Écrire une fonction initialiser qui positionne tous les octets du tableau tab à 1. Cette fonction doit aussi positionner la variable pgm à la valeur 0 pour spécifier qu’aucun nombre du tableau n’est marqué.

  5. \(\blacksquare\) Écrire une fonction effacer_multiples qui prend un argument p et qui positionne à 0 les cases du tableau tab correspondant aux entiers qui sont multiples de p.

  6. \(\blacksquare\) Écrire une fonction premier_suivant qui prend un argument i et renvoie dans eax la valeur du premier nombre supérieur à i tel que l’octet correspondant dans le tableau tab vaut 1. Si une telle valeur n’existe pas, la fonction renvoie N + 1.

  7. \(\blacksquare\) Écrire une fonction afficher qui affiche dans l’ordre croissant les nombres qui sont codés comme présents par le tableau tab.

  8. \(\blacksquare\) Rassembler et utiliser les fonctions écrites en un programme complet qui implante l’algorithme d’Ératosthène. Le programme, lorsqu’il est exécuté, doit afficher les nombres premiers inférieurs à N.

  9. \(\blacksquare\) Améliorer le programme afin qu’il sorte de la boucle principale (instruction 2.) lorsque le plus grand nombre marqué dépasse \(\sqrt{N}\).

    Note : Il n’est pas nécessaire de savoir calculer la racine carrée de \(N\).