9
\$\begingroup\$

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 \$N\$, find the sum of the even-valued terms.

Input Format:

First line contains \$T\$ that denotes the number of test cases. This is followed by \$T\$ lines, each containing an integer, \$N\$.

Output Format:

Print the required answer for each test case.

Constraints:

\$1 \le T \le 10^{5}\$
\$10 \le N \le 4 \times 10^{16}\$

#include <iostream>

int main () {
    int nCases;
    std::cin >> nCases;
    for (int i = 0; i < nCases; i++) {
        unsigned long back = 1;
        unsigned long front = 2;
        unsigned long total = front;
        unsigned long maxNumber;
        std::cin >> maxNumber;
        while (true) {
            unsigned long frontPrime = front;
            front = (3 * front) + (2 * back);
            back = (2 * frontPrime) + back;
            if (front > maxNumber) {
                break;
            } else {
                total += front;
            }
        }
        std::cout << total << '\n';
    }
    return 0;
}

Commented and formatted:

#include <iostream>

int main () {
    int nCases;
    std::cin >> nCases;

    for (int i = 0; i < nCases; i++) {
        unsigned long back  = 1; // First number of the sequence
        unsigned long front = 2; // Second number of the sequence
        unsigned long total = front; // Since out of the 2, only front is even

        unsigned long maxNumber;
        std::cin >> maxNumber;

        // Keep on getting the even numbers until the number becomes
        // greater than the max
        while (true) {
            unsigned long frontPrime = front; // Need to store its original value for use later

            // We know that every 3rd number is even:
            // 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
            // o, o, e, o, o, e,  o,  o,  e,  o,  o,   e...
            // Since an odd plus an odd has to equal an even,
            // but an even and an odd is always odd.
            //
            // So using f(n+2) = f(n+1)        + f(n)
            //                 = f(n) + f(n-1) + f(n)
            //                 = 2f(n) + f(n-1)
            //
            // and      f(n+3) = f(n+2)               + f(n+1)
            //                 = f(n+1)        + f(n) + f(n) + f(n-1)
            //                 = f(n) + f(n-1) + f(n) + f(n) + f(n-1)
            //                 = 3f(n) + 2f(n-1)
            //
            // Where n = front, and n-1 = back,
            // we can save from iterating more than once.
            // n+2 is 3 spaces ahead of n-1, and n+3 is 3 spaces ahead of n,
            // thus we go to each even only and save a modulo check.

            front = (3 * front) + (2 * back);
            back  = (2 * frontPrime) + back;

            if (front > maxNumber) {
                break;
            } else {
                total += front;
            }
        }

        std::cout << total << '\n';
    }

    return 0;
}

I was wondering if there is anything I could do to improve the efficiency, both processor- and memory-wise, size (of the code itself not the comments), or general style.

I am also curious as to whether or not there would be a better way to do my algorithm so as not to store frontPrime.

\$\endgroup\$
  • \$\begingroup\$ Just curious where you got this problem? Project Euler #2 is much, much simpler as stated here: projecteuler.net/problem=2. Notice that it only ask for a single summation, and the upper bound is 4 million (4E6) not 4E16 \$\endgroup\$ – thurizas Jul 29 '16 at 18:20
  • 1
    \$\begingroup\$ This is ProjectEuler+ at Hackerrank. \$\endgroup\$ – Ziyad Edher Jul 29 '16 at 18:58
11
\$\begingroup\$

I see a number of things that may help you improve your code.

Make it clear when loops end

The code currently uses while (true) but it doesn't really loop infinitely. It's better, generally, to have the loop exit condition explicitly stated. For example we could rewrite your main loop as:

unsigned long total = 0;
while (front <= maxNumber) {
    total += front;
    unsigned long frontPrime = front;
    front = (3 * front) + (2 * back);
    back = (2 * frontPrime) + back;
}

Analyze the mathematics

Your mathematical analysis is correct as far as it goes, but there's a bit easier way to do it. A bit more algebra will convince you that the series looks like this:

$$a_0 = 0$$ $$a_1 = 2$$ $$a_n = 4a_{n-1} + a_{n-2}$$

Derivation of this sequence

The Fibonacci numbers are defined as: $$F_0 = 0$$ $$F_1 = 1$$ $$F_n = F_{n-1} + F_{n-2}$$ As you've already noted, the sum of two odd number is even, and the sum of an odd and even number is odd. For the Fibonacci sequence, this means that the sequence of \$O\$ (odd) and \$E\$ (even) looks like this:

$$E, O, O, E, O, O, E, ...$$ In other words, every third term is even. This gets us to the fact that \$a_n = F_{3n}\$. From this observation, we have this:

$$a_n = F_{3n}$$ $$a_{n-1} = F_{3(n-1)} = F_{3n-3}$$ $$a_{n-2} = F_{3(n-2)} = F_{3n-6}$$ $$a_n = F_{3n-1} + F_{3n-2}$$ Using the definition of the Fibonacci sequence, and expanding the terms on the right, this becomes: $$a_n = F_{3n-2} + F_{3n-3} + F_{3n-3} + F_{3n-4}$$ Substituting \$a\$ terms for \$F\$ terms, we have: $$a_n = F_{3n-2} + 2a_{n-1} + F_{3n-4}$$ Expanding the \$F\$ terms on the right again using the definition of the Fibonacci sequence yields: $$a_n = F_{3n-3} + F_{3n-4} + 2a_{n-1} + F_{3n-5} + F_{3n-6}$$ Again, substitute \$a\$ terms for \$F\$ terms: $$a_n = a_{n-1} + F_{3n-4} + 2a_{n-1} + F_{3n-5} + a_{n-2}$$ Doing one last substitution and rearranging terms, we get: $$a_n = 4a_{n-1} + a_{n-2}$$

