私は、ハードウェアの乗算と除算を行わないマイクロコントローラーに取り組んでいます。コンパクトなサイズと効率のバランスが取れた、これらの基本的な操作のためのソフトウェアアルゴリズムを作成する必要があります。私のCコンパイラポートは、C開発者自身ではなく、これらのアルゴリズムを採用します。
私のgoogle-fuは、これまでのところ、このトピックに関するほとんどのノイズを上げています。
誰かが私に何か有益なことを教えてもらえますか？add/subおよびshift命令を使用できます。テーブルルックアップベースのアルゴリズムも私には役立つかもしれませんが、いわばコンパイラのバックエンドに詰め込むのが少し心配です。
簡単な乗算アルゴリズムは次のとおりです。
乗数の右端のビットから始めます。
乗数のビットが1の場合、被乗数を追加します
被乗数を1だけシフトします
乗数の次のビットに移動し、ステップ2に戻ります。
そして、これが除算アルゴリズムです：
除数が被除数よりも大きい場合は、停止します。
除数レジスタが被除数レジスタよりも小さい間、左にシフトします。
除数レジスタを1だけ右にシフトします。
被除数レジスタから除数レジスタを減算し、除数レジスタに対して行われたシフトの総数に対応するビットで、結果レジスタのビットを1に変更します。
除数レジスタを元の状態にして、手順1からやり直します。
もちろん、ゼロ除算のチェックを入れる必要がありますが、うまくいくはずです。
もちろん、これらのアルゴリズムは整数専用です。
このようなものについての私のお気に入りのリファレンスは、本の形で入手できます：
http://www.hackersdelight.org/
また、TAoCPを間違えることはできません：http ：//www-cs-faculty.stanford.edu/~uno/taocp.html
除算アルゴリズムは次のとおりです。http：//www.prasannatech.net/2009/01/division-without-division-operator_24.html
私たちはintについて話していると思いますか？
ハードウェアサポートがない場合は、独自のゼロ除算例外を実装する必要があります。
（私は乗算アルゴリズムをすぐに見つけることができませんでしたが、他の誰かがそれを見つけられないかどうかを探し続けます）。
整数の単純でかなりパフォーマンスの高い乗算アルゴリズムの1つは、RussianPeasantMultiplicationです。
有理数については、通常よりも除算が簡単な2進引用表記を試すことができます。
長い乗算と長い除算のための古い68000アセンブラコードがまだあることがわかりました。68000コードは非常にクリーンでシンプルなので、チップに合わせて簡単に変換できるはずです。
68000には乗算と除算の命令IIRCがありました-これらは学習演習として書かれたと思います。
ここにコードを置くことにしました。コメントを追加し、その過程で問題を修正しました。
;
; Purpose : division of longword by longword to give longword
; : all values signed.
; Requires : d0.L == Value to divide
; : d1.L == Value to divide by
; Changes : d0.L == Remainder
; : d2.L == Result
; : corrupts d1, d3, d4
;
section text
ldiv: move #0,d3 ; Convert d0 -ve to +ve - d3 records original sign
tst.l d0
bpl.s lib5a
neg.l d0
not d3
lib5a: tst.l d1 ; Convert d1 -ve to +ve - d3 records result sign
bpl.s lib5b
neg.l d1
not d3
lib5b: tst.l d1 ; Detect division by zero (not really handled well)
bne.s lib3a
rts
lib3a: moveq.l #0,d2 ; Init working result d2
moveq.l #1,d4 ; Init d4
lib3b: cmp.l d0,d1 ; while d0 < d1 {
bhi.s lib3c
asl.l #1,d1 ; double d1 and d4
asl.l #1,d4
bra.s lib3b ; }
lib3c: asr.l #1,d1 ; halve d1 and d4
asr.l #1,d4
bcs.s lib3d ; stop when d4 reaches zero
cmp.l d0,d1 ; do subtraction if appropriate
bhi.s lib3c
or.l d4,d2 ; update result
sub.l d1,d0
bne.s lib3c
lib3d: ; fix the result and remainder signs
; and.l #$7fffffff,d2 ; don't know why this is here
tst d3
beq.s lib3e
neg.l d2
neg.l d0
lib3e: rts
;
; Purpose : Multiply long by long to give long
; Requires : D0.L == Input 1
; : D1.L == Input 2
; Changes : D2.L == Result
; : D3.L is corrupted
;
lmul: move #0,d3 ; d0 -ve to +ve, original sign in d3
tst.l d0
bpl.s lib4c
neg.l d0
not d3
lib4c: tst.l d1 ; d1 -ve to +ve, result sign in d3
bpl.s lib4d
neg.l d1
not d3
lib4d: moveq.l #0,d2 ; init d2 as working result
lib4a: asr.l #1,d0 ; shift d0 right
bcs.s lib4b ; if a bit fell off, update result
asl.l #1,d1 ; either way, shift left d1
tst.l d0
bne.s lib4a ; if d0 non-zero, continue
tst.l d3 ; basically done - apply sign?
beq.s lib4e ; was broken! now fixed
neg.l d2
lib4e: rts
lib4b: add.l d1,d2 ; main loop body - update result
asl.l #1,d1
bra.s lib4a
ちなみに、最初はすべてをポジティブに変換する必要があるかどうかはわかりませんでした。シフト操作に注意すれば、それは回避可能なオーバーヘッドかもしれません。
Microchip PICmicro 16Fxxxシリーズチップには、乗算または除算命令はありません。おそらく、そのためのソフト乗算およびソフト除算ルーチンのいくつかをMCUに移植することができます。
除算の「ニュートン法」もチェックしてください。説明は実際よりも複雑に聞こえますが、この方法は、これまでに見た除算アルゴリズムの中で最小の実行可能サイズを提供すると思います。初期のクレイスーパーコンピューターの中には、ニュートン法を使って除算したものがあると聞いています。
乗算するには、乗算器の対応するビットが設定されている場合に、シフトされた被乗数からアキュムレータに部分積を加算します。ループの終わりで被乗数と乗数をシフトし、乗数と1をテストして、加算を行う必要があるかどうかを確認します。