Compute Fibonacci numbers efficiently using finite fields
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
copying
fibfloat.h
fibint.h
main.cpp
makefile
readme.md

readme.md

fibint

Compute Fibonacci numbers efficiently using finite fields. This allows for Fibonacci numbers to be computed from a closed-form expression, by using only integer arithmetic. For any integer width, this makes it possible to compute all Fibonacci numbers representable by that integer, without resorting to floating-point numbers or wider integers.

How it works

Instead of using the closed-form expression for computing the n-th Fibonacci number in the field of real numbers, it uses an analogous closed-form expression in a finite field that is big enough to contain the largest representable Fibonacci number.

See my blog post for a more thorough explanation.

Licence

This project is an implementation of a mathematical concept. The implementation is licensed under the MIT license. See the file copying.