The problem

Let’s begin by introducing the problem at hand.

Overview

We want a REST API that processes Fibonacci-related queries. It must provide two services, via two different routes:

  • One route must allow, for a given n, to obtain fib(n);
  • One route must allow, for a given n, to obtain k such that fib(k) is the Fibonacci number closest to n.

The exercise also requires to cache all results, so as to speed up not only future requests for the same number, but also computations of higher numbers. This is called memoization, and I will talk about it more further below.

  • A dev log in English is also required, which hey, you’re reading it right now! :D
  • Models and services must be clear; that’s called the single-responsibility principle;
  • A little HTML / JS form must be provided to help check the API;
  • A Git repo must be provided;
  • And finally, a README must be provided that documents the API and the form.

About that last one, I will probably use a web page on this site instead, since it would be coherent with the route I’m taking for the dev log, and it would let you, dear reader, be able to use the tools as well :) Though, the Git repo will certainly also contain a README, and may embed the documentation directly, especially given that rustdoc is a thing. I’ll see.

And finally, a little bonus: providing a Docker image to set up the API more cleanly. I don’t know much about Docker, and absolutely nothing about actually using it, but I’ll definitely give this a shot!

Memoization

Not using memoization for computing Fibonacci sequences is fine for simplistic implementations, and if not planning to compute more than fib(around 20). Consider that, starting with just fib(0) = 0 and fib(1) = 1, computing fib(3) naively would go like this:

fib(4) = fib(2)          + fib(3)
       = fib(2)          + fib(1) + fib(2)
       = fib(0) + fib(1) + fib(1) + fib(0) + fib(1)

But, as you can see, this computes fib(2) twice! Not good.

Side note: treating the computations as a binary DAG, we can see that such a naive computation would essentially amount to a DFS through it while forgetting about already-visited nodes, so we can guess that the complexity would be exponential. Again, not good.

Also, yes, I am aware that Binet’s formula allows computing fib(n) directly, but it’s obviously not the point of the exercise.

Back to memoization: if you didn’t click the Wikipedia link, the short version is that memoization amounts to keeping track of already-computed values. Noting intermediate values on a whiteboard, piece of paper, what have you, while manually calculating fib(n), has been you doing memoization all along!!

Going back to the DAG, it would make the search remember which nodes it already passed through, making it significantly faster.

The downside to memoization is that you have to keep track of all these intermediate values somehow, so you trade processing time for memory usage. Note also that it only applies to pure functions, i.e. functions that do not have any side effects, as it assumes the cached value depends solely on the parameter (assumption: does not rely on anything external), and skips function calls (assuption: the function call has no idea effects).

Choice of technology

The task let me be free in my choice of technology. As you certainly saw from the post index, I chose Rust. So then, let’s discuss this choice for a bit.

The good

Rust is a language that encourages proper memory management, which should allow me to spend less time debugging some stupid mistakes, and focus more on actual development.

It is also an object-oriented language with a rich standard library, and plenty of community-made libs as well. This, plus correct encapsulation, should make writing reusable code and respecting single-responsibility easier.

It is also a modern language, including a lot of facilities: unit tests, versioning, documentation, and more that I’m forgetting.

The bad

Rust is not the language I’m most comfortable with; I have been using C for far longer, for example. This means I will certainly stumble on some fairly beginner-ish problems. However, I have been able to learn Rust blazingly fast, in large part, I believe, to its similarities with C++.

I do know the Rust community is very helpful, so I should be able to get help fairly easily, including for choosing libraries. For this exercise, I am essentially alone, but in a production environment, I would either be with other more experienced Rustaceans, or probably wouldn’t have picked Rust for this.

Further, this is a small project, so I shouldn’t encounter that many implementation hurdles. And lastly, in this specific case, this is not something that will go into production, so I am allowed to make mistakes; and I would rather use this opportunity to also hone some of my skills!

Conclusion

Finally, I just like this language, and am able to write code really easily in it. Plain and simple, I’m good and efficient at it.

↑