137
\$\begingroup\$

The Fibonacci sequence is a sequence of numbers, where every number in the sequence is the sum of the two numbers preceding it. The first two numbers in the sequence are both 1. Here are the first few terms:

1 1 2 3 5 8 13 21 34 55 89 ...

Write the shortest code that either:

  • Generates the Fibonacci sequence without end.

  • Given n calculates the nth term of the sequence. (Either 1 or zero indexed)

You may use standard forms of input and output.

(I gave both options in case one is easier to do in your chosen language than the other.)


For the function that takes an n, a reasonably large return value (the largest Fibonacci number that fits your computer's normal word size, at a minimum) has to be supported.


Leaderboard

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body {
  text-align: left !important;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I am sort of waiting for a response like "f", 1 byte, in my math based golf language. \$\endgroup\$ Aug 11 '20 at 11:57

284 Answers 284

1
2
3 4 5
10
6
\$\begingroup\$

TypeScript's type system, 193 188 186 bytes

type L='length'
type T<N,U extends 0[]=[]>=U[L]extends N?U:T<N,[...U,0]>
type S<A,B>=T<A>extends[...infer U,...T<B>]?U[L]:0
type F<N>=N extends 0|1?N:[...T<F<S<N,1>>>,...T<F<S<N,2>>>][L]

There's no way to do I/O here, but we can use hovering to view the value (also note that the generated JS is empty):

Fibonacci(10)

Unfortunately, TypeScript has strict recursion limits and on F18 we get a Type instantiation is excessively deep and possibly infinite. error:

Fibonacci(11)

Demo on TypeScript Playground


Ungolfed version:

type NTuple<N extends number, Tup extends unknown[] = []> =
  Tup['length'] extends N ? Tup : NTuple<N, [...Tup, unknown]>;

type Add<A extends number, B extends number> =
  [...NTuple<A>, ...NTuple<B>]['length'];

type Sub<A extends number, B extends number> =
  NTuple<A> extends [...(infer Tup), ...NTuple<B>] ? Tup['length'] : never;

type Fibonacci<N extends number> =
  N extends 0 | 1 ? N : Add<Fibonacci<Sub<N, 1>>, Fibonacci<Sub<N, 2>>>;
\$\endgroup\$
5
\$\begingroup\$

GolfScript, 13 chars

2,~{..p@+.}do

(My answer from a previous Stack Overflow question.)

\$\endgroup\$
5
\$\begingroup\$

JavaScript, 41 39 33 bytes

(c=(a,b)=>alert(a)+c(b,a+b))(0,1)
\$\endgroup\$
2
  • \$\begingroup\$ I don't think the function without the parenthesis is still valid. \$\endgroup\$ Apr 8 '13 at 16:22
  • \$\begingroup\$ I don't believe this is valid because ES6 came after the challenge was created. Even if it was, you could save a byte by making it a function to return fib(n): f=(n,a=0,b=1)=>n?f(n-1,b,a+b):a; \$\endgroup\$
    – Kade
    Dec 16 '16 at 14:33
5
\$\begingroup\$

Perl 5, 36 35 bytes

(1x<>)=~/^(..?)*$(?{++$i})\1/;say$i

Try it online!

This works by using the regex ^(..?)*$ to count how many distinct partitions \$n\$ has as a sum of the numbers \$1\$ and \$2\$.

For example, \$5\$ can be represented in the following \$8\$ ways:

1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
1+2+2
2+1+1+1
2+1+2
2+2+1

This tells us that the \$F_5=8\$.

I had this basic idea on 2014-03-05 but it didn't occur to me until today to try coding it into a program.

To count the number of distinct matches ^(..?)*$ can make in a string \$n\$ characters long, we must force Perl's regex engine to backtrack after every time the regex completes a successful match. Expressions like ^(..?)*$. fail to do what we want, because Perl optimizes away the non-match, not attempting to evaluate the regex even once. But it so happens that it does not optimize away an attempt to match a backreference. So we make it try to match \1. This will always fail, but the regex engine isn't "smart" enough to know this, so it tries each time. (It's actually possible for a backreference to match after $ with the multiline flag disabled, if it captured a zero-length substring. But in this particular regex, that can never happen.)

Embedded code is used to count the number of times the regex engine completes a match. This is the (?{++$i}), which increments the variable $i. We then turn it into a non-match after the code block executes.

For golf reasons, this defines \$F_0=1,\ F_1=1\$. To define \$F_0=0,\ F_1=1\$ we would need an extra byte:

(1x<>)=~/^.(..?)*$(?{++$i})\1/;say$i

Try it online!

Here it is as a (reasonably) well-behaved anonymous function (47 46 bytes):

sub{my$i;(1x pop)=~/^.(..?)*$(?{--$i})\1/;-$i}

Try it online! - Displays \$F_0\$ through \$F_{31}\$

The above actually runs faster than the standard recursive approach (39 bytes):

sub f{my$n=pop;$n<2?$n:f($n-2)+f($n-1)}

Try it online! - Displays \$F_0\$ through \$F_{31}\$

If that is golfed down using Xcali's technique it becomes even slower, at 38 bytes:

sub f{"@_"<2?"@_":f("@_"-2)+f("@_"-1)}

Try it online! - Displays \$F_0\$ through \$F_{31}\$

or with the same indexing as my main answer here, 34 bytes:

sub f{"@_"<2||f("@_"-2)+f("@_"-1)}

Try it online! - Displays terms \$0\$ through \$30\$

See Patience, young "Padovan" for more variations and comparisons.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can convert this to Perl 6 using the ex flag to match all possible combinations. Try it online! \$\endgroup\$
    – Jo King
    Apr 16 '21 at 22:49
  • \$\begingroup\$ @JoKing Awesome, thanks! I was thinking of looking into Raku, but now I definitely will. \$\endgroup\$
    – Deadcode
    Apr 16 '21 at 23:04
  • \$\begingroup\$ @JoKing Have you considered defining a SBCS for Raku? It's a shame not to be able to use as it would save a byte. There are probably plenty of other examples. \$\endgroup\$
    – Deadcode
    Apr 17 '21 at 5:53
5
+50
\$\begingroup\$

jq -n, 30 28 bytes

-2 bytes thanks to Michael Chatiskatzi!

Prints the infinite sequence.

[0,1]|while(1;[last,add])[1]

Try it online!

Start with [0,1].
while(1; ... ) infinite loop, 1 is a truthy value.
[last,add] the new pair is the last value of the old pair and the sum of the old pair.
while returns all intermediate pairs, [1] gets the second element of each pair.


jq, 35 33 bytes

A recursive filter written for this tip.

def f:(.<2//[.-1,.-2|f]|add?)//.;

Try it online!

\$\endgroup\$
1
4
\$\begingroup\$

bc, 36 chars

r=0;l=1;while(i++<99){r+=l;l+=r;r;l}
\$\endgroup\$
4
\$\begingroup\$

C: 48 47 characters

A really really truly ugly thing. It recursively calls main, and spits out warnings in any sane compiler. But since it compiles under both Clang and GCC, without any odd arguments, I call it a success.

b;main(a){printf("%u ",b+=a);if(b>0)main(b-a);}

It prints numbers from the Fibonacci sequence until the integers overflow, and then it continues spitting out ugly negative and positve numbers until it segfaults. Everything happens in well under a second.

Now it actually behaves quite well. It prints numbers from the Fibonacci sequence and stops when the integers overflow, but since it prints them as unsigned you never see the overflow:

VIC-20:~ Fors$ ./fib
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368
75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352
24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170
1836311903 2971215073 VIC-20:~ Fors$
\$\endgroup\$
4
  • \$\begingroup\$ Printing out overflowed numbers and/or segfaulting is probably not part of the spec, but nice try. :-) \$\endgroup\$ Apr 4 '13 at 11:53
  • \$\begingroup\$ Certainly, but it's not the only solution here that segfaults. :) I will edit it so that it behaves more properly, since I got the character count down anyway. \$\endgroup\$
    – Fors
    Apr 4 '13 at 13:09
  • \$\begingroup\$ Yay! Have an upvote. :-) \$\endgroup\$ Apr 4 '13 at 13:56
  • \$\begingroup\$ I'm pretty sure you could shave off 2 bytes by replacing if(b>0) with b>0&& and yes, I realize this post is over 4 years old :) \$\endgroup\$ Aug 24 '17 at 16:29
4
\$\begingroup\$

C#: 38 (40 to ensure non-negative numbers)

Inspired by the beauty of Jon Skeet's C# answer and St0le's answer, another C# solution in only 38 characters:

Func<int,int>f=n=>n>2?f(n-1)+f(n-2):1;

Tested with:

for(int i = 1; i <= 15; i++)
    Console.WriteLine(f(i));

Yay for recursive Func<>! Incorrect when you pass in negative numbers, however - corrected by the 40 character version, which doesn't accept them:

Func<uint,uint>f=n=>n>2?f(n-1)+f(n-2):1;

Note: as pointed out by @Andrew Gray, this solution doesn't work in Visual Studio, as the compiler rejects the in-line function definition referring to itself. The Mono compiler at http://www.compileonline.com/compile_csharp_online.php, however, runs it just fine. :)

Mono Compilation

Visual Studio: 45

Func<int,int>f=null;f=n=>n>2?f(n-1)+f(n-2):1;
\$\endgroup\$
5
  • \$\begingroup\$ looks rather familiar...dunno where I've seen that before... ;) As far as I can tell, though, in C# this is the best way of doing it. However, your way won't work - you have to assign null to your function to use a recursive lambda. As that code stands, it won't compile, with a syntax error 'use of unassigned function f' at the line that your lambda is being defined at. \$\endgroup\$ Apr 17 '13 at 18:14
  • 1
    \$\begingroup\$ Depends on your compiler. :) It does exactly as you say in Visual Studio - but the Mono compiler at compileonline.com/compile_csharp_online.php runs it perfectly as-is. \$\endgroup\$ Apr 17 '13 at 18:45
  • 1
    \$\begingroup\$ Didn't know that. I wonder why VS and Mono went two different directions on this one...or, maybe the Mono guys are just smarter. The answer is beyond me. D: \$\endgroup\$ Apr 17 '13 at 18:49
  • \$\begingroup\$ Updated to clearly point out our findings. ;) \$\endgroup\$ Apr 17 '13 at 18:53
  • \$\begingroup\$ Does this handle the F(0)=0 case? It's an easy fix that doesn't cost any extra bytes: just exchange :1 for :n \$\endgroup\$
    – Cyoce
    Mar 25 '16 at 5:59
