MIPSアセンブリ言語による階乗の計算

目的

大学の課題として、階乗の計算をMIPSアセンブリ言語で書けとの課題が出された。
100!まで計算させるだけでも文献が少なく、chatgptも誤った答えばかり出してくるため、後々見返せるように記載しておくことを目的に本記事を作成した。そのためMIPSの説明等は省略(他の詳しい方々にお願いさせていただく)し、コードと概要を記載することとする。なお、実行できることだけをメインに記載したため、詳しい方が見たらおそらく怒られうるコードを書いている場合がある。

到達基準

実行後、"Input a number:"の表示を行ったのちに整数の入力を待機する。計算後、 "Output: "を表示し、結果を表示する。
100!を正しく計算する。

妥協

0! = 01, 1! = 01 2! = 02, 3! = 06, 10! = 03628800のように、出力する時に無駄な0を表示するのはOKとする。

コード

SPIM Version 8.0

.data 
result: .word   0:200
usd:    .word   0
prmp:   .asciiz "Input a number: "
oupr:   .asciiz "Output: "
zero: .asciiz "0"

.text
.align 2
.globl main
.ent main
#原理上は100!以上も計算できるが、ここでは100!が計算できれば良いということにする。
main:
        addi    $sp, $sp, -16           # mainのスタックフレーム確保
        sw      $ra, 12($sp)            # mainのraを保存
        li      $v0, 4                  # $v0 = 4
        la      $a0, prmp               # $a0 = prmp
        syscall                         # prmpを表示
        li      $v0, 5                  # intの要求
        syscall                         # syscall
        move    $a0, $v0                # もらったintを$a0に
        la      $t0, result             # $t0 = resultのアドレス
        lw      $t1, 0($t0)             # $t1にresult[0]を格納
        addi    $t1, $t1, 1             # $t1 = 1
        sw      $t1, 0($t0)             # $t1をresult[0]のアドレスに保存
        jal     factorial               # factorialの呼び出し
        jal     print_result            # print_resultの呼び出し
        lw      $ra, 12($sp)
        addi    $sp, $sp, 16
        jr      $ra

factorial:
        addi    $sp, $sp, -16           # factorialのスタック確保 
        sw      $ra, 12($sp)            # factorialのraを確保
        li      $s0, 1                  # $s0 = 1
        move    $s1, $a0                # $s1 = $a0
    factorial_loop:
        bgt     $s0, $s1, factorial_end # 引数よりもs0がおおきくなったら終了
        move    $a0, $s0                # $a0 = $s0
        jal     multiply                # call multiply
        addi    $s0, $s0, 1             # $s0 += 1
        j       factorial_loop          # factorial_loopへとぶ
    factorial_end:
        lw      $ra, 12($sp)            # factorial ra の復活
        addi    $sp, $sp, 16            # factorialのスタックの解放
        jr      $ra                     # raへの復帰

multiply:
# $t0 address of result
# $t1 address of usd
# $t2 integer value of usd
# $t3 carry
# $t4 value to be stored to result
# $t5 counter
# $t6 temporary
        addi    $sp, $sp, -16            #スタック確保
        sw      $ra, 12($sp)            #リターンアドレスの保存
        sw      $s0, 8($sp)
        sw      $s1, 4($sp)
        la      $t0, result             #result[0]のアドレス読み込み
        la      $t1, usd                #usdのアドレス読み込み
        lw      $t2, 0($t1)             #usdのデータ読み込み
        li      $t3, 0                  #carryの初期化
        li      $t5, 0                  #カウンタiの初期化
    multiply_loop:
        bgt     $t5, $t2, carry_check   #カウンタiの値がusdを上回ったらcarry_checkへ
        lw      $t4, 0($t0)             #result[i]の読み込み
        mul     $t4, $t4, $a0           #result[i]と引数a0の掛け算
        add     $t4, $t4, $t3           #result[i]へのキャリーの加算
        li      $t6, 100
        div     $t4, $t6                # result[i] / 100
        mflo    $t3                     # $t3(キャリー) = result[i] / 100
        mfhi    $t4                     # $t4(result保存用) = result[i] % 100
        sw      $t4, 0($t0)             # resultの保存
        addi    $t5, $t5, 1             # カウンタのインクリメント
        addi    $t0, $t0, 4             # 配列resultの次要素へのアクセス(オーバーは考慮していない)
        j       multiply_loop            # jump to multiply_loop
    carry_check:
        beqz    $t3, multiply_ret       #キャリーがループ脱出時点でないのなら復帰の処理へ移る
        addi    $t2, $t2, 1             #usdの拡張
        sw      $t2, 0($t1)             #usdの保存
        sw      $t3, 0($t0)             #キャリーを拡張後のところへ保存
    multiply_ret:
        lw      $s1, 4($sp)
        lw      $s0, 8($sp)
        lw      $ra, 12($sp)
        addi    $sp, $sp, 16
        jr      $ra

