Go Fibonacci

Golang Fibonacci is a single endpoint service that listens for GET requests on /fib?n=<n> and calculates n-th Fibonacci sequence number of the given number.

Dependencies

This project was designed against Go 1.16. The service uses Kubernetes and Docker to startup.

• Docker
• Kubernetes
  • Minikube

Decisions taken on this implementation

The service as it is, solves up to element 93 of the Fibonacci sequence with an iterative approach, which has been chosen for its efficiency compared to the alternatives. The application is limited by the length of the int64 type, so the maximum value that can be stored in that data type is 18,446,744,073,709,551,615.

However, I have implemented a solution using the math/big library to demonstrate that even if the computational cost skyrockets, the Fibonacci sequence can still be calculated and stored on data types beyond 64 bits using Golang.

Both benchmarking and testing can be proved by running the functions contained in fibonacci_test.go

make bench
make test

To explore what else you can do with the Makefile:

make

Instructions to run the project

By running the following command, the project will be (docker) built, deployed on minikube and started.

make k8-minikube-start

The next step is to open a minikube tunnel, to access the service through localhost. I have opted for this option to avoid having to make too many changes to fib.yaml in case of sending the service to production.

minikube tunnel

After successful execution, the service should be running on port 8080. Hit the health endpoint to check that all is running as expected:

• :8080

You should receive a {"status": "ok"} as the response.

The next step is to hit the fib endpoint and start querying the API

curl http://localhost:8080/fib?n=1
> 1

curl http://localhost:8080/fib?n=72
> 498454011879264

Packaging

.
├── cmd                     # Entrypoint, Main API
└── internal
    ├── handlers            # HTTP layer
    ├── models              # Business logic
    └── web                 # Framework for common HTTP related tasks

Author

Noel Ruault - @noelruault

Feedback

Has implementations of multiple basic Fibonacci algorithms but don’t have matrix exponentiation or phi approximations. Has some wrong claims in the comments - recursive algorithm is not O(n) complex, it’s O(2^n). Besides that, the code structure is actually really nice and reminds me how one would do a longer-term web service project, not a two-hour exercise. Most importantly it shows familiarity and experience with Go. Kubernetes part is basic, doesn’t do health checks even though the service has health check endpoint.

Further development

High-performance Fibonacci numbers generator in Go

Matrix

The Go Playground

The optimal algorithm of Fibonacci sequence (golang code) - Programmer Sought

Go Fibonacci sequence generator

Fibonacci matrix-exponentiation

Phi

The Golden Section - the Number

Complexity

Determining complexity for recursive functions (Big O notation)