4
\$\begingroup\$

Windows PowerShell – 34 30

for($b=1){$a,$b=$b,($a+$b)
$a}
\$\endgroup\$
8
  • \$\begingroup\$ You can save 3 by doing away with defining $a at the start (assuming $a is not already defined in the environment), and moving the echo of $a to the end of the loop. \$\endgroup\$
    – Iszi
    Nov 19 '13 at 17:11
  • \$\begingroup\$ I can even save one more by including the initialisation in the loop header. \$\endgroup\$
    – Joey
    Nov 19 '13 at 22:13
  • \$\begingroup\$ Wow. I never actually ran this until today for some reason. It's interesting that, past around 1E+308, PowerShell just gives up and calls it Infinity. \$\endgroup\$
    – Iszi
    Nov 27 '13 at 21:57
  • \$\begingroup\$ I put together a solution, somewhat based on this, that accepts user input and outputs the nth number. Came out to 45 characters. You want that here, or as a separate answer? \$\endgroup\$
    – Iszi
    Nov 27 '13 at 22:06
  • \$\begingroup\$ @Iszi, give a separate answer, I guess. It solves a different problem, after all. \$\endgroup\$
    – Joey
    Nov 28 '13 at 5:55
4
\$\begingroup\$

GNU Octave: 19 chars

