149
\$\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, in accordance to the standard rules:

  • Generates the Fibonacci sequence without end.

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

  • Given n calculates the first n terms of the sequence

You may use standard forms of input and output.


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\$
5
  • 4
    \$\begingroup\$ I am sort of waiting for a response like "f", 1 byte, in my math based golf language. \$\endgroup\$ Commented Aug 11, 2020 at 11:57
  • \$\begingroup\$ @ChrisJesterYoung can we use 1.0 are 1 only? \$\endgroup\$ Commented May 11, 2022 at 2:45
  • \$\begingroup\$ @NumberBasher 1.0 is fine. \$\endgroup\$ Commented May 20, 2022 at 19:10
  • \$\begingroup\$ What about 1.3? \$\endgroup\$ Commented Aug 28, 2022 at 15:10
  • 2
    \$\begingroup\$ Am I allowed to start the sequence with 0, 1? \$\endgroup\$
    – hakr14
    Commented Oct 11, 2022 at 3:41

336 Answers 336

1
6 7
8
9 10
12
1
\$\begingroup\$

Axiom, 113 bytes

f(n:NNI):NNI==(n=0=>0;n:=n-1;x:=sqrt(5);floor(numeric(((x+1)/(2*x))*((1+x)/2)^n+((x-1)/(2*x))*((1-x)/2)^n)))::INT

code for test and results

