Algorytm modulacji zespołu na procesorze bez operatora podziału

Question

Potrzebuję zaimplementować proste makro, które znajdzie modulo dwóch liczb na procesorze, który nie ma operatora podziału (myślę, że ARM). Mógłbym użyć podziału przez wielokrotne odejmowanie, ale nie wiem, czy był to najskuteczniejszy lub najłatwiejszy w obsłudze.

Wszelkie sugestie? Kod byłby jeszcze bardziej pomocny. W tej konkretnej klasie używamy podzbioru SPARC, więc większość operacji wygląda następująco: add r1, r2, rdest.

To konkretne zadanie wymaga sprawdzenia, czy a mod b == 0 lub pozostałej części podziału wynosi zero. Tak więc wszelkie wskazówki i sugestie dotyczące skutecznego wdrożenia byłyby mile widziane.

Answer 1

Nie mam pojęcia, jakie operacje dokładny jesteś ograniczony, ale myślałem, że zrobisz długą podział, coś takiego, w pseudo-kod:

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) 

Aby właściwie obliczyć iloraz (lub przynajmniej jego wartość bezwzględna), ostatnia część będzie coś takiego:

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

Nic z tego nie jest testowany i jest prawdopodobnie usiane błędami.

Answer 2

Jweede, nie miałem pojęcia, jak rozwiązać twój problem, ale znalazłem pozornie relevent post here.

Answer 3

Mogę wymyślić dwa możliwe podejścia. Ponieważ jest to praca domowa będzie po prostu wymienić je i pozwala działać, jeżeli są one wykonalne i jak je realizować:

1. A/B = 2^(log2 (A) -log2 (b)): Jeśli można uzyskać logarytm wartości, można dokładnie zbliżyć podział.

2. Binarna długa dywizja: Nauczyłeś się, jak robić dziesiętny długi podział, zanim mógłbyś dokonać podziału, prawda? Więc naucz twój komputer, aby wykonywał długie dzielenie binarne (w rzeczywistości powinno być łatwiejsze w systemie binarnym).

(edit:. Poprawione nr 1, równanie podział log)

Answer 4

To nie jest odpowiedź na swoje pytanie bezpośrednio, ale to ciekawy przypadek jednak. Jeśli numer jest modulo'd przez potęgi dwójki operacja może być wykonywana jako

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

który wykorzystuje pojedynczą i obsługi, która zwykle jest operacją jeden lub dwa cykl.

Więcej informacji At Wikipedia

Answer 5

Wygląda odjęcie (lub dodanie jeśli jest ujemna) przez b, aż trafisz lub przejechać 0 byłaby łatwa implementacja choć prawie na pewno nie najbardziej skuteczny.

Answer 6

Dzięki za porady wszystkie!

Zacząłem używać prostego podziału przez powtarzany algorytm odejmowania, aby to zaimplementować. Ale jak podkreślił Ysth, jest o wiele łatwiejszy sposób.Oto pierwszy algorytm:

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

To przypomina:

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

Answer 7

A/B = P, więc A = B * P. Wiemy, że zarówno & B, chcemy Q.

Mój pomysł, aby dodać do mieszanki: Binary wyszukiwania Q. Rozpocznij Q = 0 & Q = 1, może jako przypadkach bazowych. Podwajaj aż do B * Q> A, a następnie masz dwa granice (Q i Q/2), więc znajdź poprawną Q pomiędzy tymi dwoma. O (log (A/B)), ale nieco trudniejsze do wdrożenia:

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

Dodatkowo, można również iterację bitów ustawienie każdy do 1. Jeżeli B * P < = A jest prawdą trzymaj bit jako 1, w przeciwnym razie zeruj go. Kontynuuj MSB-> LSB. (Musisz być w stanie wykryć B * Q wyleje jednak

Answer 8

mod można obliczyć po trochu..

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; 

który daje resztę, q będzie ilorazem Jeśli posiadasz instrukcję bsrl, możesz ustawić wyższą granicę dla i, ponieważ możesz zacząć od najbardziej znaczącego bitu.