Sqrt of a Integer in Assembler

Question

I am planning to create the sqrt of a integer so I think we have to consider the only the pre comma part. I am using nasm 64bit. So I already have create a pseudo code that looks like that:

a := value
b := 0
while (a-b)>1
         a := ((a+b)/2)
         b := (value/a)
end_while
result := min{a,b}

mathematically it looks like:

x = max{x ϵ Z | x**2 <=z}

I create this pseudo code to understand the math to implement it but stuck now

It looks like this has already been solved before: http://codereview.stackexchange.com/questions/48847/integer-square-root-in-x86-assembly-nasm — Matthew, Jun 05 '14 at 20:12
You've got good pseudo code... break it down further and begin coding individual steps... start from the inside if you like: x=a+b; x=x/2, y=value/x ... convert to registers... RAX = (a) + (b) (add) , RAX = RAX / 2 (idiv or div), RBX=RAX, RAX=value / RBX (idiv/div again)... don't try to streamline or improve ... make it WORK first... plenty of registers... little steps, you'll get it. Perhaps have a look at another of my posts about multiplying values in assembly: http://stackoverflow.com/questions/11270118/multiplying-two-values-and-printing-them-to-the-screen-nasm-linux/11282330#11282330 — lornix, Jun 05 '14 at 20:17
I'm not too familiar with assembly, but I am guessing the first argument on the stack. — Matthew, Jun 05 '14 at 20:56
[esp+4] refers to the memory location, which is addressed by the sum of contents of register esp (the stack pointer) and 4 — Deleted User, Jun 05 '14 at 21:00

score 0 · Answer 1 · answered Jun 06 '14 at 10:47

I presume that you want as result also an integer. For the files:

; uname -m -o:          x86_64 GNU/Linux
; Calling convention:   System V AMD64 ABI
; Name:                 isqrt.asm
; Assemble:             nasm -felf64 isqrt.asm
; Link:                 gcc -m64 isqrt.o
; Run:                  ./a.out

; b := value
; a := 0
; while (b-a)>1 => while b > a (integer!)
;       b := ((b+a)/2)
;       a := (value/b)
; end_while
; result := b

extern printf
%MACRO PRINT 1
;   extern printf
    mov rdi, %1
    mov rsi, rax
    xor eax, eax
    call printf
%ENDM

section .data
    value: dq 1000
    fmt1: db `isqrt32:   rax=%u\n`,0
    fmt2: db `isqrt64:   rax=%u\n`,0
    fmt3: db `isqrt_fpu: rax=%u\n`,0

section .text
global main:

main:

    mov edi, [value]
    call isqrt32
    PRINT fmt1

    mov rdi, [value]
    call isqrt64
    PRINT fmt2

    mov rdi, [value]
    call isqrt_fpu
    PRINT fmt3

    xor al,al               ; Exitcode 0
    ret

isqrt64:

    mov rbx, rdi
    xor rax, rax

    .while:
    cmp rax, rbx
    jnb .endwhile

    add rbx, rax
    shr rbx, 1

    mov rax, rdi
    xor rdx, rdx
    div rbx

    jmp .while

    .endwhile:
    mov rax, rbx
    ret

isqrt32:

    mov ebx, edi
    xor eax, eax

    .while:
    cmp eax, ebx
    jnb .endwhile

    add ebx, eax
    shr ebx, 1
    mov eax, edi
    xor edx, edx
    div ebx

    jmp .while

    .endwhile:
    mov eax, ebx
    ret

isqrt_fpu:

    push rdi
    fild qword [rsp]
    fsqrt
    fisttp qword [rsp]
    pop rax
    ret

Sqrt of a Integer in Assembler

1 Answers1