@(x)([1,1;1,0]^x)(1)

This solution has the distinction of running in O(log n) time.

\$\endgroup\$
1
  • \$\begingroup\$ Edited it to a language that I can test. \$\endgroup\$ Nov 18 '15 at 5:43
4
\$\begingroup\$

Cy, 33 31 30 bytes (non-competing)

This is going for the function option (takes N, outputs F(N))

0 1 :>i {1 - $&+ times} &if :<

Ungolfed/explanation:

0 1       # first two fibs are 0, 1
:>i       # read input as integer (let's call it N)
{
  1 -    
    {&+}      # add the last two values
  times     # repeat N-1 times ^
} &if     # if N is non-zero ^
:<        # output the last calculated value (if N is 0, that would be 0)
\$\endgroup\$
4
\$\begingroup\$

Detour (non-competing), 8 bytes

[$<<]!S.

Try it online!

This one is shorter than the word "fibonacci"

[$<<]!S.
Fibonacci

explanation:

[   ]     # while n > 0
 $<<       # replace n with [n-1, n-2]
     !S.  # invert, output




Just for fun, here's one that will always take exactly 19 ticks to terminate, whether given 0 or 1474. On my really old macbook, it on average terminates after 7ms.


Detour, 30 28 bytes

$Q{G<!d}seQ
.{5Vg>d}se-$G_c!

