Other Sunday Quiz - Fibonacci series

Erel

Administrator
Staff member
Licensed User
Inspired by this thread: http://www.b4x.com/android/forum/threads/a-little-programmers-humor.52576/#post-329226

Create a program that calculates the 300 and 500 numbers in Fibonacci series.

The answers are:
B4X:
300: 222232244629420445529739893461909967206666939096499764990979600
500: 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
Naive implementation:
B4X:
Sub Fibonacci1(x As Int) As Long
   If x = 1 Then Return 1
   If x = 2 Then Return 1
   Return Fibonacci1(x - 1) + Fibonacci1(x - 2)
End Sub
 

derez

Expert
Licensed User
I use this formula:


with this code with bigdecimals:
B4X:
Sub Process_Globals
    Private fx As JFX
    Private MainForm As Form
   
    Dim phi, phim As BigDecimal
    phi.Initialize(1.61803398874989484820458683436563811772030917980576)
    phim.initialize(-0.61803398874989484820458683436563811772030917980576)
    Dim p5 As Double = 2.23606797749979  ' = sqrt(5)
   
End Sub

Sub fibonacy(n As Int) As Int
Dim bd As BigDecimal
bd.Initialize5(phi.Pow(n).Subtract(phim.Pow(n))) '.Divide(p5))
Return Round( bd/p5)
End Sub
It goes up to 46 because I can't get the bigdecimal to divide by sqrt(5).
 

Erel

Administrator
Staff member
Licensed User
Nice. But there is still some room for improvement...

My implementation is actually quite simple and not far from the "naive solution". It solves Fibonnaci(1000) in 23ms.

This is the result:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
 
Last edited:

derez

Expert
Licensed User
Can someone solve the division problem for me please ?
B4X:
bd.Initialize5(phi.Pow(n).Subtract(phim.Pow(n))) '.Divide(p5))
 

RandomCoder

Well-Known Member
Licensed User
With this code I get the same result as you @Erel for 300 and 500 numbers so I'm guessing its a working solution. It took some getting my head around how BigNumbers work! I've also no idea how fast or slow it is at working the solution out.
B4X:
Private Sub Fibonacci(N As Int) As BigInteger
    Dim result As BigInteger
    If N = 1 Then result.Initialize(1)
    If N = 2 Then result.Initialize(1)
    If N > 2 Then
        Dim n_1 As BigInteger
        Dim n_2 As BigInteger
        n_1.Initialize(1)
        n_2.Initialize(1)
        For i = 1 To (N-2)
            result.Initialize(0)
            result.Add(n_1)
            result.Add(n_2)
            n_2.Initialize7(n_1)
            n_1.Initialize7(result)
        Next
    End If
    Return result
End Sub
 

Erel

Administrator
Staff member
Licensed User
Try this:
B4X:
Sub fibonacy(n As Int) As String
   Dim phi, phim As BigDecimal

   phi.Initialize(1.61803398874989484820458683436563811772030917980576)
  phim.initialize(-0.61803398874989484820458683436563811772030917980576)
   
   Dim bd As BigDecimal
   bd.Initialize5(phi.Pow(n).Subtract(phim.Pow(n))) '.Divide(p5))
   Dim sqrt5 As BigDecimal
   sqrt5.Initialize(Sqrt(5))
   Return bd.Divide2(sqrt5, 1000, bd.ROUND_HALF_EVEN).Round(1000, bd.ROUND_HALF_EVEN).ToBigInteger.ToString
End Sub
It is not 100% accurate.
 

RandomCoder

Well-Known Member
Licensed User
Nice solution RandomCoder. I expect it to be very fast. Simple and elegant.
A polite way of saying 'old school' :)
Your naive implementation gave me a headache trying to suss out how it actually worked, recursively calling itself.
 

imbault

Well-Known Member
Licensed User
My solution using BigNumbers too: (little bit like Randomcoder)
B4X:
Sub Fibonacci( n As Int) As BigInteger
    Dim k As Int
    Dim i,res As BigInteger
    i.Initialize(1)
    res.Initialize(0)
    For k=1 To n
        Dim temp As BigInteger
        temp.initialize(i)
        temp.Add(res)
        i=res
        res=temp
    Next
    Return res
End Sub
 

derez

Expert
Licensed User
Erel
The solution in #7 differs from your soultion in #3 after this 434665576869... I wouldn't trust the formula for big numbers.
 
Top