# OtherSunday Quiz - Fibonacci series

#### Erel

##### B4X founder
Staff member
Longtime User

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

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
Longtime 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, NJDude and thedesolatesoul

#### Erel

##### B4X founder
Staff member
Longtime 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:
• Peter Simpson

#### derez

##### Expert
Longtime 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
Longtime 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)
n_2.Initialize7(n_1)
n_1.Initialize7(result)
Next
End If
Return result
End Sub``````

#### Erel

##### B4X founder
Staff member
Longtime 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.

• derez

#### Erel

##### B4X founder
Staff member
Longtime User
Nice solution RandomCoder. I expect it to be very fast. Simple and elegant.

#### RandomCoder

##### Well-Known Member
Longtime 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.

• Peter Simpson

#### imbault

##### Well-Known Member
Longtime 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)
i=res
res=temp
Next
Return res
End Sub``````