Skip to content

Instantly share code, notes, and snippets.

@m-ender

m-ender/fibonacci.md

Last active October 21, 2015 14:54
Show Gist options
  • Save m-ender/b77bbf2c02e48b50becd to your computer and use it in GitHub Desktop.
Save m-ender/b77bbf2c02e48b50becd to your computer and use it in GitHub Desktop.
Download ZIP
Draft for Fibonacci spec
Raw
fibonacci.md

Task

With as little code as possible, you are to compute the Fibonacci numbers. You may do this one of two ways:

  1. Generate an infinite sequence of Fibonacci numbers. This may either be in the form of the numbers printed to standard output, or as a stream or generator in languages that support them. If you choose this option, there should be no upper bound on the numbers produced other than your computer's memory. In particular, your code must not terminate (or produce wrong output) early due to things like fixed-size integers (e.g. 64-bit), recursion limits etc.
  2. Given n, calculate the nth Fibonacci number. If you choose this option, your submission may assume that a reasonable limit on the input, but your code must at least support all Fibonacci numbers up to 1,836,311,903 (such that it fits into 31 bits).

You may choose whether the sequence starts from 0 or the first 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

If you've chosen the second option, you may also (independently) choose whether the numbering starts from 0 or 1. That is, all of the following are valid, as long as you are consistent:

F(6) = 5
F(6) = 8
F(6) = 13

Here, the F(6) = 8 option is strongly preferred, but the others are allowed so as not to invalidate any old answers.

You may write a full program or a function (which may be unnamed). In particular, you must not write a snippet or assume a REPL environment.

Input

If you chose the second option, there are several valid input methods:

  • If your language is able to read from standard input, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if your code does not support more than 256 Fibonacci numbers).

  • If you are writing a function, you may also take input as a function parameter in the form of an integer or a string (using any of the representations above).

  • If (and only if) your language is unable to accept any kind of user input, you may hardcode the input in your program.

    In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.

    For scoring purposes, submit the program that corresponds to the input 1.

Output

Valid output methods include:

  • Standard output or closest alternative.
  • Functions may also output via their return value or an out parameter (either as a string or an integer).
  • If possible, output should consist solely of the Fibonacci number(s) using any of the integer representations mentioned in the input section. If you chose the first option and decide to print to the standard output, individual numbers must be unambiguously separated.
  • The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

Additional rules

  • This is not about finding the language with the shortest approach for computing Fibonacci numbers, this is about finding the shortest approach in every language.

  • Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

    The language Piet, for example, will be scored in codels, which is the natural choice for this language.

    Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

  • Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program prints a stream of Fibonacci numbers, then congrats for paving the way for a very boring answer.

    Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

  • If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

  • Built-in functions for computing Fibonacci numbers are allowed. This challenge is meant to catalogue the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.

  • Unless they have been overruled earlier, all standard [tag:code-golf] rules apply, including the http://meta.codegolf.stackexchange.com/q/1061.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalogue as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment