計算に要する一時変数の個数
過去ブログの転載です。
RPGツクール2000における、複雑な計算で使う一時変数の個数のお話です。プログラミングをされている方の場合、ここでいう一時変数はレジスタみたいなもんだと思ってもらっていいです。
RPGツクール2000ではプログラミングの書き方ができないので、計算式を入力して直接計算するということが出来ません。難しい計算を入れようと思うと、変数を一個一個定義して、それらの四則演算を駆使する必要があります。
1＋2×3 みたいな式であれば、優先度の高い掛け算の方を先に計算して
◆変数1番 ＝ 2（2を代入）
◆変数1番 × 3（3倍する）
◆変数1番 ＋ 1（1足す）
みたいにしてやれば、1個の変数で足ります。
しかし、2×3＋4×5 のような式を計算する際は変数1個では足りません。一時的に計算用の変数を用意しておいて、それを途中計算で使うことになります。
◆変数1番 ＝ 2
◆変数1番 × 3
◆変数2番 ＝ 4
◆変数2番 × 5
◆変数1番 ＋ 変数2番
一般に、計算式が複雑になればなるほど一時変数は多く必要になります。
では、最低何個あれば足りるのか、というのを計算式から判断できるでしょうか。
使用変数の個数計算アルゴリズム
まず、上のように計算式をツリー構造に置き換えます。一つ一つの丸のことをノードと呼びます。
2＋3×5だったら3×5を先に計算するので、3と5を×の木で結び、その結果と2を足すので、それぞれを＋の木で結びます。計算するときは、下から順にまとめていけばいいですね。
上の式なら次のように1つの変数があれば計算できます。
◆変数1番 ＝ 3
◆変数1番 × 5
◆変数1番 ＋ 2
3×5の結果を使い、それに2を足せばOKです。
計算によって各ノードに至るまでに必要な使用変数の個数を下に数字で書いています。ただの数値は基本変数を使わないので0としていますが、初めの3×5の計算を行うために、3か5のどちらかを一旦変数に入れないといけません。ここでは3を入れるものとし、3に変数を一つ使っています。3×5の計算結果を変数1番に入れればよいので、×の使用変数は1となっています。さらに、それに足した結果をそのまま変数1番に入れますから、＋の使用変数はそのまま1となります。
複雑な式になっても同じです。ただ、引き算や割り算のように交換法則が成り立たない演算の場合は、左の数の方を必ず変数に入れなければなりません。それに注意しながら使用変数の個数を振っていくと上図のようになります。
◆変数1番 ＝ 1
◆変数1番 ÷ 5
◆変数2番 ＝ 1
◆変数2番 － 変数1番
◆変数2番 ＝ 8
◆変数2番 ÷ 変数1番
1÷5ではまず変数1番に1を入れておき、そこから5を割り算。次に1からその結果を引く必要がありますが、変数1個では無理なので、変数2番を用意して、そこに1を入れておき、変数2番から変数1番を引けばOKです。（A－B＝－(B－A)でいいじゃんというツッコミは禁止です＾＾；）
これを繰り返し、変数2個で計算できるということが分かります。
では、子ノードの値から親ノードの値を求めるにはどうすれば良いでしょうか。
そのノードに振られている値は、言わば計算がそこに至るまでに使用した変数の最大個数を表します。例えば上の式では「－」の部分で2となっていますが、－の計算を終えた直後はもう変数1番しか使っていないので、変数2番が使えます。8をわざわざ変数3番に入れなくても、使っていない変数2番に入れれば済みます。だから、最後の「÷」は1＋2＝3個ではなく、それまでの最大個数であった2個がそのまま÷に振られます。
演算を行う際には、各演算に用いるノードで使用変数が多かった部分を先に計算して計算時に変数1個としておくことで、使用変数の節約が出来るようになります。
上図でいうと、使用変数が0個で済む2の方ではなくて、使用変数が1個必要な3×5の方を先に計算すると最大個数が少なくて済みます。
上図のように使用変数が1個必要なもの同士を使って演算する場合は、変数1番に左の×の結果を、変数2番に右の×の結果を入れて足し算する必要があるので、変数は2個必要になります。
以上のことから、使用変数の個数について次の法則が言えます。
【四則演算における親ノードの使用変数個数】
2つの子ノードの使用変数個数がそれぞれa, bとすると、
・a≠bのときmax{a, b}（a, bのうち大きい方）
・a＝bのときa＋1
使用変数個数がお互い同じときしか個数が増えないということになります。さっきの例がその法則に従って得られるか確認してみてください。
例
下のイベント命令は、変数1番に角度を入れると、sinの値を計算して、変数2番にその100倍の値を入れるものです。
◆変数の操作：[0003:一時]代入，変数[0001]の値
◆変数の操作：[0003:一時]乗算，変数[0001]の値
◆変数の操作：[0003:一時]乗算，64
◆変数の操作：[0003:一時]除算，2025
◆変数の操作：[0002:結果]代入，変数[0003]の値
◆変数の操作：[0002:結果]乗算，-20
◆変数の操作：[0002:結果]加算，12000
◆変数の操作：[0003:一時]乗算，変数[0003]の値
◆変数の操作：[0003:一時]除算，100
◆変数の操作：[0002:結果]加算，変数[0003]の値
◆変数の操作：[0002:結果]乗算，変数[0001]の値
◆変数の操作：[0002:結果]除算，6750
◆変数の操作：[0002:結果]乗算，変数[0004]の値
◆
一時変数を含めて変数を3個使っていますが、本当に3個必要なのか確認しましょう。この計算過程を下図のようなツリー構造にします。
たどっていくと、確かに3になっていることが分かりますね。
この法則は何らかの計算アルゴリズムを作ったときに、その必要な使用変数の個数を求める際に便利だと思います。
ツクール2000では使えますが、最近のツクールだとあまり使わないかもしれませんね。メモリがありあまる今の時代、こんなの大して役に立たないかもしれません。組み込み屋さん向けかな＾＾；
