ASM Community

Sounds like this is a piece homework, and that you've been sleeping during class... show a tiny bit of effort yourself?

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

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.