ソフト乗算およびソフト除算アルゴリズムはどこで見つけられますか?
https://stackoverflow.com/questions/2390354
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はハードウェアの乗算と除算を使用しないマイクロコントローラーを開発しています。これらの基本的な操作のために、コンパクトなサイズと効率性のバランスのとれたソフトウェア アルゴリズムを作成する必要があります。私の C コンパイラ ポートは、C 開発者自身ではなく、これらのアルゴを使用します。
私の Google 検索では、これまでのところ、このトピックに関するほとんどのノイズが見つかっています。
誰かが私に何か有益なことを教えてくれませんか？加算/減算命令とシフト命令を使用できます。テーブル ルックアップ ベースのアルゴも私にとっては機能するかもしれませんが、コンパイラのバックエンドにあまりにも多くのものを詰め込むのは少し心配です...ええと、いわば。
解決
簡単な乗算アルゴリズムを次に示します。
乗算器の右端のビットから始めます。
乗数のビットが 1 の場合、被乗数を加算します
被乗数を 1 シフトする
乗算器の次のビットに移動し、ステップ 2 に戻ります。
そして、これが除算アルゴリズムです。
除数が被除数より大きい場合は停止します。
除数レジスタが被除数レジスタより小さい間、左にシフトします。
除数レジスタを右に 1 シフトします。
被除数レジスタから除数レジスタを減算し、除数レジスタに対して行われたシフトの合計数に対応する結果レジスタのビットを 1 に変更します。
除数レジスタを元の状態にして、ステップ 1 からやり直します。
もちろん、0 で割るチェックを入れる必要がありますが、機能するはずです。
もちろん、これらのアルゴリズムは整数のみを対象としています。
他のヒント
本の形で利用できるこのようなことのための私のお気に入りの参照、：
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 について話していると思いますか?
ハードウェア サポートがない場合は、独自のゼロ除算例外を実装する必要があります。
(乗算アルゴリズムをすぐに見つけるのはあまり幸運ではありませんでしたが、他の人がアルゴリズムを見つけなかったら探し続けます)。
これは、私はまだ長い乗算と長い除算のためのいくつかの古い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
ところで - 私は開始時に正にすべてを変換する必要があったかどうかを把握することはなかったです。シフト操作としている慎重にあなたがいる場合、それは回避オーバーヘッドかもしれません。
乗算、シフト被乗数からアキュムレータに部分積を追加します。ループの終わりにシフト被乗数と乗数、加算が行われるべきかどうかを確認するために乗算器と1のテスト
マイクロチップのPICmicro 16Fxxxシリーズチップは、乗除算命令を持っていません。 おそらくそれのための乗算ソフトとソフト除算ルーチンのいくつかは、あなたのMCUに移植することができます。
