Stratus3D

Software Engineering, Web Development and 3D Design

Fibonacci Algorithms in Elixir

A look at algorithm time complexity

I recently was asked to write a function in Elixir to generate a list Fibonacci numbers. I had forgotten the typical implementation of the algorithm for generating Fibonacci numbers but since my function was returning a list I knew I could just add the two previous numbers in the list to compute the next number. I quickly threw together an simple 8 line function and that took a number and returned a list with that many of first Fibonacci numbers in it. After writing it and testing it out I realized my function was somewhat different from the implementations I had seen. My code looked like this:

1
2
3
4
5
6
7
8
9
10
11
12
defmodule Fibonacci do
  def fibonacci(number) do
   Enum.reverse(fibonacci_do(number))
  end

  def fibonacci_do(1), do: [0]
  def fibonacci_do(2), do: [1|fibonacci_do(1)]
  def fibonacci_do(number) when number > 2 do
    [x, y|_] = all = fibonacci_do(number-1)
    [x + y|all]
  end
end

With my implementation we have a function called fibonacci_do/1 with three clauses, the first two are for the first and second Fibonacci numbers and the third generates all the rest of the numbers in the sequence by adding the previous two numbers in the list and returning a list with the new number added. The function actually generates a list with the numbers in reverse order, so I defined the fibonacci/1 function to reverse the list. This function can generate the first 100,000 Fibonacci numbers in less that a second. Not too bad I thought.

Common Fibonacci in Elixir

After doing this I went and looked at the other Elixir implementations. Here are two of them:

Rosetta Code algorithm:
1
2
3
4
5
6
7
8
9
10
11
12
13
defmodule Fibonacci do
    def fib(0), do: 0
    def fib(1), do: 1
    def fib(n), do: fib(0, 1, n-2)

    def fib(_, prv, -1), do: prv
    def fib(prvprv, prv, n) do
        next = prv + prvprv
        fib(prv, next, n-1)
    end
end

IO.inspect Enum.map(0..10, fn i-> Fibonacci.fib(i) end)
From a gist by Dave Thomas, most of the Elixir implementations followed this pattern:
1
2
3
def fib(0), do: 0
def fib(1), do: 1
def fib(n), do: fib(n-1) + fib(n-2)

Now this variation is by far the most common. I’ve seen this implementation in several slide decks at Elixir conferences, and I’ve seen it used as example code many times, so I’m unsure of its origin. Dave Thomas presented this implementation at the first ElixirConf because it mirrored the mathematical formula for generating Fibonacci numbers. In this blog post I’ll call this the Dave Thomas implementation. If you were to naively use this function to generate a list of Fibonacci numbers you’d most likely do something just like the Enum.map/2 call in the Rosetta Code example above:

1
IO.inspect Enum.map(0..10, fn i-> fib(i) end)

Which function generates a list of Fibonacci numbers the fastest?

Looking at these three algorithms it’s clear they are have some similarities. All of them are recursive functions that start with the base cases for first Fibonacci numbers, 0 and 1. All of them take a single argument, the number in the Fibonacci sequence to generate.

But these algorithms have some key differences as well.

My function calls itself recursively and builds up a list of numbers in the sequence and returns the list directly.

The Rosetta Code function also recursively calls itself once until it has generated a number. Since it only generates a single number it must be executed multiple times to generate a list of numbers in the sequence.

The Dave Thomas algorithm differs from the two others in that it recursively calls itself not once but twice. Just like the Rosetta Code algorithm it also must be executed multiple times to generate a list of numbers in the sequence. At only 4 lines it’s by far the most succinct of the three.

Benchmarking

I opted to do simple benchmarking of these three algorithms. The benchmark script feeds the function a number N and expects the function to return a list containing the first N numbers of the first Fibonacci sequence. Only my algorithm returned a list directly, so for the other two algorithms I created a function that would map over the range and repeatedly call the fibonacci function:

1
2
3
def fibonacci(number) do
  Enum.map(0..number, fn(n) -> fib(n) end)
end

Results

I ran the benchmark against each algorithm four times. The average run times are shown in the table below in microseconds.

List Size Rosetta Code Dave Thomas Mine
3 4 543 1
5 2 3 0
10 8 11 0
20 5 880 4
30 8 97500 1
45 17 131900822 2

I’m not sure why the Dave Thomas algorithm was so slow at computing a list of the first 3 Fibonacci numbers. My guess is that CPU core was busy with something else when that number was benchmarked and it skewed the results.

