Theoretical and pragmatic approaches
04/11/2025

The decimal to octaphi converter presented in the previous post is unlikely to be of any use in everyday life. But it is a perfect example to see how theoretical and pragmatic approaches complete each other.

The algorithm of the decimal to octaphi converter dramatically relies on the computation of values of the Fibonacci sequence defined as:

The Fibonacci sequence is defined by: $F\left(0\right)=0,F\left(1\right)=1,F\left(n\right)=F(n-1)+F(n-2)\text{for}n>1$

This beautifully translates in C—the best language, ever— by the totally ineffective following code (fibr with an r for recursive):

Ineffective as it is damn slow; it starts stalling after F₃₈ on a Raspberry Pi (Model 5, with 4Gb of RAM) where it takes more than 0.5s, the common threshold for an acceptable IHM.

Fortunately there is another solution for its implementation. A mere iterative loop:

Indeed, on the same platform, computing F₃₈= 39088169 takes 0.4s with fibr() and only 185ns (yes, only 0.000000185s) with fibi().

First lesson learned: beautiful code are not always the most efficient.

The following graph compare the time spent by fibr() and fibi(). Guess what is the colour of each functions.

Alas, beyond F₉₃= 12200160415121876738, despite using unsigned long long, fibi() overflows and is unable to return the correct value. And 93 is a too low figure for the requirements of the octaphi converter.

However, fibi(94) overflows in only 667ns.

Second lesson confirmed—not a surprise—: basic C types might be inappropriate for some contexts.

Fortunately, it is possible to achieve exact computations on arbitrarily large integer. The best way to do it in C is certainly to rely on the excellent GMP library. But here we will use a custom code, slower but that allows us to see which inner function is the most time-consuming.

Run on the same platform, comparing the delay of computation for the Fibonacci values shows that the cost is high for handling arbitrarily large integers. Besides, the iterative process has an expected steady rise.

That's where a theoretical knowledge helps a lot.

Indeed there is another way to compute Fibonacci values, known as the quadratic form. It roughly involves computing consecutive pairs and jump from n to 2n with formula depending on the evenness or oddness of n.

In any case, we have to compute a and b with: $a=F_0(2F_1-F_0)$ and $b=F_0^2+F_1^2$

Then if n is odd: F 0 ← b , F 1 ← a + b else: F 0 ← a , F 1 ← b

With this computation method, we swap a mere addition for at least an additional subtraction and three multiplications. Add the added cost of handling arbitrarily large numbers and you easily understand the huge difference of processing times.

Anyway, as computations with basic C types end at F₉₃, the use of handling arbitrarily large numbers is not a choice.

As for the comparison between the simple iterative computation and the use of quadratic formulas, it quickly pays off: starting from F₅₀ in our context of pragmatic tests.

In the graph below, the dbi curve is the iterative process adapted to deal with large integers. The dbq curve uses the quadratic algorithm to compute F_n.

Yet, for relatively small figures, as the computation time for F₉₃ is as low as 6.5μs with the simple iterative method, a pragmatic approach can comfortably decide to keep it that simple.

Previous | Next