Comment boucler et encoder en binaire?

Sep 02 2020

J'essaie de faire fonctionner un programme dans le LMC qui convertit n'importe quel numérique en binaire.

Normalement, j'utiliserais simplement la méthode de division, mais je ne peux pas le faire car le Little Man Computer ne permet pas la division ou la multiplication. Le plus loin que je connaisse n'est qu'un simple INP. A ce stade, je ne sais pas comment démarrer des boucles, ni même comment commencer.

Comment puis-je démarrer des boucles? Et comment puis-je les arrêter? J'aurais en quelque sorte besoin d'une boucle répétée qui soustrait une valeur jusqu'à ce qu'elle atteigne un 1 ou un 0. Cela atteindra mon objectif car je peux simplement le sortir ensuite.

Par exemple: j'entre 33 et cela donne un 100 001 dans la sortie.

Je suis un débutant total. Je viens de le ramasser aujourd'hui, donc le garder simple serait grandement apprécié.

Réponses

trincot Sep 07 2020 at 19:31

Vous écrivez que pour 33, la sortie doit être 100 001. Cela peut ne pas fonctionner (selon le simulateur LMC), car la deuxième valeur pourrait être sortie sans les zéros pré-ajoutés, et donc elle afficherait 100 1. Cela peut être déroutant car ressemble beaucoup à ce que vous attendez de l'entrée 9.

Je suggérerais de sortir chaque chiffre binaire sous forme de nombre séparé : de cette façon, vous vous assurez que tous les chiffres sont visibles dans la sortie.

Un algorithme pour encoder une entrée n comme ça, pourrait être le suivant:

Comparez n avec 512. Si ce n'est pas moins:

une. Sortez 1 et soustrayez 512 de n , sinon:

b. Sortie 0
Doubler la valeur de n , c'est-à-dire ajouter n à lui-même
Répétez ce qui précède 9 fois de plus. Décrémentez un compteur qui commence par 10 et répétez tant qu'il ne définit pas l'indicateur négatif.

Comment boucler

Vous «lancez» donc une boucle de manière statique: définissez la valeur initiale d'un compteur dans une DATinstruction. Dans l'algorithme ci-dessus, nous voulons que le compteur commence à 10:

COUNTER DAT 10

Ensuite, lorsque vous avez besoin de boucler, décrémentez le compteur:

LDA COUNTER
SUB ONE
STA COUNTER

Et (comme de nombreux programmes LMC), vous avez besoin d'une constante ONEpour cela:

ONE DAT 1

Enfin, pour savoir si le compteur n'est pas descendu en dessous de 0, vous pouvez cocher le drapeau "négatif". C'est un indicateur qui peut être défini par SUB, lorsqu'il y a un dépassement négatif (rappelez-vous que le LMC ne peut pas vraiment stocker de valeurs négatives, vous n'avez donc l'indicateur que comme indication). L' BRPinstruction (branchement lorsqu'il est positif) utilisera cet indicateur pour décider de sauter ou non:

BRP LOOP

LOOP doit être l'étiquette du début du code de votre boucle.

la mise en oeuvre

Notez que dans ce cas pratique, il n'est pas utile d'exécuter cette boucle plus de 10 fois, car l'entrée dans LMC ne peut pas être supérieure à 999, ce qui en binaire prend 10 chiffres.

Voici la mise en œuvre de l'algorithme décrit ci-dessus, avec également une précaution que le compteur démarrera à sa valeur initiale même lorsque le compteur du programme est réinitialisé après une première exécution:

#input:13
         INP
         STA NUM
         LDA NINE
LOOP     STA COUNTER
         LDA NUM
COMPARE  SUB POW_9
         BRP BIT1
BIT0     LDA ZERO
         OUT
         BRA DOUBLE
BIT1     STA NUM  ; Reduce number with 512
         LDA ONE
         OUT
DOUBLE   LDA NUM
         ADD NUM
         STA NUM
         LDA COUNTER
         SUB ONE
         BRP LOOP
ZERO     HLT
POW_9    DAT 512
ONE      DAT   1
NINE     DAT   9
NUM      DAT
COUNTER  DAT

<script src="https://cdn.jsdelivr.net/gh/trincot/[email protected]/lmc.js"></script>

Alternative

Il existe plusieurs autres façons d'accomplir cette tâche. Par exemple, nous pouvons coder en dur les puissances de 2 dont nous avons besoin pour 10 chiffres binaires: 1, 2, 4, ..., 512.

Ensuite, comparez la valeur d'entrée avec la plus grande de celles-ci (avec 2 ⁹ = 512). Si ce n'est pas moins, émettez 1 bit, sinon sortez 0. Si 1, soustrayez la puissance de 2 du nombre d'entrée. Dans les deux cas, passez à la puissance précédente de 2 (2 ⁸ ) et répétez ce processus. Répétez ceci jusqu'à ce que vous ayez fait le travail pour 2 ⁰ .

Vous pouvez essayer de l'implémenter sans boucle, mais vous aurez 10 fois le même code, avec juste une puissance différente de 2. Cela peut même être un défi de tenir dans la mémoire de 100 "boîtes aux lettres" du LMC (cela fonctionnerait cependant, si vous limitez l'entrée à 64, vous n'aurez donc besoin que de 6 chiffres binaires).

Pour implémenter cela avec une boucle (moins de code), vous pouvez utiliser une technique d'adressage indirect. Dans LMC, il n'y a pas d'instruction pour l'adressage indirect, mais avec un code auto-modifiable, c'est possible.

Supposons que vous ayez la liste des pouvoirs mis en œuvre comme suit:

POW_9   DAT 512
POW_8   DAT 256
; ... etc
POW_0   DAT 1

Ensuite, vous feriez une comparaison de l'accumulateur avec POW_9 par:

COMPARE SUB POW_9

L'étiquette nous permet d'y stocker une instruction différente, de sorte que la prochaine fois qu'elle est exécutée, elle l'exécute effectivement:

COMPARE SUB POW_8

Ceci est possible avec la manipulation suivante:

LDA COMPARE
ADD ONE
STA COMPARE

C'est un peu délicat car le code est traité comme des données, ce qui modifie le code. Notez comment le changement SUB POW_9fonctionne réellement comme si vous référeniez un élément dans un tableau et augmentez l'index dans ce tableau.

Vous devez avoir une condition d'arrêt pour ne pas donner au code référence une puissance de 2 qui ne figure pas dans votre DATliste. Pour cela, vous pouvez comparer le code modifié avec un morceau de code fixe (également a SUB, mais qui n'est jamais exécuté) qui fait référence à la puissance la plus faible de 2.