In this article, I show you how to compute Fibonacci numbers at blazing speed by leveraging both the Arrow functional library for Kotlin and the ‘exponentiation by squaring algorithm’.

This approach is heavily inspired by this Haskell For All article . You can find the code here .

If you are a programer, chances are you have come across the Fibonacci sequence more than once but here is a quick reminder anyway.

The sequence is defined as follows:

F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), n > 1

The simplest way to implement this sequence is with a doubly recursive function. For example, in Kotlin:

This is a simple approach but extremely inefficient; the time complexity is `O(2^n)`

.

This can be improved to `O(n)`

by memoizing the two previous values. Let’s see if we can do better.

It turns out there is a mathematical formula that can compute any Fibonacci number in `O(1)`

time and memory complexity:

(You can see here why there is a link between Fibonacci numbers and the golden ratio : if you divide *f(n+1)/f(n)* it converges to .)

Even though this is really fast in theory, it does not work in practice because of the floating precision arithmetic.

Don’t be put off by the fancy looking maths, it will get much simpler when we get to the code.

You can also express recursive sequences like Fibonacci using matrices.

For example for:

f(n) = a.f(n-1) + b.f(n-2)

You can write:

The conditions:

f(0) = ⍺ f(1) = β

become:

So eventually you get:

or:

*Note that this works for any linear recursive sequence where f(n) depends on f(n-1), f(n-2),…,f(n-m). Then you get a* mxm *matrice.*

So our Fibonacci expression becomes:

Don’t worry if you don’t fully understand these matrix operations, it’s actually quite straightforward to turn into code.

The beautiful part of the formula above is that all the work is done by the matrix multiplication. If you have a binary operation of the form *x⊗ y* and you want to compute *x⊗ x⊗…⊗ x, n* times, you can use Exponentiation by Squaring :

Intuitively, you can define the operation `pow(x,n)`

recursively:

`pow(x,n) = `

if(n == 0) empty()

else if(n even) pow(x*⊗*x, n/2)

else x*⊗*pow(x*⊗*x, (n-1)/2)

We also need a neutral element here called `empty()`

. For natural numbers this is just `1`

.

This algorithm keeps dividing `n`

by *2* so the time complexity is `O(log₂(n)).`

Exponentiation by squaring doesn’t just work for integer multiplication, it works for any type that has a binary operation and neutral value for that operation (1 in the case of natural numbers). So in the Java world we could have an interface like this:

In the functional world, there is something called Type Classes . There is a set of standard type classes and they are shipped with Arrow , a functional library for Kotlin.

The type class that defines a binary operation for a type is called Semigroup . In Kotlin, it would look like this:

The interesting bit about the Kotlin implementation, is that it uses the extension functions in Kotlin . In the Java world if we had a `Foo`

class, it would be extending a `Semigroup`

interface like this:

In Kotlin, we wouldn’t make `Foo`

extend an interface, we would create a new singleton class called `FooSemigroup,`

which provides an extension function for `Foo`

:

So, if we had two foo instances:

val foo1 = Foo() val foo2 = Foo()val foo3 = foo1.combine(foo2) //this does not compileval foo3 = FooSemigroup().run { foo1.combine(foo2) //this compiles }

You see that we have to run the code within the context of `FooSemigroup`

for the `Foo`

class to have the `combine`

method.

## 我来评几句

登录后评论已发表评论数()