why my code is slow when finding Fibonacci sum?

Question

I'm writing answers for project Euler Questions in this repo but having some performance issues in my solution

Question 2: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

My Solution is

func solution2()
{
    func fibonacci(number: Int) -> (Int)
    {
        if number <= 1
        {
            return number
        }
        else
        {
            return fibonacci(number - 1) + fibonacci(number - 2)
        }
    }

    var sum = 0

    print("calculating...")
    for index in 2..<50
    {
        print (index)
        if (fibonacci(index) % 2 == 0)
        {
            sum += fibonacci(index)
        }
    }

    print(sum)
}

My Question is, why it gets super slow after iteration 42, i want to do it for 4000000 as the question says, any help?

solution 2

func solution2_fast()
{
    var phiOne : Double = (1.0 + sqrt(5.0)) / 2.0
    var phiTwo : Double = (1.0 - sqrt(5.0)) / 2.0

    func findFibonacciNumber (nthNumber : Double) -> Int64
    {
        let nthNumber : Double = (pow(phiOne, nthNumber) - (pow(phiTwo, nthNumber))) / sqrt(5.0)
        return Int64(nthNumber)
    }

    var sum : Int64 = 0

    print("calculating...")
    for index in 2..<4000000
    {
        print (index)
        let f = findFibonacciNumber(Double(index))
        if (f % 2 == 0)
        {
            sum += f
        }
    }

    print(sum)

}

Answer 1

The most important thing about PE questions is to think about what it is asking.

This is not asking you to produce all Fibonacci numbers F(n) less than 4000000. It is asking for the sum of all even F(n) less than 4000000.

Think about the sum of all F(n) where F(n) < 10.

1 + 2 + 3 + 5 + 8

I could do this by calculating F(1), then F(2), then F(3), and so on... and then checking they are less than 10 before adding them up.

Or I could store two variables...

F1 = 1
F2 = 2

And a total...

Total = 3

Now I can turn this into a while loop and lose the recursion altogether. In fact, the most complex thing I'm doing is adding two numbers together...

I came up with this...

func sumEvenFibonacci(lessThan limit: Int) -> Int {
    // store the first two Fibonacci numbers
    var n1 = 1
    var n2 = 2

    // and a cumulative total
    var total = 0

    // repeat until you hit the limit
    while n2 < limit {
        // if the current Fibonacci is even then add to total
        if n2 % 2 == 0 {
            total += n2
        }

        // move the stored Fibonacci numbers up by one.
        let temp = n2
        n2 = n2 + n1
        n1 = temp
    }

    return total
}

It runs in a fraction of a second.

sumEvenFibonacci(lessThan: 4000000)

Finds the correct answer.

In fact this... sumEvenFibonacci(lessThan: 1000000000000000000) runs in about half a second.

Answer 2

The second solution seems to be fast(er) although an Int64 will not be sufficient to store the result. The sum of Fibonacci numbers from 2..91 is 7,527,100,471,027,205,936 but the largest number you can store in an Int64 is 9,223,372,036,854,775,807. For this you need to use some other types like BigInteger

Answer 3

Because you use the recursive, and it cache in the memory.If you iteration 42, it maybe has so many fibonacci function in your memory, and recursive.So it isn't suitable for recursive, and you can store the result in the array, not the reason of the swift.

Answer 4

this is the answer in two different ways

func solution2_recursive()
{
    func fibonacci(number: Int) -> (Int)
    {
        if number <= 1
        {
            return number
        }
        else
        {
            return fibonacci(number - 1) + fibonacci(number - 2)
        }
    }
    var sum = 0
    print("calculating...")
    for index in 2..<50
    {
        print (index)
        let f = fibonacci(index)

        if( f < 4000000)
        {
            if (f % 2 == 0)
            {
                sum += f
            }
        }
        else
        {
            print(sum)
            return
        }
    }
}

solution 2

func solution2()
{
    var phiOne : Double = (1.0 + sqrt(5.0)) / 2.0
    var phiTwo : Double = (1.0 - sqrt(5.0)) / 2.0

    func findFibonacciNumber (nthNumber : Double) -> Int64
    {
        let nthNumber : Double = (pow(phiOne, nthNumber) - (pow(phiTwo, nthNumber))) / sqrt(5.0)
        return Int64(nthNumber)
    }

    var sum : Int64 = 0

    print("calculating...")
    for index in 2..<50
    {
        let f = findFibonacciNumber(Double(index))
        if(f < 4000000)
        {
            if (f % 2 == 0)
            {
                sum += f
            }
        }
        else
        {
            print(sum)
            return
        }
    }
}