B4J Question Fibonacci recursive performance test

[giggetto71]

Hi,
last week I tried to compare the B4J performances against Python 3.11 in executing the classic Fibonacci number recursive implementation. here's the code I have used for both cases.
Edit: below the correct B4J code. in the original post I missed to specify the parameter type so string was used...
B4J:

Sub fib(n as long) As Long
    If n <= 1 Then
       Return n
    Else
       Return (fib(n-1)+fib(n-2))
    End If
End Sub

Sub Button1_Click
    'xui.MsgboxAsync("Hello World!", "B4X")
    Dim ExecTime As Long, ff As Float
    Dim fiblong As Long
  
    ExecTime = DateTime.Now
    fiblong = fib(38)
    ExecTime = (DateTime.Now-ExecTime) '/1000
    Log(fiblong)
    Log(ExecTime)
    ff = ExecTime/1000
    Label1.Text = ff
End Sub

Python:

import time
def fib(n):
    if n <= 1:
       return n
    else:
        return (fib(n-1)+fib(n-2))

st = time.time()
print(fib(38))
et = time.time()
elapsed = et - st
print('Exec time:',elapsed,'seconds')

Of course the test is performed on the same pc (my pc, i7 2.8Ghz, 16Gb Ram).

For B4J I am using 9.8 (64bit) version.
For python I have used Pycharm 2022.2.3 configured to use Python 3.11 as interpreter.
here's the results:
EDIT (new numbers after correcting my code mistake in original post)

B4J: ~0.2 sec (with console app it goes down to 0.13)
Python; ~ 6 sec


Is this an expected result or am I making something wrong in the comparison?
thanks and happy new year!

 

[jahswant]

Create a console app for b4j instead and come back with performance measures.

 

[Quandalle]

your declaration of the fib(n) function in B4J does not give a type to the parameter n. So by default a string type is used.

The initial call to fib(38) recursively generates more than 126 million calls to the fib function. At each call there is a conversion to string, then a conversion to long

To improve performance, declare a long type for the parameter n

sub fib (n as long) as long

this will greatly reduce the execution time for the B4J code

 

[giggetto71]

THANKS!!!!! that improved massively! thanks again! Now the time is about 0.2 sec!

 

[Quandalle]

If you want to reduce the time further just remove the recursion, and you should get an execution time of less than 1 millisecond

Sub fibNoRecursive(n As Long)  As Long
  Dim first  As Long =  0
  Dim second As Long =  1
  Dim tmp    As Long
    For i = 1 To n
        tmp    = first + second
        first  = second
        second = tmp
    Next
  Return first
End Sub

 

[giggetto71]

thanks. thank you very much. this community is just unbelievable!

 

[giggetto71]

Create a console app for b4j instead and come back with performance measures.

with the console app and the proper parameter type definition it runs fib(38) in 0.13 sec..so overall
B4J vs Python 3.11 = 0.13 - 6
just another planet.. B4X RULES!

 

[Quandalle]

For those who have been following the news of AI for code, tools like ChatGPT are also amazing. Try for example on chatGPT the following 2 prompts and you will get correct answers :

"write a function in B4J that calculates Fibonacci with long argument"​

or

"write in B4J a non-recursive function that computes Fibonacci with a long argument​

Here is an example of a non-recursive function in B4J that calculates the Fibonacci number for a given input n:

Sub Fibonacci(n As Long) As Long
    Dim a As Long = 0
    Dim b As Long = 1
    Dim c As Long = 0
    For i = 0 To n - 1
        c = a + b
        a = b
        b = c
    Next
    Return a
End Sub


This function uses a loop to iterate through the sequence and calculate each number in the Fibonacci sequence up to the input n. The variables a and b represent the previous two numbers in the sequence, and c is used to store the current number being calculated. The loop starts at 0 and goes up to n - 1, so that the nth Fibonacci number is calculated.

For example, if you call Fibonacci(10), the function will return the value 55, which is the 10th number in the Fibonacci sequence.

 

[giggetto71]

impressive...I tried:
"can you write a B4A function that calculates the perfect numbers lower than the input parameter?"
and immediately I got:
"Sure! Here is a function in B4A (Basic4Android) that calculates and returns a list of all perfect numbers lower than a given input number:

Sub PerfectNumbers(max As Int) As List
Dim numbers As List
numbers.Initialize
For i = 2 To max
Dim sum As Int
For j = 1 To i / 2
If i Mod j = 0 Then sum = sum + j
Next
If sum = i Then numbers.Add(i)
Next
Return numbers
End Sub


This function takes an integer parameter max and returns a list of integers containing all the perfect numbers lower than max.

To use this function, you can simply call it and pass the maximum number as an argument, like this:
Dim perfectNumbers As List
perfectNumbers = PerfectNumbers(10000)
This will calculate and return a list of all perfect numbers lower than 10000.

Note: A perfect number is a positive integer that is equal to the sum of its proper divisors, which are the positive integers that divide the number without leaving a remainder. For example, 6 is a perfect number because its proper divisors (1, 2, and 3) add up to 6."




all in about 5 seconds....
absolutely scary, impressive. I think SkyNet is coming...

 

[Erel]

Better to edit the first post with the correct code and numbers...

 

[giggetto71]

done. thanks and happy new year

 

[Erel]

A bit related: https://www.b4x.com/android/forum/threads/b4j-primes-benchmark.132951/