4

MIPSアセンブリを使用して整数の平方根を正確に見つけるにはどうすればよいですか?

4

7 に答える 7

9

この質問に提出されたようなアルゴリズムを使用して、必要に応じて適応させることができます。MIPS に入る前に、C での実装を見てみましょう。

//Function to compute sqroot(n)
int sqroot(int n) {
        int x = n;
        for (int i = 0; i < (n/2); i++)
             x = (x + n / x) / 2;

        return x;
}

このsqroot(n)関数は、 の平方根の床に相当する整数を計算しnます。したがって、呼び出したsqroot(225)場合、予想どおり 15が返されますがsqroot(15)、3.87298 ではなく 3 が返されます。

C コードから、MIPS コードがどのようになるかを概説できます。

In calling function:
    Load the number to be squared into $a0
    jal root

root:
    Initialize $t0 = n, $t1 = i = 0, $t2 = x = n = $a0, $t3 = n/2

Loop:
    Divide n/x
    Add x to n/x
    Divide (x + n/x) by 2
    Check if $t1 < $t3
    If it is, branch back to loop
    Else, move x into return register $v0

ご注意ください：

  1. 必要に応じて、必ずスタックをプッシュおよびポップしてください。簡単にするためにそれを省略しました。
  2. 2 の累乗で割る場合は、srl 命令を使用できます。
  3. MIPS 命令の説明と追加情報については、ここをクリックしてください。
于 2013-07-26T06:06:07.560 に答える
3

MIPS ではありませんが、それでもアセンブリです。私が見つけた基本的なアルゴリズムは、最初の n 個の奇数の合計 = n^2 という事実に基づいていました。

したがって、プロセスを逆にして、平方根を取りたい数値から減算することでそれを利用すると、ループスルーして正確な答えまたは近似値を取得できます。完全ではない正方形のルート + 1 だと思います。

ループする回数は n であり、これは平方根です。

お役に立てれば。

   mov eax, 9513135         ; eax = number to take square root of
    mov ebx, eax            ; make a copy of eax in ebx


    loopIt :
        sub ebx, count      ; count starts as 1, 3, 5, 7, 9
        inc count           ; count = even
        inc count           ; count = odd
        inc sqrt            ; gives sqrt value
        mov eax, sqrt
        cmp ebx, 0
        js timetoReturn     ; return value if signed num, aka goes over zero
        jnz loopIt


    timetoReturn :
        mov reg, eax            ; just outputting the value
于 2013-12-06T21:40:45.757 に答える
1

このアルゴリズムを試すと、数値の平方根以下の整数が得られます。

の平方根が必要だとしますn。次に、次の計算を繰り返します。

x = (x + n/x) / 2

開始を選択x = nし、x の変化が止まるまで繰り返します。

于 2013-07-25T21:09:35.993 に答える
0

C で正の整数の平方根の下限を計算するための、理解しやすいアルゴリズムを次に示します。

int approx_sqrt(int x) {
    int result;
    for (int partialSum = 0, oddNum = 1; partialSum < x; partialSum += oddNum, oddNum +=2) result++;
    return result;
}

少し異なる方法で、okstoryの回答と同じ原則に依存しています。

理論: partialSum がオペランドより小さい限り、徐々に増加する奇数が partialSum に追加されます。結果は、partialSum を生成するために合計された奇数の数に等しくなります。

于 2015-03-02T03:31:12.060 に答える
0

mips で整数の平方根を計算する場合は、最初に整数を浮動小数点に変換する必要があります。平方根を取りたい数値が $t1 に格納されていると仮定すると、浮動小数点への変換は次のようになります

mtc1 $t1, $f1
cvt.s.w $f1, $f1

これで、sqrt.s 関数を使用して平方根を計算できます。

sqrt.s $f1,$f1

したがって、$f1 は $t1 に格納された整数の平方根を保持します。

于 2021-03-31T17:52:30.550 に答える