【アセンブリ】100番目までの素数を求めるプログラムを作ってみる【MIPS】

手順

素数を最初から100番目まで求めてプリントするMIPSのアセンブリ言語プログラムを作ってみる。

素数を求めるために、2つのルーチンを作る

prim(n) - nが素数であれば1を返し、そうでなければ0を返す
main() - 整数を順々に繰り返し調べて、素数であるかどうかを判定する。得られた素数を最初から100個まで出力する

C言語のサンプル

Cのサンプルに沿って考えながらアセンブリに人力で翻訳してみる。

int prime(int n)
{
  int i;
  for (i = 2; i < n; i++){
    if (n % i == 0)
      return 0;
  }
  return 1;
}

int main()
{
  int match = 0, n = 2;
  while (match < 100){
    if (prime(n) == 1){
      printf("%d",n);
      printf(" ");
      match++;
    }
    n++;
  }
  printf("\n");
}

実行結果は以下

$ gcc prime.c
$ ./a.out
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

これを目指して人力コンパイル。。。よし。。。笑

翻訳していく - main編

まずはmain()関数（ルーチン）から作った。

前のwhileの練習で作ったソースコードをベースにしながら作ってみる。

        .data
space:  .asciiz " "        
        .text
        .align 2
main:   li    $s0, 100        # set maximum number 
        li    $s1, 0          # number of loop
        li    $s3, 2          # number to check and print (n)
        li    $s7, 1          # for comparing
Loop:   beq   $s0, $s1, Exit  # break if $s1==100
        jal   prime           # $v0 = prime
        bne   $v0, $s7, Else  # go to Else if prime(n)!=1
        li    $v0, 1          # for syscall of print_int
        li    $a0, $s3        # put the prime number
        syscall               # print the prime number
        li    $v0, 4          # for syscall of print_string
        li    $a0, space      # " "
        syscall               # print " "
        addi  $s0, $s0, 1     # increase the number of prime number
Else:   
        addi  $s3, $s3, 1     # n = n + 1 
        j     Loop            # go to Loop
Exit:   j     $ra

こんな感じになった。うん、アセンブリなんか、原始的でいいな笑ただ、Loopとかif分岐とかは概念としてしか表せないので、そこの書き方とかはかなりプログラマー次第な感じがする。

書くときに意識したことは最後にまとめようと思う。

Cで13行だったmain関数の部分はだいたい27行になった。約２倍。（この比率の名前なんて言うんだっけ笑）

prime関数を作る前に、なんかテストしてみよう。

prime()は常に１を返す、つまり全ての数は素数だという結果が返ってくるって感じに設定して、かつ繰り返す回数を10にしてステップ実行しながら挙動を確かめてみる。

バグをいくつか発見。まず、レジスタ同士の値をコピーする時もliを使ってた。あと、ループを抜ける設定がなんかおかしい。これだと無限ループになる。。。

ということで修正して、さらにテストバージョンに改変したのが以下。

        .data
space:  .asciiz " "        
        .text
        .align 2
main:   li    $s0, 10         # set maximum number (match number)
        li    $s1, 0          # number of loop
        li    $s3, 2          # number to check and print (n)
        li    $s7, 1          # for comparing
Loop:   beq   $s0, $s1, Exit  # break if $s1==100
        # jal   prime           # $v0 = prime
        # bne   $v0, $s7, Else  # go to Else if prime(n)!=1
        li    $v0, 1          # for syscall of print_int
        move  $a0, $s3        # put the prime number
        syscall               # print the prime number
        li    $v0, 4          # for syscall of print_string
        la    $a0, space      # " "
        syscall               # print " "
        addi  $s1, $s1, 1     # increase the number of prime number
Else:   
        addi  $s3, $s3, 1     # n = n + 1 
        j     Loop            # go to Loop
Exit:   j     $ra

出力は以下のようになった。

2 3 4 5 6 7 8 9 11

思惑通り2を先頭に10個出力された。

とりあえずmainの部分はできた！！！よっしゃ！！！！

翻訳していく - prime関数編

ということで次は素数かどうかを判定するprime関数を作っていくことにする。

prime関数はCではこんな感じだった。

int prime(int n)
{
  int i;
  for (i = 2; i < n; i++){
    if (n % i == 0)
      return 0;
  }
  return 1;
}

ひたすらiを1ずつ増やしながら全部で割っていくという肉弾戦（笑）

ここのアルゴリズムはもうちょっとうまいこといく気もするけど、とりあえずこの方法に従って実装を進めてみよう。

とりあえず第一弾はこんな感じ。エラーは出なかったので実行してみる。

            .text
            .align 2
prime:      li    $t0, 2          # number to loop and divide (i)
Loop_prime: beq   $t0, $s3, Exit_prime # break the loop if i == n
            rem   $t1, $s3, $t0   # $t1 = n % i
            beqz  $t1, Exit_prime # goto Exit_prime if $t1 == 0
            j     Loop_prime
            li    $v0, 0          
            j     $ra             # return 0 
Exit_prime: li    $v0, 1         
            j     $ra             # return 1

# ここまで追加

            .data
space:      .asciiz " "        
            .text
            .align 2
main:       li    $s0, 10         # set maximum number (match number)

# 
# こっからmainなので省略
#

2が表示されてから、無限ループ笑

ということでステップ実行してエラーを確かめて該当箇所をなおしていく。

いろいろと間違いはあったけど、主な原因はiをインクリメントしてなかったっぽい。for文を読んで翻訳するときの落とし穴。。。笑

ということで、最終盤のソースコードをあげておきます。

*以下の記事を参考にしながらきちんと呼び出し手続き規約に従って書き直してみた(2014/11/25)

【アセンブリ】再帰で10の階乗を求めるプログラムを通して手続き呼び出し規約を理解する学習ノート【MIPS】 - 凸ろぐ

100までの素数を求めて表示するプログラム(アセンブリ言語）

行数は36行。もともとのC言語が23行なのでprime()部分はそんなに行数かからなかったらしい。

ん！なかなかいいんじゃないかな！！笑