News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Dijkstras algo with fpu?

Started by daydreamer, September 22, 2023, 05:08:39 PM

Previous topic - Next topic

daydreamer

Hi
Anyone coded dijkstras algo in asm?
First you setup distances to infinite, examples show define some high integer as infinite
But if i write a fpu version using REAL10, for example distances = between stars, I could use fpu own infinity + when comparing and not be capped to use max dword as infinity?
+infinity =7F800000h
-infinity =FF800000h

Should I use some random create grid proc, but with fixed seed = creates same grid every time?
Beginning coding
; dijkstras algo

Cost Db 8*5 dup (infinity)
Align 8 ; can use [reg*8 ] indirect addressing for one dimension of array
G db 0,1,0,3,10
Align 8
    Db 1,0,5,0,0
Align 8
    Db 0,5,0,2,1
Align 8
    Db 3,0,2,0,6
Align 8
    Db 10,0,1,6,0
 
Local n,u
Mov n,5
Mov u,0
Invoke dijkstra(G,n,u);
  return 0;
dijkstra proc,(G,n,u);
Mov edx,0
Lea esi,G
L1:Mov ecx,0
     
L2: Mov eax,[addr G+edx*8+ecx]
If eax==0
Mov [addr cost+edx *8+ecx ],infinity
Else mov [addr cost+edx*8+Ecx],eax
Endif
 
Inc ecx
Cmp ecx,n
Jne l2
Inc edx
Cmp edx, n
Jne l1

 
Ret
dijkstra endp
 

my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

daydreamer

maybe better to start with GDI drawing street network,by drawing streets up to 4 directions from nodes,easier understood and easier to watch it find the way if it works or bug causes it to take wrong route???
route taken = draw in different street color
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

NoCforMe

Sorry, no answer (as usual, I have trouble even understanding just what you're after here), but for those of you like me who have no idea what Dijkstra's algorithm is, here's a really good explanation. (I really like it when someone clearly and elegantly explains something.)
Assembly language programming should be fun. That's why I do it.

HSE

Other source:  https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Apparently was a simple code and an easy translation  :biggrin::eusa_naughty: )

In 64 bit is largeaddressaware:no to make that more easy. And 32/64 differ because vasily conditionals, then only Masm SDK requiered:
dijkstra proc src:xword
    local i : xword, count : xword, u : xword, v : xword

    ; Function that implements Dijkstra's single source
    ; shortest path algorithm for a graph represented using
    ; adjacency matrix representation
   
   
    ; Initialize all distances as INFINITE and stpSet[]
    ; as false
    ForLpD i, 0, sgraph
        mov xcx, infinite
        mov dist[xax*@WordSize], xcx
        mov sptSet[xax*@WordSize], 0
    Next i

    ; Distance of source vertex from itself is always 0
    mov xax, src
    mov dist[xax*@WordSize], 0

    ; Find shortest path for all vertices

    ForLpD count, 0, sgraph-1
        ; Pick the minimum distance vertex from the set
    ; of vertices not yet processed. u is always
    ; equal to src in first iteration.
    call minDistance
        mov u, xax
        ; Mark the picked vertex as processed
        mov sptSet[xax*@WordSize], 1

        ; Update dist value of the adjacent vertices of
        ; the picked vertex.
        ForLpD v, 0, sgraph, xdx

            ; Update dist[v] only if is not in sptSet,
            ; there is an edge from u to v, and total
            ; weight of path from src to v through u is
            ; smaller than current value of dist[v]
            .if sptSet[xdx*@WordSize] == 0
           
                matrix u, v, sgraph
                mov xcx, graph[xax*@WordSize]
                .if xcx != 0
                    mov xdx, u
                    mov xax, dist[xdx*@WordSize]
                    .if xax != infinite
                        add xax, xcx
                        mov xdx, v
                        .if  xax < dist[xdx*@WordSize]
                            mov dist[xdx*@WordSize], xax
                        .endif
                    .endif
              .endif
            .endif
        Next v
    Next count 
    ; print the constructed distance array
    invoke printSolution
    ret
dijkstra endp
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
Equations in Assembly: SmplMath

zedd

Pardon my ignorance here... xax, xcx, xword??? What type of sorcery conjured this up?  :biggrin:
A  new CPU architecture? Macros? Other? :tongue:

I haven't downloaded it yet, HSE.. But now I'm curious...  :biggrin:

Seems a little advanced... But a very interesting topic. Maybe this would be more suitable in the Workshop? Or even the Laboratory (to make it better, faster, etc)...

zedd

#5
Later...
Quotexax, xcx, xword
Ah, okay I see. Macros... You made the program conditionally usable with either 32 bit or 64.  :thumbsup:


The batch file may need correction.
Quote\masm32\bin64\ml64.exe /c %appname%.asm

\masm32\bin64\polink.exe /SUBSYSTEM:CONSOLE /MACHINE:X64 /ENTRY:entry_point /nologo /LARGEADDRESSAWARE:NO %appname%.obj
Originally hutch had everyone incorporate masm64 within the masm32 directory.
The latest version of the SDK is meant to be installed apart from the masm32 SDK... in the root of the drive....
I have corrected the batch files for my installation of the masm64 SDK...
Quote\masm64\bin64\ml64.exe /c %appname%.asm

\masm64\bin64\link.exe /SUBSYSTEM:CONSOLE /MACHINE:X64 /ENTRY:entry_point /nologo /LARGEADDRESSAWARE:NO %appname%.obj
Nice work there HSE.  :thumbsup:

With some modifications perhaps, should do what Magnus needs.  :smiley:

daydreamer

thanks hector  :thumbsup:
; Initialize all distances as INFINITE and stpSet[]
    ; as false
I already changed to already db 5*8 dup (infinite)
but I still believe in a graphics version better than print data
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

zedd

What HSE posted could be a good starting point???

HSE

Quote from: zedd151 on October 12, 2023, 02:53:31 AMYou made the program conditionally usable with either 32 bit or 64.  :thumbsup:

That is the point  :thumbsup: Biterider refer to this like "Neutral Bitness", sometimes you see the concept like "x96".

This example is partially x96 for simplicity reasons, and don't need any additional macro.

To be complete Neutral Bitness for ML/ML64 must use some macros presents in SmplMath, not the idea here.


Quote from: daydreamer on October 12, 2023, 04:18:55 AMbut I still believe in a graphics version better than print data

You are the expert in graphics  :thumbsup:
Equations in Assembly: SmplMath

jj2007

Quote from: HSE on October 12, 2023, 06:52:47 AM
Quote from: zedd151 on October 12, 2023, 02:53:31 AMYou made the program conditionally usable with either 32 bit or 64.  :thumbsup:

That is the point  :thumbsup: Biterider refer to this like "Neutral Bitness", sometimes you see the concept like "x96".

Same as Dual 64- and 32-bit Assembly

HSE

Quote from: jj2007 on October 12, 2023, 07:17:59 AMSame as Dual 64- and 32-bit Assembly

Neutral Bitness is about a few equates and a couple of very simple macros.

For a system, like your "Dual", is far better ObjAsm package complemented with SmplMath (and all code is available)   :skrewy:





Equations in Assembly: SmplMath

jj2007

Quote from: HSE on October 12, 2023, 09:42:01 AMNeutral Bitness is about a few equates and a couple of very simple macros.

You are the expert :thumbsup: