115
\$\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\$

239 Answers 239

1
\$\begingroup\$

VBA, 28 Bytes

Anonymous VBE immediate window function that takes no input and infinitely outputs the n-th term of the Fibonacci Sequence while iterating n

i=1:Do:k=i+j:i=j:j=k:?j:Loop
\$\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\$

Pyt, 1 byte

Get the nth Fibonacci number:

Explanation:

           Implicit input
 Ḟ         Return (input)-th Fibonacci number

Try it online!

Pyt, 7 bytes

Get an infinite list of Fibonacci numbers:

0`ĐḞƤ⁺ł

Explanation:

0           Push 0 [this is the counter]
 `    ł     While the counter is not zero (checked at 'ł')
  Đ         Duplicate the counter
   ḞƤ       Print the (counter)-th Fibonacci number
     ⁺      Increment the counter

Try it online!

\$\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\$

Japt, 3 bytes

Just to add to the collection.

0-indexed, using 0 as the first number in the sequence.

MgU

Try it

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

><>, 11 bytes

10r:n:@+aor

Try it online!

Prints the Fibonacci sequence forever, separated by newlines.

\$\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\$

R16K1S60 Assembly, 36 bytes

mov bx, ip
mov ax, ip
mov sp, data
jmp inner
prg:
mov cx, [sp+ax]
mov [sp+bx], cx
inner:
mov ex, [sp]
mov dx, [sp+bx]
mov [sp], dx
add ex, dx
mov [sp+ax], ex
send ax, ex
jmp prg

data:
dw 0x0000
dw 0x0001

Pretty simple. Abuses 7 registers, including the instruction pointer (for some predefines)

To note why I used the IP instead of a constant, it's because the R16K1S60 has to use an extra word (two bytes) to encode a constant into an instruction.

Alongside that, I used ax and bx instead of ex and dx for the offset because ex and dx cannot be referenced in only 3 bits (the size of the offset section of instructions that support it)

Outputs the number as a word on port 2

\$\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\$

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\$

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
\$\begingroup\$

Rust, 100 characters

|n|{let mut a=1u64;let mut b=1u64;let mut s=vec![a,b];for _ in 0..n {let t=b;b=a+b;a=t;s.push(b);}s}

A closure that takes an integer n as input and returns a vector of the first n items of the Fibonacci sequence.

\$\endgroup\$
  • \$\begingroup\$ You could shave off a few bytes given the fact that you don't have to return all the Fibonacci numbers, just the nth one. \$\endgroup\$ – Loovjo Sep 23 '18 at 15:06
1
\$\begingroup\$

Prolog, 36 35 29 bytes

X+Y:-writeln(X),Z is X+Y,Y+Z.

Run with 1+1. (I don't think having to call the base case is cheating, but let me know.)

Prints the first parameter and a newline, sets Z to X+Y, then does a recursive call.

Edit 1: Can use writeln(X) instead of write(X),nl, saving one character.

Edit 2: Can use X+Y as a predicate instead of f(X,Y), saving 6 characters. Also the initial call is shorter.

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! The usual consensus is to include the function invocation if it needs to be called with special arguments. \$\endgroup\$ – Laikoni Nov 4 '18 at 10:46
  • \$\begingroup\$ Should I include the call in the character count? \$\endgroup\$ – Alex Trotta Nov 4 '18 at 16:54
1
\$\begingroup\$

Pip, 10 9 bytes

(The language is newer than the question.)

W1o:y+YPo

Outputs infinite Fibonacci numbers on separate lines, beginning with 1. Try it online!

Explanation

The easy part is W1, which uses 1 as an always-truthy condition to create an infinite while loop.

We use two built-in variables, o and y, which are initially 1 and "", respectively. Note that an empty string in arithmetic contexts is treated as 0. At each iteration, y will hold the smaller of two consecutive Fibonacci numbers, and o will hold the larger.

The loop body is a single expression: o:y+YPo. It's important to know that Pip evaluates a binary-operator expression by first evaluating the left operand, then the right operand, then performing the operation. So, using the third iteration as an example (y is 1, o is 2):

  • The left operand of : (the assignment operator) is o; we'll compute y+YPo and then assign that value to o.
  • The left operand of + is y, which is currently 1.
  • The right operand of + is YPo. YP is a unary operator that takes the value of its operand--here, o, which is 2--prints it, and yanks it into y. So when YPo is evaluated, 2 is printed, y is set to 2, and the expression evaluates to 2.
  • + adds 1 and 2 and gives 3.
  • : assigns 3 to o.

The end result is that 2 is printed, y becomes 2, and o becomes 3. Repeat ad infinitum.

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

Burlesque, 8 bytes

Update: With current WIP one can use 1J2q?+C~.

Shortest way to produce [fib(0)..fib(n)] without trashing the stack (14B):

{0 1q?+#RC!}RS

Explanation

There's the concept of "Continuation" in Burlesque which basically means that you run a function on a stack without destroying the stack. Fibonacci is the perfect example use-case for what these continuations are good for. If you have a program like 1 1 add then this results in a stack of 2 because add destroys the data. If add were not to destroy the data the stack would look like 1 1 2 and if we just do 1 1 add add it would look like 1 1 2 3. So all we need to do to generate a Fibonacci sequence is to call add n-times without popping the arguments. A continuation takes a snapshot of the stack, runs the function, pops the result from the stack, reverts the stack to the snapshot and pushes the result of the function to it. C! is the Burlesque built-in for "run this continuation n-times". However, doing so would trash our stack (which is no problem if you just want to print out Fibonacci numbers). Otherwise we need to use the RS built-in which runs a function in a different stack environment. RS takes a value as an argument, creates an empty stack, pushes that value to it and then runs the given function on that stack and after the function has run it will collect that stack into a list and push that list to the main stack. #R rotates the stack because the stack layout will look like N 0 1 but we need that N because it's the argument for C! so we rotate the stack. q?+ is just shorthand for {?+} (q wraps the next token into a block).

If you don't care about trashing the stack you just drop the RS:

blsq ) 10 0 1q?+#R!C
0
1
1
2
3
5
8
13
21
34
55
89

Try it online here.

Shortest way to produce fib(n) as a reusable non stack-trashing piece of code I can think of is (17B):

0 1{Jx/?+}#RE!jvv

Older Stuff

There's dozens of ways to do that. These push the fibonacci numbers to the stack:

blsq ) 0 1{#s2.+++}10E!
blsq ) 0 1q?+10C!

