15

除算演算子を持たないプロセッサ (ARM と考えてください) で 2 つの数値のモジュロを見つける単純なマクロを実装する必要があります。繰り返し減算による除算を使用することもできましたが、これが最も効率的であるか、作業が最も簡単であったかはわかりません。

助言がありますか？コードはさらに役に立ちます。この特定のクラスでは SPARC のサブセットを使用しているため、ほとんどの操作は次のようになりますadd r1, r2, rdest。

a mod b == 0この特定の割り当てでは、除算の余りがゼロであることを確認する必要があります。したがって、効率的な実装に向けたヒントや提案は大歓迎です。

4

8 に答える 8

10

あなたが制限されている正確な操作はわかりませんが、疑似コードで次のような長い除算を行うと思います:

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)

これはどれもテストされておらず、おそらくエラーだらけです。

于 2009-06-02T06:57:22.333 に答える
4

考えられるアプローチは 2 つあります。これは宿題なので、それらについて言及し、それらが実現可能かどうか、およびそれらを実装する方法を説明します。

  1. A/B = 2^(log2(A)-log2(b)): 値の対数を求めることができれば、除算を近似することができます。

  2. 2 進除算: 除算を行う前に、10 進除算の方法を学びましたよね? そのため、コンピューターに 2 進数の長除算を行うように教えてください (実際には 2 進数の方が簡単なはずです)。

(編集: #1.、対数除算式を修正)

于 2009-06-02T05:57:53.487 に答える
1

Jweede、あなたの問題を解決する方法がわかりませんでしたが、一見関連性のある投稿を見つけましたhere .

于 2009-06-02T05:47:39.803 に答える
0

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 の上限をより適切に設定できます。

于 2014-02-28T21:25:49.303 に答える
0

アドバイスありがとうございます！

これを実装するために、繰り返し減算アルゴリズムによる単純な除算を使用し始めました。しかし、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
}
于 2009-06-03T01:06:14.100 に答える
0

A/B=Q なので、A=B*Q です。A と B の両方を知っているので、Q が必要です。

ミックスに追加する私のアイデア: 二分探索 Q. おそらく基本ケースとして、Q=0 & Q=1 から始めます。B * Q > A になるまで 2 倍し続けると、2 つの境界 (Q と Q/2) が得られるので、それらの 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 がオーバーフローすることを検出できる必要があります。

于 2009-06-03T02:43:59.630 に答える