BINARY INTEGER SQUARE ROOTS

[zedd151]

Now I am bit insecure whether Ognil is really Lingo, because that code works indeed

Code Select Expand

include \masm64\include64\masm64rt.inc

.data

.code

start proc

mov rdi, 1000000
call isqrt

    invoke ExitProcess, 0
start endp

align 16
isqrt:
    push    rbx                 ; Save callee-saved register
    mov     rcx, rdi            ; rcx = n (input)   ; input number passed in rdi
    xor     rbx, rbx            ; rbx = result (initially 0)
    mov     rdi, 0              ; rdi = low (initially 0)
    mov     rsi, rcx            ; rsi = high (initially n)
loop_start:
 ; Calculate mid = low + (high - low) / 2
    mov     rax, rsi            ; rax = high
    sub     rax, rdi            ; rax = high - low
    shr     rax, 1              ; rax = (high - low) / 2
    add     rax, rdi           ; rax = mid
 ; Compute mid^2 and check against n
    mov     r8, rax             ; r8 = mid
    mul     rax                 ; rdx:rax = mid^2
    cmp     rdx, 0              ; Check if high 64 bits are zero
    jne     mid_too_big         ; If not, mid^2 > n
    cmp     rax, rcx               ; Compare low 64 bits with n
    jg      mid_too_big         ; If mid^2 > n
; Update result and adjust low
    mov     rbx, r8        ; Update result to mid
    add     r8, 1                  ; mid + 1
    mov     rdi, r8             ; low = mid + 1
    jmp     next_iter
mid_too_big:
; Adjust high
    sub     r8, 1               ; mid - 1
    mov     rsi, r8             ; high = mid - 1
next_iter:
; Check if low <= high
    cmp     rdi, rsi
    jle     loop_start
; Return result
    mov     rax, rbx            ; Move result to rax
    pop     rbx                 ; Restore callee-saved register
    ret

end

 
I tested it too.
He forgot to mention that the input number is passed in rdi. I input 1000000, results of course 1000
I only slapped this together, ran and and inspected the results in rax in the debugger x64dbg.
If you want an interface or some kind of display, maybe he can provide it. 

edit: I had the isqrt function within start procedure, I fixed that little issue. 
I was wondering why there was a LEAVE before the return there.   

[NoCforMe]

Now I am bit insecure whether Ognil is really Lingo, because that code works indeed

For that you can thank "AI", not Lingo/Ognil.

[ognil]

Thanks guys for the compliments,

but I don't think Raymond, who started this post with interesting code (unlike you), will like them very much...    

[NoCforMe]

You know, you really are a total ass, whoever you are.
I'm pretty sure I speak for the congregation on this.

[zedd151]

Thanks guys for the compliments,
but I don't think Raymond, who started this post with interesting code (unlike you), will like them very much...  

And I do not think that MichaelW, who has not even been around here (since November 02, 2018) to defend himself against folks like you, will much like your comments either.

I saw MichaelW's post and was immediately disappointed and lost interest in it.
...
This is another example of bad programming practice that is widely used in this forum.

Conversely, raymond still frequents the forum almost daily and can speak for himself.

Apologies to raymond, for the nonsense that has been going on here in this thread by myself and others.

[jack]

the code posted by ognil makes me think that it's original target was Linux, in Linux rdi is the first integer argument to a function, whereas in Windows it's rcx
also the code fails to preserve the non-volatile registers rdi and rsi
also, raymond's code 2 times faster

[NoCforMe]

the code posted by ognil makes me think that it's original target was Linux, in Linux rdi is the first integer argument to a function, whereas in Windows it's rcx
also the code fails to preserve the non-volatile registers rdi and rsi
also, raymond's code 2 times faster

So whaddya expect from "AI"?

[daydreamer]

@Zedd
Sqrt(1000000) = 1000,that's kinda approximation I want to try with string reducing approximately by halved zeros after first digit

for 2 to sqrt(n)

[jj2007]

Thanks guys for the compliments,

Just for fun, I wrote a testbed to get some timings for your isqrt algo:

Code Select Expand

