Fibonacci by Oxygen

[Johannes]

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.

[Charles Pegge]

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

[Johannes]

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

[Johannes]

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.

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