Algoritmo di assemblaggio mod sul processore senza operatore di divisione

Question

Ho bisogno di implementare una semplice macro che trovi il modulo di due numeri su un processore che non ha un operatore di divisione (pensa ARM). Potrei usare la divisione per sottrazione ripetuta, ma non so se questo è stato il più efficiente o più facile da usare.

Qualche suggerimento? Il codice sarebbe ancora più utile. Questa particolare classe ci ha utilizzato un sottoinsieme di SPARC, quindi la maggior parte delle operazioni ha questo aspetto: add r1, r2, rdest.

Questo particolare incarico richiede di verificare che a mod b == 0 o che il resto della divisione sia zero. Quindi qualsiasi suggerimento o suggerimento per una implementazione efficiente sarebbe il benvenuto.

Answer 1

Non ho idea di quali operazioni esatta si sono limitati a, ma mi piacerebbe che tu faresti lunga divisione, qualcosa di simile, in pseudo-codice:

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) 

Per calcolare realmente il quoziente (o almeno il suo valore assoluto), l'ultima parte sarebbe qualcosa di simile:

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

Niente di tutto questo è testato, e probabilmente è pieno di errori.

Answer 2

Jweede, non avevo idea di come risolvere il problema ma ho trovato un post apparentemente pertinente here.

Answer 3

Posso pensare a due possibili approcci. Perché questo è compito Mi limito a citare loro e consentono di lavorare se sono fattibili e modalità di attuazione:

1. A/B = 2^(log2 (A) -log2 (b)): Se si può ottenere il logaritmo dei valori, è possibile approssimare strettamente la divisione.

2. Divisione binaria lunga: hai imparato come eseguire la divisione decimale lunga prima di poter eseguire la divisione, giusto? Quindi insegna al tuo computer a fare una lunga divisione binaria (in realtà dovrebbe essere più semplice in binario).

(edit:. 1 corretto #, la divisione equazione log)

Answer 4

Questo non risponde alla tua domanda direttamente, ma è un caso interessante comunque. Se il numero è modulo'd da una potenza di due l'operazione può essere eseguita come

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

che utilizza una singola operazione AND, che solito è un'operazione una o due ciclo.

Maggiori informazioni At Wikipedia

Answer 5

Sembra come sottraendo (o l'aggiunta di se a è negativo) da b fino a colpire o attraversare 0 sarebbe una facile implementazione anche se quasi certamente non il più efficiente.

Answer 6

Grazie per il consiglio a tutti!

Ho iniziato a utilizzare una semplice divisione mediante un algoritmo di sottrazione ripetuto per implementarlo. Ma come sottolineato da ysth, c'è un modo molto più semplice.Ecco il primo algoritmo:

 .macro mod a, b, r 
     mov a, r 
divlp: sub r, b, r 
     cmp r, b 
     bge divlp 
     .endmacro 

Questo assomiglia da vicino:

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

Answer 7

A/B = Q, quindi A = B * Q. Sappiamo entrambi A & B, vogliamo Q.

La mia idea di aggiungere al mix: binario di ricerca D. Inizia con Q = 0 & Q = 1, forse come casi di base. Continua a raddoppiare fino a B * Q> A, e poi hai due limiti (Q e Q/2), quindi trova il Q corretto tra i due. O (log (A/B)), ma un po 'più complicato da implementare:

#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; 
} 

Inoltre, si possono anche iterano attraverso i bit, impostando ciascuno a 1. Se B * Q < = A è vero, mantieni il bit come 1, altrimenti azzeralo. Procedere MSB-> LSB. (Avrete bisogno di essere in grado di rilevarlo B * Q traboccherà, tuttavia

Answer 8

mod può essere calcolato a poco a poco:..

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; 

Che ti dà il resto, q sarebbe il quoziente Se si dispone dell'istruzione bsrl, è possibile impostare un limite superiore migliore per i, poiché è possibile iniziare solo dal bit più significativo