2

クラス用に構築したプロセッサで実行する非常に単純なプログラムを作成しています。乗算または除算する機能はありません。ただし、ループ制御のための加算、減算、および、または、および分岐 (MIPS に精通している場合は等号分岐など) はサポートされていました。その上で実行するきちんとしたプログラムは、ある種の x^n プログラムになると考えていました。もちろん、これらの数値はハードコーディングする必要がありますが、プロセッサの制限を考えると現実的でしょうか?

指数の加算のみの計算はありますか? ありがとう。

4

6 に答える 6

7

小さい整数の場合、なぜですか?

まず、繰り返し加算を使用して乗算を実装します。次に、繰り返し乗算を使用して pow() を実装します。遅くなりますが、うまくいきます。

Exponentiation by Squaringと呼ばれる、より高速な累乗アルゴリズムがあります。ただし、高速な乗算がないことを考えると、それだけの価値があるかどうかはわかりません。まず、高速な乗算アルゴリズムの実装に取り​​組みたいと思うかもしれません。

于 2009-12-13T23:35:11.593 に答える
6

cスタイルの構文でのdmazzoniの応答に沿って：

int mulitply(int x, int y)
{
    int product;

    for (int i = 0; i<y; i++)
       product += x;

    return product;
}

int power(int x, int exponent)
{
    int result = 1;

    for (int i = 0; i < exponent; i++)
        result = multiply(result, x);

    return result;
}
于 2009-12-13T23:40:31.300 に答える
2

Aequitarum のソリューションと似ていますが、べき乗には 2 乗を繰り返し、乗算には 2 倍を繰り返します。大きなx、yの場合は高速になるはずです:

int multiply(int x, int y) {
  int product = 0;
  int bitmask = 1;

  while (y >= bitmask) {
    if (y & bitmask) product += x;
    x += x;
    bitmask += bitmask;
  }
  return product;
}

int power(int x, int exponent)
{
  int result = 1;
  int bitmask = 1;

  while (exponent >= bitmask) {
    if (exponent & bitmask) result = multiply(result, x);
    x = multiply(x, x);
    bitmask += bitmask;
  }
  return result;
}
于 2009-12-14T07:52:32.650 に答える
0

とてもリアルです。プロセッサに、乗算や除算などの高度な演算を実行できるALUがなかったのはそれほど昔のことではありません。

乗算は通常、シフトと加算を使用して行われます。いくつかの疑似アセンブリを次に示します。

; multiply registers a and b

; use c as high b
mov c,#0
; use d as low result
mov d,#0
; use e as high result
mov e,#0
.nextbit:
  ; shift low bit out of a
  shr a
  ; skip if zero
  bcc .noadd
    ; add b to result
    add d,b
    adc e,c
  .noadd:
  ; double b
  shl b
  rcl c
  ; test a
  cmp a,#0
bne .nextbit

（2バイト値を乗算した結果は2バイト値であることに注意してください。）

乗算ができたら、ループして電力を計算できます。

使用した手順：

mov x,y = move y into x
shr x = shift right one bit
shl x = shift left one bit
rcl x = rotate left one bit with carry inserted
add x,y = add y to x
adc x,y = add y to x with carry
cmp x,y = compare x to y
bcc = branch on carry clear
bne = branch on not equal
#0 = literal number zero (as opposed to 0, which would be the address zero)
于 2009-12-14T00:05:54.067 に答える
0

指数 n の k 乗:

exponent(n,k) {
   for(x=1..n)
      x = x + exponent(x,k-1)
}
于 2009-12-19T21:09:46.507 に答える
0

関連する乗算 ALUに関するウィキペディアの記事を見つけることができます。加算演算とビット演算 (and and or) を使用すると、乗算をビットごとに 1 ステップで実装できます。小さい方の演算子の大きさと同じ数だけ加算する必要はありません。

于 2009-12-14T09:54:25.430 に答える