.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 < yx sw $s1, 4($sp) # call GCD(x, (yx)) # after returning from GCD(x, (yx)) 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 < xy 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
GCD alg rec... help
Page 1 of 14 Replies  5209 Views  Last Post: 19 December 2012  02:44 PM
#1
GCD alg rec... help
Posted 18 December 2012  09:44 AM
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.
Replies To: GCD alg rec... help
#2
Re: GCD alg rec... help
Posted 18 December 2012  03:19 PM
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:
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:
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
#3
Re: GCD alg rec... help
Posted 18 December 2012  03:44 PM
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
#4
Re: GCD alg rec... help
Posted 19 December 2012  08:22 AM
BTW: where is the promised call?
sub $s1, $s1, $s0 # $a1 < yx
sw $s1, 4($sp) # call GCD(x, (yx))
# after returning from GCD(x, (yx))
sub $s1, $s1, $s0 # $a1 < yx
sw $s1, 4($sp) # call GCD(x, (yx))
# after returning from GCD(x, (yx))
#5
Re: GCD alg rec... help
Posted 19 December 2012  02:44 PM
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?
Can someone check whether this program is written in recursive style or is it wrong?
Page 1 of 1