Try it online! This is the way of expressing (((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)




Old way:


Detour (non-competing), 10 9 bytes

<Q>S.
;$<

Try it online!


This is non-competing: I just pushed the required version of the language about 10 minutes ago.

Detour works like befunge, fish etc. except for one crucial difference: where those languages redirect the instruction pointer, detour redirects data.

Input is pushed in at the beginning of the middle line (in this case the first). < decrements a number, > increments it. Q sends it down if a number is greater than 0, forward otherwise.

the line ;$< is the same as $<; because edges wrap. What it does is take the number it is given, then push that number and 1 less than that number to the input. This is how detour does recursion.

S reduces with addition, and . outputs the result.

For a better explanation, visit the site and it will give a visual representation of all the numbers.

\$\endgroup\$
4
\$\begingroup\$

AsciiDots, 22 21 20 17 16 15 bytes

/.{+}-\
\#$*#1)

Prints the Fibonacci sequence. Outgolfs the sample by 12 13 14 17 18 19 bytes. This is now just 1 byte longer than exactly as long as a simple counter! Try it online!


AsciiDots, 31 30 bytes

 /#$\
.>*[+]
/{+}*
^-#$)
\1#-.

Here's a faster version. It prints out the Fibonacci sequence at a rate of 1 number per 5 ticks, compared to the maximally golfed version's 1 per 8 10 8 12 14 ticks. It's twice as fast as the sample and is still shorter by 3 4 bytes! Try it online!

\$\endgroup\$
4
\$\begingroup\$

Symbolic Python, 34 31 bytes

-3 bytes thanks to H.PWiz!

__('__=_/_;'+'_,_=_+__,__;_'*_)

Try it online!

Returns the nth element of the Fibonacci, 1-indexed, starting from 1,1,2,3,5....

Explanation:

__(                           ) # Eval as Python code
   '__=_/_;'                    # Set __ to 1
            +'             '*_  # Then repeat input times
              _,_=_+__,__;      # On the first iteration, set _ to __ (1)
                         ;_     # On future iterations, prepend a _
             __,_=_+__,__;      # Set __ to the next fibonacci number
                                # And set _ to the old value of __
                                # Implicitly output _

Or, H.PWiz's version:

__('_=__=_/'+'_;__,_=_+__,_'*_)

Try it online!

Explanation:

__('_=__=_/'+'_;__,_=_+__,_'*_)

__(                           ) # Eval as Python code
   '_=__=_/'+'_;                # Set both _ and __ to 1
             '             '*_  # Repeat input times
                __,_=_+__,__    # Set __ to the next fibonacci number
                                # And set _ to the old value of __
                __,_=_+__,_     # Except on the last iteration
                                # Implicitly output _
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is possible in 31 bytes. See if you can see how :) \$\endgroup\$
    – H.PWiz
    Dec 17 '18 at 7:33
4
\$\begingroup\$

Alchemist, 104 87 bytes

-10 bytes thanks to ASCII-only!

_->b+c+m
m+b->m+a+d
m+0b->n
n+c->n+b+d
n+0c->Out_a+Out_" "+o
o+d->o+c
o+0d+a->o
o+0a->m

Produces infinitely many Fibonacci numbers, try it online!

Ungolfed

_ -> b + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> Out_a + Out_" " + s2

# c <- d & clear a
s2 +  d     -> s2 + c
s2 + 0d+  a -> s2
s2     + 0a -> s0

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ 95? too lazy to check if algo is shorter \$\endgroup\$
    – ASCII-only
    Jan 29 '19 at 11:08
  • 1
    \$\begingroup\$ 94 and left sides in better order \$\endgroup\$
    – ASCII-only
    Jan 30 '19 at 6:29
  • \$\begingroup\$ @ASCII-only: Nice! Noticed I can also output \$\infty\$ many terms, saved another 7 bytes.. but Alchemist indeed needs some work done (atm. it only works when properly killing the process due to some buffering issues). \$\endgroup\$ Jan 31 '19 at 15:48
  • \$\begingroup\$ lol > bytes bytes \$\endgroup\$
    – ASCII-only
    Jan 31 '19 at 23:37
4
\$\begingroup\$

Intel 8087 FPU, 13 bytes

Binary:

00000000: d9e8 d9ee dcc1 d9c9 e2fa df35 c3         ...........5.

Listing:

D9 E8       FLD1                ; push initial 1 into ST(1)
D9 EE       FLDZ                ; push initial 0 into ST
        FIB_LOOP:
DC C1       FADD ST(1), ST      ; ST(1) = ST(1) + ST 
D9 C9       FXCH                ; Exchange ST and ST(1)
E2 FA       LOOP FIB_LOOP       ; loop until n = 0
DF 35       FBSTP [DI]          ; store result as BCD to [DI]
C3          RET                 ; return to caller

As a callable function, input n in CX, output to a 10 byte little-endian packed BCD representation at [DI]. This will compute up to Fibonacci n=87 using the Intel x87 math-coprocessor using 80-bit extended-precision floating point arithmetic.

Run using DOS DEBUG with n = 9, result 34:

enter image description here

n = 87 (0x57), result 679891637638612258:

enter image description here

\$\endgroup\$
4
\$\begingroup\$

convey, 8 bytes

Generates the sequence.

v+"}
1"1

Try it online!

enter image description here

The values (initially 1 and 1) follow the conveyor belts indicated by the arrow heads. " duplicates the input into both outputs, + adds them, and } writes them to the output.

\$\endgroup\$
4
\$\begingroup\$

COBOL (GNU), 170 bytes

I am surprised at the lack of COBOL answers on this site. Well, it is ancient after all.

This outputs the fibonacci sequence correctly up to 38 digits.

PROGRAM-ID.H.DATA DIVISION.LOCAL-STORAGE SECTION.
1 a PIC 9(38).
1 b PIC 9(38).
PROCEDURE DIVISION.G.COMPUTE a=0**b+b -a
ADD a TO b
DISPLAY b(38- FUNCTION LOG10(b):)GO G.

Try it online!

Explanation

We just need two variables, a and b to compute the whole fibonacci sequence. Here is pseudocode of what this would look like:

a = 0
b = 1
loop {
  a = b - a
  b += a
  print(a)
}

Translating the pseudocode above in COBOL is relatively short and simple. But we see that variables in COBOL are set to 0 by default, and having one of them set to a 1 is kind of (8 bytes) long, so we hack it out like so:

a = 0
b = 0
loop {
  a = b - a + 0 ** b
  b += a
  print(b)
}

The 0 ** b ensures that a = 1 on the first iteration. From then on, the logic is the same as in our first pseudocode implementation (since 0 ** (any number greater than 0) = 0). The change from print(a) to print(b) is just to ensure that the numbers are outputted in the correct order.

Ungolfed

PROGRAM-ID. H.

DATA DIVISION.
LOCAL-STORAGE SECTION.
1 a PIC 9(38).                     // Declare a variable named `a` (a = 0)
1 b PIC 9(38).                     // Declare a variable named `b` (b = 0)

PROCEDURE DIVISION.
G.                                 // Define a label named `G`
COMPUTE a=0**b+b -a                // a = b - a + 0 ** b
ADD a TO b                         // b += a
DISPLAY b(38- FUNCTION LOG10(b):)  // Print `b` without trailing zeros
GO G.                              // Jump to the label named `G` (4 lines above)
\$\endgroup\$
3
\$\begingroup\$

J - 20

First n terms:

(+/@(2&{.),])^:n i.2
\$\endgroup\$
3
\$\begingroup\$

Common Lisp, 48 Chars

(defun f(n)(if(< n 2) n(+(f(decf n))(f(1- n)))))
\$\endgroup\$
4
  • \$\begingroup\$ Is left-to-right evaluation order guaranteed in CL? If not, your solution won't work. (There is no such guarantee in Scheme, and many implementations are right-to-left.) \$\endgroup\$ Apr 5 '11 at 2:12
  • \$\begingroup\$ Left-to-right is in the standard so since these are all built-in functions it is reliable. (Macros can of course do stupid things :-) \$\endgroup\$
    – Dr. Pain
    Apr 29 '11 at 18:00
  • \$\begingroup\$ This is actually 47; you can get rid of the space between (< n 2) and n. \$\endgroup\$ Nov 17 '15 at 20:54
  • \$\begingroup\$ And a slight modification is 46: (defun f(n)(if(< n 2)n(+(f(1- n))(f(- n 2))))). \$\endgroup\$ Nov 17 '15 at 20:55
3
\$\begingroup\$

BrainFuck, 172 characters

>++++++++++>+>+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>]<<<]

