Fibonacci by Oxygen

[ErosOlmi]

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 :good:
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

[Charles Pegge]

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

[ErosOlmi]

Your ASM version output is:

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


But ... I do not understand it :xyzw: :D

[ErosOlmi]

Charles,

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

:occasion:

[Michael Hartlef]

Charles,

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

:occasion:



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

[Charles Pegge]

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

[kryton9]

My results:

Eros's original post result: .0871

first ASM version: .0111

Last Version: .0206

[Charles Pegge]

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

[Lionheart008]

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

[Johannes]

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. :D 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.

[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. :D



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