As you can see these three algorithms perform very differently as the length of the list they must generate grows. Up to around 10 items the Rosetta Code algorithm and Dave Thomas algorithm perform about the same. After 10 items the run time for the Dave Thomas algorithm quickly climbs, for a list of 30 it takes nearly 1/10 a second, and for a list of 45 it takes over two minutes. The Rosetta Code algorithm performs much better. Only taking around 17 microseconds to compute a list of the first 45 Fibonacci numbers. My algorithm appears to have similar performance characteristics to the Rosetta Code algorithm, but with times that averaged less than a quarter the run time of the of the Rosetta Code algorithm. Note that the timing code was rounding to the nearest microsecond, so some computations took less than half a microsecond for my algorithm.

I decided to do a little more benchmarking of my algorithm and the Rosetta code algorithm. Since both algorithms seemed pretty fast I tried using them to generate much larger lists of Fibonacci numbers. The results are shown in the table below. Again, time is in microseconds.

List Size Rosetta Code Mine
100 76 5
500 2892 36
1000 15058 78
5000 631680 870
10000 4152261 4767
100000 > 5 minutes (never returned) 1195938

Clearly my algorithm performs better as it doesn’t have to generate each number from scratch each time it computes a new number in the resulting list. As the list it must generate grows in size the Rosetta Code algorithm’s run time grows exponentially. For generating a list of Fibonacci numbers it’s clear my algorithm performs the best.

Conclusion

Clearly these three algorithms have very different performance characteristics. For generating a single Fibonacci number the Rosetta Code function will work fine. My function will also work fine for generating a single Fibonacci number, but will use more memory due to the list that it builds. The Dave Thomas algorithm performs poorly for anything beyond the first 30 Fibonacci numbers and probably shouldn’t be used for anything other than exercises like this.

My algorithm, which was designed to generate a list of Fibonacci numbers, turns out to be the best algorithm for generating a list of Fibonacci numbers. Looping over the Fibonacci functions for the other algorithms greatly degrades their performance. It’s better to design a new Fibonacci function that generates the full list in one recursive call rather than reusing an existing Fibonacci function that only generates one number at a time to build the list.

Resources

Maintaining an Open Source Project

This was a talk I gave at the Sarasota Software Engineers User Group in Sarasota on July 26, 2018

Maintaining open source software is often time consuming and difficult. Open source maintainers have to deal with reports of hard to reproduce bugs, incomplete and buggy pull requests, requests for support, and bug reports mistakenly opened by confused users. Despite the challenges maintainers face they can still greatly benefit from the support of their software’s users and contributors. Through proper organization and automation maintainers can better manage their project and have more time to focus on the long term goals of the software. In this talk I will talk about my experience working as a maintainer of asdf, an open source version management tool. I’ll talk about how I got started as a contributor and what I learned throughout my work. I’ll share the techniques I have learned that make open source maintenance easier. You will learn how to apply these techniques to your own open source (and closed source) projects to improve efficiency and speed of development. Geared for those have some experience with software development and want to begin contributing to open source projects or get better at maintaining existing software.

My Experience as a Maintainer of asdf

In the talk I gave I talked a lot about my experience with asdf and how I got started in open source. I explained how asdf works, talked about my work as a maintainer, and presented some of the tools that have helped us build asdf. All of these things can be found in other places, I previously written about how asdf works and the tools we use for asdf can all be seen at work in the build for the project. In this post I’m only going to list the advice I gave at the end of the talk. First is advice for users and contributors.

Advice for users and contributors

  • Fastest way to get something done is to do it yourself
  • Be extremely detailed when reporting bugs and proposing features
  • PRs and issue tracker are your friend
    • Look and see if the issue or patch you want to contribute already exists
    • Look at past PRs and comments to determine if your changes would be welcome
  • Don’t get discouraged by lack of attention
  • Don’t assume maintainers know more than you
  • Have a backup plan

Advice for maintainers

Automate automate automate!

  • Automate all repetitive tasks that can be automated
  • Linting, tests, builds, releases/tags, deployments
  • Try to codify all requirements in something that’s automated

Be nice, But also be strict

  • Be thankful for all contributions
  • Be open to different solutions
  • But don’t merge PRs that:
    • Are confusing
    • For bugs that are not understood or documented
    • Violate project standards
    • Negatively affect the existing code in the codebase
  • Don’t give someone commit access until they’ve proven themselves with their contributions

Encourage contribution

  • Make it easy to contribute
  • Have well defined standards for contributions that users can read
  • Point people in the right direction
  • Offer contributors help when it makes sense

Be organized

  • Repositories, files, and directories should have descriptive names
  • All code should have corresponding unit tests
  • Everything should be under version control (GitHub makes this easy)
  • Software should versioned
    • Tagging should be automated
    • Users should be encouraged to use the latest stable version when installing
    • Users should have an easy way to view version and other environmental information to make bug reporting easier

Have good docs

  • Everything should be documented
    • Usage, APIs, bug reporting, contribution guidelines, standards, review and release processes, and on and on…
  • Have official documentation that goes through a review process
  • Have a wiki so users can easily share unofficial documentation on specific use cases of the software

Resources

Stop Excluding Editor Temp Files in .gitignore

Many of the open source projects that I rely on have large .gitignore files with rules for ignoring temp files that their contributor’s editors generate. Sometimes these rules are added to the .gitignore intentionally by well meaning developers, other times they are copied in from other repository’s .gitignore files, sometimes build tools generate .gitignore files that contain these rules when generating new projects. It’s easy to see how repositories come to have editor-specific ignore rules in their .gitignore files. From ordinary libraries to massive open source projects like Electron ignore editor-specific files you will find editor-specific rules in the .gitignore file.

In this blog post I’ll explain why it’s unwise to try to ignore editor temp files with rules in a repository’s .gitignore file.

What’s wrong with excluding editor temp files in a project’s .gitignore?

Defining rules that properly exclude temporary files generated by text editors and IDEs can be very difficult if not impossible to do properly, and excluding temporary files for all editors is impossible. It may seem a little extreme to consider all editors when creating a .gitignore, but if your repository is open source or has many committers it’s possible that many different text editors or IDEs will be used. It’s hard to know ahead of time what tools the committers will choose to use. It’s much safer to have individual committers exclude the temp files generated by their own tools in their own global gitignore files.

The global gitignore

Creating a global gitignore is easy and the rules in the global gitignore will be applied to every repository you work on. To setup a global gitignore create file somewhere on your file system with rules to exclude the temporary files generated by your editor (I use ~/.gitignore_global. See my dotfiles for more details). Then run:

1
git config --global core.excludesfile <path to the file you created>

That’s all you need to do. Every rule you defined in the global excludes file will be ignored in every repository to you work on. The git config command will add a line to your .gitconfig file in your home directory that will look like this:

1
2
[core]
excludesfile = ~/.gitignore_global

You can edit your .gitconfig manually if you prefer.

But why not ignore editor temp files in each .gitignore to be safe?

Properly ignoring all temp files for an editor isn’t always as simple as it might seem. Take for example Vim, often you will find .gitignores with a single line like this intended to ignore all Vim swap files:

1
*.swp

This rule is similar to the rule you would get in a StackOverflow answer if you asked about this on there. But this ignore rule is wrong. Vim’s swap files may have the .swp extension, but they may also have many other extensions as well. StackOverflow answerers aren’t the only ones who get this wrong, gitignore.io also gets it wrong. It takes multiple rules to exclude all Vim swap files:

1
2
3
4
[._]*.s[a-v][a-z]
[._]*.sw[a-p]
[._]s[a-v][a-z]
[._]sw[a-p]

In other words, Vim swap files don’t just have the extenions .swp or .sw*, they could be *.saa or *.sab if the other extensions have been taken. Here is the source code that generates these extensions if you are curious. And because these rules for excluding Vim swap files are so broad, they will exclude files that might not be swap files at all. For example, a file ending in .swf may be a Shockwave Flash file, but it will be ignored by these Vim swap file rules.

Worse still, some editors allow you to customize the names of the temp files they generate. This makes it impossible to define rules in a repository’s .gitignore that properly exclude editor temp files, even if you are only targeting a small set of editors and IDEs. It’s far better for developers to define their own rules to exclude their own editors temp files.

What’s wrong with trying to ignore what we can?

The problem is ignoring what you know about will result in most things being ignored most of the time. Most temp files will be caught by the rules and ignored. But from time to time a temp file might slip through and get staged or committed. If no editor temp files are ignored by the repository’s .gitignore it will be more clear to the developer that their Git configuration isn’t excluding files it should. This will prompt them to add more ignore rules; hopefully in their global ignore file.

But then contributors will check in their temp files!

Most will notice their mistake. And the few that don’t can be asked to remove the temp files from their PR. We get several PRs a week for asdf, many from new contributors, and I have never once seen a contributor accidentally check in a temp file. The asdf .gitignore file does not ignore any editor specific files and we have never had any trouble with this.

Conclusion

My approach to ignore rules is very simple.

I put any ignore rules that are specific to the tools I choose to use in my global ignore file. Any ignore rules that are specific to the language or tools required by a project I put in the project’s .gitignore file.

References