  Other Sunday Quiz - Fibonacci series

Discussion in 'Android Questions' started by Erel, Apr 5, 2015.

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

Code:
`300: 222232244629420445529739893461909967206666939096499764990979600500: 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125`
Naive implementation:
Code:
`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`

2. I use this formula: with this code with bigdecimals:
Code:
`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 SubSub fibonacy(n As Int) As IntDim bd As BigDecimalbd.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 like this.
3. 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: Apr 5, 2015
Peter Simpson likes this.
4. Can someone solve the division problem for me please ?
Code:
`bd.Initialize5(phi.Pow(n).Subtract(phim.Pow(n))) '.Divide(p5))`

5. 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.
Code:
`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 resultEnd Sub`

6. Try this:
Code:
`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.ToStringEnd Sub`
It is not 100% accurate.

derez likes this.
7. Nice solution RandomCoder. I expect it to be very fast. Simple and elegant.

8. 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 likes this.
9. My solution using BigNumbers too: (little bit like Randomcoder)
Code:
`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 resEnd Sub`

Peter Simpson, Erel and RandomCoder like this.
10. Erel
The solution in #7 differs from your soultion in #3 after this 434665576869... I wouldn't trust the formula for big numbers.