Assemblée mod algorithme sur le processeur sans opérateur de division

J'ai besoin de mettre en œuvre une macro simple qui trouve le modulo de deux numéros sur un processeur qui n'est pas un opérateur de division (pensez à BRAS). Je pourrais utiliser la division par soustraction répétée, mais je ne sais pas si c'était la plus efficace ou la plus facile de travailler avec.

Des suggestions? Code serait encore plus utile. Cette classe particulière nous a l'aide d'un sous-ensemble de SPARC, de sorte que la plupart des opérations ressembler à ceci: add r1, r2, rdest.

Cette mission en particulier appels pour vérifier que a mod b == 0 ou que le reste de la division est égal à zéro. Donc tous conseils ou de suggestions sur la mise en œuvre efficace serait la bienvenue.

+1 pour l'auto-étiquetage devoirs, quelque chose que je n'ai pas vu arriver très souvent si loin.

InformationsquelleAutor Jon W | 2009-06-02

Aucune idée de ce exact des opérations, vous êtes limité à, mais je pense que vous feriez division longue, quelque chose comme cela, en pseudo-code:

dividend = abs(dividend)
divisor = abs(divisor)
if divisor == 0,
    barf
remainder = dividend
next_multiple = divisor

do
    multiple = next_multiple
    next_multiple = left_shift(multiple, 1)
while next_multiple <= remainder && next_multiple > multiple

while multiple >= divisor,
    if multiple <= remainder,
        remainder = remainder - multiple
    multiple = right_shift(multiple, 1)

Réellement calculer le quotient (ou au moins de sa valeur absolue), la dernière partie serait quelque chose comme:

quotient = 0
while multiple >= divisor,
    quotient = left_shift(quotient, 1);
    if multiple <= remainder,
        remainder = remainder - multiple
        quotient = quotient + 1
    multiple = right_shift(multiple, 1)

Rien de tout cela est testé, et c'est probablement truffée d'erreurs.

qu'en est-il mystérieux "barf' opération?
Une opération personnalisée, bien sûr. Vos instructions disent quoi faire un diviseur de 0?
Merci! J'ai changé ce code à Python et il semble fonctionner.

InformationsquelleAutor ysth

4

