hi. a have a task " Floating point reciprocal square root of integer number without using FP unit. " , and i dont know which algorith should i implement? a have to use MIPS assembly language...
Posted on 2006-11-09 16:40:43 by metoda
Sounds like this is a piece homework, and that you've been sleeping during class... show a tiny bit of effort yourself?
Posted on 2006-11-09 17:24:44 by f0dder
yeah, its my laboratory task, but i do not ask for code in MIPS, but i ask which algorithm of square root should i take , to be easy to implement in MIPS.. nothing more
Posted on 2006-11-09 17:52:19 by metoda
Hi, here is an implementation for integer sqarre root using x86_64 assembler, maybe it will help...

  .file "math.S"
  .text

//
// long new_sqrt( long value );
//
// abstract    fast integer square root algorithm.
//            Compliant to the x86_64 ABI.
// in          rdi = value
// out        rax = integer square root of value
//
  .align  2
new_sqrt:
  pushq    %rcx
  pushq    %rdx

  xorq    %rax, %rax          // c = 0
  movq    $0x40000000, %rcx    // b = 0x40000000

.L1:
  cmpq    $0, %rcx            // b == 0
  je      .L3                  // yes: done

  movq    %rax, %rdx          // t = c
  addq    %rcx, %rdx          // t += b
  sarq    %rax                // c >>= 1

  cmpq    %rdi, %rdx          // r > t
  jg      .L2                  // yes: next

  subq    %rdx, %rdi          // r -= t
  addq    %rcx, %rax          // c += b

.L2:
  sarq    $2, %rcx            // b >>= 2
  jmp      .L1                  // next guess

.L3:
  popq    %rdx
  popq    %rcx
  ret

  .size    new_sqrt, . - new_sqrt
  .type    new_sqrt, @function
  .globl  new_sqrt
Posted on 2006-11-09 21:32:43 by llaurrentt
thanks a lot, but x86 i will have during second half of the semester and do not understand this code at all :(
Posted on 2006-11-10 02:48:38 by metoda
You can use the property of square sum decomposition: (a+b)^2 = a^2+2ab+b^2.
I only know the algorithm for doing this by hand in a decimal base, but it shouldn't be too hard to implement in software using binary base.

1) split the input number by groups of two digits starting at the decimal point. (e.g. 324 will become 3 and 24, lets call them X and Y. )
2) find a digit, square of which will be less or equal to X. let's call this number Z (=1)
3) subtract it from the X (now X = 2)
4) combine the result with the remaining digit pair Y. (we got 224)
5) do 2Z^2 (=2)
6) find a number which if combined with the result of previous step and multiplied by itself will yield result smaller/equal to the result of 4th step. (in this case it's 8. i.e. 28*8 = 224 => 224 = 224. )
7) repeat the algorithm. (in this example we got a result already, so no need to repeat anything. square root of 324 is 18.)

So in this particular case: a=10*1 and b=8. And indeed: (2*1*10+8)*8=2*1*10*8+8^2 conforms with 2ab+b^2.
Posted on 2006-11-10 02:49:42 by arafel
thanks, but i wonder if it is easy to implementi in mips ;/ any other ideas ?
Posted on 2006-11-10 06:28:30 by metoda