Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Exercise in MIPS assembly language: compute the two-argument Ackermann function.
#!/usr/bin/spim -file
# ackermann.asm
# (c) 2015 Michael F. Lamb <http://datagrok.org>
# License: AGPLv3+
#
# A naive implementation of the two-argument Ackermann function:
#
# / n+1 if m = 0,
# A(m,n) = { A(m-1, 1) if m>0 and n=0,
# \ A(m-1, A(m,n-1)) if m>0 and n>0.
#
# Details: https://en.wikipedia.org/wiki/Ackermann_function
#
# Which was kindof silly, given how fast Ackermann grows and we're only working
# with integers.
# Implementation notes:
#
# This uses recursion, so with large enough input values it is possible to
# exhaust the stack and crash. Ackermann grows rapidly too; on my relatively
# fast 1.9Ghz Core i5 4300U laptop:
#
# - attempting to compute A(4,1), A(3,11), or anything larger crashes after
# about 4m25s. A(4,2) should equal 2**65536-3, which will certainly not work,
# as there's no mechanism for large integers in this code.
# - A(4,0) = 14 is successfully computed in less than a second.
# - A(3,9) = 4093 is successfully computed in 17s.
# - A(3,10) = 8189 is successfully computed in 1m9s.
#
# A non-naive implementation would store the result of previous computations to
# re-use instead of recursively re-calculating them. It might also employ a
# mechanism to deal with bignums (integers larger than what will fit in a MIPS
# register.) It might also do something besides silently die when the stack
# overflows.
#
# I use "add (register) (register) (immediate)" below. Technically that's
# syntactically incorrect; I should be using "addi" (add immediate.) But I
# think spim is smart enough to auto-convert that into the right code by
# examining the arguments? Same for "sub (register) (register) (immediate)."
.text # begin text segment,
.globl main # so "main" can be found
# Ackermann subroutine.
#
# Call with m in $a0, n in $a1. Result A(m,n) will be stored in $v0.
Ackermann:
# We'll be using jal (which modifies $ra), and $s0 so we need to back up
# the current value of $ra and $s0 onto the stack. If we were using
# frame-based linkage convention here, we'd also want to backup $fp.
# Prologue: backup registers to stack before modifying them.
sub $sp,$sp,8 # make room on the stack for the following 2 variables (4 bytes each)
sw $s0,4($sp) # store old $s0 at $sp+4
sw $ra,0($sp) # store old $ra at $sp+0
# Ackermann Logic
bgtz $a0,_Ack_b # If m > 0, skip over these next instructions.
# Case for m = 0:
add $v0,$a1,1 # - result = n+1
j _Ack_end # - jump to end of conditional
_Ack_b:
bgtz $a1,_Ack_c # if n > 0, skip over these next instructions.
# Case for m>0 and n=0:
sub $a0,$a0,1 # - prep m = m-1
li $a1,1 # - prep n = 1
jal Ackermann # - with m-1 in $a0 and 1 in $a1, call Ackermann
j _Ack_end # - its result will be in $v0, just return it.
_Ack_c:
# Case for m>0 and n>0:
# We need to make two recursive calls to Ackermann, but after the first,
# our register $a0 holding m may be modified. So we hang onto a copy of m
# in $s0.
move $s0,$a0 # - copy m to $s0
sub $a1,$a1,1 # - prep n = n-1. $a0 already contains m.
jal Ackermann # - with m in $a0 and n-1 in $a1, call Ackermann
move $a1,$v0 # - prep n = result of A(m, n-1)
sub $a0,$s0,1 # - prep m = m-1
jal Ackermann # - with m-1 in $a0 and A(m, n-1) in $a1, call Ackermann
# - no need to jump, fall through to _Ack_end
# Epilogue: restore original registers before returning. Then return.
_Ack_end:
lw $s0,4($sp) # restore old $s0
lw $ra,0($sp) # restore old $ra
add $sp,$sp,8 # remove those from stack
jr $ra # return to caller
# Main subroutine (standard entry point.)
#
#
main:
# This is mostly user-interface tedium. Print some prompts, read two
# integers for input, call the Ackermann subroutine with those as input,
# print the output, and exit.
# print the first input prompt
la $a0,p1 # - address of input prompt
li $v0,4 # - system call to print string: 4
syscall # - fire
# read an integer (m)
li $v0,5 # - system call to read integer: 5
syscall # - result will be stored in $v0
move $t0,$v0 # - so copy it to $t0 (we still need to use $a0)
# print the second input prompt
la $a0,p2 # - address of input prompt
li $v0,4 # - system call to print string: 4
syscall # - fire
# read an integer (n)
li $v0,5 # - system call to read integer: 5
syscall # - result will be stored in $v0
move $a1,$v0 # - so copy it (n) to $a1
move $a0,$t0 # - and copy $t0 (m) to $a0
jal Ackermann # with m in a0 and n in a1, call Ackermann(m, n)
# once we return here, $v0 contains the result
# print the integer result
move $a0,$v0 # - copy result from $v0 (above) to $a0
li $v0,1 # - system call to print integer: 1
syscall # - fire
# print a newline:
la $a0,nl # - address of newline
li $v0,4 # - system call to print string: 4
syscall # - fire
# exit program:
li $v0,10 # - system call to exit: 10
syscall # - fire
#------------------------------------------------------------------------------
.data # begin data segment
p1: .asciiz "Ackermann function A(m,n)\nValue for m: "
p2: .asciiz "Value for n: "
nl: .asciiz "\n"
# vim: set et ts=4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment