Blazing fast Fibonacci with Kotlin and Arrow library

TLDR;

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 .

Fibonacci Sequence

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

Double recursive implementation

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.

Closed-Form

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.

Matrix form

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.

Exponentiation by Squaring

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(xx, n/2)
else xpow(xx, (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)).

Enters Arrow

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.

Semi-group

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

Semigroup typeclass in Kotlin

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.

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章