Problem 2: Fibonacci C-quence

Find_ifs & types & Boole, oh my!

C++ next to the R code. It looks a little busy ’cause C++ needs to do certain things differently.

1

At the very least you get a gist of what’s going on. I’m gonna go through this in order of things which make most sense. And it’s colour coded for better mental digestion.

R-if-thym & blues

You can afford to have two separate if-statements checking for evenness. There’s other ways, like using vectors and iterators and loops, but there’s nothing to gain in efficiency when you only need to check two values.

The green while

This part is almost exactly the same. But remember that hooplah about ensuring the last value was below the threshold? Originally in the while-loop, it created a new Fibonacci number and then added it. This meant that “while(newfib<thr)” always checked the previous Fibonacci number, so the last time through the loop, it ends up adding a number larger than the threshold. Here, we immediately add the new Fibonacci number, and then create the new one. This way it always adds the most recently checked number, and never goes above the threshold. Swish.

R-oxanne! You don’t have to declare the red type

R represents all numbers the same way. C++ doesn’t. For integers, you tend to use int or long, either signed/unsigned. A long long unsigned (8 bytes / 64 bits) precisely stores integers up to 1.8E+19. Since you rarely deal with numbers that large, you can sacrifice precision for range. You can drop the number of significant digits to 7 or 15 (float or double), and use the bits gained, to have a larger range for the exponent, reaching up to 1.7E ± 308. See here for type ranges. What types to use? Consider what each variable is doing:

  • Since s1 and s2 are provided by the user, and checked for evenness by integer division, they are just integers.
  • fibc is gotten by adding up s1 and s2, and is only used for finding out which of the first three numbers is even. This is also int.
  • fiba, fibb, and newfib are used in the while-loop, and store increasingly larger numbers, so we’ll use double.
  • thr is provided by the user, and is likely to be in the range of int or long, but it doesn’t hurt to make it double. fibsum is our final cumulative sum, so that’s double.
  • Note: when you mix numbers of different types  in a calculation, the lower (less precise) type gets ‘promoted’ to a more precise type. For example, int fibc = s1+s2, which are also both int. But we declare double newfib = fibc. Fibc and s1 and s2 remain unmolested, but the int value of fibc, when put into newfib, is stored as double. Useful!

Orange you glad I left this ’till last?

There may be easier ways of doing this, but I haven’t found it. But hey, it’s a good opportunity to introduce new ideas. We want to store the index of whichever of the first three values is even. We can’t use ‘which’ in C++, so we use an iterator. See ‘unique’ here for a reminder.

  • We want fiba, fibb, fibc as a vector, and to work out which is even. We can’t just explicitly put elements into a vector in C++ (unless we do it one-by-one), so we have to initialize it. There’s a number of ways you can initialize/construct it: it can be empty, or each value can be identical, or you can copy a range from somewhere, or you can copy a preexisting vector. The third option is the one to use, here.
  • You can explicitly put elements in an array (a fixed-length vector) though.
  • 2
  •  Then we copy this whole range into the vector we want to search through.
  • 3
  • The stuff in parentheses, in this context, is called a constructor. By default, if you put an object (fibarr) in the beginning location of a constructor, it refers to the first element, which is numbered [0]. fibarr+3 refers to the [4]th element, which is one-past-the-end, essentially saying ‘up to but not including’, so we have the three elements fiba, fibb, fibbc, numbered [0],[1],[2].
  • 4
  • This says: search (find_if) through this vector, returning an iterator/pointer to the element which fulfils a certain (IsEven) condition.
  • 5
  • IsEven is a tiny little function which returns a Boolean value (true) if a certain condition (evenness) is met. Otherwise, it returns false. (George Boole is considered the father of computer logic. Like, he banged computer logic’s mom).
  • We define this before main, so that main knows what’s happening when IsEven is called. Or we can define it after main, as long as we declare it “bool IsEven (int i)” before. (This function is too small to justify a header-file).
  • Anyway, the above line returns an iterator (it) to the first instance of that condition being true (since there can only be one even instance in a group of three sequential Fibonacci numbers, that’s all we need).
  • ‘it’ points to the value though, not the index. So here’s a little trick to get the index:
  • 6
  • This finds the distance between the first value and ‘it’. So you add 1 to get the true index.
  • We also have setprecision in the final line to specify the number of significant digits to use in returning an answer (7 sig figs / 6 decimal places).

That’s it! Sorted.

Next up: a spectacular proof that works out a formula for generating Fibonacci numbers, without needing to find any earlier Fibonacci numbers. Gosh! Mathemagical.

Advertisements
This entry was posted in C++, Problem 2 and tagged , . Bookmark the permalink.

4 Responses to Problem 2: Fibonacci C-quence

  1. coreykpunches says:

    Just curious; was there a reason not to use a recursive function? Like the old saying goes, “There’s more than one way to skin a cat.” Which come to think of it is a pretty horrible thing to think about doing. Regardless, computer programming allows one a certain amount of creativity in solving a particular problem and your way works just fine. When I was a lad in school we almost always were introduced to recursion in a particular language by programming two functions: factorials and the Fibonacci sequence. An example (in C++ that I stole from internet)

    long fib(int n)
    {
    if ((n == 0) || (n == 1)) // stopping cases
    return 1;
    else // recursive case
    return fib(n – 1) + fib(n – 2);
    }

  2. hercles says:

    To be honest, it never even occurred to me!! But looking at it, I don’t think recursive is the best for Fibonacci. For fib(5), you end up calling fib(3) twice, fib(2) thrice, fib(1) five times, and fib(0) thrice: http://i.minus.com/iU3S8fUtyFlWd.gif
    14 calls and 10 additions! Compared to needing just 5 loops and 5 additions!
    Actually, just tried it, and for fib values<10000000, recursive was 1.5 seconds, while the original is 0.03.

    Though thinking about it, if for every fib (n-1) + fib (n-2), if you were able to execute fib(n-2) first and the smaller one of that etc before returning to the top level, and store the answer, so that fib (n-1) and all the other left-hand ones already had a value they could return, then you could do it quicker. Although now that I've put it into words, I realize that's exactly the same as the original method, but in reverse, heh.

    I will keep it in mind and use recursion if I see a problem it would work well for though. Like Quicksort (i dunno if you're familiar, but there's a great visual here http://en.wikipedia.org/wiki/Quicksort), where each half of the task can be done independently (which also means it can be parallelized).

  3. coreykpunches says:

    Interesting, too be honest I would have thought the recursive method would have been faster as the compiler would just need to generate “jump” instructions for the recursive calls vs the need to “unroll” the loops to generate corresponding “test” and “jump” instructions, which should lead to faster code. Go figure! 😉

  4. hercles says:

    I don’t really know too much about optimization or compilers yet. But if it executes sequentially, then recursive being slower still makes sense to me. So I just fiddled with the compiler and turned on whatever optimization options I could find, and recursive doubled in speed to 0.75s. The regular one more-or-less stayed the same though.
    If I understand you correctly, then ‘unrolling’ is putting the code in long-form so that the whole path is set out?
    In which case, the recursive one will still always at the bottom level, end up being 1+1+1+1+…
    The original, each time through the loop has two tests, three assignments, and then that modular 123123 addition. So for each time through the loop it’s 6 operations. And a third of the time it adds an even number. So, for 16 fib numbers, it’s (16*6)+5 = 101 operations. Which is just a linear time-complexity.
    Whereas the 16th Fibonacci number is 1597, which is still a pain in the ass to add up 1-by-1, and the time complexity is more exponential.

    (Except I think instead of the base being 2, it’s the golden ratio).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s