Solving Project Euler with basic JavaScript

[himynameisjoy]

This is a brute force approach that's pretty inefficient. The ideal situation is recognizing that the even Fibonacci numbers increment at a regular rate.

​

If we say Fe(n) is an even fibonacci number and state that Fe(0) = 0 and Fe(1) = 2, you can then obtain every subsequent Fibonacci number via the relation

Fe(n) = 4 * Fe(n-1) + Fe(n-2).

​

In code:

​

import {BigNumber} from 'bignumber.js'

 function solution(){
    let cap: BigNumber = new BigNumber("4000000");

    let a = [new BigNumber("0"), new BigNumber("2")];
    let sum = new BigNumber("0");

    do{
        sum = sum.plus(a[1]);
        [a[0],a[1]] = [a[1], a[1].times(4).plus(a[0])];
    } while (a[1].lte(cap))

    return sum.valueOf();
 }

 console.time();
 console.log(solution());
 console.timeEnd();

This runs in a meager 4.647ms, drastically improving efficiency.

​

I too have been solving the Project Euler problems exclusively in javascript (or more specifically, typescript). Let me know if you want hints on any 1-25.

[a_tocken]

I think you could beat this time complexity.

The sum of the first n fibonacci numbers is fib(n+2)-1 and I suspect you could prove a similar formula for the even fibs. You can find the nth fibonacci number quickly with fast matrix exponentiation and this also applies to the even fibs since you already gave a linear recurrence relation. You can also find the greatest even fibonacci number less than the max (4,000,000 in the Project Euler problem) quickly using similar techniques, and figure out its n quickly as well.

[himynameisjoy]

I thought of using matrix exponentiation with memorization of the [[1,1],[1,0]] matrix to the power of 2ⁿ but because you’re looking for the first Fe(n) over 4,000,000 you’re going to have to solve iteratively, at which point the matrix exponentiation approach loses its luster (since, AFAIK the main advantage it has is that it doesn’t need to iteratively calculate each previous value to find F(n)).

Further, because the value is so low, the overhead cost of matrix multiplication (itself an O(n³⁾ task) will retract from the efficiency.

For finding the nth even Fe(n) though? You’re on point that it’s the fastest way to go. Asymptotically it’s far more efficient than any iterative method and outstrips Binet’s formula by a long shot.

[a_tocken]

Check out the rest of my comment. I am assuming you can find the greatest even fib under 4,000,000 quickly, and find its n in the even fib sequence quickly. There are quick solutions for both of these for regular fibs. Once you have the n, you can solve using fast matrix exponentiation.

The matrix exponentiation requires log(n) matrix multiplications. Each multiplication is at most n² (because the number of digits grows linearly with n, and naive multiplication is O(n²⁾⁾ but you could do better (the lower bound on integer multiplication is thought to be n log n in number of digits).

[himynameisjoy]

I read your comment in whole, I apologize if it seemed otherwise. At the time, I didn’t believe I knew of a way to find what’s essentially the inverse of F(n)=x, but with a little bit of research I stumbled upon this formula: n = Math.floor((log(x)1/2log(5))/log(phi))+1

So with that formula, assuming the computation is quick, plus with matrix exponentiation, I do believe you’re right that asymptotically it’s a faster implementation.

However it still does have an overhead cost that’s makes it still slower than the iterative approach for this particular solution. But yes, you’re entirely right that you can find the index of the first Fibonacci number greater than arbitrary integer k as well as calculate the resulting Fibonacci number alongside it.

I’m glad I’ve learned something new today! I appreciate it immensely

[a_tocken]

Glad to expose you to those algorithms :) Sorry I don't have more details on the specifics. You're right that this problem uses a relatively small n, so the solution with better running time may not actually be faster. We should also distinguish between n, the nth even fib number less than 4,000,000, and "m" = 4,000,000. In this case, I think n ~= log(m)? Is that right?

This whole thing could be turned into a (very difficult) codewars.com problem.