However, the snippets above will also trash your stack. Alternatives for that are either:

blsq ) 0 1{Jx/?+}10E!jvv

which just computes the 10th fibonacci number. Also by still using continuations you can let the whole thing run in a seperate stack environment like uhm so:

blsq ) {10}{0 1q?+#RC!}rs
{89 55 34 21 13 8 5 3 2 1 1 0}
blsq ) 10{0 1q?+#RC!}RS
{89 55 34 21 13 8 5 3 2 1 1 0}

Really depends on your needs.

\$\endgroup\$
  • \$\begingroup\$ This is code-golf, so please post the shortest solution you can find with its byte count. \$\endgroup\$ – lirtosiast Oct 22 '15 at 17:20
1
\$\begingroup\$

Python 3, 43 Bytes

a,c=0,0;b=1
while 1:print(a);c=a+b;a=b;b=c
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that Python has a swap statement to avoid having to use an extra variable: a,b=b,a+b. Also, there are plenty of shorter Python answers already posted. \$\endgroup\$ – FlipTack Dec 17 '18 at 20:21
  • \$\begingroup\$ Also, 0 isn't supposed to be included in this challenge. \$\endgroup\$ – Ørjan Johansen Dec 18 '18 at 1:30
1
\$\begingroup\$

Pure, 66 bytes

using system;do(printf"%Zd\n")(f 1L 1L with f a b=a:f b(a+b)&end);

Try it online!

First answer in Pure \o/

Prints until TIO stops it or the heat death of the universe, whatever comes first.

How:

using system;do(printf"%Zd\n")(f 1L 1L with f a b=a:f b(a+b)&end); // Anonymous lambda;
using system;                                                      // Import system functions
             do                                                    // Infinite loop
               (printf"%Zd\n")                                     // Print bigints + linefeed
                              (f 1L 1L                             // Declare f with 2 bigint args
                                                                   // starting with 1
                                       with f a b=                 // with f(a,b) being
                                                  a:f b(a+b)       // a list from a until f(b,(a+b));
                                                            &      // transformed into a stream
                                                                   // to prevent overflowing
                                                             end);
\$\endgroup\$
1
\$\begingroup\$

IBM PC 8087 FPU, 119 113 bytes

This will compute up to Fibonacci n=87 (679891637638612258) using only the Intel 8087 math-coprocessor. Might not be the smallest code, but it will run on an original IBM PC from 1981 (with optional 8087 chip of course).

Very impressive that the PC was capable of 80-bit extended-precision floating point arithmetic in hardware back then!

Try it on DOS!

    MOV  AX, DS:[82H]   ; get two digits from command line
    CMP  BYTE PTR DS:[80H], 2 ; check if only one digit + space?
    JG   A2I            ; if <= 2, use the first two
    JL   DEF_VAL        ; if no input, use default MAX (87)
    XCHG AL, AH         ; else only one digit
    MOV  AL, '0'        ; pad byte with 0
    JMP  A2I
DEF_VAL:
    MOV  AX, '78'       ; default value (endian reversed)
A2I:
    SUB  AX, '00'       ; convert from ASCII
    JZ   DEF_VAL        ; if input is 0, use default value
    XCHG AL, AH         ; endian convert
    AAD                 ; base convert from 10 to binary
    MOV  CX, AX         ; set up loop counter
    FLD1                ; ST(1) = 1
    FLDZ                ; ST  = 0
FIB_LOOP:
    FADD ST(1), ST      ; ST(1) = ST(1) + ST
    FSUBR ST, ST(1)     ; ST = ST(1) - ST
    CALL PRINT_ST       ; print the BCD number
    LOOP FIB_LOOP
EXIT:
    MOV  AH, 4CH        ; exit to DOS
    INT  21H

PRINT_ST PROC
    PUSH CX             ; save CX
    MOV  SI, SP         ; use SI for index of BCD data
    SUB  SP, 10         ; reserve 10 bytes from stack
    FLD  ST             ; push (copy) ST since FBSTP pops stack 
    FBSTP [SI][-10]     ; pop ST into BCD
    SUB  SI, 2          ; skip first byte (sign), and move to next
    MOV  CH, 9          ; 9 bytes
    MOV  CL, 4          ; shift 4 times
    MOV  AH, 2          ; DOS display char function
PB_LOOP:
    MOV  DL, [SI]       ; get byte
    SHR  DL, CL         ; high digit to low nibble
    OR   DL, '0'        ; convert to ASCII
    INT  21H            ; display digit
    MOV  DL, [SI]       ; get byte again
    AND  DL, 0FH        ; mask out high nibble
    OR   DL, '0'        ; convert low digit to ASCII
    INT  21H            ; display digit
    DEC  SI             ; next byte
    DEC  CH             ; more digits?
    JG   PB_LOOP        ; yes, repeat
PB_CRLF:
    MOV  DL, 0DH        ; display newline CRLF
    INT  21H
    MOV  DL, 0AH
    INT  21H
    ADD  SP, 10         ; put stack back the way it was
    POP  CX
    RET
PRINT_ST ENDP

I/O

Takes n-th term as input on the command line, and displays up to that (zero padded to 18 digits). If no number is specified will display up to the max (n=87) that can be handled by the FPU.

A>FIB 10
000000000000000001
000000000000000001
000000000000000002
000000000000000003
000000000000000005
000000000000000008
000000000000000013
000000000000000021
000000000000000034
000000000000000055

A>FIB
000000000000000001
000000000000000001
000000000000000002
000000000000000003
000000000000000005
000000000000000008
000000000000000013
000000000000000021
000000000000000034
000000000000000055
000000000000000089
000000000000000144
000000000000000233
000000000000000377
000000000000000610
000000000000000987
000000000000001597
000000000000002584
000000000000004181
000000000000006765
000000000000010946
000000000000017711
000000000000028657
000000000000046368
000000000000075025
000000000000121393
000000000000196418
000000000000317811
000000000000514229
000000000000832040
000000000001346269
000000000002178309
000000000003524578
000000000005702887
000000000009227465
000000000014930352
000000000024157817
000000000039088169
000000000063245986
000000000102334155
000000000165580141
000000000267914296
000000000433494437
000000000701408733
000000001134903170
000000001836311903
000000002971215073
000000004807526976
000000007778742049
000000012586269025
000000020365011074
000000032951280099
000000053316291173
000000086267571272
000000139583862445
000000225851433717
000000365435296162
000000591286729879
000000956722026041
000001548008755920
000002504730781961
000004052739537881
000006557470319842
000010610209857723
000017167680177565
000027777890035288
000044945570212853
000072723460248141
000117669030460994
000190392490709135
000308061521170129
000498454011879264
000806515533049393
001304969544928657
002111485077978050
003416454622906707
005527939700884757
008944394323791464
014472334024676221
023416728348467685
037889062373143906
061305790721611591
099194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258

Size Notes

As is typical with machine code and simple programs, I/O and data type conversion takes up the large majority of the code. For example, of the 113 byte FIB.COM executable:

  • 59 bytes to display an 8087 register as a decimal number to the screen
  • 31 bytes to handle and sanitize two digits of command line input
  • 18 bytes to calculate Fibonacci number sequence
  • 4 bytes to gracefully exit to DOS (yes, I could maybe get away with a 1 byte RET)
  • 1 byte for a NOP instruction added automatcially by MASM for alignment purposes
\$\endgroup\$
1
\$\begingroup\$

Awk, 35 bytes

BEGIN{for(y=1;z=x+y;y=z)print(x=y)}

Try it online

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

BitCycle, 21 bytes

  1+ ~!
CB0CA~
^ 1  <

Outputs an unending sequence. Use the -u flag to get output in decimal. Try it online!

Note: the current BitCycle interpreter doesn't play very well with infinite output. You have to halt the program (Ctrl-C) before it displays anything. On TIO, letting the program run until the 60-second timeout shows no output, either--you have to click the Run button (or hit Ctrl-Enter) again to halt it.

Explanation

This explanation assumes you're familiar with BitCycle.

Conceptually, we store two numbers at a time, the smaller and the larger. At each step, we output the larger, set the new larger to be the larger plus the smaller, and set the new smaller to be the larger.

We store and output the numbers in unary (using 1 bits), but we also need a separator (0 bit) after each number output. Our approach is to store the separator at the end of each number. When adding two numbers, we discard the separator from the first number added, and keep the separator from the second number added.

In the code, the leftmost C collector holds the smaller number, while the rightmost C collector holds the larger. We're actually going to store everything negated, so the numbers are made of 0 bits and the separators are 1 bits. Thus, the leftmost C initially gets a single 1 (unary zero plus a separator bit) and the rightmost C gets 01 (unary one plus a separator bit).

The C collectors open and dump their contents straight into the B and A collectors.

Next, the A collector opens, holding the larger number. It goes through a couple of dupneg devices, with the following results:

  • A copy goes into the leftmost C collector, becoming the new smaller number.
  • A negated copy goes into the sink ! and is output.
  • A doubly-negated copy goes into the rightmost C collector, but the + ensures that it's only the 0 bits, not the trailing 1 separator.

Finally, the B collector opens and dumps its contents into the rightmost C, adding the former smaller number to the former larger number to create the new larger number. The cycle repeats forever.

Other versions

Here's a modified version (still 21 bytes) that strips the separator off the smaller number (instead of the larger) before adding:

10>v ~!
BA+BA~
^    <

And here's an 18-byte version that starts at 0 instead of 1. (Thanks to Jo King for golfing it down from 21 bytes.) Here, we start with the "smaller" number at 1 and the "larger" number at 0, generating the extended Fibonacci sequence 1,0,1,1,2,3,... (Since the "larger" number is what we output, we don't see the first 1.)

 1+ ~!