This program was assembled with UAsm64 in 64-bit format.
875 ticks for isqrt, result=1234567
797 ticks for isqrt, result=9876543
 31 ticks for fsqrt, result=1234567
 32 ticks for fsqrt, result=9876543

Code Select Expand

This program was assembled with ml64 in 64-bit format.
907 ticks for isqrt, result=1234567
828 ticks for isqrt, result=9876543
 15 ticks for fsqrt, result=1234567
 32 ticks for fsqrt, result=9876543

[jack]

I made a simple test in FreeBasic, I replaced labels with numbers otherwise it may give a duplicate symbol error, also replaced rsi with r9 which is volatile
hope you guys won't mind

Code Select Expand

' compile with fbc64
#cmdline "-asm intel -w all -arch native -gen gcc -v"

Function asmsqrt Naked Cdecl(Byval n As Ulongint) As Ulongint
    Asm
        Push    rbx                 ' Save callee-saved register
        Push    rdi                 ' Save callee-saved register
        'mov     rcx, rdi           ' rcx = n (input)
        'n is already in register rcx
        Xor     rbx, rbx            ' rbx = result (initially 0)
        mov     rdi, 0              ' rdi = low (initially 0)
        mov     r9, rcx         ' r9 = high (initially n)
    0:
     ' Calculate mid = low + (high - low) / 2
        mov     rax, r9         ' rax = high
        Sub     rax, rdi            ' rax = high - low
        Shr     rax, 1              ' rax = (high - low) / 2
        Add     rax, rdi        ' rax = mid
     ' Compute mid^2 and check against n
        mov     r8, rax             ' r8 = mid
        mul     rax                 ' rdx:rax = mid^2
        cmp     rdx, 0              ' Check if high 64 bits are zero
        jne     1f      ' If not, mid^2 > n
        cmp     rax, rcx            ' Compare low 64 bits with n
        jg      1f      ' If mid^2 > n
    ' Update result and adjust low
        mov     rbx, r8     ' Update result to mid
        Add     r8, 1               ' mid + 1
        mov     rdi, r8             ' low = mid + 1
        jmp     2f
    1:
    ' Adjust high
        Sub     r8, 1               ' mid - 1
        mov     r9, r8             ' high = mid - 1
    2:
    ' Check if low <= high
        cmp     rdi, r9
        jle     0b
    ' Return result
        mov     rax, rbx            ' Move result to rax
        Pop     rdi                 ' Restore callee-saved register
        Pop     rbx                 ' Restore callee-saved register
        ret
    End Asm
End Function

Dim As Ulongint n, root
Dim As Longint sum
Dim As Double t

t=Timer
sum=0

For n=1 To 10000000
    root=asmsqrt(n)
    'root=fix(sqr(n))
    sum+=root
Next
t=timer-t
Print sum
Print t
Print "Press return to end"
Sleep


[TimoVJL]

Is isqrt for CPUs like ARM, that don't have FPU ?

[daydreamer]

Is isqrt for CPUs like ARM, that don't have FPU ?

Maybe arduino and 8 bit cpus that is used in embedded?

[TimoVJL]

Is isqrt for CPUs like ARM, that don't have FPU ?

Maybe arduino and 8 bit cpus that is used in embedded?

Do you even know, what is ARM CPU family ?

[ognil]

Just for fun, I wrote a testbed to get some timings for your isqrt algo:

Thank you jj for the compliment and recognition of my code for actively participating in your pleasures.

I became a C++ guy from university with two projects implemented in my bank, related to transferring all S.W.I.F.T. daily transactions to the bank's general ledger.
Therefore, it is important for me that the program runs without errors, since the hardware takes care of the speed.

With the availability of modern hardware, optimizing the code has long been a thing of the past and is now just a distant memory for old people.

[NoCforMe]

With the availability of modern hardware, optimizing the code has long been a thing of the past and is now just a distant memory for old people.

Hah! What you seem to have missed--what sailed right over your head--is that your "modern hardware" code (using XMM) was a couple orders of magnitude SLOWER than legacy (FPU) code, as demonstrated by JJ's timings above.

Do you even bother reading replies here? One gets the feeling that you're like a "write-only" bot.