algoritmo Asamblea mod en el procesador sin operador de división

Question

Necesito aplicar una macro simple que se encuentra el módulo de dos números en un procesador que no tenga un operador de división (piensa ARM). Podría utilizar la división por resta repetida, pero no sé si esto era la más eficiente o más fácil de trabajar.

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

Esta asignación particular llama para comprobar que a mod b == 0 o que el resto de la división es cero. Por lo que cualquier consejos o sugerencias hacia una implementación eficiente sería muy bienvenida.

Answer 1

Ni idea de qué operaciones exacto que está limitado a, pero yo pensaría que haría la 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 al menos su valor absoluto), la última parte sería algo 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

No 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 ponerlas en práctica:

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

2. Long Division binaria: Usted aprendió cómo hacer la división larga decimal antes de poder hacer una división, ¿verdad? Así que enseñar a su computadora para hacer la división larga binario (que en realidad debería ser más fácil en binario).

(edit:. Corregida # 1, la ecuación de división log)

Answer 3

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 En Wikipedia

Answer 4

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 5

Jweede, no tenía ni idea de cómo resolver su problema, pero he encontrado un puesto relevante en apariencia aquí .

Answer 6

A / B = Q, por lo tanto, A = B * Q. Sabemos que tanto A y B, que quieren Q.

Mi idea para agregar a la mezcla: La búsqueda binaria de inicio P. con Q = 0 y Q = 1, tal vez como casos base. Seguir doblando hasta que B * Q> A, y entonces usted tiene dos límites (Q y Q / 2), por lo que encontrar la Q correcta entre los dos de ellos. 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 puede iterar a través de los bits, el establecimiento de cada uno de ellos a 1. Si B * Q <= A es verdad, mantener la broca 1, de lo contrario cero él. Proceder MSB-> LSB. (Tendrá que ser capaz de detectarlo B * Q se desbordará, sin embargo.

Answer 7

Gracias por el consejo de todo!

he empezado a utilizar una simple división por el algoritmo de resta repetida para implementar esto. Sin embargo, como ha señalado 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 8

mod puede ser calculada 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;

Eso le da el resto, q sería el cociente. Si usted tiene instrucción BSRL, se puede establecer una mejor alta cota para i, ya que se puede empezar por el bit más significativo solamente.