Page 1 of 2 12 LastLast
Results 1 to 10 of 14

Thread: Fibonacci by Oxygen

  1. #1
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    57
    Posts
    8,777
    Rep Power
    10

    Fibonacci by Oxygen

    My first real try in Oxygen: Fibonacci

    Native thinBasic Fibonacci function takes about 15 seconds on my computer to calculate Fibonacci of 30
    With oxygen it takes 0.050.. seconds
    The power of Oxygen module.

    '---Fibonacci by Oxygen
    uses "Console", "Oxygen"
     
    dim T1    as quad
    dim T2    as quad
     
    dim p0,p1   as dword
    dim src    as string
     
    '--- Prepare Oxygen script
    src = "
     
     FUNCTION fibonacci(byval sequence as Dword) as Dword at #p1
      IF sequence < 2 THEN
       FUNCTION = sequence
      ELSE
       FUNCTION = fibonacci(sequence - 1) + fibonacci(sequence - 2)
      END IF
     END FUNCTION
    
     sub finish() at #p0 
      terminate
     end sub
    "
    
    '--- Compile Oxygen source 
    o2_basic src
    if len(o2_error) then
     msgbox 0, o2_error : stop
    end if
    o2_exec
    
    
    declare function Fibonacci(byval s as DWORD) as DWORD at p1
    declare sub finish () at p0
    
    
    dim Result as dword
    dim n    as dword = 30
    
    hirestimer_init
     
    T1 = hirestimer_get
    Result = Fibonacci(n)
    T2 = hirestimer_get
    
    printl "Fibonacci of " & n & " is " & Result
    printl "Script time: " & FORMAT$(T2 - T1, "#,") & " microseconds or " & format$((T2 - T1)/10^6, "#0.000000") & " seconds"
    
    
    finish
    waitkey
    
    www.thinbasic.com | www.thinbasic.com/community/ | help.thinbasic.com
    Windows 10 Pro for Workstations 64bit - 32 GB - Intel(R) Xeon(R) W-10855M CPU @ 2.80GHz - NVIDIA Quadro RTX 3000

  2. #2

    Re: Fibonacci by Oxygen

    Thanks Eros!

    I could not resist producing an Assembler version of the algorithm. I'd be interested to know how much this further reduces the time.

    Charles

    (I get about 6x)

    '---Fibonacci by Oxygen
    uses "Console", "Oxygen"
    
    dim T1 as quad
    dim T2 as quad
    
    dim p0,p1 as dword
    dim src as string
    
    '--- Prepare Oxygen script
    src = "
    
    FUNCTION fibonacci(byval sequence as Dword) as Dword at #p1
     '
     function=call fibon sequence : exit function 'TURBOCHARGE!!
     '
     IF sequence < 2 THEN
      FUNCTION = sequence
     ELSE
      FUNCTION = fibonacci(sequence - 1) + fibonacci(sequence - 2)
     END IF
     
     EXIT FUNCTION
    
     fibon:
     (
      mov eax,[esp+4] : cmp eax,2 : jl exit
      dec eax : call fibon eax
      push eax 'HOLD FIRST RESULT ON STACK
       mov eax,[esp+8]
       dec eax : dec eax : call fibon eax
      pop ecx : add eax,ecx 'ADD FIRST TO SECOND
     )
     ret 4
     
    END FUNCTION
    
    
    sub finish() at #p0 
     terminate
    end sub
    
    "
    
    '--- Compile Oxygen source 
    o2_basic src
     if len(o2_error) then
     msgbox 0, o2_error : stop
    end if
    
    o2_exec
    
    declare function Fibonacci(byval s as DWORD) as DWORD at p1
    declare sub finish () at p0
    
    
    dim Result as dword
    dim n as dword = 30
    
    hirestimer_init
    
    T1 = hirestimer_get
    Result = Fibonacci(n)
    T2 = hirestimer_get
    
    printl "Fibonacci of " & n & " is " & Result
    printl "Script time: " & FORMAT$(T2 - T1, "#,") & " microseconds or " & format$((T2 - T1)/10^6, "#0.000000") & " seconds"
    'msgbox 0, result
    
    finish
    waitkey
    

  3. #3
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    57
    Posts
    8,777
    Rep Power
    10

    Re: Fibonacci by Oxygen

    Your ASM version output is:

    Fibonacci of 30 is 832040
    Script time: 19,492 microseconds or 0.019492 seconds


    But ... I do not understand it
    www.thinbasic.com | www.thinbasic.com/community/ | help.thinbasic.com
    Windows 10 Pro for Workstations 64bit - 32 GB - Intel(R) Xeon(R) W-10855M CPU @ 2.80GHz - NVIDIA Quadro RTX 3000

  4. #4
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    57
    Posts
    8,777
    Rep Power
    10

    Re: Fibonacci by Oxygen

    Charles,

    just to let you know, Oxygen Fibonacci in Basic like syntax is a little faster than a compiled Power Basic equivalent version.


    Attached Files Attached Files
    www.thinbasic.com | www.thinbasic.com/community/ | help.thinbasic.com
    Windows 10 Pro for Workstations 64bit - 32 GB - Intel(R) Xeon(R) W-10855M CPU @ 2.80GHz - NVIDIA Quadro RTX 3000

  5. #5

    Re: Fibonacci by Oxygen

    Quote Originally Posted by Eros Olmi
    Charles,

    just to let you know, Oxygen Fibonacci in Basic like syntax is a little faster than a compiled Power Basic equivalent version.


    What? It's time for an Oxygen thinBasic SDK.

  6. #6

    Re: Fibonacci by Oxygen

    We can get a significant improvement by eliminating the Function overhead, by deploying an internal sub fibon2.
    In this case the Sub leaves the result of the last expression in the eax register, which is what we want for an integer return.

    Cheating just a little bit


    '---Fibonacci by Oxygen
    uses "Console", "Oxygen"
    
    dim T1 as quad
    dim T2 as quad
    
    dim p0,p1 as dword
    dim src as string
    
    '--- Prepare Oxygen script
    src = "
    
    #view
    
    SUB fibon2(byval sequence as Dword)
     var long a  ' uninitialised variable
     'dim a  'initialised to zero
     IF sequence < 2 THEN
      a = sequence 
     ELSE
      a = fibon2(sequence - 1) + fibon2(sequence - 2)
     END IF
    END SUB
    
    #endv
    
    FUNCTION fibonacci(byval sequence as Dword) as Dword at #p1
     '
     'function=call fibon sequence : exit function 'TURBOCHARGE ASM!!
     function=fibon2 sequence : exit function   'TURBOCHARGE BASIC!!
     '
     IF sequence < 2 THEN
      FUNCTION = sequence
     ELSE
      FUNCTION = fibonacci(sequence - 1) + fibonacci(sequence - 2)
     END IF
     
     EXIT FUNCTION
    
     fibon:
     (
      mov eax,[esp+4] : cmp eax,2 : jl exit
      dec eax : call fibon eax
      push eax 'HOLD FIRST RESULT ON STACK
       mov eax,[esp+8]
       dec eax : dec eax : call fibon eax
      pop ecx : add eax,ecx 'ADD FIRST TO SECOND
     )
     ret 4
    
     
    END FUNCTION
    
    
    sub finish() at #p0 
     terminate
    end sub
    
    "
    
    '--- Compile Oxygen source 
    o2_basic src
     if len(o2_error) then
     msgbox 0, o2_error : stop
    end if
    
    o2_exec
    
    declare function Fibonacci(byval s as DWORD) as DWORD at p1
    declare sub finish () at p0
    
    
    dim Result as dword
    dim n as dword = 30
    
    hirestimer_init
    
    T1 = hirestimer_get
    Result = Fibonacci(n)
    T2 = hirestimer_get
    
    printl "Fibonacci of " & n & " is " & Result
    printl "Script time: " & FORMAT$(T2 - T1, "#,") & " microseconds or " & format$((T2 - T1)/10^6, "#0.000000") & " seconds"
    msgbox 0, result
    'msgbox 0,o2_prep "o2h "+src
    
    finish
    waitkey
    

  7. #7
    thinBasic MVPs kryton9's Avatar
    Join Date
    Nov 2006
    Location
    Naples, Florida & Duluth, Georgia
    Age
    67
    Posts
    3,869
    Rep Power
    404

    Re: Fibonacci by Oxygen

    My results:

    Eros's original post result: .0871

    first ASM version: .0111

    Last Version: .0206
    Acer Notebook: Win 10 Home 64 Bit, Core i7-4702MQ @ 2.2Ghz, 12 GB RAM, nVidia GTX 760M and Intel HD 4600
    Raspberry Pi 3: Raspbian OS use for Home Samba Server and Test HTTP Server

  8. #8

    Re: Fibonacci by Oxygen


    This algorithm, builds a large tree of recursing functions. Because it is so simple, the wrappings around the basic function is where most of the processing takes place: namely pushing registers onto the stack, setting up frame for referencing local variables and param, then setting local variables to zero. Then afterwards assigning the function= resilt back to the eax register and popping the saved registers from the stack. The sub avoids most of this unnecessary work.

    Charles

  9. #9
    Senior Member Lionheart008's Avatar
    Join Date
    Sep 2008
    Location
    Germany, Bad Sooden-Allendorf
    Age
    51
    Posts
    934
    Rep Power
    109

    Re: Fibonacci by Oxygen

    hi all

    my fibonacci time results on my old notebook...

    1) 0.135 = eros script
    2) 0.043 = assembler script
    3) 0.068 = charles last script

    good to see that my old computer isn't so fast as a dumping snail-shell
    salve, Lionheart
    you can't always get what you want, but if you try sometimes you might find, you get what you need

  10. #10
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25
    It's an old thread but I wanted to explore the exchange of variables between Oxygen script functions and "true" assembler. My Oxygen script is as follows and should replace any of the scripts in the examples given.

    '--- Prepare Oxygen script
    src = "
    Function fibonacci(ByVal sequence As DWord) As DWord At #p1
    '
      Function = Call fibon sequence
      Exit Function 
     
    ' Why so recursive?
     
    .fibon
      mov eax,[esp+4]  
      mov ebx,0         
      mov ecx,1       
      dec eax
      js fibon2
    .fibon1
      add ebx,ecx      
      mov edx,ebx
      mov ebx,ecx
      mov ecx,edx
      dec eax
      jns fibon1
    .fibon2
      mov eax,ebx
      ret
     
    '
    End Function
     
     
    Sub finish() At #p0 
     terminate
    End Sub
    "
    
    I went for iterative instead of recursive. This eliminates all calling/stack overhead and with the x86's branch prediction this creates a monster.

    Execution times on my machine:

    Eros' script: 39,915 microseconds
    Charles' script 1: 12,470 microseconds
    My script: 8 microseconds

    No, I did not leave out digits. The actual machine code does not take any measurable time to execute and those 8 microseconds is the overhead for interpreting the instruction and calling the function. HiresTimer counts in microseconds but a microsecond on my machine is still 3,160 clock cycles. The main loop (.fibon1) takes at most 10 cycles but more likely 6 cycles per loop. A maximum of 29 loops (for this example) gives between 174 and 290 clock cyles or less than 0.1 microseconds for the worst case. Zero time for HiresTimer.

    And to add insult to injury: ECX contains the next Fibonacci number but it would take more code (and time) to leave out the extra loop but still work for Fibonacci numbers 0 and 1.

Page 1 of 2 12 LastLast

Similar Threads

  1. Fibonacci sequence
    By macleay in forum Shout Box Area
    Replies: 1
    Last Post: 22-08-2011, 15:39
  2. Fun with Fibonacci
    By Johannes in forum BigInt module. Big Integer handling by Johannes
    Replies: 14
    Last Post: 12-04-2011, 16:29

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •