Алгоритм модуляции сборки на процессоре без оператора деления

Question

Мне нужно реализовать простой макрос, который находит по модулю два числа на процессоре, который не имеет оператора разделения (думаю, ARM). Я мог бы использовать деление путем повторного вычитания, но я не знаю, было ли это наиболее эффективным или простым в работе.

Любые предложения? Код будет еще более полезным. В этом конкретном классе мы используем подмножество SPARC, поэтому большинство операций выглядят так: add r1, r2, rdest.

Это конкретное задание требует проверки того, что a mod b == 0 или что остаток деления равен нулю. Поэтому любые намеки или предложения относительно эффективной реализации были бы наиболее желанными.

Answer 1

Не знаю, какие именно операции вы ограничены, но я думаю, что вы могли бы сделать длинное деление, что-то вроде этого, в псевдокоде:

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) 

Чтобы действительно вычислить фактор (или крайней мере, его абсолютное значение), последняя часть будет что-то вроде:

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

Ничего из этого не тестируется, и это, вероятно, пронизана с ошибками.

Answer 2

Jweede, я понятия не имел, как решить вашу проблему, но я нашел по-видимому уместное сообщение here.

Answer 3

Я могу думать о двух возможных подходах. Поскольку это домашнее задание, я просто упомянуть о них и позволяют работать, если они выполнимы и как их реализовать:

1. A/B = 2^(log2 (A) -log2 (б)): Если вы может получить логарифм значений, вы можете близко аппроксимировать деление.

2. Двоичный длинный дивизион: вы узнали, как сделать десятичное деление, прежде чем вы сможете сделать деление, не так ли? Поэтому научите свой компьютер делать двоичное длинное деление (на самом деле это должно быть проще в двоичном виде).

(редактирование:. Исправлен # 1, уравнение деление журнала)

Answer 4

Это не ответ на ваш вопрос прямо, но это интересный случай, тем не менее. Если число в настоящее время modulo'd от степени два операция может быть выполнена, как

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

, который использует одну и операцию, которая обычно операция выполняется один или два цикла.

Дополнительная информация At Wikipedia

Answer 5

Кажется, вычитая (или добавления, если отрицательна) на Ь, пока вы не нажмете или пересекающие 0 будет легкой реализации, хотя почти наверняка не является самым эффективным.

Answer 6

Спасибо за советы!

Я начал использовать простое деление с помощью алгоритма повторного вычитания для его реализации. Но, как указано ysth, есть намного более простой способ.Вот первый алгоритм:

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

Это очень напоминает:

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

Answer 7

A/B = Q, следовательно, A = B * Q. Мы знаем, как A & B, мы хотим Q.

Моя идея добавить к смеси: Двоичный поиск Q. Начните с Q = 0 & Q = 1, возможно, в качестве базовых случаев. Продолжайте удвоение до тех пор, пока B * Q> A, и тогда у вас есть две границы (Q и Q/2), так что найдите правильный Q между ними. O (журнал (A/B)), но немного сложнее реализовать:

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

Кроме того, вы также можете перебирать биты, установив каждый 1. Если B * Q < = A верно, держите бит как 1, иначе обнулите его. Выполните MSB-> LSB. (Вы должны быть в состоянии обнаружить его B * Q будет переполнение, однако

Answer 8

мод может быть вычислена по крупицам:..

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; 

Это дает вам остаток, д будет фактор Если у вас есть инструкция bsrl, вы можете установить лучшую границу для i, так как вы можете начинать только с самого значительного бита.