Ackermann function

アッカーマン関数という関数があります。
バカ正直に計算しようとするとすぐ計算量が膨大になり、計算できなくなるたぐいの関数です。

これをアセンブリでバカ正直に計算させるコードを書いてみました。階乗を計算させるコードのおまけ付きです。

実際に実行させたところ、ack(3, 12) あたりになるとスタックがあふれました。
スタックサイズを調整すればもうちょっといけると思います。

使用した高速化のテクニック

• 末尾再帰を CALL から JMP に置き換え
• TEST+JE でmacro fusion できる命令形式にした
• INC / DEC を ADD / SUB に置き換えて、フラグレジスタの依存関係を解消
• MOV RDX, 1 を MOV EDX, 1 にして命令長を短縮

    .code

ack PROC public

    ; RCX = m, RDX = n
    TEST    RCX, RCX
    JE      m_zero

    TEST    RDX, RDX
    JE      n_zero

    PUSH    RCX
    SUB     RDX, 1
    CALL    ack
    POP     RCX
    SUB     RCX, 1
    MOV     RDX, RAX
    JMP     ack

n_zero:
    MOV     EDX, 1
    SUB     RCX, 1
    JMP     ack

m_zero:
    MOV     RAX, RDX
    ADD     RAX, 1
    RET

    ack ENDP

factorial PROC public
    
    MOV     EAX, 1
    CMP     RCX, 1
    JLE     f_ret

f_loop:
    IMUL    RAX, RCX
    SUB     RCX, 1
    CMP     RCX, 1
    JNLE    f_loop

f_ret:

    RET

    factorial ENDP

    END

一応 C で書いた以下のコードよりは、3割ぐらい速いようです(Visual C++ 2010 で /O2 としてコンパイル)。階乗は微妙に速いだけでほとんど変わりませんでした。CPU は Penryn ベースの Core2 Duo です。

int64_t factorial_c(int64_t n)
{
    int64_t r = 1;
    while(n > 1) r *= n--;
    return r;
}

int64_t ack_c(int64_t m, int64_t n)
{
    return m == 0 ? n + 1 : n == 0 ? ack_c(m - 1, 1) : ack_c(m - 1, ack_c(m, n - 1));
}