Credit goes to Daniel Cristofani

\$\endgroup\$
3
\$\begingroup\$

PowerShell: 42 or 75

Find nth Fibonacci number - 42

A spin-off of Joey's answer, this will take user input and output the nth Fibonacci number. This retains some weaknesses also inherent to Joey's original code:

  • Technically off by 1, since it starts the Fibonacci sequence at 1,1 instead of the more proper 0,1.
  • Only valid for Fibonacci numbers which will fit into int32, because this is PowerShell's default type for integers.
  • Example: Due to the int32 limitation, the highest input that will return a valid report is 46 (1,836,311,903) and this is technically the 47th Fibonacci number since zero was skipped.

Golfed:

($b=1)..(read-host)|%{$a,$b=$b,($a+$b)};$a

Un-Golfed & Commented:

# Feed integers, from 1 to a user-input number, into a ForEach-Object loop.
# Initialize $b while we're at it.
($b=1)..(read-host)|%{
    # Using multiple variable assignment...
    # ...current $b is put into new $a, and...
    # ...sum of current $b and current $a are put into new $b.
    $a,$b=$b,($a+$b)
};
# When loop exits, output $a.
$a

# Variable cleanup, not included in golfed code.
rv a,b

List Fibonacci numbers - 75

Another derivative of Joey's answer, but with some improvements:

  • Zero is included in the output, as it should be according to OEIS.
  • Goes up to the maximum Fibonacci number that can be handled as uint64 instead of the default int32. (Highest Fibonacci number in uint64 is 12,200,160,415,121,876,738.)
  • Output stops once the maximum value is reached, instead of looping through 'Infinity' or continuously throwing errors.

