Problem 2: Fibonacci sequence

Look, I  just need to get this out of the way first, then I’ll go back to what passes for normal:

libseq

Okay.

Problem 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.

Since Fibonacci numbers are based on simple recursion (old output is new input), they tend to pop up quite a bit (particularly in nature). Don’t worry, I’m not gonna go on about their “mystical power” or anything, because that has been done to death, and I’d feel like a hack. I will say that regardless of how familiar you are with the numbers, do check out these three (short!) videos by Vi Hart, who has a really delightful and playful approach to math.

All we wanna do is: generate the Fibonacci numbers less than 4,000,000. Sum up all the even numbered ones. Simple. I tried this about a year ago when I hadn’t been using R for very long, and needless to say, present-Herc is extremely disappointed in past-Herc’s early functions.

Pic1

It’s okay, you can point and laugh, I have no illusions. They don’t even merit being translated into C++ code.

  • I used vectors. In a situation where we’re only interested in each number for but a moment. Stoopid. And I used append. Like a moron. If computer memory was a rainforest, I’d have sooo many tree-huggers up in my grille right now.
  • If I’d written the while-loop more carefully, I wouldn’t have needed to do add a line removing the last element. Even worse, instead of directly removing the last element, I used ‘which’, which checks every element in the vector. Dumb.
  • About the only non-dumb thing I did was use a while-loop instead of a for-loop. But that’s only because there was no way of knowing how many times I would need to loop.
  • The only display of inspiration here is the use of seq(uence) in the second function. The first function checks all numbers in the (long and stupid) vector, for evenness (dumb). The second creates a sequence from 2 to the length of the vector, in multiples of 3, and adds the numbers at those indices. Why?

Our seed numbers for our sequence are 1, 2. Odd/even. So the next numbers are:

  • 1+2=3 or odd+even=odd
  • 2+3=5 or even+odd=odd
  • 5+3=8 or odd+odd=even
  • 8+13=21 or even+odd=odd and obviously the pattern keeps repeating!

Since we know that the first even number in the sequence is the 2nd one, then it means the 5th, 8th etc must all be even!

  • Both functions return the correct answer for the sum of even Fibonacci numbers below 4,000,000. Fine.
  • The first function fails at 4E+16 (4 followed by 16 zeros), due to “probable complete loss of accuracy in modulus”. Yeah, checking every number for evenness is, what’s the word I’m looking for? Dumb. Because R stores integers as real numbers (so 1 is 1.0), and doing remainder division gets stupid at large numbers.
  • The second function, which doesn’t dick around with calculations on large numbers, returns an answer up to and including 4E+307. Fucking hell!
  • But it only returns correct answers up to and including 4E+306, because of the limit R reaches in representing numbers.

The fact that it can even get to numbers that high sounds weird, considering we’re storing all the Fibonacci numbers up to that point, in a vector, and using append, which isn’t efficient memory use. But Fibonacci numbers get big very quickly. To get to the next number, you’re essentially multiplying the current one by a number that is somewhere between 1 and 2 (it’s actually pretty close to 1.6, and is called the Golden ratio. we’ll come back to this when it’s relevant). In fact, going up to 4E+308 just takes 1474 Fibonacci numbers, only 492 of which are even! But the value of the 1475th Fibonacci number comes out as INF, as the largest number R can represent is 1.797693E+308. Which is fair enough. This is how quickly the numbers get ridiculous:

Pic4

Anyway, ‘dumb’ is not a good look for anyone, so we’ll ditch vectors, and only worry about the absolutely necessary numbers. It’s a straightforward while-loop: we have two numbers, ‘fiba’ and ‘fibb’. ‘newfib’ is the sum of these. In the while-loop, if newfib is even, we add it to our cumulative sum. Then we just replace fiba and fibb each time, So 1,2 becomes 2,3 etc. Pretty simple:

Pic5

Note: the 2nd condition in the if-statement (newfib<thr) is because of bad loop design (my bad), and is for making sure the last element is below 4,000,000. Again, this function was written ages ago, and even though it gives the right answers, we still have the problem of checking the modulus/remainder of large numbers, and it still fails at 4E+16. But you can tell that it’s better than the first function. But how to deal with that dividing/remainder for large numbers problem?

  • We know there’s an even number every 3 numbers.
  • We could set up a loop counter. Instead of dividing a huge value by 2, we divide a much smaller index by 3. But still, theoretically, there’s no limit to how large this index can get.
  • What if we use remainder/modulus to cycle through the numbers 1, 2, 3 repeatedly, only adding a Fibonacci number at the right time? This also means that 1 and 2 don’t always have to be the start of the sequence. The code becomes more general. Smart:

Pic7

Here’s a clearer explanation:

Pic8

This works reliably all the way up to 4E+306, without vectors or performing calculations (apart from simple addition) on very large numbers! Swish!

Hmm. Covered four drafts of the algorithm in under 1,000 words. I’m getting a wee bit better at this. Next up: translating this to C++.

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

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