print_result:
        addi    $sp, $sp, -16
        sw      $ra, 12($sp)
        la      $t0, result
        la      $t1, usd
        lw      $t2, 0($t1)
        sll     $t2, $t2, 2             # $t2 = $t2 << 2
        add     $t0, $t0, $t2           # resultの末尾のアドレス
        lw      $t4, 0($t1)             # usdの値を取得
        li      $v0, 4
        la      $a0, oupr
        syscall
    print_result_loop:
        bltz    $t4, print_result_ret   # 添字が0以下なら終了
        lw      $t3, 0($t0)             # resultの中身の取得
        move    $a0, $t3                # a0 = $t3
        li      $t5, 10                 # $t5 = 10
        bgt    $a0, $t5, sk            # 今から表示したい値が10以上ならそのまま表示する.そうでなければ桁取り0を表示
        sw      $a0, 8($sp)             # $a0の保存
        li      $a0, 0                  # $a0=0
        li      $v0, 1                  #
        syscall
        lw      $a0, 8($sp)             #$a0を復活
        
    sk:
        li      $v0, 1                  # print int
        syscall
        addi    $t0, $t0, -4            # 一個戻る
        addi    $t4, $t4, -1            # 添字を一つ落とす
        j       print_result_loop       # jump to print_result_loop
    print_result_ret:
        lw      $ra, 12($sp)
        addi    $sp, $sp, 16
        jr      $ra

コメント

C言語でいうところの

#include <stdio.h>
#define MAX 500
int result[MAX];
int result_size = 1;

void multiply(int x) {
    int carry = 0;  // Initialize carry
    for (int i = 0; i < result_size; i++) {
        int prod = result[i] * x + carry;
        result[i] = prod % 10;  // Store last digit of 'prod' in result
        carry  = prod / 10;  // Put rest in carry
    }
    while (carry) {
        result[(result_size)++] = carry % 10;
        carry = carry / 10;
    }
}

void factorial(int n) {

    for (int x = 2; x <= n; x++) {
        multiply(x);
    }

    // Print the result in reverse order
    printf("Factorial of %d is: ", n);
    for (int i = result_size - 1; i >= 0; i--) {
        printf("%d", result[i]);
    }
    printf("\n");
}

int main() {
    int res;
    result[0] = 1;
    printf("Enter a number: ");
    scanf("%d", &res);
    factorial(res);
    return 0;
}

のようなやつをゴニョゴニョ弄ってとりあえず実行できる形に落とし込んだ感じ。
位取りのゼロの表示のためにprint_resultの中でskの分岐を行っている。
二回連続で実行すると値がバグる。例えば、このコードを読み込んで10の階乗を2回計算すると、1回目は正しいものが表示され、2回目の結果は誤ったものとなる。これはresultを毎回の実行で初期化するように設定していないためであると考えられる。

感想

アセンブリ言語のコードをchatgptに書かせるのはまだ厳しい部分がある(5回聞いたうち、自分でコードの8割を書いたもの以外は誤った回答であった。)
MIPSと聞いてものすごく恐怖を感じていたが、実際に触れてみて、MIPSにもMIPSの利点があるのを感じた。(とは行っても、CとかJavaの方が処理をよりざっくりとしたもので書けるからそっちの方が好きだが)
とりあえず手を動かして、脳死状態でもCとMIPSの変換ができるように訓練する。