Other Sunday Quiz - Fibonacci series

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

  1. Erel

    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:
    Code:
    300222232244629420445529739893461909967206666939096499764990979600
    500139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
    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. derez

    derez Expert Licensed User

    I use this formula:
    [​IMG]

    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 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 like this.
  3. Erel

    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: Apr 5, 2015
    Peter Simpson likes this.
  4. derez

    derez Expert Licensed User

    Can someone solve the division problem for me please ?
    Code:
    bd.Initialize5(phi.Pow(n).Subtract(phim.Pow(n))) '.Divide(p5))
     
  5. RandomCoder

    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.
    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 result
    End Sub
     
  6. Erel

    Erel Administrator Staff Member Licensed User

    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.ToString
    End Sub
    It is not 100% accurate.
     
    derez likes this.
  7. Erel

    Erel Administrator Staff Member Licensed User

    Nice solution RandomCoder. I expect it to be very fast. Simple and elegant.
     
  8. RandomCoder

    RandomCoder Well-Known Member Licensed User

    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. imbault

    imbault Well-Known Member Licensed User

    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 res
    End Sub
     
    Peter Simpson, Erel and RandomCoder like this.
  10. derez

    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.
     
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice