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

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

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

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

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

(редактирование: исправлено # 1., Логарифмическое уравнение деления)

Answer 3

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

Answer 4

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

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

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

Больше информации В Википедии

Answer 5

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

Answer 6

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

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, поскольку вы можете начинать только с самого старшего бита.

Answer 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 - true, оставьте бит равным 1, в противном случае установите его на ноль. Продолжайте MSB-> LSB. (Однако вам нужно будет обнаружить его, однако B * Q переполнится.

Answer 8

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

Я начал использовать простое деление на алгоритм повторного вычитания, чтобы реализовать это. Но, как указывает 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
}