Golfed:

for($a,$b=0,1;$a+$b-le[uint64]::MaxValue){$a;$a,$b=$b,[uint64]($a+$b)}$a;$b

Un-Golfed & Commented:

# Start Fibonacci loop.
for
(
    # Begin with $a and $b at zero and one.
    $a,$b=0,1;

    # Continue so long as the sum fits in uint64.
    $a+$b-le[uint64]::MaxValue
)
{
    # Output current $a.
    $a;

    # Using multiple variable assignment...
    # ...current $b becomes new $a, and...
    # ...sum of current $b and current $a is forced to uint64 and stored in new $b.
    $a,$b=$b,[uint64]($a+$b)
}

# Output $a and $b one more time.
$a;$b

# Variable cleanup - not included in golfed code.
rv a,b
\$\endgroup\$
5
  • \$\begingroup\$ One thing that bugs me a little in PowerShell: Read-Host always reads interactively and won't pick up things you pipe into the script (or process), whereas $input (which is what I tend to use) only picks up piped input (for obvious reasons; that's how it's defined) but cannot be used interactively. Which means that you can write a PowerShell script that either works interactively or one that works with piped input, but not both at the same time (at least not for golfing). \$\endgroup\$
    – Joey
    Nov 28 '13 at 20:21
  • \$\begingroup\$ Yeah, and I personally prefer my scripts to be interactive whether the challenge calls for it or not. Wait... Did you just golf the un-golfed code? And not just any part of it, but particularly the bit that's not at all in the golfed code? \$\endgroup\$
    – Iszi
    Nov 28 '13 at 22:57
  • \$\begingroup\$ I merely optimized it, since Remove-Variable takes a string[]. There is no need to have two calls ;-) \$\endgroup\$
    – Joey
    Nov 29 '13 at 6:13
  • \$\begingroup\$ I meant to say I found it amusing that of all the code to be optimized, you had to go and fix the bit that wasn't even part of the golfed solution. It's like you had an OCD moment or something. \$\endgroup\$
    – Iszi
    Nov 29 '13 at 7:25
  • \$\begingroup\$ Sometimes I do ;-). I don't see anything that makes the golfed code smaller either. For an algorithm this simple there aren't many options and range|% is often the shortest (but also the slowest) way. \$\endgroup\$
    – Joey
    Nov 29 '13 at 7:27
3
\$\begingroup\$

Forth - 38 33 bytes

: f dup . 2dup + 2 pick recurse ;

Generates and prints a Fibonacci series recursively until it runs out of stack space.

Usage:

 1 1 f

Or to generate Fn, where n>=1 (66 bytes):

: f dup 3 < if 1 nip else dup 1- recurse swap 2 - recurse + then ;

Example of usage:

9 f .

output:

34 
\$\endgroup\$
6
  • \$\begingroup\$ It does work, but like I said it doesn't terminate itself. It should generate correct output up until 46! at least, and after that it will just keep on going and output "garbage". And since that online compiler doesn't appear to have any way of halting the execution without clearing the console output it gets pretty hard to see the correct output at the beginning. \$\endgroup\$
    – Michael
    Oct 14 '15 at 15:23
  • \$\begingroup\$ So it just runs so fast that all I can see is the zeros? \$\endgroup\$
    – mbomb007
    Oct 14 '15 at 18:39
  • \$\begingroup\$ Right. If you run it in Win32Forth you can scroll up and get it to stay at the top so that you actually can see the correct output for Fn up to n=46. \$\endgroup\$
    – Michael
    Oct 14 '15 at 19:37
  • \$\begingroup\$ Also, if I'm not mistaken : f over . 2dup + recurse ; is shorter (27 bytes). This way, the first number is printed first, and the numbers are in order on the stack, so we don't need 2 pick. \$\endgroup\$
    – mbomb007
    Oct 14 '15 at 20:19
  • \$\begingroup\$ Yup, that seems to generate the same sequence as my version. \$\endgroup\$
    – Michael
    Oct 14 '15 at 20:53