(80) -> [f(i)  for i in 0..20]
   (80)
   [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
                                            Type: List NonNegativeInteger
(81) -> f 100
   (81)  354224848179261915076
                                                    Type: PositiveInteger
(82) -> f 200
   (82)  280571172992510140037336354957747795525632
                                                    Type: PositiveInteger
(83) -> f 400
   (83)
  1760236806450139664680709294813170892283658770059881093310828506440687624218_
   31925760
                                                    Type: PositiveInteger
(84) -> f 800
   (84)
  6928308186422471713609360660466569632290421684876894264783997577258487494487_
   420363654234099779749410573113727333378633545181944038619446626409501657425_
   3135847342735360
                                                    Type: PositiveInteger
(85) -> f 1500
   (85)
  1355112566856310195162377575526951323656561770431639555079987987810736653460_
   922122221302671882558120755439823360357867711740787668744312284056217232330_
   713983569575833249689158528416736647370129969548463847884661978641646883591_
   466734576231634867107272686298047871451723693301109753896341229444935835304_
   2229054930944
                                                    Type: PositiveInteger
(86) -> f 2000
   (86)
  4224696333392304878698067179976673472756391964001565086095500593531167791551_
   743662247281607190958887487440686606420026093467732621145548367502217030083_
   858092272596709322168369132666938424515347258074945014044152199085287931830_
   556530989999311940427567701708311778838430925973655760228465275886647451746_
   556255968313014088560151159533857580044154666168801306507492995800168547537_
   206536250047308876795741658264221262020608
\$\endgroup\$
1
\$\begingroup\$

Taxi, 864 bytes

1 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:W 1 L 2 R 1 L 1 L 2 L.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Cyclone.Go to Sunny Skies Park:W 1 R.[a]Go to Cyclone:N 1 L.Pickup a passenger going to The Babelfishery.Pickup a passenger going to Addition Alley.Go to Fueler Up:N 2 R, 2 R.Go to The Babelfishery:S.Pickup a passenger going to Post Office.Go to Post Office:N 1 L 1 R.Go to Sunny Skies Park:S 1 R 1 L 1 R.Pickup a passenger going to Cyclone.Go to Cyclone:N 1 L.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Addition Alley:N 2 R 1 R.Pickup a passenger going to Sunny Skies Park."," is waiting at Writer's Depot.Go to Writer's Depot:N 1 L 1 L.Pickup a passenger going to Post Office.Go to Sunny Skies Park:N 2 R.Switch to plan "a".

Try it online!

Ungolfed:

1 is waiting at Starchild Numerology.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd right 1st left 1st left 2nd left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Cyclone.
Go to Sunny Skies Park: west 1st right.
[a]
Go to Cyclone: north 1st left.
Pickup a passenger going to The Babelfishery.
Pickup a passenger going to Addition Alley.
Go to Fueler Up: north 2nd R, 2nd right.
Go to The Babelfishery: south.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.
Go to Sunny Skies Park: south 1st right 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Cyclone.
Go to Addition Alley: north 2nd right 1st right.
Pickup a passenger going to Sunny Skies Park.
"," is waiting at Writer's Depot.
Go to Writer's Depot: north 1st left 1st left.
Pickup a passenger going to Post Office.
Go to Sunny Skies Park: north 2nd right.
Switch to plan "a".
\$\endgroup\$
1
\$\begingroup\$

Braingolf, 23 bytes

1!_# @.!_[# @!+!_<1+>];

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 17 bytes \$\endgroup\$
    – Mayube
    Commented Jun 16, 2017 at 9:20
  • 1
    \$\begingroup\$ 14 bytes \$\endgroup\$
    – Mayube
    Commented Jun 16, 2017 at 9:23
  • 1
    \$\begingroup\$ 8 bytes for output the nth number \$\endgroup\$
    – Mayube
    Commented Jun 16, 2017 at 9:35
1
\$\begingroup\$

Joy, 45 bytes

DEFINE f ==[2<][][[1 - f][2 - f]cleave+]ifte.

Try it online! Zero-indexed. Example usage: 6 f yields 8.

[2<]                         ifte . if the top stack element is less than two  
    []                            . then do nothing
      [              cleave ]     . else duplicate the element and apply two functions
                           +      . and sum the results
       [1 - f][2 - f]             . where the functions compute the two previous Fibonacci numbers

Alternative (same byte count):

DEFINE f ==[2<][][dup 1 - f swap 2 - f+]ifte.
\$\endgroup\$
1
\$\begingroup\$

cQuents, 6 bytes

=1:z+y

Try it online!

This works both with and without input - it prints the sequence without input, and the nth item (1-indexed) with input n.

For 0, 1, 1, ... version, 8 bytes:

=0,1:z+y

Try it online!

Explanation

=1      Set first item in sequence to 1
  :     Mode: Sequence 1 (prints sequence with no input, or nth item with input n
   z+y  Each term equals the previous two terms added together (defaults to 0)

I really, really like the way this language is going :)

\$\endgroup\$
1
  • \$\begingroup\$ Note current version uses Z and Y instead of z and y \$\endgroup\$
    – Stephen
    Commented Feb 1, 2019 at 4:54
1
\$\begingroup\$

ReRegex, 50 bytes.

(0+),(0+):0/$1,$2,$1$2:/.*?(0+),0+:$/$1/0,0:#input

0 indexed. Takes input and gives output via Unary.

Try it online!

About the Program

ReRegex was designed to be much like an advanced version of ///. It offers the same very basic concept of repeatedly doing string match and replace operations. However, that's where the similarities end. ReRegex instead uses a list of match and replace operations, separated by /s, to perform in a loop, and the original string to effect. The Regexes will continue being performed on the original string until a constant state is achieved, at which point the program will dump the string to STDOUT.

This program in particular is just 2 regular expressions and then the input with some default values.

(0+),(0+):0  -> $1,$2,$1$2:
.*?(0+),0+:$ -> $1

And the input is formatted with;

0,0:#input

ReRegex defaultly replaces #input with whatever is passed to the program on STDIN.

For an example, let's say 00000 is passed to STDIN. First, the "Memory" looks like this:

0,0:00000

In the first loop, the regex (0+),(0+):0 is matched, the replace then creates the next itteration of the fibonnachi sequence.

0,0,00:0000

And in doing so, it also pops one of the 0's off, which is why :0 is at the tail end of the match, but not the replace. This then happens 4 more times in a row.

0,0,00,000,00000,00000000,0000000000000:

Now that first regex doesn't match, as there's no more :0 at the end, so we're almost at a stable end point. Now that there's nothing after :, .*?(0+),0+:$ matches, and all it does is clear all data but the second last group of 0s.

00000000

Now, nothing else matches, so it's outputted.

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

Joy, 28 bytes

[2<][][1 - dup 1 -][+]binrec

Try it online!

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

Forth, 39 36 bytes

0 1 : f BEGIN 2DUP + ROT . AGAIN ; f

Explanation

First 0 and 1 are pushed to the stack. Then starts an endless loop where 2DUP duplicates the top two stack items which are then summed with +. At this point stack is 0 1 1. Then the bottom item of the stack is moved on top with ROT. . prints and removes the item on the top of the stack. Creates an endless sequence of Fibonacci numbers.

Had to check out what's Forth about. And is there a better way to learn than trying to golf Fibonacci series. I see that there's already an answer with Forth but desided to post anyway. At least this is a different approach.

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

Proton, 24 bytes

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

Try it online!

(Not working on TIO yet; waiting for pull)

The @ is not necessary but it enables caching for the lambda which makes it considerably faster (as in, it actually finishes in a reasonable amount of time). That being said, when I tried computing it up to 10000 (which I needed to increase sys.setrecursionlimit to do), it gave me a Segmentation Fault because the program ran out of memory (Proton is very inefficient) :P

\$\endgroup\$
2
  • \$\begingroup\$ Polyglot with ES6. \$\endgroup\$
    – Adalynn
    Commented Aug 12, 2017 at 21:54
  • \$\begingroup\$ @Zacharý Huh that's cool. This is weird; Proton is often a polyglot with Python too :P \$\endgroup\$
    – hyper-neutrino
    Commented Aug 13, 2017 at 0:51
1
\$\begingroup\$

C, 224 229 227 chars

...prints the n'th fibonacci or 2^n

Golfed up:

#import <Foundation/Foundation.h>
typedef unsigned long long f;f main(int c,char*v[]){f n=strtoull(v[1],(char**)v[2],10)-1;f x=(c>2&&++n==0)?0:1;f y=0;while(n--!=0&&x+y>=x&&x>0){f z=x;c>2?x+=y=z:(x+=y,y=z);}printf("%llu\n",x);}

Readable:

#import <Foundation/Foundation.h>
typedef unsigned long long f;
f main(int c,char*v[]){
    f n=strtoull(v[1],(char**)v[2],10)-1;
    f x=(c>2&&++n==0)?0:1;
    f y=0;
    while(n--!=0&&x+y>=x&&x>0){
        f z=x;
        c>2?x+=y=z:(x+=y,y=z);
    }
    printf("%llu\n",x);
}

If the number exceeds the length of an unsigned long long it will print the highest it can get. Return type is f (unsigned long long) for short code, it does generate 2 compiler warnings and a note but it still compiles!

It also has the option to calculate 2^n because it initially printed that.

Usage:

  • ./fibbin 42 - prints 42'th fibonacci number (267914296)
  • ./fibbin 42 anyInputHere - prints 2^n (4398046511104).

Don't enter values of 0, higher than 93 (fibonacci) or higher than 63 (2^n).

Examples:

  • ./fibbin 1 = 1

  • ./fibbin 2 = 1

  • ./fibbin 3 = 2

  • ./fibbin 4 = 3

  • ./fibbin 42 = 267914296

  • ./fibbin 92 = 7540113804746346429

  • ./fibbin 93 = 12200160415121876738 - this is the highest i can go

  • ./fibbin 94 = should be 19740274219868223167, but it doesn't fit into an unsigned long long so i will print #93

  • ./fibbin 1 bin - 2

  • ./fibbin 2 bin - 4

  • ./fibbin 3 bin - 8

  • ./fibbin 4 bin - 16

  • ./fibbin 42 bin - 4398046511104

  • ./fibbin 62 bin - 4611686018427387904

  • ./fibbin 63 bin - 9223372036854775808 - this is the highest i can go

  • ./fibbin 64 bin - should be 18446744073709551616, but it doesn't fit into an unsigned long long so i will print 0

These tests match the output of wolfram-alpha, due to the heavy calculations wolfram may time out but it generally doesn't.

\$\endgroup\$
2
  • \$\begingroup\$ I'm no C expert but I think n--!=0&&... can be replaced with n--&&... \$\endgroup\$
    – Cyoce
    Commented May 2, 2016 at 15:17
  • \$\begingroup\$ 117 bytes \$\endgroup\$
    – c--
    Commented Jul 21, 2022 at 17:53
1
\$\begingroup\$

Element, 12 (option two) or 11 (option one)

I've decided to go back in time and answer some classic golfing questions with Element to give it some more street cred.

The following code prints out the Fibonacci sequence continuously (it overflows rather quickly). Each number is printed separately, although there is no whitespace separation.

1!{4:`~2@+}
1            push 1 onto the stack
 !           flip the empty control stack to 1 to enable looping
  {       }  infinite while loop
  {4:     }  have 4 copies (3 additional) of the newest number on the stack
  {  `    }  output one copy
  {   ~   }  A fancy way to get zero from a copyusing the variable retrieval function
  {    2~ }  Move one copy from position 0 to position 2 (behind the old number)
  {      +}  add the number to the old number

The following code inputs a number and outputs the Nth number in the sequence (0-indexed).

1_'[3:~2@+]`
1             push a 1
 _'           take input then move it to the control stack
   [      ]   FOR loop
   [3:    ]   make two additional copies of the top number (3 is the total count)
   [  ~   ]   turn one copy into a zero
   [   2@ ]   move from position 0 to position 2, behind the old number
   [     +]   add the old and newer number
           `  output the result 

For completion's sake, here is a link to the interpreter.

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

Tampio, 107 bytes

uni on 1 lisättynä 1:een lisättynä yhteenlaskuun sovellettuna unen jäseniin ja unen hännän jäseniin

Explanation:

uni on 1 lisättynä 1:een lisättynä
uni =  1 :         1     :

yhteenlaskuun sovellettuna  unen jäseniin ja unen hännän jäseniin
(+)           `zip`        (uni           ,  tail uni            )
\$\endgroup\$
1
\$\begingroup\$

Axiom, 35 bytes

a(0)==0;a(1)==1;a(n)==a(n-1)+a(n-2)

above it is one succession defined by Recurrence... Results

(7) -> [a(i)  for i in 0..20]
   (7)  [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
\$\endgroup\$
0
1
\$\begingroup\$

Recursiva, 16 bytes

<a3:1!+#~a$#~~a$

Try it online!

Explanation:

<a3:1!+#~a$#~~a$
<a3:1            - If a<3 then 1
     !           - Else
      +          - Sum
       #~a$      - Call Self but with parameter a-1, will be replaced by result
           #~~a$ - Call self but with parameter a-2, will be replaced by result      
\$\endgroup\$
1
\$\begingroup\$

Cy, 11 + 1 (-p flag) = 12 bytes (non-competing)

This is going for the infinite stream

0 1 $&+ &do

(the -p flag implicitly prints every non-block value pushed to the stack)

Literally,

  • push 0
    • print it
  • push 1
    • print it
  • forever
    • push the sum of the last two items
    • print it



Without the -p flag semi-cheat:

Cy, 24 bytes

0 &:< 1 &:< {&+ &:<} &do
\$\endgroup\$
1
\$\begingroup\$

><>, 12 Bytes

10:r+:nao20.

Output:

1
1
2
3
5
...

Could save 2 bytes by removing the new line, but then there would be no separation in the output at all.

Explanation:

Pretty basic. Start by pushing 1, 0 to the stack. Duplicate the top item, reverse the stack, and sum the top two items. If we had f_n, f_n-1 on the stack before, we now have f_n+1, f_n. Duplicate the top item, and print it. 'ao' prints a new line. '20.' moves the pointer to (2,0) in the codebox, which is right after the '10'. Start again.

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

tinylisp, 40 bytes

The language is much newer than question, of course.

(d f(q((x y)(i(disp x)1(f y(a x y
(f 0 1

This is a full program that outputs Fibonacci numbers until you stop it. Try it online!

The first line defines a function f that takes numbers x and y, outputs x, and calls f recursively on y and the addition of x and y. The main trick is the use of if to simulate a "do A, then B" structure: the disp call is used as the condition; its return is always falsey; so we put the recursion in the false branch.

The second line calls f with 0 and 1.

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

QBasic, 32 bytes

b=1
DO
?b
b=b+a
a=b-a
SLEEP
LOOP

Generates and prints Fibonacci numbers forever. SLEEP waits for a user keypress between numbers; otherwise, the output would scroll off the screen very rapidly.

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

FALSE, 13 bytes

1 1[1][$2ø+]#

Numbers are pushed to the stack.

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

Coconut, 28 bytes

def f(a=1,b=1)=[a]::f(b,a+b)

Try it online!

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

Forked, 17 15 bytes

01v
  >sP+%A!"U

Try it online!

This uses the same method as my Implicit answer.

The first line sets up the stack: pushes 0, pushes 1, and then directs the control flow South.

The > on the second line turns the IP East where it hits the main code:

sP+%A!"U
  • s - swap top two stack values
  • P - pop top of stack, store in register
  • + - pop top two stack values, add together, push result
  • % - print top of stack as integer
  • A! - print 0xA as codepoint character (ASCII newline)
  • " - swap top two stack values
  • U - push register to stack

Since the IP wraps, this line is executed infinitely.

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

Add++, 74 bytes

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,r,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{r}

Try it online!


Old version, 75 bytes

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,r,@:,1b]$oVcGbM
x:?
-1
I,$f>x>0>1>0
$r>x

Try it online!

It's long, but I rather this than have a builtin. Takes a single input n, and outputs the nthe Fibonacci number.

How it works

Executable demonstration with an example input of 8:

D,fib,@@@@*,	; Create a tetradic function 'fib'
		; This returns the nth and (n-1)th fib number
		; Example arguments:	[8 0 1 0]
	V	; Save the top value;	[8 0 1]	  ; 0
	$	; Swap;			[8 1 0]	  ; 0
	2D	; Take the 2nd value;	[8 1 0 1] ; 0
	+	; Sum;			[8 1 1]	  ; 0
	G	; Retrieve;		[8 1 1 0]
	1+	; Increment;		[8 1 1 1]
	d	; Duplicate;		[8 1 1 1 1]
	A	; Push the arguments;	[8 1 1 1 1 8 0 1 0]
	ppp	; Pop 3 values;		[8 1 1 1 1 8]
	=	;   Cond: Equal?	[8 1 1 1 0]
	0$Qp	;   If: Return 0
	{fib}p	;   Else: Call 'fib' again
                ; Eventually, this returns:
		;	[7 13 21 7 0]

D,ret,@:,	; Create a monadic function 'ret' that outputs the final result
		; Example argument:	[[7 13 21 7 0]]
	1b]	; Push [1];		[[7 13 21 7 0] [1]]
	$	; Swap;			[[1] [7 13 21 7 0]]
	o	; Logical OR;		[[1] [7 13 21 7 0]]
	VcG	; Clear all but one;	[[7 13 21 7 0]]
	bM	; Take the maximum;	[21]

x:?		; Take input;		x = 8
-1		; Decrement;		x = 7
I,		; If x != 0:
	$fib>x	;	Call 'fib'	x = [7 13 21 7 0]
	>0>1>0	; 
$ret>x		; Call 'ret'		x = 21

Try it online!

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

Retina 0.8.2, 23 bytes

.+
$*
+`11(1*)
1$1 $1
1

Try it online! Explanation:

.+
$*

Convert to unary.

+`11(1*)
1$1 $1

Repeatedly replace all n greater than 1 with copies of n-1 and n-2, thus calculating f(n) = f(n-1) + f(n-2) for n greater than 1.

1

Count the remaining 1s, as f(0) = 0 and f(1) = 1.

\$\endgroup\$
1
  • \$\begingroup\$ 4 days ago I set out to implement Fibonacci in Retina using emulation of the ^(.|..)*$ partition counting method. After golfing it down it turned out to be almost exactly the same as yours at the same size in bytes, except that I was thinking about it differently at a conceptual level. \$\endgroup\$
    – Deadcode
    Commented Jul 24, 2022 at 9:38
1
\$\begingroup\$

µ6, 16 bytes

[>#[,.[+.]][[,>[#/0[+/1]<>]]/1]]

Try it online!

Explanation

[>                               -- right element of the tuple generated by
  #                              -- | primitive recursive function
                                 -- | base case:
   [,                            -- | | pair of
     .                           -- | | | constant zero
     [+.]                        -- | | | successor of constant zero
   ]                             -- | | : (0,1)
                                 -- | recursive case:
   [                             -- | | compose the two
    [,                           -- | | | pair of
     >                           -- | | | | the right element
     [#/0[+/1]<>]                -- | | | | add left & right element
    ]                            -- | | | (snd, fst + snd)
    /1                           -- | | | second argument (we only need the tuple)
   ]                             -- | : (f (n-1), f (n-2) + f (n-1))
]                                -- : f n
\$\endgroup\$
1
\$\begingroup\$

x86 assembly (32-bit), 14 bytes

Bytecode:

58 59 50 41 31 c0 99 40 01 c2 92 e2 fb c3

That 3-byte add/xchg is quite concise :-)

1-indexed.

0:   58                      pop    %eax
1:   59                      pop    %ecx
2:   50                      push   %eax
3:   41                      inc    %ecx
4:   31 c0                   xor    %eax,%eax
6:   99                      cltd   
7:   40                      inc    %eax
8:   01 c2                   add    %eax,%edx
a:   92                      xchg   %eax,%edx
b:   e2 fb                   loop   8
d:   c3                      ret
\$\endgroup\$
1
  • \$\begingroup\$ how does this output? \$\endgroup\$
    – qwr
    Commented Feb 10, 2023 at 22:38
1
\$\begingroup\$

Binary-Encoded Golfical, 27+1 (-x flag)=28 bytes

Noncompeting, language postdates the question.

Hexdump:

00 90 02 00 01 14 0C 01 14 00 00 14 1B 1E 08 01
14 2C 17 0A 01 3A 0C 01 2D 1C 1D

This encoding can be converted back to the original image using the github repo's included Encoder utility (java Encoder d "<encoded file>" "<target file>") or run directly by adding the -x flag

Original image:

enter image description here

Magnified 50x:

enter image description here

Rough translation:

*p=1;
*(p+1)=*p;
*p=0;
while true:
 p++;
 push *p;
 p--;
 *(p+1)=*p;
 *p=pop;
 *p+=*(p+1);
 print *p;
end while;
\$\endgroup\$
1
\$\begingroup\$

Ahead, 15 bytes

1loN+{<
>\:O\:^

Uses signed 32-bit ints so eventually reaches overflow and wraps negative. Starts at 0, which is technically correct?

Try it online!

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

Tidy, 15 bytes

recur2(1,1,(+))

Try it online! Returns an infintie range of Fibonacci numbers.

Explanation

recur2 defines a recursive function which takes the previous 2 items and applies a function to them, in the case, addition. This is equivalent to saying "the first two entries are both 1 and every entry after that is the sum of the previous two".

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

Alumin, 19 bytes

zhdnqhhhhhdaodradnp

Try it online!

Explanation

zhdnqhhhhhdaodradnp
zh                    push 0, 1                 [0, 1]
  dn                  output 1                  [0, 1]
    q             p   loop (forever)            
     hhhhh            push 5                    [0, 1, 5]
          da          double (10)               [0, 1, 10]
            o         output as char (newline)  [0, 1]
             d        duplicate TOS             [0, 1, 1]
              r       reverse stack             [1, 1, 0]
               a      add top two               [1, 1]
                dn    output top w/out popping  [1, 1]
\$\endgroup\$
1
\$\begingroup\$

Pascal (FPC), 70 bytes

var i,j:word;begin i:=1;repeat writeln(i);i:=i+j;j:=i-j until 1<0 end.

Try it online! (limited)

Prints the sequence forever, 1-indexed.

Explanation:

var i,j:word;   //declare 2 integers, i and j;
                //word gives range [0,65535];
                //for bigger ranges, you can use Int32, Int64 or QWord
begin
  i:=1;         //set i to 1
                //j has not been set, so it gets 0 as initial value
  repeat        //start a block to be repeated (first time enters unconditionally)
    writeln(i); //write current value of i with a newline to separate numbers
                //i needs to get the value of the next number, which is obtained by adding i and j
    i:=i+j;     //j is used to keep track of the last written value
    j:=i-j      //which is used in the next iteration;
                //since i is now the sum of 2 previous values in the sequence
                //and j is the earlier one, the later one can be obtained
                //by substracting current j from i
  until 1<0     //end a block to be repeated
                //condition is always false, so the program will loop in repeat block forever
end.
\$\endgroup\$
1
6 7
8
9 10
12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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