おちゃめくらぶ掲示板 - 1659321896

1464：御茶目菜子：2013/02/01(金) 23:59:40: プチコンで32bit整数演算を行う方法
プチコンの1つの問題点として32bit固定小数点であり、小数部分に12bit使用され整数は
19bit＋符号1bitとなっているため最大で±525287までの数値（2^19-1）までしか扱うことが
できないにょ。
実務用に使うことはほとんどなくほぼホビー用に使われるであろうプチコンであればそれほど
問題はないとはいえ、最大52万程度の数しか扱えないということで不満を感じている人も
結構いるにょ。

制限があってもそれを工夫すれば乗り越えることは可能にょ。
1つの改善作として考えられるのが多倍長演算のようなことをするというものにょ。
多倍長演算はその言語でサポートしている最大数に収まる範囲内で桁を区切りそれを元に
数値表記を行うものにょ。
例えば1つの変数に10000まで入れるという場合は簡単に言えば1万進数で表記するという
ような感じにょ。
こうすることでその言語がサポートしている上限数を大幅に越えた計算をすることが可能で
あり、非常に多くの桁数の演算が必要になる円周率などの計算にも活用されているにょ。
多倍長演算をデフォでサポートしている言語も一部にはあるものの基本的にはソフトウェアで
実装する必要があるにょ。
これはそれほど難しいものではなく人が筆算で行うのと同じアルゴリズムで行われるにょ。

2桁＋2桁の加算の例として36＋47を計算する場合は次のようになるにょ。

　　　　３６
　　　＋４７
　　　－－－
　　　　８３

この場合は6と7を足して13となり、1の位は3になるにょ。
10の位は1+3+4で8になるにょ。
したがって、答えは83にょ。

これを211万6789＋315万7895を計算する場合に1万進数で行う場合0～9999を1つの変数に入れて
計算することになるにょ。
変数AH（変数Aの上位桁）、変数AL（変数Aの下位桁）、変数BH（変数Bの上位桁）、変数BL
（変数Bの下位桁）と4つの変数にAH=211、AL=6789、BH=315、BL=7895を入れておくにょ。
そうすれば下位桁同士をまず計算して14684となり、1繰り上がって下位桁は4684となるにょ。
1＋211＋315で上位桁は527となるにょ。

このように加算は繰り上がり処理だけ注意すれば簡単に実現できるにょ。
減算は同様に繰り下がり処理だけ注意すればいいにょ。
しかし、乗算はそうはいかないにょ。

　　　　３６
　　　×４７
　　　－－－
　　　２５２
　　１４４
　　－－－－
　　１６９２

これも同じく筆算の要領で計算すれば良くまずは36x7を計算して7x6=42（4繰り上がり）、
7x3+4=25（2繰り上がり）となるにょ。
そして、36x40を同様に計算して最後に同じ桁同士で加算を行えば答えが出るにょ。
ここで1つ重要な問題があるにょ。
それはプチコンの演算における上限数の問題にょ。
加減算だと10000を1まとめにして計算しても最大でも9999+9999であるため上限数に達する
ことはないけど乗算の場合は最大数では9999x9999という場合が起こりうるからね。
SQR(524287)を計算すると724.07・・・であるため乗算をサポートするならば2桁単位で
計算する（つまり100進数とする）必要があるにょ。（724進数までなら大丈夫なので256進数
でもいいけど後から10進数に直すのに処理時間がかってしまう）
その場合には10桁の演算をサポートする（2桁単位で5つ分）だけでも数10回の演算が必要と
なりさらに後述の例外処理も非常に複雑になってしまうにょ。（基本的に区切る数の二乗の
割合で演算量は増えていく）

多倍長演算は扱えるデフォでその言語がサポートしている演算桁数の制限を突破するには
非常に有用な方法だけど演算速度がポケコンや8bitパソコンのBASICよりも桁違いに速いとは
いえそれほど速くはないプチコンにおいてリアルタイムで求めるためには加減算程度しか
実装は難しいと思われるにょ。
ゲームのスコアに使うならばそれで困ることはほとんどないけど四則演算を行いたいならば
あと多倍長演算は加減乗除それぞれ演算ルーチンが必要になるため必要なルーチンを別途
実装するならばプログラムが長くなってしまうのも厄介だしね。

