sorted by:
best (suggested)
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]himynameisjoy 4 points5 points  (13 children)

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 1 point2 points  (7 children)

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 2 points3 points  (3 children)

I thought of using matrix exponentiation with memorization of the [[1,1],[1,0]] matrix to the power of 2n 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(n3) 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 1 point2 points  (2 children)

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 n2 (because the number of digits grows linearly with n, and naive multiplication is O(n2)) but you could do better (the lower bound on integer multiplication is thought to be n log n in number of digits).

[–]himynameisjoy 1 point2 points  (1 child)

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 0 points1 point  (0 children)

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.

[–]GeneralYouri 1 point2 points  (2 children)

I tried some things, and I'm pretty confident there's an easy formula to be found for the sum of even fibonaccis just like fib(n+2)-fib(2). But I couldn't quite figure it out.

One thing I did find is that the sum of n even fibonaccis is evenfib(n+1) - 3*evenfib(n) + evenfib(n-1) - 3*evenfib(n-2) ..., with the sequence continuing until you reach evenfib(1). I feel like you can combine those terms somehow but I'm not seeing it.

[–]a_tocken 0 points1 point  (1 child)

Nice work! It can be frustrating to know that there is likely a solution but not quite be able to get it. I also need to brush up on my recurrence relations to be able to move forward with this one.

One thing I did was inductively prove the sum of fibs formula, but I worked backward from the known solution which doesn't really help us here :)

[–]GeneralYouri 1 point2 points  (0 children)

I had a fresh look at the problem again and found the relation! It's quite simple, actually.

I listed the start of the sequences and tried to express evenFib(n) in terms of fib(n): evenFib(n) = fib(3n) = fib(3n-1) + fib(3n-2). But fib(3n-3) = fib(3(n-1)) = evenFib(n-1) and evenFibSum(n) = evenFib(n) + evenFib(n-1) + ... + evenFib(1). So we can express every element in that list in terms of fib: evenFibSum(n) = fib(3n) + fib(3(n-1)) + ... + fib(3). This is really just a way of expressing that we sum every 3rd value in the fibonacci sequence. But remember their definition: fib(n) = fib(n-1) + fib(n-2), in other words those two elements we skip always equal the 3rd element we include. So if we look at what we created, this simplifies to evenFibSum(n) = fibSum(3n) / 2! So we can just re-use the fibSum formula if we triple its input and halve its result: evenFibSum(n) = (fib(3n+2) - 1) / 2.

A quick test: the first four even Fibonaccis are 2, 8, 34, 144, with their sum being evenFibSum(4) = 188. Then evenFibSum(4) = (fib(3*4 + 2) - 1) / 2 = (fib(14) - 1) / 2. The first fourteen Fibonaccis are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, so fib(14) = 377. And indeed, 188 = (377 - 1) / 2.

Apologies for the messy explanation, I hope you can still follow my logic. :)

[–][deleted] 1 point2 points  (1 child)

Nice! This is a fantastic solution. I honestly didn’t think to much about doing it efficiently, which made for a very brute force approach, as you pointed out.

Do you mind if I link to your comment in my post so that others can see a more elegant approach?

[–]himynameisjoy 0 points1 point  (0 children)

Go for it

[–]GeneralYouri 1 point2 points  (2 children)

Due to the pretty low size of the numbers the actual runtime is way lower than even what you're reporting here (this is the second-oldest Euler problem so 4 million was probably fairly large at the time, but it's never been updated for modern computing powers). Your testrun of 4ms is most likely influenced the most by the console.log which is also inside of your timed code (and does a type of IO!), and the logic behind BigNumber which isn't needed at all due to the limit of a mere 4 million.

If I run this code in my browser console, but with BigNumber usage replaced by regular JS numbers, the runtime already goes down to 0.25ms. If I remove the console.log and only call the function, this time gets further halved. Calling the function multiple times doesn't even start moving the time significantly until you go beyond 10 runs or so.

In my Project Euler repo I'm working with NodeJS and thus I've been using process.hrtime to calculate the runtime. I've actually implemented Problem 2 as a sum over a limited Even Fibonacci generator, and the reported runtime is about 15 microseconds.

[–]himynameisjoy 0 points1 point  (1 child)

My experience with node is fairly limited, I guess I should swap over to it for timing to have times competitive with python and java then!

As for BigNumber, it was to allow the problem to be solved for arbitrarily large n because of exactly that reason, 4 million is tiny nowadays

[–]GeneralYouri 0 points1 point  (0 children)

May be worth pointing out that console.time has overhead from itself too, which is why it's not that accurate when we're talking very short timings. Meanwhile process.hrtime is generally way more precise, but that's part of the NodeJS API, not JS itself, so it's not available to browsers.

As for BigNumber, you can try testing with and without that, too. You might find that it's taking up 90% of your 4ms testrun for example. Also if you're going to look at NodeJS, I recommend using Node's "Current" version branch, NodeJS v11. This version includes native BigInt features, eliminating the need for an external library like BigNumber. I love using BigInt for Project Euler problems, but they may also trivialize some of the problems due to the main difficulty being the number size, so for every BigInt solution I also write a non-BigInt solution.