Fibonacci sequence and Golden Ratio

I haven’t written a math-related article in a while, so in this article, I’ll tell you about the Fibonacci sequence, the golden ratio and some associated program code.

Say you’re given this math formula, and told to find what the nth term is.
F(n) = F(n-1) + F(n-2)
where F(1) = F(2) = 1

Wow, initial conditions are given, a formula is given. Functions! In fact, use recursive functions! That was easy to code, wasn’t it?

What if you’re given this sequence of numbers and told to find what the nth term is?
1,1,2,3,5,8,13,21 …

You would get exactly the same answer for both questions. Notice that each subsequent number is a sum of the previous two numbers (except the first two in the sequence). Once you find the pattern, you can make use of simple loops instead of recursive functions. Generally speaking, recursive functions are slower, and you would not have known the simpler loop solution if you hadn’t analysed the problem first.

Of course, if you knew the numbers form the Fibonacci sequence, you wouldn’t have much of a problem in the first place, would you? You might have heard of it in Da Vinci Code, where the sequence was used to decipher a password number.

Now, the interesting thing about this sequence is that Nature uses it. I haven’t personally verified this, but sunflowers, pineapples and daisies exhibit the use. If you count the number of bumps on them going to the left, and the number of bumps to the right, you’ll find that the numbers are right next to each other in the Fibonacci sequence. For example, sunflowers have 34 spirals to the left and 55 to the right.

The rabbits, man do they breed!

There’s actually a story about how the Fibonacci sequence came about. You might have guessed that Fibonacci is the name of a mathematician. Anyway, the story goes like this. Suppose there are 2 rabbits, one male and one female. Each month, they produce two rabbits, again, one male and one female. The baby rabbits take one month to grow, and become sexually reproductive in their second month. In this manner, how many rabbits are there at the end of 12 months?

In the first month, there are 2.
At the end of the second month, there’s 4 (2 original, 2 babies).
At the end of the third month, there’s 6 (2 original, 2 from 2nd month, 2 babies from original).

At the end of the fourth month, there’s the original 2, the 2 from 2nd month, the 2 from 3rd month, 2 babies from the original 2, and 2 babies from the 2 of the 2nd month. Total rabbits: 10.

Just typing this out is confusing, but you can see a pattern emerging.
2, 4, 6, 10 …
Each subsequent term is a sum of the previous two terms.

Oh yes, the number of rabbits in the 12th month is 466.

Some obvious assumptions are

• Rabbits never die
• Babies are always produced in a pair, one male and one female
• Moral values are not considered (incest shmincest!)

The golden ratio

There is another interesting thing. The ratio of F(n+1)/F(n) approaches a limit as n goes to infinity, which is approximately 1.618. This number is known as the golden ratio, with other names such as golden mean, divine proportion and others. Other than its mathematical relevance, I know it to be important as an aesthetic factor.

A rectangle with its sides in this ratio is thought of as aesthetically pleasing. This probably influenced the manufacture of computer screens. You have your standard 4:3s (1.333:1), the 800×600, 1024×768 and others. There are also some who tried the square root 2 ratio, 1.414:1 in computer applications. Then there’s the 16:9 (1.777:1) aspect ratios.

What’s the purpose of these aspect ratios? To approach the golden ratio 1.618:1. Of course, with widescreens, this point is probably moot nowadays. Still, it makes for interesting contemplation.

Ok, let’s do some coding, calculating the nth term using a loop, which I’ve hardcoded as 20. I’ll leave it to you as an exercise to write it as a function. The golden ratio is calculated as well. The first 2 terms are skipped, because they are equal to 1 (initial conditions).

int i;
int current, previous, next;
double phi = 0;
current = previous = 1;
for (i = 2; i < 20; ++i)
{
    next = current + previous;
    previous = current;
    current = next;
    phi = (double)current/(double)previous;
    Console.WriteLine("Term {0,0:d2} = {1,0:d5}, Phi = {2,0:f8}", i + 1, current, phi);
}

Fairly simple. The point is to convert a problem into a program solution. The difficult part isn’t the original problem, nor is it about coding skills. It’s about translating a problem into a program that’s difficult.

There you have it. Math theory and supporting program code. Hope you enjoyed it.

Two trains and a bumblebee problem