そこで考えられるのは32bit整数演算を行うということにょ。
プチコンでは1つの数値変数は上記のように32bitで記録されているため小数部分を何とか
うまく活用できるならば±2147483647まで対応可能になるにょ。
最大52万では不満を感じることが多くても最大21億ならば不満を感じることはかなり少なく
なりそうにょ。
というわけで早速作ってみたにょ。

@INT
Z=4096:IL=INT%(10000/Z)*Z:IH=0OR(INT-IL/Z)/10000*Z
INT$="-"*!IH*(INT<0)+STR$(ABS(IL)):INT$=STR$(IH)*!!IH+LEFT$("0"*4,(4-LEN(INT$))*!!IH)+INT$
RETURN
http://ww5.tiki.ne.jp/~ochame/petitcom/tips/routine.htm#int

固定小数点で記録されている数値を32bit整数に変換するというアイデアを考えた人は数多く
いると思うけど現時点で発表されたものはほぼないにょ。
それには次のような問題点があるからにょ。

　(1)小数型から整数型への変換処理
　(2)例外処理
　(3)計算法則の確立

(1)一番の課題はこれにょ。
最も簡単なのは1bitずつ抜き出していって順に1、2、4、8・・・の値を加算していくという
ものだけどそのためには多倍長演算のように数10回もの演算が必要になってしまうにょ。
配列変数同士の加算処理を1回行うだけで3ミリフレーム以上の時間がかかってしまうため
300回行うと1フレームくらいの時間となるからにょ。
少しでも高速化を図りたいならば別の観点で考える必要があるにょ。
そこで利用できそうなのはA%1でAの小数部分だけが取り出せるというものにょ。
これで小数部分を取り出したところで残った整数部分が4096の倍数となっているためそこから
特定の桁を得るためには結局ビット演算で各桁の値を抜き出す必要があるにょ。
しかし、「1」の剰余ではなく「10000/4096」の剰余であれば小数を整数と見なしたときの
下位4桁を抜き出すことが可能になるにょ。
つまり、残ったものは10000の倍数となるにょ。

ただし、ここからがまた厄介にょ。
A-A%1ならばそのAは整数になっているけどA-A%(10000/4096)の場合はAは小数のままだからね。
ここからどうやってAの上位桁の値を求めるかを考えなくてはならないにょ。
これは少し発想を変えれば簡単に分かるにょ。
内部では4096単位で記録されているため例えば1234という値は4096x1234=5054464という値を
示すのだけどこのまま4096を掛けるというのはOverflowになるためできないにょ。
ところが、1万で割って4096を掛ければ万単位の値は出せるにょ。
A/10000*4096でAが何万かということが分かるわけにょ。
実際に1234/10000*4096を実行すれば505という値になるからね。

しかし、これはぴったり何万という数ならばいいけどそうでないときには困るにょ。
例えば1235/10000*4096もプチコン上で505になり、実際に計算して505.856になるからね。
単に整数化すれば良いだけのことなんだけど問題は負数の場合にょ。
プチコン上でぴったり割り切れない限りは整数化した場合には絶対値が1大きな値となって
しまうにょ。
それならばぴったりの値にすればいいだけであって、すでに分かっている下位数を引いて
いるためぴったりの値にしてあるので問題はないにょ。
この簡易化によって6ミリフレームで上位、下位の各数値（ルーチン内の変数でいえばIHと
IL）を特定する処理が完了するにょ。（プチコンは配列変数と代入処理が遅いのはそれを
できるだけ減らすことが高速化に繋がる）
これは配列変数同士の加算2回分という速さにょ。
しかも、これは結果を出力する前に行う処理であるため毎回結果出力をしないのであれば
4096で割るという処理（0.37ミリフレーム）演算時間が増えるだけなので非常に高速にょ。