Je pense à deux approches possibles. Parce que c'est les devoirs, je vais juste mentionner et vous permettent de travailler si elles sont réalisables et comment les mettre en œuvre:
1. A/B = 2^(log2(A)-log2(b)): Si vous pouvez obtenir le logarithme des valeurs, vous pouvez rapproche de la division.
2. Binaire Division Longue: Vous avez appris à faire décimal division longue avant que vous pourriez faire de la division de la, droite? Donc, enseignez à votre ordinateur pour faire de la binaire division longue (il devrait en fait être plus facile en binaire).
(edit: corrigé #1., le journal de la division de l'équation)
- Euh, n'est-ce pas que A/B = 10**(log(A)-log(B))?
- Vous avez des suggestions d'approches pour obtenir le quotient, ce que l'OP demande, c'est le reste. D'ailleurs, même à mi-chemin décent approximation de la division à l'aide des journaux exige de la précision en virgule flottante, ce qui est exagéré pour trouver reste entier. @jmucchiello: Vous avez raison, mais la base est la plus probable 2 plutôt que 10, compte tenu de la situation.
- [ +1 pour le marquage des devoirs-vous ] Certainement examiner vous-même comment le faire à plusieurs chiffres de la division en "papier-crayon" (oh le choc des arbres morts!) puis de mettre en œuvre la même chose dans votre programme. ps. Les points de Bonus si vous aussi faites de même pour les racines carrées 😉
- jmucchiello: Euh, oui. Bien que la base 10 n'était pas censé être implicite... je vais corriger.
- sykora: Oui, c'est les devoirs, je n'ai donc pas donner l'intégralité de la réponse (et ne doit pas non plus quelqu'un d'autre). Je pense que la plupart d'entre nous de savoir comment aller de l'quotient pour le reste ici et qu'il est assez facile. Re, Journal de rapprochement: binaire journaux d'assez près pour approxmation peut être extraite à partir des entiers sans FP (via de Gauche Quarts). Je le sais parce que je l'ai fait il y a 35 ans avec des demi-additionneur circuits. Vous remarquerez que quelqu'un ici a déjà compris cela ainsi.
- winden: autant que je me souvienne, il y a une très belle convergence pour SQRT qui ne nécessite pas de division (autre que par 2, ce qui est facilement émulé). Donc, je pense que c'est effectivement plus que la division.
InformationsquelleAutor RBarryYoung
3

Cela ne veut pas répondre directement à votre question, mais est un cas intéressant néanmoins. Si le nombre est modulo avais par une puissance de deux, l'opération peut être effectuée que
```
x % 2^n = x & (2^n - 1)
```
Qui utilise une seule ET opération, qui généralement est un un ou deux cycle de fonctionnement.

Plus d'informations Sur Wikipedia

InformationsquelleAutor mdec
3

Semble que la soustraction (ou en ajoutant si a est négatif) par b jusqu'à ce que vous frappez ou de la croix-0 serait une mise en œuvre simple mais presque certainement pas le plus efficace.
- Je suis d'accord. Cela s'appelle la Division par soustraction répétée.
InformationsquelleAutor JP Alioto
1

Jweede, je n'avais aucune idée de comment le résoudre votre problème, mais j'ai trouvé un semblant pertinents post ici.
- c'est un bon résumé des optimisations pour le mod op. Je vais certainement tuck ce site de suite si je dois écrire un compilateur pour la classe. Merci!!
InformationsquelleAutor Tim Stewart

A/B=Q, donc A=B*q: Nous savons que les deux A & B, nous voulons Q.

Mon idée à ajouter au mélange:
Recherche binaire Q. Commencer avec Q=0 & Q=1, peut-être que la base de cas. Continuez à doubler jusqu'à ce que B * Q > A, et puis vous avez deux bornes (Q et Q/2), afin de trouver la bonne Q entre les deux de ces. O(log(A/B)), mais un peu plus compliqué à mettre en œuvre:

#include <stdio.h>
#include <limits.h>
#include <time.h>

//Signs were too much work.
//A helper for signs is easy from this func, too.
unsigned int div(unsigned int n, unsigned int d)
{
    unsigned int q_top, q_bottom, q_mid;
    if(d == 0)
    {
        //Ouch
        return 0;
    }

    q_top = 1;
    while(q_top * d < n && q_top < (1 << ((sizeof(unsigned int) << 3) - 1)))
    {
        q_top <<= 1;
    }
    if(q_top * d < n)
    {
        q_bottom = q_top;
        q_top = INT_MAX;
    }
    else if(q_top * d == n)
    {
        //Lucky.
        return q_top;
    }
    else
    {
        q_bottom = q_top >> 1;
    }

    while(q_top != q_bottom)
    {
        q_mid = q_bottom + ((q_top - q_bottom) >> 1);
        if(q_mid == q_bottom)
            break;

        if(d * q_mid == n)
            return q_mid;
        if(d * q_mid > n)
            q_top = q_mid;
        else
            q_bottom = q_mid;
    }
    return q_bottom;
}

int single_test(int n, int d)
{
    int a = div(n, d);
    printf("Single test: %u /%u = %u\n", n, d, n /d);
    printf(" --> %u\n", a);
    printf(" --> %s\n", a == n /d ? "PASSED" : "\x1b[1;31mFAILED\x1b[0m");
}

int main()
{
    unsigned int checked = 0;
    unsigned int n, d, a;

    single_test(1389797028, 347449257);
    single_test(887858028, 443929014);
    single_test(15, 5);
    single_test(16, 4);
    single_test(17, 4);
    single_test(0xFFFFFFFF, 1);

    srand(time(NULL));

    while(1)
    {
        n = rand();
        d = rand();

        if(d == 0)
            continue;

        a = div(n, d);
        if(n /d == a)
            ++checked;
        else
        {
            printf("\n");
            printf("DIVISION FAILED.\n");
            printf("%u /%u = %u, but we got %u.\n", n, d, n /d, a);
        }

        if((checked & 0xFFFF) == 0)
        {
            printf("\r\x1b[2K%u checked.", checked);
            fflush(stdout);
        }
    }

    return 0;
}

En outre, vous pouvez également faire une itération sur les bits, le réglage de chacun à 1. Si B * Q <= A est vrai, conserver le peu que 1, sinon zéro il. Procéder MSB->LSB. (Vous aurez besoin pour être en mesure de détecter B*Q débordement, cependant.

InformationsquelleAutor Thanatos

0

Merci pour les conseils tout!

J'ai commencé à l'aide d'une simple division par soustraction répétée de l'algorithme à mettre en œuvre. Mais comme l'a souligné ysth, il y a un moyen beaucoup plus facile. Voici le premier algorithme:
```
        .macro mod a, b, r
        mov a, r
divlp:  sub r, b, r
        cmp r, b
        bge divlp
        .endmacro
```
Cela ressemble à:
```
mod(a, b){
   int r = a
   while(r >= b){
      r = r - b
   }
   return r
}
```
- Oui, il y a un moyen plus efficace; voir ma réponse. Il peut ressembler à beaucoup plus de code, mais chaque boucle s'exécute seulement à plus de 32 ou 64 fois, au contraire, une boucle qui peut exécuter un bazillion fois.
- Je ne veux certainement pas à boucle une foule de fois. 🙁
InformationsquelleAutor Jon W
0

mod peut être calculée peu à peu:
```
int r = 0;
int q = 0;
for (int i = sizeof(n) * 8 - 1; i >= 0; --i) {
  r <<= 1;
  r |= (n >> i) & 1;
  if (r > d) {
    r -= d;
    q |= 1 << i;
  }
}
return r;
```
Qui vous donne le reste, q serait le quotient.
Si vous avez bsrl les instructions, vous pouvez définir un mieux élevé lié pour moi, étant donné que vous pouvez commencer à le bit le plus significatif seulement.

InformationsquelleAutor Olivier

Vous devez vous connecter pour publier un commentaire.