Exploring Ruby Algorithms for Fibonacci Numbers - RoRvsWild
RoRvsWild
This article is a deep dive into the world of Fibonacci numbers to show some really neat tools that Ruby provides. Some may not be used very often, but it is always good to have them in your toolbox.
Understanding the Fibonacci Sequence
In case you are not familiar, the Fibonacci sequence is a classic mathematical progression where each number is the sum of the previous two. Starting with 0 and 1, the sequence looks like this:
$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …$$
Basic Recursive Fibonacci Algorithm and Its Limitations
The most straightforward method to compute Fibonacci numbers is a simple recursive function:
def fibonacci(n)<br>return 0 if n == 0<br>return 1 if n == 1
fibonacci(n - 1) + fibonacci(n - 2)<br>end
This algorithm is simple and clear. However, if we look at its performance, we can see that it starts out fine, but once we cross the 30th Fibonacci number, the performance starts to degrade exponentially.
This happens because we are doing a lot of redundant calculations. Imagine calculating the 5th Fibonacci number. To calculate it, we need the 4th and the 3rd numbers. To calculate the 4th number, we need the 3rd and the 2nd. This pattern repeats until we hit the 0th or the 1st number. The larger the number, the more computations we need to perform.
Using Binet’s Formula for Constant Time Calculation
It turns out there is a closed-form expression for calculating the nth Fibonacci number. To overcome recursive inefficiency, we turn to Binet’s formula:
$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$
Where:
\$\phi = \frac{1 + \sqrt{5}}{2}\$, (phi) the golden ratio,
\$\psi = \frac{1 - \sqrt{5}}{2}\$, (psi) its conjugate.
This formula allows computation in constant time, a significant performance leap. Implementing it in Ruby involves calculating powers of irrational numbers and rounding the result.
In fact, since \$\psi^n\$ is so small, we can further simplify this formula to:
$$F_n = \Bigl\lfloor\frac{\phi^n}{\sqrt{5}}\Bigr\rceil$$
Closed-form Algorithm
SQRT_FIVE = Math.sqrt(5)<br>PHI = (1 + SQRT_FIVE) / 2
def fibonacci(n)<br>((PHI**n)/SQRT_FIVE).round<br>end
This is a constant-time algorithm according to our performance graphs.
However, this algorithm faces two major challenges:
Precision limits: At the 71st Fibonacci number, this algorithm will return a value of \$608061521170130\$, whereas the actual 71st Fibonacci number is \$608061521170129\$ — just one less.
This happens because Ruby does not have infinite precision, so at some point, rounding issues occur. As the algorithm calculates larger Fibonacci numbers, this discrepancy increases.
Float domain errors: At around the 1475th Fibonacci number, this algorithm will raise a FloatDomainError.
This occurs in Ruby when a calculation exceeds the limits of floating-point precision and returns Infinity. For example, raising \$\sqrt{5}\$ to the 883rd power yields Infinity, and calling methods like round on Infinity will trigger a FloatDomainError.
Math.sqrt(5) ** 883<br>=> Infinity
Can we do better?
Closed-form Algorithm #2
Ruby’s BigDecimal library offers arbitrary-precision decimal arithmetic, allowing us to mitigate rounding errors by specifying how many decimal places to calculate.
By replacing standard floating-point operations with BigDecimal, we can compute Fibonacci numbers with much greater accuracy and avoid early overflow issues.
SQRT_FIVE = BigDecimal("5").sqrt(1000)<br>PHI = (1 + SQRT_FIVE) / 2
def fibonacci(n)<br>((PHI**n)/SQRT_FIVE).round<br>end
This is already much better! We can compute the correct Fibonacci numbers well past the 75th. The trade-off is performance: the more precision requested, the slower the calculations become.
BigDecimal is a great library to leverage in Ruby. It is a little slower than the standard numeric options, but it avoids many of the precision pitfalls.
This gets us past the 100th Fibonacci number. What do we need to do to get to the 1000th?
Closed-form Algorithm #3
Ruby’s built-in support for rational numbers provides a promising alternative. Instead of decimals, rationals represent numbers as fractions of integers, avoiding floating-point precision problems.
\$\sqrt{5}\$ is an irrational number – it has a decimal expansion that doesn’t terminate nor repeat. However, we can approximate it:
$$\sqrt{5} = 2 + \frac{1}{4 + \frac{1}{4 + \frac{1}{4 + \frac{1}{4 + \ddots}}}}$$
Using continued fractions, we can approximate irrational numbers like \$\sqrt{5}\$ to arbitrary precision by expanding the fraction deeper and deeper.
$$\sqrt{5} = 2.23606797749978969640\dots$$
If we take this approximation a few levels deep, we get \$\frac{38}{17}\$, which is about \$2.235294117647059\$.
Going one level deeper gives us \$\frac{161}{72}\$, or approximately \$2.2361111111111\$. Each level brings a better approximation. We can see that in the error column of the following table. As we approximate \$\sqrt{5}\$ to a deeper level, the error...