This assignment is to write a MIPS assembly language functions to complete three

Question

This assignment is to write a MIPS assembly language functions to complete three of the Hofstadter functions. Most of these will require that you write one recursive function. The last one will require you to write a pair of mutually recursive functions.

1. Hofstadter G Sequence

G(0) = 0

G(n) = n - G(G(n-1)), n>0

2. Hofstadter H Sequence

H(0) = 0

H(n) = n - H(H(H(n-1))), n>0

3. Hofstadter Female and Male sequences

F(0) = 1

M(0) = 0

F(n) = n - M(F(n-1)), n>0

M(n) = n -F(M(n-1)), n>0

Code should include comments about what it is doing and what the registers are being used for, program should exit cleanly.

Explanation / Answer

.globl main
.data
#assign message String to variable

msgtext: .asciiz "Enter a value for n"

.text
main:

la $t0, msgtext # load address of msgprompt into $t0

lw $a0, 0($t0) # load data from address in $t0 into $a0
li $v0, 4 # call code for print_string
syscall # run the print string syscall

move    $a0,$t0       # assign input to argument register $a0
addi $sp, $sp, -12 # move stack pointer up 3 words
sw $a0, 0($sp) # store input in top of stack
sw $ra, 8($sp) # store counter at bottom of stack
jal GS_F      # call G(n)

lw    $s0, 4($sp)   #load return value in 4($sp)
addi $sp, $sp, 12 # move stack pointer back down where we started

#terminate main program
li $v0, 10 # system call for exit
syscall # run exit system call

.text
GS_F:

addi $sp,$sp, -8   # allocate space on Stack

lw    $t0, 0($sp)       #load input from top of the stack
beq    $t0,0, returnZero    #if n==0 return 0
addi    $t0,$t0,-1       # n =n-1 elsewise

addi $sp, $sp, -12 # move stack pointer up 3 words
sw $t0, 0($sp) # store current working number into the top of the stack segment
sw $ra, 8($sp) # store counter at bottom of stack segment

jal GS_F    # recursive call

lw $ra, 8($sp) # load this call's $ra again(we just got back from a jump)

lw $ra, 8($sp) # load this call's $ra again(we just got back from a jump)
lw $t1, 4($sp) # load child's return value into $t1

lw $t2, 12($sp) # load parent's start value into $t2

sub    $t3, $t1, $t2 # subtract child's return value by parent's working value, store in $t3.

sw $t3, 16($sp) # take result(in $t3), store in parent's return value.

addi $sp, $sp, 12 # move stackpointer back down for the parent call

jr $ra # jump to parent call

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.