Code implementation

That means that the outer loop could instead be written like this:

unsigned long back = 0;
unsigned long front = 2;
unsigned long current=0;
unsigned long total = front;
unsigned long maxNumber;
std::cin >> maxNumber;
while (front <= maxNumber) {
    total += current;
    current = 4*front + back;
    back = front;
    front = current;
}
std::cout << total << '\n';

In this scheme \$a_{n-2}\$ is named back and \$a_{n-1}\$ is named front. Naturally, \$a_n\$ is named current.

Don't recompute values

The sequence is the same every time, so it really doesn't make much sense to recompute values every time. Better would be to compute them once and save them in a std::vector or std::array. Even better is to compute the values once at compile time. Given the input range, there are less than 30 terms, which is a very modest storage requirement.

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your comments! I am wondering, though, if you could explain the algebraic proof behind the new formula that you are using, it works logically, but I can't seem to prove it arithmetically. \$\endgroup\$ – Ziyad Edher Jul 29 '16 at 15:19
  • \$\begingroup\$ I've added the derivation to my answer. \$\endgroup\$ – Edward Jul 29 '16 at 15:52
2
\$\begingroup\$

An alternative approach would be to compute the desired value directly instead of looping. For the piddling small values involved here it doesn't make a difference (there are only 81 Fibs below the limit of 4 * 10^16) but it could be useful in a challenge.

Inspecting the sequence of the sums of even Fibs (i.e. every 3rd Fib) shows that

sum(F(3*i)) for 1..n = (F(3n + 2) - 1)  / 2

If we had a function fib(n) that returns the nth Fibonacci number and its inverse bif(n) which returns the index of the largest Fibonacci number not exceeding n, then it would be trivially easy to obtain the desired sum:

ulong Euler0002 (ulong n)
{
    int k = bif(n), last_even_term = k - k % 3;

    return (fib(last_even_term + 2) - 1) / 2;
}

The Wikipedia article on Fibonacci numbers gives a closed form for the nth Fib; translated to C# it reads:

const double PHI     = 1.6180339887498948482045868343656381177;
const double LOG_PHI = 0.4812118250596034474977589134243684231;
const double SQRT_5  = 2.2360679774997896964091736687312762354;

// note: works only up to n = 70 with .Net!
static ulong fib (int n)
{
    return n <= 0 ? 0u : (ulong)Math.Round(Math.Pow(PHI, n) / SQRT_5);
}

My hashish rendering of the inverted function is not as lean and mean as I'd like, but it is at least serviceable:

static int bif (ulong n)
{
    int x = Math.Max(0, (int)(Math.Log(SQRT_5 * n) / LOG_PHI));

    if (fib(x) > n)
        return x - 1;

    if (fib(x + 1) <= n)
        return x + 1;

    return x;
}

That completes the exercise - Euler #2 computed directly, without enumerating the whole sequence.

P.S.: doubles are limited to 53 bits of precision - not enough for the task under consideration - and I've vetted the code only with regard to the original Euler specs (4 * 10^6). When testing revealed the limit of fib() to be 70 (first faulty value is for n = 71) I decided it was good enough. Since the problem under consideration requires F(83) it would be necessary to code a version of fib() that can go that high. However, I only wanted to show an alternative road and for that my sample code should suffice.

\$\endgroup\$
  • 1
    \$\begingroup\$ "sum(F(3*i)) for 1..n = (F(n+2) - 1) / 2" is wrong, and should be \$\frac{F_{3n+2} - 1}{2}\$. I also suggest not using the closed form for Fibonacci; Fibonacci grows exponentially so precision decreases before any speed-up would be meaningful. I think pow uses iteration internally anyway. The inverted function is useful, though. \$\endgroup\$ – Veedrac Jul 31 '16 at 10:57
  • \$\begingroup\$ @Veedrac: the closed forms can be useful in connection with something like gp/PARI when dealing with big numbers. Also, Delphi and BC++ aren't hobbled like .Net; they have a long double type with 64 bits of precision and so the sample code works there. \$\endgroup\$ – DarthGizka Jul 31 '16 at 11:08
  • \$\begingroup\$ Regarding the formula, you're right of course, and I've adjusted it in the text. \$\endgroup\$ – DarthGizka Jul 31 '16 at 11:18
  • 1
    \$\begingroup\$ I'd still expect repeated squaring on big integers to do better than the closed formula on arbitrary precision floats. You linked PARI, which seems to also use big integers for its implementation. It's just that repeated squaring is cheap enough that I can easily calculate values of fib 100MB long, so clearly it's Fast Enough™ that it doesn't make sense to give away correctness. \$\endgroup\$ – Veedrac Jul 31 '16 at 11:40
  • 1
    \$\begingroup\$ Haha, true \$\ddot\smile\$. \$\endgroup\$ – Veedrac Jul 31 '16 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.