# 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:

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 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)