0

I am attempting to utilize the Mid Section method to determine the integer square root of a number. I am attempting to program this loop in assembly code. 

l=1; u=x;
while l<=u
    m=(l+u)/2
    if m*m>x
        l=m+1
    else
        u=m-1
return m

This is the code I have written for the Mid Section method in assembly

INCLUDE Irvine32.inc
.data
; PLACE DATA DIRECTIVES HERE
    value   SDWORD  1
    lower   SDWORD  1
    upper   SDWORD  0
    middle  SDWORD  ?

;Prompts and messages
prompt      BYTE    "Please enter a signed integer value. The program will terminate if a non-positive number or zero is entered.",0dh, 0ah, 0
endOfLine   BYTE    " ",0dh, 0ah, 0


.code
main PROC
; PLACE SOURCE CODE HERE

program_loop:
    mov     edx, OFFSET prompt      ;print prompt for user to enter height
    call    WriteString
    call    ReadDec
    mov     value, eax              ;read user's height and store it in a variable
    mov     eax, value
    cmp     eax, 0

    jle     endprogram
    mov     upper, eax
    while_loop:
        mov     eax, lower
        cmp     eax, upper
        jg      end_while
        add     eax, upper
        mov     dl, 2
        idiv    dl
        mov     middle, eax
        imul    middle
        cmp     eax, value
        jle     else_if
            mov     eax, middle
            add     eax, lower
            mov     lower, eax
            jmp     end_if
        else_if:
            mov     eax, middle
            sub     eax, lower
            mov     upper, eax
        end_if:

        jmp     while_loop
    end_while:
    mov     edx, OFFSET middle
    call    WriteDec
    call    CrLf
    jmp     program_loop
endprogram:
    call    DumpRegs
    call    WaitMsg
    exit
main ENDP
; PLACE ADDITIONAL PROCEDURES HERE
END main

Whenever I attempt to divide (l+u) and that is an odd number by 2 to find middle I get the value 258?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Patsfanx247
  • 3
  • 1
  • Use `shr eax,1` to do unsigned division by 2. `idiv dl` does `AX / DL` (signed division) and sets `al=quotient`, `ah=remainder` (and leaves the top two bytes of EAX unmodified). – Peter Cordes Feb 25 '18 at 21:57
  • Also, you don't need memory storage for `middle` (or the other values). x86 has enough registers. It would be more efficient to just `mov ecx, eax` / `imul eax,eax`, to save `m` in `ecx` before squaring it in `eax`. You also don't need one-operand `imul` to produce the full 64-bit result in `edx:eax`, which is why I used `imul eax,eax` instead of `imul eax`. – Peter Cordes Feb 25 '18 at 22:09
  • clang and ICC do an interesting job compiling the C version of this (with `unsigned int`), using branchless `cmova l, m+1` / `cmovbe u, m-1`. https://godbolt.org/g/PvS72J. gcc uses a branch. Looks pretty nice. – Peter Cordes Feb 25 '18 at 22:20

0 Answers0