c - 足し算・引き算だけでモジュロ関数を書く

Question

MIPS浮動小数点計算 IE モジュロ、除算、乗算を使用できないライブラリを作成しています。

私は除算と乗算の関数を C で書き、そのコードを に翻訳しましたMIPS。

Cただし、加算または減算のみを使用してモジュロを計算する関数を作成する方法がわかりません。

加算と減算のみを使用してモジュロを計算する関数を作成するにはどうすればよいですか?

Answer 1

注:次のコード スニペットは、両方のオペランドが正の場合にのみ機能します。x % y一方または両方のオペランドが負の場合の結果は言語やプラットフォームによって異なるため、負の値の処理は省略しました。一般に、計算abs(x) % abs(y)してから、結果に対して何らかの変換を実行できます。

---

x % y加算と減算のみを使用して計算する最も簡単な方法yは、残りの値が 未満になるまで繰り返し減算することyです。

/* Compute x mod y naively. */
int mod_basic(int x, int y) {
    int result = x;   
    while (result >= y)
        result -= y;

    return result;
}

ただし、この方法はかなり非効率的です。より複雑ではあるがより高速な方法は、2 進数の長除算を使用することです。これは通常の長除算と似ていますが、バイナリでは各ステップの結果がの代わりに0またはになります。BLDで計算するための基本的なアプローチは次のようになります。10..9x % y

/* Compute x mod y using binary long division. */
int mod_bld(int x, int y)
{
    int modulus = x, divisor = y;

    while (divisor <= modulus && divisor <= INT_MAX/2)
        divisor <<= 1;

    while (modulus >= y) {
        while (divisor > modulus)
            divisor >>= 1;
        modulus -= divisor;
    }

    return modulus;
}

上記の 1 つの落とし穴: はwhenでのdivisor <= INT_MAX/2オーバーフローを停止するために必要です。divisor <<= 1x > MAX_INT/2

さらにdivmod、1 回の計算で商とモジュラスの両方が得られる は、ほとんど同じように見えます。

/* Compute divmod(x, y) using binary long division. */
void divmod(int x, int y, int *div, int *mod) {
    int quotient = 0, modulus = x, divisor = y;

    while (divisor <= modulus && divisor <= INT_MAX/2)
        divisor <<= 1;

    while (modulus >= y) {
        while (divisor > modulus) {
            divisor >>= 1;
            quotient <<= 1;
        }

        modulus -= divisor;
        quotient++;
    }

    while (divisor != y) {
        quotient <<= 1;
        divisor >>= 1;
    }

    *div = quotient;
    *mod = modulus;
}

y最後に、が 2 のべき乗である場合、ごまかすことができることに注意してください。この場合x % yはちょうどx & (y - 1)です。

Answer 2

バイナリの長除算は問題を解決できます。

16 / 3 の例 (バイナリ 10000 ₂ / 11 ₂ ):

 10000 | Quotient
 1     | 0         // 1 < 11 (append 0 to quotient, no effect)
 10    | 0         // 10 < 11 (append 0 to quotient, no effect)
 100   | 1         // 100 > 11, append 1 to quotient
- 11   | 
----   |
   1   |
   10  | 10        // 10 < 11, append 0 to quotient
   100 | 101       // 100 > 11, append 1 to quotient
 -  11 | 101
 ----- |
     1 | 101       // Quotient = 101, Remainder = 1

結果は 2 進数であるため、商に 0 または 1 を追加するタイミングがすぐにわかります。前の計算のフラグメントが除数より小さい場合は、0 を追加します。フラグメントが除数よりも大きい場合は、1 を追加します。

Answer 3

私は除算と乗算の関数を C で書き、そのコードを MIPS に変換しました。

あなたが書いた除算関数は、アルゴリズムの終わりまでに係数 x%N をすでに計算している可能性があると思います。このため、x86 のような高レベルのアーキテクチャでは、x/N と x%N の両方を同時に返すアセンブリ命令 (divl など) が用意されています。多くの場合、一方の計算に使用するアルゴリズムが何であれ、自動的に他方のアルゴリズムが得られるため、2 羽の鳥を殺すことができます。両方が同時に必要な場合は、1 つの石で。

また、除算関数と乗算関数を記述した場合は、モジュラスを計算するために必要なものがすべて揃っていますx%N == x - N*( x/N )。したがって、最悪の場合、足し算と引き算のみを使用して x%N を計算したい場合、および足し算と引き算のみを使用して乗算と除算を行う方法を知っている場合は、上記の式を使用して x%N を取得できます。そうは言っても、すでに提案されているように、たとえば長い除算を介して、これよりもうまくいく可能性があります。

Answer 4

上記の実装ほど効率的ではありませんが、インタビュー中にこの質問をされた場合に使用できる JavaScript の再帰的な解決策を次に示します。これは、負数と小数の入力もサポートしていることに注意してください。

var modulo = function(x, y) {
    y = Math.abs(y);
    return (x < y) ? x : modulo(x - y, y);
};

console.log(modulo(12, 5)); //2
console.log(modulo(10, 2)); //0
console.log(modulo(4, 10)); //4
console.log(modulo(4, 2.4)); //1.6
console.log(modulo(-1, 10)); //-1
console.log(modulo(10, -3)); //1
console.log(modulo(10, -4)); //2
console.log(modulo(10, -3)); //1