(2)例外処理とは例えば10240という値を上位と下位に分けた場合には1と240になるけど
そのままだと1240となってしまうため間に0を埋める処理が必要になるにょ。
しかし、これはそれほど難しくはないにょ。
問題なのはどのような例外処理が考えられるかをすべて掃き出しそれをすべて実装する
必要があるということにょ。
上位桁が0の時は0240ではなく240のみでいいというのはすぐに分かるけど問題は負数にょ。
負数の時は剰余も負数になるためSTR$で下位桁を文字化してしまうと上位と下位の間に
不要なマイナスが入ってしまうにょ。
したがって、下位桁は絶対値でないとダメにょ。
とはいえ、さらに例外もあり、上位桁が0の時は絶対値ではだめでその符号もそのまま付ける
必要があるにょ。
簡単な処理とはいえ、私の作ったルーチンの大半はこれら例外処理に対応するためのものと
なっているため（処理時間の面では）馬鹿にはできないにょ。

(3)計算法則の確立については加減算と乗除算のときの小数点の移動がどうなるのかを理解
していれば良いだけなので難しくはないにょ。
そうなるとあとはプチコンの内部演算の仕組みさえ理解していれば問題は全くないにょ。
そもそも1/4096単位で記録されており、それ未満は切り捨てられるということを知らないと
(1)も作ることができないので(1)ができた時点で(3)の条件は満たせそうな気がするにょ。

ということで(1)さえできればあとは難しいことはあまりないといえるにょ。
さて、そうなるとこれまで作られなかったのは(1)が難しいためかもしくは需要そのものが
無かったためだと思われるにょ。
確かに(1)はA%(10000/4096)で固定小数点で記録されたAを整数化した時の下位4桁が抜き出せる
ということを知らなければ詰んでしまうからね。（1bitずつ抜き出せばいいだけなので難しく
ないけどそうすると処理速度が大幅にダウンしてしまう）
あと、ゲームのスコアで使う場合上位、下位に分けた簡易多倍長演算の加算のみで十分に
対応できるため四則演算の必要性もないわけだからね。（加算のみなら例外処理も短くて
済むわけだし）
確かにゲームなどを作る際に何百万、何千万という整数値で四則演算をするという機会は
ほとんどないためこれは仕方ないのかもしれないにょ。
もっとも誤差の出ない整数演算で21億まであれば今までプチコンでは困難だった多くの実務
演算はこなせるけど元々プチコンでそういう需要は少なそうだからね。
実際、このルーチンを作った私でさえ何に使うのかと聞かれたら困ってしまうにょ（笑）
単に出来そうだから作ってみたというだけのことにょ。

さて、話は変わるけど先日twitterのプチコンクラスタにてラスタースクロール祭があったにょ。
http://togetter.com/li/447861
みんなでラスタースクロールを使ったサンプルプログラムを発表しあったけど私も2つほど
作ったにょ。

まず1つ目が旅の扉風ラスタースクロールにょ。
http://twitpic.com/bzsaer
ドラクエの旅の扉のような演出で2枚のGRPを入れ替えるという単純なものだけどRPGにおいては
GPUTCHRでGRPに描き出せば実際に旅の扉みたいな感じで使うことができるにょ。
あとはこれを使って文字を表示して少しずつ見えていく文字を当てるクイズゲームなどにも
使えるかもしれないにょ。

続いてテキストラスタースクロールにょ。
http://twitpic.com/bzsbi8
こちらはコンソール文字をすべて書き換えて強引にラスタースクロールを実現しているもので
非常に重いのが特徴にょ。
これはプチコンのCHRSETによる書き換えがこういう用途には向いていないというのもあるけど
横1列がすべて同じ文字で代用が効く横縞模様にすれば大幅に高速化が可能だと思われるにょ。
実際何に使えるのかというのは悩みどころだけどGRPに余裕がなくBGFしか利用できないという
特定条件下でなら使えるかもしれないにょ。（そういう状況はよほどの例外だけど）