I was intrigued by this math problem a while ago. It took me a couple of pages of calculations to get the solution. Then I kicked myself because the solution was actually staring in my face.

I can’t find the original problem now, although there seem to be other variations of it. So I’m going to give you my (highly embellished) version. Then see if you can get the answer. Here goes the story of Blitz the bumblebee and the fateful encounter of two trains…

Blitz the bumblebee and the meeting of two caterpillars
Blitz the bumblebee was an adventurous kind of guy. He’d wander further out in the fields than his fellow bumblebees. Now he’d seen these huge black caterpillars (trains) spewing out lots of grey and black clouds passing his fields before. Now Blitz, despite his big size, could fly very fast. But these caterpillars zoomed past him, leaving him in a whirlwind spiral as he tried to get back into control.

So one sunny morning, he decided to test his limits. He waited for one of these caterpillars, and when he heard their telltale “choo choo” from a distance, he started flying as fast as he could in the direction where the caterpillar would move. When the caterpillar moved close to his level, Blitz simply flew to the head of the caterpillar and hung on.

What a thrill! The wind was howling around him and the scenery was speeding past him. Then Blitz wondered where the caterpillar was going. So, using the caterpillar’s speed as initial momentum, Blitz took off.

To his surprise, he flew even faster than the caterpillar! So Blitz shot straight ahead. After some time, Blitz was starting to worry where he’s going, when he heard the “choo choo” coming from in front of him. Before he realised it, he bounced off another caterpillar. Somehow Blitz survived the bounce and flew, out of instinct, back in the direction where he came from.

“This is fun!” Blitz thought. And wondered if he’d meet the first caterpillar again. Sure enough, the first caterpillar appeared, and Blitz bounced off it, and flew towards the second caterpillar. Through this bouncing and flying, it never occurred to Blitz what would happen when the two caterpillars meet.

When the two caterpillars were within sight of each other, Blitz realised that his bounces were getting more frequent. By the time this revelation came, he found he couldn’t stop nor get out of the bouncing cycle anymore.

“They’re gonna crash! I’m too young to die!”

And Blitz promptly fainted, while the two caterpillars amazingly brushed past each other and continued on their merry way…

The end.

The real math problem
Alright, maybe the original problem wasn’t phrased like that, so I’ll give you the short version.

There are two trains running at 45km/h in opposite directions towards each other on two separate (straight) tracks. Assume for the discussion that the difference caused by the separate tracks is negligible. A bumblebee is positioned at the head of the first train. When the trains are 90km apart, the bumblebee flies at 60km/h towards the second train. When the bumblebee meets the second train, it returns and flies back towards the first train. It continues to fly back and forth in this manner until the two trains meet. What is the distance covered by the bumblebee?

I wrote down tons of calculations and numbers. I scrutinised my work and finally found a relationship between the numbers. Then I used mathematical induction to convince myself that the relationship can be written in the form of a geometric progression. The ratio of the geometric progression turned out to be less than 1, so that simplified the equation further. And the answer was … 60km.

Immediately after I got this answer, I found that since the time taken for the two trains to meet is 1 hour (time = distance / speed = 90km / (45km/h + 45km/h)), it also means the bumblebee only flew for 1 hour. With the speed of 60km/h, flying for 1 hour means a distance of 60km covered. I spent about an hour or so and a couple of pieces of paper to figure this out…

Moral of the story? Sometimes, it’s better to think through a problem instead of jumping on the first solution that pops up in your head.

Rapidly calculating Bezier points

The standard cubic Bezier curve is given by
B(t) = (1-t)³p0 + 3(1-t)²tp1 + 3(1-t)t²p2 + t³p3
where p0, p1, p2, p3 are the control points and t is in the interval [0, 1].

Very elegant, but not very practical. Too many multiplications and additions to be used in a fast-paced environment such as game development. If it’s a 3D Bezier curve, 3 separate calculations are needed for the x-, y- and z-component for a given t value. What we need is a simplication of the equation.

Expanding the polynomial equation, we have
B(t)
= (1 - 3t + 3t² - t³)p0
+ (3t -6t² + 3t³)p1
+ (3t² - 3t³)p2
+ t³p3

Rearranging the coefficients of tⁿ, we have
B(t)
= t³(-p0 + 3p1 - 3p2 + p3)
+ t²(3p0 - 6p1 + 3p2)
+ t(-3p0 + 3p1)
+ p0