CBCA~
^10 <
\$\endgroup\$
1
\$\begingroup\$

Python 3, 37 bytes

lambda p,a=5**.5:round((.5+a/2)**p/a)

Try it online!

Explanation

Fib(n) = Fib(n-1) + Fib(n-2) with Fib(0) = Fib(1) = 1

Using some simplification, this becomes:

Fibonacci Golden Ratio

For n > 0, this becomes

n greater than 0

Where round is a function that rounds to the nearest integer.

lambda p,                              # defines the anonymous function
         a=5**.5:                      # sets a to \sqrt{5}
                 round((.5+a/2)**p/a)  # Runs the function and returns the result
\$\endgroup\$
  • \$\begingroup\$ This loses precision at only n=71, outputting 308061521170130 instead of 308061521170129 \$\endgroup\$ – Jo King Jul 26 at 4:58
1
\$\begingroup\$

BitCycle, 17 16 bytes

~1~ +
AB~/!
^ +/

Try it online!

Outputs the 0 based sequence. This could be 14 bytes:

~1~+
AB~!
^ +/

Try it online!

But it prints an extra 0 in front of the sequence, which takes a couple of bytes to fix...

There's also a 17 byte solution:

v0<
AB~
~ +\
~  !

Try it online!

Which I like because you can switch between 0-based and 1-based just by changing the 0 on the first line to a 1.

For both solutions, the numbers are infinitely output is in unary 1 bits separated by 0 bits. The -u flag converts the unary numbers to decimal instead, but the TIO tends to cut off the outputting section sometimes, and the last number is always truncated too. There's a bit in the footer to prevent this.

Explanation:

Basically, these solutions only use a single pair of collectors and distinguishes between the two numbers by storing one as unary 1 bits and the other as unary 0 bits.

This starts off with 1 being pushed to the collectors to initialise the sequence.

~ ~    Invert the whole stack
AB~    This basically swaps the values of the two numbers
       Also duplicate a copy downwards and rightwards
       Split the stream into zeroes and ones with the plus
!  /!  Print a single 0 as the separator
^ +/   And add a copy of the 1s to the collector
  ~ +
    !  Print a copy of the 1s to the output

This repeats infinitely, basically executing the pseudocode:

a=0
b=1
while 1:
    oldA = a
    b,a = a,b
    print ','
    a += oldA
    print oldA
\$\endgroup\$

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.