Algoritmo de modulación de ensamblaje en procesador sin operador de división

Question

Necesito implementar una macro simple que encuentre el módulo de dos números en un procesador que no tiene un operador de división (piense en ARM). Podría usar división por sustracción repetida, pero no sé si fue la más eficiente o más fácil de trabajar.

¿Alguna sugerencia? El código sería aún más útil. Esta clase particular nos tiene usando un subconjunto de SPARC, por lo que la mayoría de las operaciones se ven así: add r1, r2, rdest.

Esta asignación particular requiere la verificación de que a mod b == 0 o que el resto de la división es cero. Entonces, cualquier sugerencia o sugerencia para una implementación eficiente sería bienvenida.

Answer 1

Ni idea de qué operaciones exacto que está limitado a, pero yo creo que haría una división larga, algo como esto, en pseudo-código:

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) 

Para calcular realmente el cociente (o por lo menos su valor absoluto), la última parte sería algo así como:

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

Nada de esto se prueba, y probablemente está plagado de errores.

Answer 2

Jweede, no tenía idea de cómo resolver su problema, pero encontré una publicación aparentemente relevante here.

Answer 3

Puedo pensar en dos posibles enfoques. Debido a que esta es la tarea voy a mencionar sólo ellos y le permiten trabajar si son factibles y cómo implementarlas:

1. A/B = 2^(log2 (A) -log2 (b)): Si puede obtener el logaritmo de los valores, puede aproximarse bastante a la división.

2. División larga binaria: Aprendió cómo hacer división larga decimal antes de poder hacer la división, ¿verdad? Así que enséñele a su computadora a hacer divisiones largas binarias (en realidad debería ser más fácil en binario).

(edit:. Corregidas # 1, la ecuación de la división de registro)

Answer 4

Esto no responde a su pregunta directamente, sino que es un caso interesante, no obstante. Si el número está siendo modulo'd por una potencia de dos la operación se puede realizar como

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

que utiliza una sola operación AND, que generalmente es una operación de uno o dos ciclos.

Más información At Wikipedia

Answer 5

parece que restar (o añadir si a es negativo) por B hasta llegar a cruzar o 0 sería una implementación sencilla aunque muy probablemente no es el más eficiente.

Answer 6

Gracias por el consejo de todos!

Comencé a usar una división simple mediante un algoritmo de resta repetido para implementar esto. Pero como se señala por ysth, hay una manera mucho más fácil.Aquí está el primer algoritmo:

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

Esto se parece mucho a:

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

Answer 7

A/B = Q, por lo tanto, A = B * Q. Sabemos que tanto A como B &, queremos P.

Mi idea para agregar a la mezcla: binario de búsqueda P. inicio con Q = 0 & Q = 1, tal vez como casos base. Sigue doblando hasta B * Q> A, y luego tienes dos límites (Q y Q/2), así que busca la Q correcta entre los dos. O (log (A/B)), pero un poco más complicado de implementar:

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

Además, también se pueden repetir los bits, el establecimiento de cada uno de ellos a 1. Si B * Q = < A es verdadero, mantenga el bit como 1, de lo contrario, ciérrelo. Continuar MSB-> LSB. (Tendrá que ser capaz de detectarlo B * Q se desbordará, sin embargo

Answer 8

mod puede calcularse 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; 

que le da el resto, q sería el cociente Si tiene instrucciones bsrl, puede establecer un límite alto mejor para i, ya que puede comenzar solo en el bit más significativo.