3
\$\begingroup\$

Java, 41 bytes

There are a couple other Java answers here, but I'm surprised nobody has posted this simple one:

int f(int n){return n<2?n:f(n-1)+f(n-2);}

For an extra byte you can extend the range up to long.

\$\endgroup\$
3
\$\begingroup\$

TeaScript, 4 bytes

F(x)

F(x) //Find the Fibonacci number at the input

Compile online here (DOES NOT WORK IN CHROME). Enter input in the first input field.

\$\endgroup\$
2
3
\$\begingroup\$

J, 9 bytes

+/@:!&i.-

Gets the nth Fibonacci number by finding the sums of the binomial coefficients C(n-i-1, i) for i from 0 to n-1.

Also, a short way using 12 bytes to generate the first n Fibonacci numbers is

+/@(!|.)\@i.

It uses the same method as above but works by operating on prefixes of the range [0, 1, ..., n-1].

Usage

   f =: +/@:!&i.-
   f 10
55
   f 17
1597

Explanation

+/@:!&i.- Input: n
        - Negate n
     &i.  Form the ranges [n-1, n-2, ..., 0] and [0, 1, ..., n-1] 
    !     Find the binomial coefficient between each pair of values
+/@:      Sum those binomial coefficients and return
\$\endgroup\$
1
  • \$\begingroup\$ Whoa. Just whoa. \$\endgroup\$ Sep 24 '16 at 0:38
3
\$\begingroup\$

Javascript, 28 Characters

f=n=>(n<=2)?1:f(n-1)+f(n-2);

Try it here!

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Welcome to PPCG! How about n<3? And do you really need the parentheses around the inequality? You can probably also omit the semicolon. \$\endgroup\$ Mar 25 '17 at 19:43
  • \$\begingroup\$ @MartinEnder is correct, use f=n=>n<3?1:f(n-1)+f(n-2) for a total of 24 bytes \$\endgroup\$
    – user100690
    Mar 16 '21 at 10:44
3
\$\begingroup\$

Emojicode, 100 bytes

🐖🔢➡️🚂🍇🍊◀️🐕2🍇🍎🐕🍉🍓🍇🍎➕🔢➖🐕1🔢➖🐕2🍉🍉

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Piet, 17 codels

Not sure how to count this one. There are 17 pixels within the code that count as instructions/control flow modifiers (18 if you count the required NOP to get the color back to the correct cycle for the loop).

Shown here at 20 pixels per codel:

Short Fibonacci in Piet

Explanation in pseudocode:

push 1
push 1
push 1
push 1
out (number)
out (number)
START OF INFINITE LOOP
duplicate
push 3
push 1
roll ; the last three instructions amount to "rotate the top to the third spot once"
add
duplicate
out (number)
END OF INFINITE LOOP

This outputs the Fibonacci sequence (starting with 1,1) without delimiters.

Actual image (way too small to see clearly): SMALLER Fibonacci in Piet

\$\endgroup\$
1
  • \$\begingroup\$ Oh, didn't know there was a convention for this. Was unsure. Will change now. \$\endgroup\$ Sep 13 '17 at 11:29
3
\$\begingroup\$

Common Lisp, 38 bytes

Generates the Fibonacci sequence without end.

(do((a 1 b)(b 1(+ a b)))(())(print a))

Try it online!

The other Common Lisp solution is a function to generate the n-th number. This solution works since in the do loop the assignments to the iteration variables are performed in parallel: so the initialization is equivalent to:

a, b = 1, 1

while at each repetition the assignment is equivalent to:

a, b = b, a+b
\$\endgroup\$
1
2
3 4 5
10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.