Подтвердить что ты не робот

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 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)

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Дополнительная информация В Википедии

Ответ 4

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

Ответ 5

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

Ответ 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
}

Ответ 7

A/B = Q, поэтому A = B * Q. Мы знаем как A, так и B, мы хотим Q.

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

Ответ 8

mod может быть вычислен поэтапно:

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;

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