0

Hi I need help in coding in MIPS. I have to find the Floor Square root of the n input. I have the C version of the code..

uint32_t isqrt(uint32_t n) {
  if(n<2) return n;
    uint32_t s = isqrt(n >> 2) << 1;
    uint32_t l = s + 1;
  if (l * l > n) 
    return s;
  else
    return l;
}

apparently it recurses itself..

Right now my function looks something like. Im not really sure what I am doing wrong

#isqrt
isqrt:
#prologue
subu    $sp, $sp, 12
sw  $ra, 8($sp)
sw  $s0,  4($sp)
sw  $s1, 0($sp)

#if(n<2) n Branch if Greater Than 2
blt     $a0, 2, lt2 #if(n<2) return n;
#else uint32_t small = isqrt(n >> 2) << 1;       
srl     $s0, $a0, 2  # small = isqrt(n >> 2)
jal     isqrt
sll   $s0, $s0, 1 # then  << 1 

add    $s1, $s0, 1 # large = small + 1
li     $s3, 0
mul     $s3, $s1, $s1 # large = large * large\
#if large * large > n return small else return large
bgt     $s3, $s0, small # if l * l > n return small
move    $v0, $t1 # else return large

lt2:
move $v0, $a0;
j end

small:
move $v0, $s0
j end

end:
lw $ra, 8($sp)
lw $s0, 4($sp)
lw $s1, 0($sp)
addi $sp, $sp, 12
jr      $ra
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
uknown11
  • 1
  • 1
  • Shouldn't that first bgt be a blt if you want to branch if it's less than 2? – Joachim Isaksson Nov 27 '22 at 21:23
  • yeah i noticed that too, edited my code now, but think it still doesnt work right now – uknown11 Nov 27 '22 at 22:24
  • You might be able to adapt something from here... https://stackoverflow.com/questions/65986056/is-there-a-non-looping-unsigned-32-bit-integer-square-root-function-c/70550680#70550680. My code from here https://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer/74416232#74416232 is comparatively slow but only uses simple operations, and is 64bit. – Simon Goater Nov 27 '22 at 22:48
  • 2
    Please do not vandalize your posts. By posting on the Stack Exchange network, you've granted a non-revocable right for SE to distribute that content (under the [CC BY-SA 4.0 license](https://creativecommons.org/licenses/by-sa/4.0/)). By SE policy, any vandalism will be reverted. – tripleee Nov 28 '22 at 05:45
  • Your last edit was almost ok, but you changed the `lt2` and `small` label names without changing the branches that target them. So the code was no longer a [mcve] of anything and wouldn't assemble. It's also not great to remove comments which explain the algorithm you're implementing, and definitely makes the question worse. I'm not sure whether an edit like that would be ok. I considered leaving it alone, and probably would have if you hadn't broken the code itself. – Peter Cordes Nov 28 '22 at 22:55

1 Answers1

2

Good effort, but many, many, many errors.  Suggest trying a more methodological approach.  Check your choices of registers, you register numbers, and prologue/epilogue code for proper handling of the various register kinds.

  • That code is doing if (n>=2) return n; — the exact opposite of the C code.

  • The called function isqrt expects a formal parameter in $a0, but that code is passing the actual argument in $t0, so there's a mismatch.

  • The called function isqrt provides the return value in $v0, but when calling that recursively, expects it to have been provided in $t0, another mismatch.

  • The function uses $s0, but fails to ensure its value is call-preserved as it should have been.

The following code:

li      $t0, 2        # small = isqrt(n >> 2) << 1
srl     $t0, $t0, 2
  • generates 2>>2, which is clearly different from the n>>2 in the C code.

The following code:

equal:
move $v0, $t1
j end
  • is doing return l*l; where the C code wants return l;

I'd suggest starting with an analysis of what registers to use for what variables — this analysis requires examining liveness across the (recursive) function call.  Start that analysis on the C version initially.  When you're finished with that, you'll have a mapping of register numbers for all the C variables.  Then write prologue/epilogue that handle those registers as required.  Then translate the C code line by line into assembly paying careful attention to what variables are in what registers, and what expressions you're trying to recreate in assembly.

Erik Eidt
  • 23,049
  • 2
  • 29
  • 53
  • i had edited and commented to make sure I am using the right registers. not sure whats still wrong. what did you mean by srl not generating the same thing as in the mips? shouldnt it be shiftinh the t0 by 2? – uknown11 Nov 27 '22 at 22:32
  • You're using `blt` and `bgt` which are signed, use `bltu` and `bgtu` instead. What test values are you using? – puppydrum64 Nov 28 '22 at 14:52
  • @puppydrum64, great catch! But that comment belongs on the question post, as I would point out that's where those incorrect instructions are written. To my points though, the code is so broken as it stands that sign vs. unsigned won't help yet until these other problems are resolved. We would expect signed vs. unsigned to matter when inputs go very large. – Erik Eidt Nov 28 '22 at 15:31
  • @ErikEidt Ah yes, I comment on the wrong one quite often. Whoops! – puppydrum64 Nov 28 '22 at 15:32
  • @puppydrum64, still, great catch! – Erik Eidt Nov 28 '22 at 15:32
  • @ErikEidt Sometimes I'm not sure since I've only ever worked with N64 and PS1 so I don't know if something has changed between those versions of MIPS and the more recent ones. – puppydrum64 Nov 28 '22 at 15:33