Computing the square root of a 32-bit integer

[clive]

Thanks, Clive, with LEA codesize is down to 40 bytes. But it's still not competitive with the FPU...

Indeed, something I'd use on non-FPU implementations (68K, ARM, MIPS). Although the way it's described a hardware implementation would be reasonably viable if you could spare the gates.

As for optimization, the best one is to avoid the SQRT completely, especially if you are comparing/sorting based on the result.

[Number1awa]

So I found another way to do this which I wanted to try: implementing the
http://en.wikipedia.org/wiki/Bisection_method I followed the pseudo-code found at the bottom of the page except for the break condition i used k*k <= N && (k+1)(k+1) > N

When i attempt to run it. It just runs forever without ever breaking from the loop 

This is the code that I have

Code Select Expand


INCLUDE irvine32.inc
.data

left EQU ebx ; left interval
right EQU eax ; right interval
midpoint EQU ecx ; midpoint

firstIfP EQU esi ; first product in checking
secondIfP EQU edi ; second product in checking

loopP1 EQU edx ; UNTIL condition holders
loopP2 EQU esp ; ........................

N DWORD ? ; holds root squared
.code
main PROC
; RESETING REGISTERS
sub eax, eax
sub ebx, ebx
sub ecx, ecx
sub edx, edx
sub esp, esp
sub esi, esi
sub edi, edi

mov N, 400
mov right, 400 ; right interval ( to take root of
mov left, -10 ; left interval
.REPEAT

push right ; saves right interval
add right, left ; (b + a)
shr right, 1 ; / 2
mov midpoint, right ; the midpoint
pop right

push left ; saves left interval
imul left, midpoint ; left * midpoint
mov firstIfP, left
pop left

.IF firstIfP < 0 ; left * midpoint < 0
mov right, midpoint ; new right interval
.ENDIF

push right ; saves right interval
imul right, midpoint ; right * midpoint
mov secondIfP, right
pop right

.IF secondIfP < 0; ; right * midpoint < 0
mov left, midpoint ; new left interval
.ENDIF

mov loopP1, midpoint ; computes k*k < N
imul loopP1, loopP1

mov loopP2, midpoint ; computes (k+1)(k+1) > N
inc loopP2
imul loopP2, loopP2


.UNTIL  (loopP1 <= N) && (loopP2 > N)


mov eax, midpoint ; moves root to eax
call WriteInt


exit
main ENDP
END main


Thanks :)

[jj2007]

.IF firstIfP < 0

See The .if eax<0 trap

[Number1awa]

I tried using

SDWORD PTR firstIfP

and when i try to run the program it still just stops working and i have to stop the program....

[jj2007]

Your use of registers is, well, kind of unorthodox. Check what you did to esp :wink
The code below should work but is still stuck in an endless loop. You will need Olly to find out why (I don't have the time, sorry).

Hint:

imul loopP1, loopP1
   .Break .if Carry?  ; lets you exit the endless loop when edx becomes negative

Code Select Expand

include \masm32\include\masm32rt.inc
.data

left EQU ebx ; left interval
right EQU eax ; right interval
midpoint EQU ecx ; midpoint

firstIfP EQU esi ; first product in checking
secondIfP EQU edi ; second product in checking

loopP1 EQU edx ; UNTIL condition holders
loopP2 EQU ebp ; ........................

N DWORD ? ; holds root squared

.code
start:

; RESETING REGISTERS
sub eax, eax
sub ebx, ebx
sub ecx, ecx
sub edx, edx
;sub esp, esp
sub esi, esi
sub edi, edi

mov N, 400
mov right, 400 ; right interval ( to take root of
mov left, -10 ; left interval
; int 3 ; Olly is your friend: http://ollydbg.de/
push ebp
.REPEAT
push right ; saves right interval
add right, left ; (b + a)
shr right, 1 ; / 2
mov midpoint, right ; the midpoint
pop right

push left ; saves left interval
imul left, midpoint ; left * midpoint
mov firstIfP, left
pop left

.IF sdword ptr firstIfP < 0 ; left * midpoint < 0
mov right, midpoint ; new right interval
.ENDIF

push right ; saves right interval
imul right, midpoint ; right * midpoint
mov secondIfP, right
pop right

.IF sdword ptr secondIfP < 0; ; right * midpoint < 0
mov left, midpoint ; new left interval
.ENDIF

mov loopP1, midpoint ; computes k*k < N
imul loopP1, loopP1

mov loopP2, midpoint ; computes (k+1)(k+1) > N
inc loopP2
imul loopP2, loopP2

.UNTIL  (loopP1 <= N) && (loopP2 > N)
pop ebp
print str$(midpoint), " returned"
exit
end start

[Number1awa]

Ok, so I figured out why it is being an infinite loop mostly....

at the bottom i did this:
   push eax
   mov eax, midpoint
   call WriteInt
   pop eax


With the number to take the root of set at 400:

just to see what the midpoint was every time, and it prints out forever "200" the if you output the right interval it prints forever as "400" same for left interval printing "0"
right and left are not taking on the values of whatever they should be taking on and continuing with that value to the next iteration of the loop....
So...at least that is an error that i can hopefully work with now :D

[MichaelW]

Where in the above code is the functionality of the f(left), f(right), and f(midpoint) calls, as specified in the Wikipedia pseudo-code, implemented? Assuming that you are trying to find the square root of 400, this function should return (arg * arg - 400).

[Number1awa]

Oh....really....lol perhaps i should add that to the code....hehe

I surely do hope that that is the only thing that is missing....

[Number1awa]

ok so i just added this now.....which in all ways that i can see computes f(left) f(right) and f(midpoint) and it still does and infinite loop..... :(

Code Select Expand


push left ; saves left interval
push midpoint
imul left, left ; left*left - 400
sub left, 400
imul midpoint, midpoint ; midpoint*midpoint - 400
sub midpoint, 400
imul left, midpoint ; f(left) * f(midpoint)
mov firstIfP, left
pop midpoint
pop left

.IF SDWORD PTR firstIfP < 0 ; left * midpoint < 0
mov right, midpoint ; new right interval
.ENDIF

push right ; saves right interval
push midpoint
imul right, right ; right*right - 400
sub right, 400
imul midpoint, midpoint ; midpoint*midpoint - 400
sub midpoint, 400
imul right, midpoint ; f(right) * f(midpoint)
mov secondIfP, right
pop midpoint
pop right

.IF SDWORD PTR secondIfP < 0 ; right * midpoint < 0
mov left, midpoint ; new left interval
.ENDIF


[Number1awa]

Hold on guys I just figured it out!!!!

It works now!!!!!

Yay....that took so long to figure out lol

Thank you all could not have done it without you guys :)

[MichaelW]

The attachment is a small test app (done in C) that implements a workable integer version of the wiki pseudo-code.

In case the logic behind the f() function is not clear, here is a probably not very good explanation:

The bisection method is used to solve equations of the form f(x) = 0. To use your example value, if x is the square root of 400, we know that:

x² = 400

So we algebraically manipulate this to the form:

x² – 400 = 0

And the task is then to find the root of f(x) = x² – 400