DEV Community

Cover image for Yet Another Fibonacci
Montegasppα Cacilhας
Montegasppα Cacilhας

Posted on • Edited on

1

Yet Another Fibonacci

From Kodumaro.

One of the most interesting algorithms is the Fibonacci numbers. It’s pretty tricky ’cause it might leads to a binary tree recursion if coded carelessly.

There’s a lot of ways to go around that issue, and I’d like to approach two of them using Cython.

Accumulators and tail-call optimisation

Prolog is a declarative logic programming language, consisting of describing the factual domain and then querying it.

The simpliest (and wrong) way to code Fibonacci in Prolog is:

% vim: filetype=prolog
:- module(fib, [fib/2]).

fib(N, R) :- % step
  N > 0,
  N1 is N - 1,
  N2 is N - 2,
  fib(N1, R1),
  fib(N2, R2),
  R is R1 + R2.

fib(0, 1). % stop
Enter fullscreen mode Exit fullscreen mode

This describes Fibonacci number precisely, but don’t do it. It dives into a binary tree, doubling the stack every step.

The way to fix it is by using two accumulators, A and B:

% vim: filetype=prolog
:- module(fib, [fib/2]).

fib(N, R) :- N >= 0, fib(N, 0, 1, R).

fib(N, A, B, R) :- % step
  N > 0,
  N1 is N - 1,
  AB is A + B,
  fib(N1, B, AB, R).

fib(0, A, R, R). % stop
Enter fullscreen mode Exit fullscreen mode

Now it accumulates the values linearly until the stop condition, when the last B is bound to R.

Try it:

?- [fib].
true.

?- findall(X, (between(0, 5, I), fib(I, X)), R).
R = [1, 1, 2, 3, 5, 8].

?-
Enter fullscreen mode Exit fullscreen mode

Prolog was used as basis for another programming language called Datalog, focused on database query.

The whole thing becomes simplier when Datalog comes into play. Let’s see the same domain coded in Datalog:

fib(0, A, B, R) :- B = R.
fib(N, A, B, R) :- N > 0, fib(N-1, B, A+B, R).
fib(N, R) :- N >= 0, fib(N, 0, 1, R).
Enter fullscreen mode Exit fullscreen mode

And then:

> between(0, 5, I), fib(I, X)?
fib(0, 1).
fib(1, 1).
fib(2, 2).
fib(3, 3).
fib(4, 5).
fib(5, 8).
>
Enter fullscreen mode Exit fullscreen mode

Enter pyDatalog

Python has a Datalog bind egg called pyDatalog, installed by just a single pip:

python3.8 -mpip install pyDatalog
Enter fullscreen mode Exit fullscreen mode

You can use a virtual environment, or install directly into your system as root – your choice.

We’re gonna need Cython too:

python3.8 -mpip install cython
Enter fullscreen mode Exit fullscreen mode

In order to do some Datalog inside Python/Cython code, we need to declare the Datalog terms we’re using.

The code below is the very same Datalog one, using a cpdef to expose the fib/2:

#cython: language_level=3
from libc.stdint cimport uint64_t
from pyDatalog.pyParser import Term

cdef:
    object _fib = Term()
    object A = Term()
    object B = Term()
    object R = Term()
    object N = Term()
    object X = Term()

_fib(0, A, B, R) <= (R == B)
_fib(N, A, B, R) <= (N > 0) & _fib(N-1, B, A+B, R)

cpdef uint64_t fib(size_t n) except -1:
    _fib(n, 0, 1, X)
    return X.v()
Enter fullscreen mode Exit fullscreen mode

Now we need to compile it. Save it as fib.pyx and run:

cythonize fib.pyx
clang `python3.8-config --cflags` -fPIC -c fib.c
clang -o fib.so `python3.8-config --libs` -shared fib.o
Enter fullscreen mode Exit fullscreen mode

(Or use gcc.)

It’s time to see it working. Open the bpython:

>>> from fib import fib
>>> [fib(i) for i in range(5)]
[1, 1, 2, 3, 5, 8]
>>>
Enter fullscreen mode Exit fullscreen mode

Using matrices

The Fibonacci numbers can also be represented as a matrix power:

│1 1│ⁿ
│1 0│
Enter fullscreen mode Exit fullscreen mode

That’s a very elegant approach. We can do it by using NumPy. First let’s install the egg:

python3.8 -mpip install numpy
Enter fullscreen mode Exit fullscreen mode

Now let’s recode Fibonacci using matrices:

#cython: language_level=3
from libc.stdint cimport uint64_t
from numpy cimport ndarray
from numpy import matrix, uint64

cdef:
    ndarray m = matrix('1, 1; 1, 0', dtype=uint64)

cpdef uint64_t fib(size_t n) except -1:
    return (m ** n)[0, 0]
Enter fullscreen mode Exit fullscreen mode

NumPy represents the Fibonacci matrix as '1, 1; 1, 0'. You can compile the code exactly the same way you did before, with the same results.

Agent.ai Challenge image

Congrats to the Agent.ai Challenge Winners 🏆

The wait is over! We are excited to announce the winners of the Agent.ai Challenge.

From meal planners to fundraising automators to comprehensive stock analysts, our team of judges hung out with a lot of agents and had a lot to deliberate over. There were so many creative and innovative submissions, it is always so difficult to select our winners.

Read more →

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay