[akerman]

Hi, trying to write code for binary gcd which is recursive however I'm not sure why my code is wrong... Can someone check and maybe adjust the code for me to work, it may have only a smaller error which I cannot see... thanks. code is below.

.data
prompt: .asciiz "Enter a number: "
answer: .asciiz "\nGCD = " # answer =
 .text
 .globl main

main:

 li $v0, 4 # display prompt
 la $a0, prompt
 syscall

 li $v0, 5 # get number from user
 syscall
 add $s0, $v0, $zero # store 1st in s0

 li $v0, 4 # display prompt
 la $a0, prompt
 syscall

 li $v0, 5 # get number from user
 syscall
 add $s1, $v0, $zero # store 2nd in s1


GCD: 
	subi $sp, $sp, 12 # create stack frame
	sw $s0, 0($sp) # save x
	sw $s1, 4($sp) # save y
	sw $ra, 8($sp) # save return address
# if x != y, jump to ‘rec’
	bne $a0, $a1, rec
# if x == y, return x
	move $v0, $s0 # $v0 <- x
	addi $sp, $sp, 12 # destroy stack frame
	j end # return

# The recursion begins
rec:
	bgt $s0, $s1, xgty # if x > y, jump to xgty
xlty: 
	sub $s1, $s1, $s0 # $a1 <- y-x
	sw $s1, 4($sp) # call GCD(x, (y-x))
	
	# after returning from GCD(x, (y-x))
	lw $s0, 0($sp) # restore x
	lw $s1, 4($sp) # restore y
	lw $ra, 8($sp) # restore return address
	addi $sp, $sp, 12 # destroy stack frame
	j GCD # return
xgty:
	sub $s1, $s1, $s2 # $a0 <- x-y
	sw $s1, 0($sp)
	
	lw $s0, 0($sp) # restore x
	lw $s1, 4($sp) # restore y
	lw $ra, 8($sp) # restore return address
	addi $sp, $sp, 12 # destroy stack frame
	jr $ra
end:
 li $v0, 4 # display prompt
 la $a0, answer

[blackcompe]

Your code is overcomplicated. It appears that you're implementing Dijkstra's algorithm, however, I'd highly suggest implementing Euclidean GCD, which is the easiest to do (at least in terms of assembler). You can find the algorithms here.

I see you're doing a lot of stack pushes so that you don't lose the function arguments every time you make a recursive call. This is why the Euclidean algorithm is more concise (13 lines). The only thing you need to push is the return address. Take a look at it:

int gcd(int m, int n) {
   if ((m % n) == 0)
      return n;
   else
      return gcd(n, m % n);
}

From the looks of things, you'd probably save yourself time if you just started over. If you do decide to take the route, here's the basic algorithm:

gcd:
     #push return addr
     #div a0 a1, mfhi t0
     #beq t0 return_a1
     #move a0 a1, move a1 t0, call gcd, exit

return_a1:
     #move v0 a1

exit:
     #load return addr, return

[akerman]

the problem is I need binary GCD in recursive style to make my other part to work, so thats why I need my code to be working. Can You or someone else have a look at it and modify it? please

[turboscrew]

BTW: where is the promised call?

sub $s1, $s1, $s0 # $a1 <- y-x
sw $s1, 4($sp) # call GCD(x, (y-x))

# after returning from GCD(x, (y-x))

[akerman]

its just a comment so it stores the value and then goes on with the instruction... do you think it needs changing?
Can someone check whether this program is written in recursive style or is it wrong?