福野泰介の一日一創

無いものは作ればOK！（IchigoJamでのR3はここでは封印）

N / M = A ... R（A:商、R:あまり、ただしNもMも正の整数とする）という割り算をする場合、割り算記号を使わずに作成できればOKです。何か、得意な言語で作ってみましょう。

例えば、IchigoJam BASICなら

10 INPUT N 20 INPUT M 30 A=0 40 N=N-M:IF N>=0 A=A+1:CONT 50 N=N+M 60 ?A;"...";N RUN ?300 ?7 42...6

割り算記号を使わない割り算、できました！

これをasm15マシン語にします（USRでは引数が1つなので、割る数R1に7と設定）

R1=7 R2=R0 R0=0 @LOOP R0+=1 R2=R2-R1 IF GE GOTO @LOOP R0-=1 R1=R2+R1 RET

アセンブルしたバイナリ(18byte、R1設定を除くと16byte)を使って、動かしてみましょう

POKE#700,7,33,2,70,0,32,1,48,82,26,252,218,1,56,81,24,112,71 ?USR(#700,300) 42

これで完成！ ・・・としてもいいのですが、割られる数が大きくて、割る数が小さい時、何万回もループすることになって遅そうです。

例えば、30000/1を計算する場合、1ループ5cycle3万回で15万cycle。CPUの周波数48MHzの逆数、21nsecが1cycleにかかる時間なので、63万nsec = 630usec = 0.63ミリ秒かかります。 足し算引き算かけ算の15万倍も遅いとなると、高速処理が命のゲームで使うには厳しいこともありそうです。

そこで登場、アルゴリズム（問題解決手法）！

ひとまず簡単に思いつくところで、2進数を使った筆算アルゴリズムで高速化してみます。 割り算を手で計算するときに筆算を使うように、大きな桁からかけ算して引いてを繰り返して答を求めます。 幸い、2進数の筆算は0か1かしかないので、とってもシンプル。何か書きやすいプログラミング言語でアルゴリズムを確かめます。

10 INPUT N 20 INPUT M 30 A=0 40 FOR I=10 TO 0 STEP -1 50 L=M<<I 60 IF N>=L N=N-L:A=A+1<<I 70 NEXT 80 ?A;"...";N RUN ?300 ?7 42...6

（変数が16bit用に、IchigoJam BASIC桁溢れ防止のため10bitシフトからスタート）
前の手法に比べて速くなったことが体感できましたね？では、こちらをマシン語にします。

R1=7 PUSH {LR,R4} R2=R0 R0=0 R3=16 @LOOP R4=R1 R4<<=R3 R2-R4 IF LT GOTO @SKIP R2=R2-R4 R4=1 R4<<=R3 R0+=R4 @SKIP R3-=1 IF !MI GOTO @LOOP R1=R2 POP {PC,R4}

ループ回数が16回にまで劇的に減り、先の最悪の場合と比較し、約1000倍高速です！

ただし、その代償として、マシン語の量が32byteと16byte増えてました。これが多いか少ないかは状況次第です。 また、割る数と割られる数が近い場合は毎回150cycleかかる今回の手法と違って、単純ループの実装の方が速かったりします。 状況によって使い分けましょう。

OSとしてのIchigoJamとしては、汎用的に使われることを想定して、あまりに遅い除算は残念なので、第二案でいきたいです。 ただ容量は極力小さくしたいので、かけ算が1cycleで動くことを利用して、もうひと工夫縮めてみます。

R1=7 PUSH {LR,R4} R2=R0 R0=0 R3=1 R3=R3<<16 @LOOP R4=R1 R4*=R3 R2-R4 IF LT GOTO @SKIP R2=R2-R4 R0+=R3 @SKIP R3=R3>>1 IF !0 GOTO @LOOP R1=R2 POP {PC,R4}

2byte縮み、引き算する場合のcycleが2減りました！
たった2byteと笑うかもしれませんが、その2byteを削るのに結構苦労したりするんです。

POKE#700,7,33,16,181,2,70,0,32,1,35,27,4,12,70,92,67,162,66,1,219,18,27,24,68,91,8,247,209,17,70,16,189 ?USR(#700,300) 42

実は、まだ落とし穴があります。マイナスの値で割り算の計算をさせてみてください。
おかしくなりますね。また、割る数に0を指定した時にどんな動きをしてほしいです���？
すべては、あなたの思い次第！

より高速で効率良いアルゴリズムを探してみるのも楽しそうです。Wikipediaの「除算」を見てみると、懐かしの割り算バグありPentiumの話がでてました。 試行錯誤の積み重ねで、今のコンピューター社会ができていることがわかります。

- 連載、IchigoJamではじめる、Armマシン語入門
1. はじめてのマシン語
2. ハンドアセンブルで超速計算！
3. マシン語メモリアクセスで画面超速表示！
4. マシン語でLEDを光らせよう！
5. 楽しさ広がるマルチバイトメモリアクセスとスタック
6. マシン語使いこなしTIPS
7. カジュアルに使うインラインマシン語
8. アセンブラを使って楽しよう
9. マシン語で高速SPI
10. マシン語を制するもの時間を制す
11. 画面をイチゴで埋め尽くす12の方法
12. レジスタ不足に上位レジスタとスタック操作
13. コンパイラはじめのいっぽ、EVAL実現法とマシン語生成
14. サイズを取るかスピードを取るか、割り算のアルゴリズムとマシン語実装
15. マシン語化で1万倍速!? セットで学ぶアルゴリズムとコンピューター