Algorithme de mod d'assemblage sur processeur sans opérateur de division

Question

Je dois implémenter une macro simple qui trouve le modulo de deux nombres sur un processeur qui n'a pas d'opérateur de division (pensez à ARM). Je pourrais utiliser la division par soustraction répétée, mais je ne sais pas si c'était la méthode la plus efficace ou la plus facile à utiliser.

Des suggestions? Le code serait encore plus utile. Cette classe particulière nous utilise un sous-ensemble de SPARC, donc la plupart des opérations ressemblent à ceci: add r1, r2, rdest.

Cette affectation particulière nécessite de vérifier que a mod b == 0 ou que le reste de la division est zéro. Donc, des conseils ou des suggestions pour une mise en œuvre efficace seraient les bienvenus.

Answer 1

Aucune idée de ce que les opérations exacte que vous êtes limité à, mais je pense que vous feriez division longue, quelque chose comme ça, 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) 

Pour calculer réellement le quotient (ou moins 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 il est probablement truffé d'erreurs.

Answer 2

Jweede, je n'avais aucune idée de la façon de résoudre votre problème mais j'ai trouvé un message apparemment pertinent here.

Answer 3

Je peux penser à deux approches possibles. Parce que c'est des devoirs que je me contenterai de les 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 peut obtenir le logarithme des valeurs, vous pouvez approcher de près la division. Longue division binaire: Vous avez appris à faire la division longue décimale avant de pouvoir faire la division, n'est-ce pas? Alors apprenez à votre ordinateur à faire une longue division binaire (il devrait en fait être plus facile en binaire).

(edit:. Corrigée # 1, l'équation de la division log)

Answer 4

Cela ne répond pas, mais directement à votre question est un cas intéressant néanmoins. Si le nombre est modulo'd par une puissance de deux l'opération peut être réalisée comme

x % 2^n = x & (2^n - 1) 

qui utilise une seule opération ET qui habituellement est une ou deux opérations de cycle.

Plus d'informations At Wikipedia

Answer 5

On dirait que la soustraction (ou en ajoutant si un est négatif) par b jusqu'à ce que vous touchez ou traverser 0 serait une mise en œuvre facile mais certainement pas le plus efficace.

Answer 6

Merci pour le conseil tous! J'ai commencé à utiliser une simple division par l'algorithme de soustraction répétée pour l'implémenter. Mais comme indiqué par 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 

Cette étroite ressemble:

mod(a, b){ 
    int r = a 
    while(r >= b){ 
     r = r - b 
    } 
    return r 
} 

Answer 7

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

Mon idée d'ajouter au mélange: recherche binaire Q. Démarrer avec Q = 0 & Q = 1, peut-être des cas de base. Continuez à doubler jusqu'à ce que B * Q> A, et alors vous avez deux bornes (Q et Q/2), alors trouvez le bon Q entre les deux. 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; 
} 

De plus, vous pouvez également itérer les bits, les paramètres un à 1. Si B * Q < = A est vrai, garder le bit comme 1, sinon le remettre à zéro. Passez MSB-> LSB. (Vous devez être en mesure de détecter B * Q va déborder, mais

Answer 8

mod peut être peu calculé par bit:..

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; 

Cela vous donne le reste, q serait le quotient Si vous avez l'instruction bsrl, vous pouvez définir une meilleure borne supérieure pour i, puisque vous pouvez commencer au bit le plus significatif seulement