Page 2 of 2 FirstFirst 12
Results 11 to 14 of 14

Thread: Fibonacci by Oxygen

  1. #11
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25
    A small explanation why the difference in execution times is so gigantic.

    When you calculate by iteration it is very clear to see that you need only 28 loops to calculate the 30th Fibonacci number. Numbers 0 and 1 are 0 and 1 respectively and for every next number you add the highest number to the lowest number. (The three MOV instructions make sure that I have the lowest number in register EBX.)

    But for any recursive routine the number of calculations are NOT 28 (or 29 or 30). Let me show you.

    F(0) = 0, that's simple.
    F(1) = 1, that's also simple.
    F(2) = F(1) + F(0). But that takes two calls.
    F(3) = F(2) + F(1). That's also two calls but F(2) needs another two calls to be calculated. Four calls in total.
    F(4) = F(3) + F(2). Again, two calls. But you need four more for F(3) and two more for F(2). Total: eight.
    F(5) = F(4) + F(3). Two for this one, eight for F(4), and four for F(3). Total: fourteen.

    This is also a sequence that looks like Fibonacci: the number of calls you need to calculate F(n) when n>3 is two plus the number of calls of F(n-1) and F(n-2). As we've seen F(2)=2 and F(3)=4. The sequence is the following: number for calls for F(n) starting at n=0.

    0, 0, 2, 4, 8, 14, 24, 40, 66, 108, 176, 286, 464, etc. (See attached spreadsheet.)

    For F(30) a total of 2692536 calls have to be made and that is why my iterative code is so much quicker.
    Attached Files Attached Files

  2. #12
    I'm not sure where the original algorithm came from. I think we used it as some kind of stress test - a most appalling misuse of recursion

    Your method on the other hand is a practical and efficient way of doing it iteratively, maxing the use of registers.

    But The Fibonacci number, unlike Pi can also be calculated directly (if you consider square roots direct)

    .5*(sqr(5)+1)=1.618033...

    I reckon it will take the FPU at least 100 clocks to resolve the square root but the precision will be very good.

    Charles

  3. #13
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25
    For comparison, iterative Fibonacci in pure thinBasic. Runs in 58 microseconds on my system.

    '--- Fibonacci straight up
     
    Uses "Console"
     
    Dim T1 As Quad
    Dim T2 As Quad
    Dim p0,p1 As DWord
     
    Function Fibonacci(s As DWord) As DWord
    Local a,b As DWord
    If s<2 Then
      Function = s
    Else 
      a = 0
      b = 1
      Do
        a += b
        Swap a,b
        s -=1
      Loop Until s<2
      Function = b
    EndIf
    End Function
     
    Dim Result As DWord
    Dim n As DWord = 30
     
    HiResTimer_Init
    T1 = HiResTimer_Get
    Result = Fibonacci(n)
    T1 = HiResTimer_Delta
     
    PrintL "Fibonacci of " & n & " is " & Result
    PrintL "Script time: " & Format$(T1, "#,") & " microseconds Or " & Format$((T1)/10^6, "#0.000000") & " seconds"
     
    WaitKey
    

  4. #14
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25
    Strictly speaking the definition of the Fibonacci sequence is recursive, just like for instance the factorial. But where the factorial recurses into a single new instance Fibonacci recurses into two instances. So for every recurse level the number of calls doubles. Implementing the factorial as
    function fact(i as long) as long
      if i<2 then
        function = 1
      else
        function = i * fact(i-1)
      endif
    end function
    
    creates some overhead but not much. But Fibonacci is something else.

    Square roots can be calculated directly, and if you don't have an opcode for it (as you don't with ARM) then it's a simpler routine than for division. It's done by isolating squares through (a + b)² = a² + 2ab + b². When you do this in assembler (binary artihmetic) this is just shifting bit streams and that is something machine code does very well. The only problem is that to calculate n bits after the binary comma you need 2n bits precision after the binary comma in your work fields.

    I beg to differ about what you consider "very good" precision though. Having finished my arbitrary precision calculation routines (I like to call them Ridiculous Precision) I calculated PI to 1,000,000 decimals (not bits, decimals) as a test case. It took 17m37s but I have been able to verify every single one of those 1,000,000 decimals as correct. It's a start.


    Quote Originally Posted by Charles Pegge View Post
    I'm not sure where the original algorithm came from. I think we used it as some kind of stress test - a most appalling misuse of recursion

    Your method on the other hand is a practical and efficient way of doing it iteratively, maxing the use of registers.

    But The Fibonacci number, unlike Pi can also be calculated directly (if you consider square roots direct)

    .5*(sqr(5)+1)=1.618033...

    I reckon it will take the FPU at least 100 clocks to resolve the square root but the precision will be very good.

    Charles
    Boole and Turing, help me!

    Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
    Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.

Page 2 of 2 FirstFirst 12

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
  •