アルゴリズム入門？
大層なタイトルですが、大した事書いてません。
１．アセンブラとは？
アセンブラとはアセンブリ言語をコンピュータの心臓部であるプロセッサが理解できる機械語(マシン語)に翻訳(interprete)するツールです。
メモリダンプを見たことがある方はわかると思いますが、メモリには
01 23 45 67 89 AB CD EF
というように、16進数の数字が羅列されていますがこの数字がプログラムの場合はプロセッサに対する命令(ニーモニック)になります。
例えばサブ処理から戻る命令は「Z80」などでは「C9」、「68000」などでは「4E 75」になります。
もちろん、直接これらを記述していきプログラムすることも可能です。
しかしこれは効率が悪くメンテナンス性も悪いため、小規模なものでない限り通常は行いません。
そこでこれらのニーモニックを人間が理解しやすいようにしたものがアセンブリ言語です。
先ほどの「C9」は「RET」となりますし、「4E 75」は「rts」となります。
これらのニーモニックはプロセッサ毎に異なりますし、可能な命令もそれぞれ異なります。
例えば8bitの80系と68系ではプロセッサが持つレジスタ(一時記憶バッファのようなもの)に値を設定する命令がそれぞれ
Z80 LD HL,01H (HLレジスタに「1」を設定)
6809 LDA #$01 (Aレジスタに「1」を設定)
といった感じとなり、似てるようで互換性は全くありません。
レジスタ構成や周りのI/O関係、それにそもそも設計思想から異なりますから当たり前ですが。
では実際にアセンブラでのプログラムとはどういうものなのでしょうか。
アセンブラの処理ではレジスタの読み書き、メモリへのアクセス(読み書き)、演算、比較処理、分岐処理などがあります。
これらを組み合わせてより複雑な処理を作って行くわけです。
例えば、画面に文字を書くという処理は昔のパソコンではVRAM(画面用のバッファメモリ)に値を書き込むことで実現できます。
つまり、直接VRAMに値を書き込むか、レジスタ経由で書き込むか、方法はいくつかありますがそのような処理を行います。
ゲームを作るのであれば、メモリ上にデータやバッファを置いておき、それを操作しながら処理を作って行くわけです。
(実際には画面やサウンドなどを扱うためにライブラリというものがあり、それに値を渡して処理をすることが多いです)
もちろんいきなりゲームを作るのは難しいので、簡単に解説するためにまず計算プログラムを考えてみましょう。
２．アセンブラでの計算方法
計算系の処理には答えを出すためにいくつもの方法があります。
プログラムを作るときにも１つの方法だけで考えるのではなく、他の方法がないかを考えることが大事です。
それぞれの考え方には必ずメリット・デメリットがあります。
実際に作成するときにどちらがよいかを検討することでより良いプログラムが作成できます。
(これはアセンブラに限らず高級言語でも同じことが言えます)
それはどういうことか。
簡単な例である数(χ)を2倍する計算を行うときにどういう計算方法を取るかを考えてみましょう。
まずχ×2を計算する方法は誰でも思いつく方法です。
mul: mulw.w #$02,d0 * D0レジスタの値を2倍する
まずメリットは人間にわかりやすいことです。
人間にわかりやすいということはプログラムミスが少ないということになります。
しかし、この方法はアセンブラのプログラムとしてはあまり良いものではありません。
コンピュータはどのように計算を行うのでしょうか。
コンピュータは基本的に加算、減算と論理計算(論理和や論理積)、ビット操作などを組み合わせて計算を行います。
つまり積算、除算はアセンブラレベルでは用意されていない場合もあるのです。
ここで68でプログラムをかじったことがある人なら反論もあると思います。
「68系なら積算・除算があるじゃないか？」
確かにその通りです。
しかし、これが「Z80」の場合はどうなるでしょうか？
「Z80」のニーモニックには積算、除算命令はありません。
つまり、この方法は「Z80」では使えないのです。
更に68系MPUでもこの命令は使用されるサイクル数(MPUが命令を実行する速度)が非常に遅いのです。
そのため、プログラムのパフォーマンスが悪くなってしまうのです。
計算回数が数回程度ならそれでも問題ありませんが、今回は計算を何度も行うため、この方法は取れません。
ではどうしたらよいでしょうか？
加算と減算だけで2倍する方法を考えてみましょう。
2倍するということは2回同じ数を足すということですよね。
これなら加算だけですので、計算は速くなります。
add: add.l d0,d0 * D0レジスタに現在のD0レジスタの値を加算する
しかし、この方法にも問題があります。
2倍ならいいのですが、例えばこれが10000倍だったらどうなるでしょう。
10000回の加算ループはいくら加算が速いといっても、1回の積算にかないません。
つまりこの方法にも問題がありました。
さぁ、困りました。
どうしましょうかね。
コンピュータでの演算は「2進数」で行われるのが基本です。
(CASIOがかつて出していた「FP1100」は内部10進数演算でしたが…)
内部では数は全てbit単位で「0」or「1」となります。
例えば「10進数」の「100」という数は「16進数」では「64」(6×16＋4)となり、「2進数」ではこれを「1100100」と表記します。
ここでこの「2進数」表記の数を1桁左にずらしてみましょう。
そうすると「1100100」→「11001000」となります。
これを「16進数」に戻すと「C8」となり、「10進数」に戻すと12×16＋8＝200となります。
もうお気づきと思いますが、「2進数」ではbitを左にずらすことによって積算を行うことができるのです。
(逆に右へずらすと除算になります)
ただし、あくまでも「2進数」の桁の重さは「2の乗数」です。
1bitずらすと「2倍」、2bitずらすと「4倍」、8bitずらすと「256倍」になります。
bit: lsl.l #$01,d0 * D0レジスタの値を左に1bitシフトする
では「10倍」したいときはどうすればよいでしょう。
「10倍」するということは「8倍」した数に「2倍」した数を足すことと同じですよね。
これでbit演算で「10倍」することが可能です。
bit演算はアセンブラでは高速な命令ですので、複数の演算を行っても1回の積算より速く計算できるのです。
(もちろんものには限界というものがありますので、余りに複雑な場合は積算1回の方が速いこともあります)
この方法は「C」などの言語でも有効です。
実際「C」でも場合にはよりますが、積算を行うよりbit演算を行った方が高速です。
３．アルゴリズムを考える
さて、計算方法で実行速度に影響があるということはわかりました。
それ以外ではどのようなアプローチがあるでしょうか。
アセンブラでのアルゴリズム(方法)の違いで、どれだけ処理速度に差が出るのでしょう。
これを実感してもらうために、ちょっとした実験をしてみましょう。
そこで、誰でもわかりそうな簡単なものとして「素数」を求めてみました。
「素数」とは？
で、その「素数」を求める方法はもちろんいっぱいあります。
まず簡単な方法を考えてみましょう。
いきなりアセンブラで書くのも分かりづらいと思うので昔懐かしい「BASIC」で上の処理を書いてみたいと思います。
1010 I=2 (１)
1020 J=2 (２)
1030 S=I/J (３)
1040 IF S<>INT(S) THEN 1100 (４)
1050 IF I<>J THEN 1070 (５)
1060 PRINT I; (６)
1070 I=I+1 (７)
1080 IF I>100 THEN END (８)
1090 GOTO 1020 (９)
1100 J=J+1 (１０)
1110 IF I=J THEN 1070 (１１)
1120 GOTO 1030 (１２)
これをもう少し洗練した書き方をするとすれば以下のようになります。
(大して洗練もされていませんけど)
「J」のループも「FOR〜NEXT」構文で書いても問題ありません。
しかしループの抜け出しは「BASIC」では少し面倒なことになる場合があるので、あえて使ってません。
「C」などであれば「break」を使えば問題ありませんがね。
「BASIC」のサンプル
1000 DEFINT A-Z
1010 FOR I=2 TO 100 (１、７)
1020 J=2 (２)
1030 IF (I MOD J)=0 THEN 1060 (３、４、５)
1040 J=J+1 (１０)
1050 IF I>J THEN 1030 (１２)
1060 IF I=J THEN PRINT I; (６)
1070 NEXT I (８、９、１２)
簡単な命令しか使ってませんので大抵のPCで動くと思います。
(「DEFINT」は「C」でいうところの「int」型宣言でこれをやらないと実行速度に影響が出ます)
ですが、もしかすると「MOD」演算(割り算の余りを求める)は機種によって「%」を使うか、そもそも存在しない場合があると思います。
(存在しない場合は割り算を行って得られた「商」に割り数を掛けたものと元値を比較して余りを返すというサブ処理を作る必要があります)
さて、これを実行してみればわかりますが、遅いですｗ
(X1turboで実験したときは10秒くらい掛かりました)
分かりやすいプログラムではあるのですが、やはり実行速度に問題があると思います。
せいぜい抵抗するなら「2」は素数であることがわかりきってますから除外して奇数だけで計算させるともう少しは速くなりますか。
(ちなみにやってみたら、偶数がはぶかれるので大体半分くらいの実行速度にはなります)
どっちにしろ、今時のPCでは流石に「BASIC」というのはちょっとどうよ、ってことで「C」ならどうでしょうね。
(まぁVisualBasicならありかな？)
「C」のサンプル
#include <stdio.h>
int main(void)
{
int i,j;
printf("%5d ", 2);
for (i = 3; i <= 10000; i += 2)
{
for (j = 3; i >= j; j += 2)
{
if ((i % j) == 0)
{
if (i != j)
{
break;
}
else
{
printf("%5d ", i);
break;
}
}
}
}
return 0;
}
この方法のいい点はメモリをほとんど使わないのとシンプルであることでしょう。
しかし、桁数が増えるとどんどん遅くなっていきます。
シンプル故に実行速度には難ありというところでしょうか。
(とはいっても現在のCPUパワーなら1000000程度まで計算させてもいくらもかかりませんけどね)
ちなみにこれをX68000を使ってアセンブラで書いてみたのがサンプルプログラム1になります。
(10000まで計算させてますが、20MHz相当のX68000を使っても結構時間掛かります)
サンプル(X680x0 asm): calc_s1.s
さすがにこれはサンプルとして使うことしかできないパフォーマンスですので、別な方法を考えましょう。
有名なものに「アリストテネスのふるい」というのがあります。
これは「2」から始めて、まず2倍したもの、つまり倍数は計算対象から外します。
同様に更に2倍したものも外します。
こうして全ての「2」の倍数を外します。
次の数「3」も同様に「3」の倍数を外します。
次は「4」ですが、これは最初の「2」の倍数で外されていますので、計算しません。
こうして次々と計算をしていく方法です。
ではこれをプログラムとして考えるとどうなるでしょうか。
プログラムを設計する時は処理とその時の状態でどのような分岐をするかを考えます。
それをまず日本語で考えるとおおまかに以下のようなものになります。
この方法にも欠点があります。
それはフラグを立てるための場所を用意する必要があるということです。
例えば1つの数に1byteを当てたとしても、1000000なら1000000bytesが必要になってしまいます。
つまり、大きな数の計算には不向きな方法なのです。
但し、今回はあえて偶数を省いていませんが、もちろん偶数を省けばフラグスペースは減ります。
またフラグの使い方を工夫することでメモリ消費量は減らせます。
(今回は欠点を強調する意味もあってやってません)
話を元に戻しますが、実際に大きな数の素数計算はどのように行われているのでしょうか。
…実はふるいをゴリ押しでやるのが結局一番だそうです(笑)
メルセンヌ数(Mn=2n-1)に関しては判定法があるのでそれを使うみたい。