The Ajax Bus Company operates only a single route -- the Clockwise Circle. They have many buses they can send out, but to save fuel they send only as many as they need. They might have a dozen buses running on a busy day, but just two or even one on a quiet day.
Each circuit takes exactly 60 minutes; a bus can do 24 complete circuits in a 24-hour period. A bus that leaves North Station at 3:00 will arrive at East Park at 3:15, South Lake at 3:30 and Westtown at 3:45. Similarly, a bus that leaves North Station at 3:19 will arrive at the other three stops at 3:34, 3:49, and 4:04.
When only one bus is running, a passenger will need to wait 30 minutes on average, and almost 60 minutes worst-case. As more buses are added, the company wants to reduce the average wait times as best it can but as we now see, it is subject to a severe constraint. Each bus, if it's running at all, sticks to its own specific schedule. For example, bus #2 will leave North station at 1:37, 2:37, 3:37, 4:37, 5:37 and so on, and will always follow that exact same schedule (if it's in service at all) every day of the week.
As a further constraint, when the company runs N buses, those buses must be #1, #2, #3, #4, ..., #N. This is the key constraint which dictates the nature of the problem. For example, suppose buses #1, #2, #3, #4 are scheduled at 3:00, 3:30, 3:20, 3:40. When two buses are running the times 3:00 and 3:30 give optimal coverage; average wait is 15 minutes and maximum wait is 30 minutes. If the company decides to run a third bus, it would be best to take #2 out of service and substitute the two scheduled for 3:20 and 3:40 to get 10-minute average and 20-minute maximum wait. But that is not permitted: With three buses, they must be specifically #1, #2 and #3, and with the stated schedule this gives 11.7-minute average wait and 30-minute maximum wait.
(We've presented this problem as a bus scheduling problem but it has real-world application in scheduling usage of asynchronous-transfer computer networks.)
Denoting φ = (√5 - 1)/2, and noting that φ * 60 minutes = 37.1 minutes, the Golden Ratio Policy is to schedule buses every 37.1 minutes in order. Bus #1 leaves North station at 3:00, Bus #2 at 3:37.1, Bus #3 at 3:14.2 (remember that all times are modulo 60 minutes), Bus #4 at 3:51.3 (3:14.2 + 37.1), Bus #5 at 3:28.4, and so on. You don't get perfect coverage. (Perfect coverage with five buses would be 3:00, 3:12, 3:24, 3:36, 3:48.) But you get the ability to add buses and keep the coverage nearly perfect. Buses #6 and #7, for example, would be added at 3:05.5 and 3:42.6 -- filling the biggest gaps.
So why did I write this page? I didn't invent the Golden Ratio Scheduling Policy and, elegant as it may be, its real-world importance may not be overwhelming. But there is a special reason why I think the Golden Ratio Policy is serendipitous. It depends on the Ratio's special properties. The Golden Ratio is irrational, of course, but first let's speak a little about rational numbers.
Practical engineers have a different understanding of rational numbers than mathematicians do. The number 18/101 = 0.178217821782... is rational by definition, but the number 0.199999999762... might not be. Yet it is the second number, not the first, which is more likely to cause the resonance problems that plague some engineering designs. For such practical purposes, the digits far to the right of the decimal point are irrelevant, let alone the arbitrarily far-away digits necessary for the mathematical definition of rationality.
Thus, for practical problems it is 0.199999999762..., a close approximation to the simple fraction 1/5, that may lead to the behavior associated with simple rational numbers, and not 0.178217821782..., even though it's the latter number that's technically rational.
Continued fractions are a technique that may shed light on this matter. Here are the two numbers
we're discussing now, in continued fraction (C.F.) notation.
18/101 = [0; 5, 1, 1, 1, 1, 2, 1]
0.199999999762 = [0; 5, 168067226, 1, 2, 4, 3, ...]
Google or Wikipedia to learn more about
continued fractions. For our purpose it's enough to know that the C.F. form of a number shows
how well it can be approximated by rational numbers. We depict this in the following table.
By convention we'll call the floor integer the 1st approximant and the next largest
Egyptian fraction the second approximant. For our two numbers, these are the same: 0, then 1/5.
But glance at the rest of the table as well.
| 18/101 | almost 1/5 | ||
|---|---|---|---|
| 0.178217822 | 0.19999999976 | ||
| approximants | |||
| 1st | 0 | 0 | |
| 2nd | .200000000 = 1/5 | .200000000000 | |
| 3rd | .166666667 = 1/6 | .199999999762 | |
| 4th | .181818182 = 2/11 | .199999999762 | |
| 5th | .176470588 = 3/17 | .199999999762 | |
| 6th | .178571429 = 5/28 | .199999999762 | |
| 7th | .178082192 = 13/73 | .199999999762 | |
| 8th | .178217822 = 18/101 | .199999999762 | |
| 9th | .178217822 = 18/101 | .199999999762 | |
For the first number, watch the continued fraction expansion process struggle to find good rational approximations. (Since the number is rational it eventually converges to the exact value, but 13/73 was the only particularly good rational approximation that it found along the way.) On the other hand, for the number that was extremely close to 1/5, the second approximant was quite good and, to the precision shown, we never get better than the third approximant.
I'm spoiling the suspense slightly ( :-) ), but look at the C.F. form of this hard-to-approximate number: 18/101 = [0; 5, 1, 1, 1, 1, 2, 1]. I deliberately chose a number with an early string of 1's in its C.F. -- this is the tip-off that the approximants won't be very good.
Ah heck! Having spoiled the suspense, I'll cut straight to the punchline: The Golden Ratio (φ) is the most irrational number of all!
The Golden Ratio (approx. 0.618034) can be observed in nature, and in the paintings of Leonardo da Vinci, but we are concerned here with its applications in computer algorithms.
One application is the Golden Section Search Algorithm. Binary search, in which you narrow
in on a value by splitting residues into equal halves (0.50, 0.50), is the well-known optimal
way to locate a value in a monotone list.
But the Golden
Section search, in which the residue is split (0.618, 0.382), is optimal when it
is the derivative that is monotone in the list. Read more about it at the
Wikipedia link.
It may be a fun exercise for you to prove the optimality of Golden Section search.
You will see that the efficacy derives from the quadratic equation
φ2 + φ = 1
This particular equation is so very simple, it should be no surprise that φ is the
solution to a wide variety of problems.
But there are some applications of the Golden Ratio in computer algorithms which have nothing to do with any quadratic equation. For example, some hashing algorithms depend on a prime number and a modulus, and the ratio of prime to modulus should not be approximately a small rational number, or an aliasing "beat" may occur. So a prime is chosen that's approximately 0.618034 times the modulus.
Here's a table similar to the one above, with the C.F. forms
of three important mathematical constants compared.
π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, ...]
e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, ...]
φ+1 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]
| π | e | φ+1 | |||
|---|---|---|---|---|---|
| 3.141592654 | 2.7182818288 | 1.618033989 | |||
| approximants | |||||
| 1st | 3.000000000 | 2.000000000 | 1.000000000 | ||
| 2nd | 3.142857143 = 22/7 | 3.000000000 | 2.000000000 | ||
| 3rd | 3.141509434 = 333/106 | 2.666666667 | 1.500000000 = 3/2 | ||
| 4th | 3.141592920 = 355/113 | 2.750000000 | 1.666666667 = 5/3 | ||
| 5th | 3.141592653 | 2.714285714 | 1.600000000 = 8/5 | ||
| 6th | 3.141592654 | 2.718750000 | 1.625000000 = 13/8 | ||
| 7th | 3.141592653 | 2.717948718 | 1.615384615 = 21/13 | ||
| 8th | 3.141592654 | 2.718309859 | 1.619047619 = 34/21 | ||
| 9th | 3.141592654 | 2.718279570 | 1.617647059 = 55/34 | ||
| 10th | 3.141592654 | 2.718283582 | 1.618181818 | ||
| 11th | 3.141592654 | 2.718281718 | 1.617977528 | ||
| 12th | 3.141592654 | 2.718281835 | 1.618055556 | ||
| 13th | 3.141592654 | 2.718281823 | 1.618025751 | ||
| 14th | 3.141592654 | 2.718281829 | 1.618037135 | ||
| 15th | 3.141592654 | 2.718281828 | 1.618032787 | ||
| 16th | 3.141592654 | 2.718281828 | 1.618034448 | ||
With the C.F [3; 7, 15, 1, 292, ...] it is no surprise that π has the excellent rational approximations shown. But with the C.F. [0; 1, 1, 1, 1, 1, 1, ...], φ is the "most irrational" number of all -- observe how slowly its approximants converge. (Observe also that these fractions come directly from the Fibonacci series!)
Does the efficacy of Golden Ratio Scheduling Policy depend on the first key property of φ: that it is the solution of the simplest non-trivial quadratic equation? Or on the second key property of φ: that it is the "most irrational" of numbers?
Answer: Both properties are relevant! The first key property makes the Policy efficacious when the number of buses is small. The second key property makes the Policy efficacious when the number of buses is large.
If you use 0.6000 (36 minutes) instead of 0.6180 (37.1 minutes) you'd have an approximation to the quadratic root and would get good behavior for up to five buses. With six or more buses, however, all buses would use one of the first five schedules.
On the other hand, the ratio (5 - √5)/10 = 0.2764 (13.8 minutes) would get off to a poor start: schedules with 2, 4, 5, or 6 buses would seem quite poor. But this ratio is not too close to any small rational numbers (its C.F. form is [3, 1, 1, 1, 1, 1, 1, 1,...]) and, like φ, works well when the number of buses is large.
(I wanted to prepare some charts depicting these results ... but there's so little time. :-) )
Anyway, I thought it rather neat that the efficacy of the Golden Ratio Scheduling Policy depends on BOTH the special properties of φ.