Readme
Le processeur papier M999
Le M999 est un processeur papier permettant de comprendre concrètement le fonctionnement d'une architecture Von Neumann. Il s'agit d'une variante du M99 avec un jeu d'instructions simplifié.
Présentation
Le M999 est une machine dotée de : - 1000 cases mémoire (adresses de 000 à 999), chacune contenant un mot de 3 chiffres - 3 registres : A, B et R (accumulateur/résultat) - 1 compteur de programme (PC) indiquant l'adresse de la prochaine instruction
Jeu d'instructions (version 1)
| Opcode | Instruction | Description |
|---|---|---|
| 0 xy | LDA xy | Charge le mot mémoire d'adresse xy dans le registre A |
| 1 xy | LDB xy | Charge le mot mémoire d'adresse xy dans le registre B |
| 2 xy | STR xy | Copie le contenu du registre R dans le mot mémoire d'adresse xy |
| 3 00 | ADD | R := A + B |
| 3 01 | SUB | R := A - B |
| 3 99 | NOP | Ne fait rien |
| 4 rs rd | MOV rs rd | Copie le registre source dans le registre destination |
| 5 xy | JMP xy | Saut inconditionnel à l'adresse xy |
| 6 xy | JPP xy | Saut à l'adresse xy si R > 0 |
Registres : 0 = A, 1 = B, 2 = R
Jeu d'instructions (version 2)
La version 2 ajoute deux instructions utiles pour l'algorithme de multiplication russe :
| Opcode | Instruction | Description |
|---|---|---|
| 3 02 | DIV2 | Divise A par 2 : quotient dans R, reste dans B |
| 3 03 | MUL2 | Multiplie A par 2 : résultat dans R |
Cycle d'exécution
Le processeur répète le cycle suivant :
- Fetch : Lire l'instruction à l'adresse PC
- Decode : Décoder l'opcode pour identifier l'opération
- Execute : Exécuter l'instruction
- Incrémenter PC (sauf si saut)
Le programme s'arrête quand PC atteint 999.
Différences avec le M99
| Opération | M99 | M999 |
|---|---|---|
| Charger A | 1xy | 0xy |
| Charger B | 2xy | 1xy |
| Stocker R | 0xy | 2xy |
| Addition | 400 | 300 |
| Soustraction | 401 | 301 |
Le M999 utilise une numérotation plus intuitive : 0 pour charger A, 1 pour charger B, 2 pour stocker.
Activité : La multiplication paysanne russe
Cette méthode ancestrale permet de multiplier deux nombres en utilisant uniquement : - Des divisions par 2 (partie entière) - Des multiplications par 2 - Des additions
Exemple : 13 × 5
| Colonne A (÷2) | Colonne B (×2) |
|---|---|
| 13 | 5 |
| 6 | ~~10~~ |
| 3 | 20 |
| 1 | 40 |
On raye les valeurs de B quand A est pair, puis on additionne les valeurs restantes : 5 + 20 + 40 = 65
Objectif
Implémenter cet algorithme sur le M999 en utilisant le jeu d'instructions version 2.
Aide : Pour savoir si A est pair, on utilise DIV2 (3 02) qui place le reste dans B. Si B = 0, alors A était pair.
Pour aller plus loin
- Écrire un programme qui calcule la factorielle d'un nombre
- Écrire un programme qui teste si un nombre est premier
- Comparer l'efficacité de la multiplication russe avec une multiplication par additions successives
Sources : - Informatique Sans Ordi - Philippe Marquet et Martin Quinson - Jeu d'instructions adapté par Philippe Boddaert
Auteur : Florian Mathieu
Licence CC BY NC