The coefficients can now be reduced to constants by precalculating them, and calculation of a Bezier point takes less computation.

In matrix form, the equation looks like

Reverse engineering Bezier curves

My initial contact with Bezier curves came when I was studying 3 dimensional computer graphics. The professor introduced the standard cubic Bezier curve equation, which looks something like this

B(t) = (1-t)³p0 + 3(1-t)²tp1 + 3(1-t)t²p2 + t³p3
where p0, p1, p2, p3 are the control points.

WARNING: you might find this an intensive discussion on math, 3D theory and programming.

So the interesting thing about Bezier curves is that they are easy to work with, theoretically and programmatically. There’s only one problem; the curve does not pass through its control points. The curve actually lies in the convex hull of the control points.
This means the control points may not lie on the curve, which makes calculating tangents and normals (for use in 3D trigonometry) tedious.

What I want to do is to define four points and have a Bezier curve passing through all four points. Basically, given the four original points q0, q1, q2 and q3, I will find four points p0, p1, p2 and p3 such that the Bezier curve calculated using points p(i), will pass through the points q(i).

So going back to the equation above, when t is zero, the equation effectively collapses into just p0. When t is one, the equation gives p3. When t is between zero and one, the resulting point lies on the curve itself, so iterating t from zero to one will give the Bezier curve. Since we know the curve will pass through p0 and p3, we need to find p1 and p2.

Suppose we want the curve to pass through p0 when t=0, f when t=u, g when t=v and p3 when t=1, where f and g are the points to be passed through. Next, we make sure that 0 < u,v < 1 and u not equal to v. These conditions will ensure a solution can be found. Next, we substitute the desired points into the equation:

f = (1-u)³p0 + 3(1-u)²up1 + 3(1-u)u²p2 + u³p3
g = (1-v)³p0 + 3(1-v)²vp1 + 3(1-v)v²p2 + v³p3

The two equations are then simplified into

3(1-u)²up1 + 3(1-u)u²p2 = c
3(1-v)²vp1 + 3(1-v)v²p2 = d

where
c = f - (1-u)³p0 - u³p3
d = g - (1-v)³p0 - v³p3

This set of equations has a unique solution when 0 < u,v < 1 and u not equal to v, and assuming c and d aren’t both zero vectors. The equations have a unique solution because the determinant is not zero. Let’s transform the set of equations into matrix form before explaining what a determinant is.

The determinant for the above 2 by 2 matrix on the left-most side is
3(1-u)²u * 3(1-v)v² - 3(1-u)u² * 3(1-v)²v

Factorising this, we get
9uv(1-u)(1-v)[(1-u)v - u(1-v)]
= 9uv(1-u)(1-v)[v -uv -u +uv]
= 9uv(1-u)(1-v)[v - u]

Since 9 obviously is not equal to 0, and 0 < u,v < 1 (so u,v not equal to 0 and (1-u),(1-v) not equal to 0) and u not equal to v (so v-u is not equal to 0), therefore, the determinant is not equal to 0. By a theorem in linear algebra, this means the set of (linear) equations has a unique solution. For a 2 by 2 matrix, the determinant can be obtained by taking the product of the top-left element and bottom-right element, then subtract the product of the top-right element and bottom-left element. Like drawing a cross.

Next, we multiply the inverse of the 2 by 2 matrix on the left of both sides of the equation and we get

Note that the inverse will cancel the matrix on the left side. The inverse (of a 2 by 2 matrix) is obtained by swapping the top-left and bottom-right elements, then switch the signs of the top-right and bottom-left elements, and then divide each element by the determinant. The determinant is non-zero, so division by zero is not a problem. A non-zero determinant also means an inverse actually exists (by another theorem in linear algebra), so all of this works out fine. Now all you have to do is calculate that right side and that’s it. Make sure you calculate for x, y and z, meaning you have to do the calculation three times.

The determinant of an n by n matrix is generally difficult to find, as is the inverse of one. Refer to a linear algebra text book for the theories (they usually use a method called Gaussian elimination. The programmatic approach uses a slightly modified version to reduce computational errors). There’s a “quick and dirty” method for getting the determinant for a 3 by 3 matrix, but anything higher requires the aforementioned theories.

You can download my C program code of reverse engineering a Bezier curve to learn more.