現在、16 ビットのカスタム マイクロプロセッサ用のソフトウェアを作成しています。16 ビットより大きい数値を処理できる必要があります。命令セットは非常に限られていますが、左シフト、右シフト、AND、OR、および NOT があります。このタイプの算術演算をどのように実装しますか?
2 に答える
足し算と引き算では、オーバーフローをある単語から別の単語に運びます。乗算については、http://en.wikipedia.org/wiki/Binary_multiplierで説明されている手法を使用すると、かなり簡単に実装でき、逐次加算よりも優れています。一般に除算はより複雑ですが、開始するのに適した場所はhttp://en.wikipedia.org/wiki/Division_algorithm#Integer_division_.28unsigned.29_with_remainderです。
その除算アルゴリズムは、実際には単なる整数の「長い除算」です。それほど速くはありませんが、正確です。この記事にはもっと複雑な方法がありますが、それらは...まあ、もっと複雑です。おそらく、簡単なものを試してから、最適化する必要があるかどうかを確認してください。
http://en.wikipedia.org/wiki/Multiplication_algorithmもご覧ください。また、 http: //x86asm.net/articles/working-with-big-numbers-using-x86-instructions/には、x86 プロセッサでのマルチワード演算に関する優れた情報があり、その多くは他の CPU にも適用できるはずです。
これで遊んだのは久しぶりです。(何年も前に) Z80 で 32 ビット演算を行ったので、ここで何に反対しているのかがわかりました。
誰かがこれを行うコードが必要な場合に備えて、私は今それを書いています。先週の時点で 64 ビットの乗算が機能しているので、現在は 64 ビットの除算に取り組んでいます。コードはhttps://github.com/drtonyrにあるか、メールを送ってください。以下のコードは非標準であるため、私に連絡するのが最善の方法です (トランジスタのはんだ付けを含め、すべてを作成/構築するつもりです)。
: 4mul pick(7) pick(4) # grab the sign words
xor mvDC # compute final sign and put on call stack
4abs 4swap 4abs 4maxmin # abs swap so that second is smallest
callocC(4) # zero space on call stack for result
allocC(4) # space for smallest multiplier
storeC(1) storeC(2) storeC(3) storeC(4) # smallest to C in reverse order
C add(8) D sub(2) # set up pointers for main _4mul_word calcs
mvCD _4mul_word _4mul_word_asl # mul X0
mvCD _4mul_word _4mul_word_asl # mul X1
mvCD _4mul_word _4mul_word_asl # mul X2
mvCD _4mul_word # mul X3
ndrop(7) # don't need X3, pointers or shift space anymore
4mvCD # move result to data stack
mvCD <0 if? 4negate # set correct sign
; # and exit happy
その多くはデータ移動ですが、アイデアは、64 ビットの結果とサイクルごとに 1 ずつシフトされる最大数を取得し、最小数のビットを取り出して、ビットが設定されている場合はアキュムレータに追加することです。 、これは _4mul_word によって達成されます (_4mul_word_asl は、上位ビットがゼロのときにシフトを完了するだけです)。最小の数値の先頭には多くのゼロが含まれる可能性が高く、最小の数値の先頭ビットを処理するとすべてが停止する可能性があるため、いつの日かさらに最適化します。_4mul_word は以下のとおりですが、ここで重要なことは、(a) できること、(b) 作業量が多く、実行速度が遅いことです。
_4mul_word: # top of stack contains the top address of accumulator (D),
# the top address of partial shifted input (A) and
# the word to multiply (B).
# This runs over all non-zero bits.
*C = E, C -= I # store E
*C = D, C -= I # store D - we will leave stack state unchanged
B = *D, D -= I # pop the main word we are going to work with
A = *D, D -= I # Address of partially shifted
D = *D, D -= Z # Address of accumulator
_4mul_word_loop:
Z = B & I # test a single bit
eq0 P = *P, P += I # skip if bit is zero
:_4mul_word_bitzero
*C = A, C -= I # store A as we are going to change it
*C = D, C -= I # store D as we are going to change it
*C = B, C -= Z # store B as we are going to change it
## add in the shifted value (A) to accumulator (D)
B = *D, D -= Z # read X0
E = *A, A -= I # read Y0
B = B + E # compute Z0
*D = B, D -= I # and store it
B = *D, D -= Z # read X1
E = *A, A -= I # read Y1
cin B = B + E # compute Z1
*D = B, D -= I # and store it
B = *D, D -= Z # read X2
E = *A, A -= I # read Y2
cin B = B + E # compute Z2
*D = B, D -= I # and store it
*D = B, D -= I # and store it
B = *D, D -= Z # read X3
E = *A, A -= I # read Y3
cin B = B + E # compute Z3
*D = B, D -= I # and store it
B = *C, C += I # restore B
D = *C, C += I # restore D
A = *C, C += Z # restore A
_4mul_word_bitzero:
## shift up the contents of A
*C = A, C -= Z # store A as we are going to change it
E = *A, A -= Z # read X0
E = E + E # compute Z0
*A = E, A -= I # and store it
E = *A, A -= Z # read X1
cin E = E + E # compute Z1
*A = E, A -= I # and store it
E = *A, A -= Z # read X2
cin E = E + E # compute Z2
*A = E, A -= I # and store it
E = *A, A -= Z # read X3
cin E = E + E # compute Z3
*A = E, A -= I # and store it
A = *C, C += Z # restore A
B = B >> I # shift down B
ne0 P = *P, P += I # loop if we haven't yet shifted down B to zero
:_4mul_word_loop
C = C + I
D = *C, C += I # restore D
E = *C, C += Z # restore E
P = *E, E += I # execute the NEXT code