Fibonacci Code Golf

Question

Generate the Fibonacci sequence in the fewest amount of characters possible. Any language is OK, except for one that you define with one operator, f, which prints the Fibonacci numbers.

Starting point: 25 14 characters in Haskell:

f=0:1:zipWith(+)f(tail f)

f=0:scanl(+)1f

Criollo

I can't think of a single course where you'd start with 25 characters of Haskell and be asked to reduce it in any language you choose. – Criollo

Do languages such as Mathematica with a built-in Fibobnacci function count? – Millen

@adam - good question.. you should put it in, but people might be unhappy with it =P. then again, we're all using built-in list operations and such.. tough where to draw the line. – Criollo

"The smallest number of characters" has nothing to do with programming excellence. The read-/understand-ability of the answers is witness. – Resonance

so... The smallest numbers of chars is the winner of this thread? I thought it was about the 'witty' implementations in different languages... – Compatriot

Answer 1

RePeNt, 9, 8 chars

1↓[2?+1]

Or 10 chars with printing:

1↓[2?+↓£1]

Run using:

RePeNt "1↓[2?+1]"

RePeNt is a stack based toy language I wrote (and am still improving) in which all operators/functions/blocks/loops use Reverse Polish Notation (RPN).

Command      Explanation                                              Stack
-------      -----------                                              -----

1            Push a 1 onto the stack                                  1
↓            Push last stack value                                    1 1
[            Start a do-while loop                                    1 1
2?           Push a two, then pop the 2 and copy the last 2 stack     1 1 1 1
             items onto the stack
+            Add on the stack                                         1 1 2
↓£           Push last stack value then print it                      1 1 2
1            Push a 1 onto the stack                                  1 1 2 1
]            Pop value (1 in this case), if it is a 0 exit the loop   1 1 2
             otherwise go back to the loop start.

The answer is on the stack which builds itself up like:

1 1
1 1 2
1 1 2 3
1 1 2 3 5

It never terminates (it has the eqivilent of a C#/JAVA do { } while(true) loop) because the sequence will never terminate, but a terminating solution can be written thus:

N_1↓nI{2?+}

which is 12 chars.

I wonder if anyone will ever read this :(

Sophisticate

"I wonder if anyone will ever read this": I do have a tendency to skip programming languages with operators I can't easily type on a keyboard. (Which means I never pay attention very far when reading about APL.) Clever little language though ;) – Henceforth

I know the pain, I'm thinking about adapting it to use characters for the operators and leaving some special ones for variables. – Sophisticate

currently I use on my GNU/Linux machine ibus, among listed input methods there's rfc 1345, that I keep always "at hand". I think modern systems shouldnt be scared by many special symbols, and I'm starting to appreciate languages that exploit more than ASCII... – Felike

Answer 2

18 characters of English..

"Fibonacci Sequence"

ok, I fail. :)

Futile

@dbr: or remove 11 characters - "fib seq" – Levasseur

@dbr or remove it all and it will give the same programming result :D – Yod

Answer 3

13 chars of Golfscript:

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

---

Update to explain the operation of the script:

1. 2, makes an array of [0 1]
2. ~ puts that array on the stack
3. So, at the time we run the do, we start the stack off with 0 1 (1 at top of stack)

The do loop:

1. Each . duplicates the top item of the stack; here, we do this twice (leaving us with 0 1 1 1 on initial run)
2. p prints the topmost value (leaving us with 0 1 1)
3. @ rotates the top 3 items in the stack, so that the third-topmost is at the top (1 1 0)
4. + adds the top 2 items in the stack (leaving 1 1)
5. . duplicates the top value, so that the do loop can check its truthiness (to determine whether to continue)

Tracing this mentally a couple of loops will be enough to tell you that this does the required addition to generate the Fibonacci sequence values.

Since GolfScript has bignums, there will never be an integer overflow, and so the top-of-stack value at the end of the do loop will never be 0. Thus, the script will run forever.

Femineity

That's the value of using the right tool for the right problem. Abd then... is the problem really relevant? – Earpiece

You wanna talk about "right tool"? See the winning entry for stackoverflow.com/questions/62188 :-) – Femineity

What does it even do? I bet no one looks at my answer. – Sophisticate

@Callum: Unlike your answer (which I now did look at), mine actually prints the numbers (even if the program runs endlessly). :-P I'll update the post to say what the script does. – Femineity

Thanks for explaining what it does - it seems our solutions are very similar. I added printing, but I still consider that you won (I am a year late :) – Sophisticate

Answer 4

Language: C++ Compiler Errors
Characters: 205

#define t template <int n> struct 
#define u template <> struct f
t g { int v[0]; };
t f { enum { v = f<n-1>::v + f<n-2>::v }; g<v> x;};
u<1> { enum { v = 1 }; };
u<0> { enum { v = 0 }; };
int main() { f<10> x; }

Enchilada

Answer 5

Perl 6 - 22 characters:

sub f{1,1...{$^a+$^b}}

Woolcott

Answer 6

Brainfuck, 33 characters:

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

Syl

Answer 7

x86 (C-callable) realmode, 14 bytes.
Input is  n  on stack, returns  F_n  in AX.

59 31 C0 E3 08 89 C3 40 93 01 D8 E2 FB C3

Doubledecker

Answer 8

22 characters with dc:

1[pdd5**v1++2/lxx]dsxx

Invoke with either:

dc -e'1[pdd5**v1++2/lxx]dsxx'

Or:

echo '1[pdd5**v1++2/lxx]dsxx' | dc

Note: not my work, poached from perlmonks.

Staging

Answer 9

J, 27 characters for a non-recursive function:

f=:3 :'{:}.@(,+/)^:y(0 1x)'

+/ sums over a list.
(,+/) appends the sum of a list to its tail.
}.@(,+/) sums a list, appends an element to its tail, and drops the first element.
}.@(,+/)^:y iterates the above function y times.
}.@(,+/)^:y(0 1x) applies the above function to the list (0,1) (the x makes it an integer).
{:}.@(,+/)^:y(0 1x) takes the last element of the output list of the above.
f=:3 :'{:}.@(,+/)^:y(0 1x)' defines f to be a function on one variable y.

Bremble

how does "f=:3 :'______'" define a function to be of one variable y? Where does the :3 come from? ahh! (head exploding). – Criollo

Heh, J is quite interesting, isn't it? All functions are unary (taking implicit 'y' argument) or binary (taking implicit 'x' an 'y') or both (well, in J terms, all verbs can be used as monads or dyads). "3 :" introduces the definition of a monadic verb. – Bremble

Answer 10

For the record:

• Lua (66 chars): function f(n)if n<2 then return n else return f(n-1)+f(n-2)end end
• JavaScript (41 chars): function f(n){return n<2?n:f(n-1)+f(n-2)}
• Java (41 chars): int f(int n){return n<2?n:f(n-1)+f(n-2);}

I am not much adept of super concise languages... :-P

Chris is right, I just took the simple, recursive algorithm. Actually, the linear one is even shorter in Lua (thanks to multiple assignment)! JavaScript isn't so lucky and Java is worse, having to declare vars...

• Lua (60 chars): function f(n)a=1;b=0;for i=1,n do a,b=b,a+b end return b end
• JavaScript (60 chars): function f(n){a=1;b=i=0;for(;i++<n;){x=a+b;a=b;b=x}return b}
• Java (71 chars): int f(int n){int a=1,b=0,i=0;for(;i++<n;){int x=a+b;a=b;b=x;}return b;}

I would write Lua's code with local a,b=1,0 but it is longer, so let's pollute _G! ;-) Idem for JS.

For completeness, here are the terminal recursive versions. Lua's one, using tail call, is as fast as the linear one (but 69 chars, it is the longest!) - need to call them with three params, n,1,0.

• Lua (69 char, longer!): function f(n,a,b)if n<1 then return b else return f(n-1,b,a+b)end end
• JavaScript (44 chars): function f(n,a,b){return n<1?b:f(n-1,b,a+b)}
• Java (52 chars): int f(int n,int a,int b){return n<1?b:f(n-1,b,a+b);}

Westnorthwest

I bet you my Golfscript implementation is faster than any of yours, for large N. Not because Golfscript is fast (it's quite slow, in fact), but because my solution doesn't do recursion. :-P – Femineity

You are right, and it is even shorter for Lua! Java[Script]'s recursive versions are "better" for the challenge of conciseness... – Westnorthwest

lua: function f(n)return n<2 and n or f(n-1)+f(n-2) end (50 characters) – Tahoe

Answer 11

Corrected after comments (thanks Sebastian), it wasn't a sequence solution, so here we go with 42 chars (includes the \n):

def f(a=0,b=1):
 while 1:yield a;a,b=b,a+b

---

OLD post below

Python, 38 chars.

f=lambda n:n if n<2 else f(n-1)+f(n-2)

Not so short but the most readable in my opinion :P

EDIT: Here is the analytic way (if someone needs to see it in python :-)

f=lambda n:int(.5+(.5+5**.5/2)**n/5**.5)

Thiosinamine

Your iterative way is not very suitable for generating the Fibonacci's sequence. See https://mcmap.net/q/512374/-fibonacci-code-golf#250041 – Mention

It's not iterative but analytic – Indomitable

Answer 12

Microsoft Batch - 15 characters

Old challenge, but the world must know it is possible:

%1
%0 %1%2 %1 #

Output is to stderr in unary, counting only the # characters. Depending on the host system's space restrictions, it may produce only the first 14 numbers or so.

Primordium

the world must know indeed! accepted as answer to bring it the glory it deserves – Criollo

@Criollo That may be, but it's still longer than both the RePeNt and GolfScript solutions, so by the rules of golf, you should pick one of those (depending on whether you view RePeNt as a valid language) as the winning solution. (Aren't you also a member of Code Golf SE? You should know this drill by now. :-P) – Femineity

oh very well. repent is as valid a language as golf-script (as far as i can tell) so it takes the cake – Criollo

Answer 13

Windows XP (and later versions) batch script. This batch function when given a single argument - amount, generates amount+1 Fibonacci numbers and returns them as a string (BATCH doesn't really have sets) in variable %r% (369 characters, or 347 characters - if we remove indentation):

:f
    set i=0
    set r=1
    set n=1
    set f=0
    :l
        if %n% GTR %~1 goto e
        set f=%f% %r%
        set /A s=%i%+%r%
        set i=%r%
        set r=%s%
        set /A n+=1
        goto l
    :e
    set r=%f%
    exit /B 0

And here's the complete script, to see it in action (just copy-past it into a CMD or BAT file and run it):

@echo off
call :ff 0
call :ff 1
call :ff 2
call :ff 3
call :ff 5
call :ff 10
call :ff 15
call :ff 20
exit /B 0

:ff
    call :f "%~1"
    echo %~1: %r%
    exit /B 0

:f
    set i=0
    set r=1
    set n=1
    set f=0
    :l
        if %n% GTR %~1 goto e
        set f=%f% %r%
        set /A s=%i%+%r%
        set i=%r%
        set r=%s%
        set /A n+=1
        goto l
    :e
    set r=%f%
    exit /B 0

Compatriot

Answer 14

F#:

(0,1)|>Seq.unfold(fun(a,b)->Some(a,(b,a+b)))

44 Chars

Graner

Answer 15

Here's my best using scheme, in 45 characters:

(let f((a 0)(b 1))(printf"~a,"b)(f b(+ a b)))

Coralloid

Answer 16

Language: dc, Char count: 20

Shorter dc solution.

dc -e'1df[dsa+plarlbx]dsbx'

Antiquated

What kind of language is this :rolleyes: – Cyst

@Ikke, a very common one: $ whatis dc dc (1) - an arbitrary precision calculator – Henceforth

Answer 17

MS Excel: 11 characters:

=SUM(A1:A2)

Type 1 in the top 2 cells, then put the above formula in cell A3. Copy the formula down the spreadsheet.

Starts losing accuracy due to floating point rounding on row 74.
Exceeds 10^307 and overflows to a #NUM! error on row 1477.

Sjambok

Isn't the act of copying the formula down the spreadsheet a case of manual stack unwinding? – Acrobatics

Answer 18

let rec f l a b =function 0->a::l|1->b::l|n->f (a::l) b (a+b) (n-1) in f [] 1 1;;

80 characters, but truly generates the sequence, in linear time.

Coady

Answer 19

C#

I'm seeing a lot of answers that don't actually generate the sequence, but instead give you only the fibonacci number at position *n using recursion, which when looped to generate the sequence gets increasingly slower at higher values of n.

using System;
static void Main()
{
  var x = Math.Sqrt(5);
  for (int n = 0; n < 10; n++)
    Console.WriteLine((Math.Pow((1 + x) / 2, n) - Math.Pow((1 - x) / 2, n)) / p) ;
}

Galla

Answer 20

@Andrea Ambu

An iterative pythonic fibonacci()'s version should look something like that:

def fibonacci(a=0, b=1):
    while True:
        yield b
        a, b = b, a+b

Spectacles

Answer 21

Ruby (30 characters):

def f(n)n<2?n:f(n-1)+f(n-2)end

Soupy

Answer 22

Generate the Fibonacci sequence. sequence SEQUENCE!

Stoicism

Answer 23

BrainF**k:

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

That'll generate the first 5. To generate more, replace the 5 + at the beginning with more: eg:

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

Okun

Use that iwriteiam.nl/Ha_bf_online.html there with the CN-execute button. – Okun

Answer 24

Befunge-93

31 chars

Will output an infinite list of the Fibonacci numbers, from 0 upwards, separated by tabs (could be reduced to 29 chars by deleting 9, in the first row, at the expense of no whitespace between numbers).

Unfortunately, all the Befunge-93 interpreters I've tried seem to overflow after 65k, so the output is only correct until and including 46368 (which is F₂₄).

#v::1p1>01g:.\:01p+9,#
 >     ^

Confirmed to work (with caveat above) with the Befunge-93 interpreter in Javascript and the Visual Befunge Applet Full.

I'm proud to say this is a completely original work (i.e. I did not copy this code from anyone), and it's much shorter than the Befunge solution currently on Rosetta Code.

Anechoic

Answer 25

Lua - 49 chars

function f(n)return n<2 and n or f(n-1)+f(n-2)end

Douglasdouglashome

Answer 26

Very old post but

f(){int cn=2,*n=calloc(9,9);n[1]=1;while(cn<32)printf("%d ",n[cn]=n[cn-1]+n[cn++-2]);} 85char in C.

Hilde

Answer 27

J - 20 characters

First n terms:

(+/@(2&{.),])^:n i.2

Forsta

Answer 28

PDP-11 Assembler (source)

    .globl  start
    .text
start:
    mov $0,(sp)
    mov $27,-(sp)
    jsr pc, lambda
print_r1:
    mov $outbyte,r3
div_loop:
    sxt r0
    div $12,r0
    add $60,r1
    movb    r1,-(r3)
    mov r0,r1
    tst r1
    jne div_loop
    mov $1,r0
    sys 4; outtext; 37
    mov $1,r0
    sys 1
lambda:
    mov 2(sp),r1
    cmp $2,r1
    beq gottwo
    bgt gotone
    sxt r0
    div $2,r0
    tst r1
    beq even
odd:
    mov 2(sp),r1
    dec r1
    sxt r0
    div $2,r0
    mov r0,-(sp)
    jsr pc,lambda
    add $2,sp
    mov r0,r3
    mov r1,r2
    mov r3,r4
    mul r2,r4
    mov r5,r1
    mov r3,r4
    add r2,r4
    mul r2,r4
    add r5,r1
    mul r3,r3
    mov r3,r0
    mul r2,r2
    add r3,r0
    rts pc
even:
    mov 2(sp),r1
    sxt r0
    div $2,r0
    dec r0
    mov r0,-(sp)
    jsr pc,lambda
    add $2,sp
    mov r0,r3
    mov r1,r2
    mov r2,r4
    mul r2,r4
    mov r5,r1
    mov r2,r4
    add r3,r4
    mul r4,r4
    add r5,r1
    mov r2,r4
    add r3,r4
    mul r2,r4
    mov r5,r0
    mul r2,r3
    add r3,r0
    rts pc
gotone:
    mov $1,r0
    mov $1,r1
    rts pc
gottwo:
    mov $1,r0
    mov $2,r1
    rts pc

    .data
outtext:
    .byte 62,63,162,144,40,106,151,142,157,156
    .byte 141,143,143,151,40,156,165,155
    .byte 142,145,162,40,151,163,40
    .byte 60,60,60,60,60
outbyte:
    .byte 12

Ewan

Answer 29

The previous Ruby example won't work w/o either semicolons or newlines, so it's actually 32 chars. Here's the first example to actually output the sequence, not just return the value of a specified index.

Ruby:
53 chars, including newlines:

def f(n);n<2?1:f(n-1)+f(n-2);end
0.upto 20 {|n|p f n}

or if you want function that outputs a usable data structure, 71 chars:

def f(n);n<2?1:f(n-1)+f(n-2);end
def s(n);(0..n).to_a.map {|n| f(n)};end

or accepting command-line args, 70 chars:

def f(n);n<2?1:f(n-1)+f(n-2);end
p (0..$*[0].to_i).to_a.map {|n| f(n)}

Tarr

Answer 30

Delphi Prism (Delphi for .net)

f:func<int32,int32>:=n->iif(n>1,f(n-1)+f(n-2),n)

49 chars

Iodometry

Answer 31

33 characters in C:

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

Millen

Answer 32

Not the shortest, but the fastest at the time of posting. :-)

float f(float n) {
    return (pow(1+sqrt(5.0))/2.0),n) - pow(1+sqrt(5.0))/2.0),n)/sqrt(n));
}

Grade

I think he means to fix the parentheses and have the second be 1 - sqrt(5.0). This is the fastest for a given n, but it is slower for generating a sequence, and also it won't work for numbers with more than a pretty small amount of digits. – Criollo

Two typos. Sorry, this should work: (pow((1+sqrt(5.0)))/2.0),n) - pow((1-sqrt(5.0)))/2.0),n)/sqrt(n)); – Grade

Ack, sorry Claudiu. Did not read your answer before posting. Claudiu is right, although it's wrong that it is slower for generating a sequence. For a sequence of n it's O(n). Fibonacci's recursion is much higher than that, unless you do not recalculate the results previously calculated. – Grade

If your intent is to generate a sequence, you would not need to recalculate any results -- you'd be saving them, in the sequence. – Bremble

@mstrobl: the haskell in the question, for example, doesn't recalculate previous results, so I think it would indeed be faster since it only performs additions. – Criollo

Answer 33

Java Iterative (73)

void f(int n){for(int a=1,b=1;n-->0;b=a+(a=b)){System.out.print(a+",");}}

Ruby (46)

def f(n);a,b=1,1;1.upto(n){p a;b=a+(a=b);};end

Update: Ruby(42)

def f(n);a=b=1;n.times{p a;b=a+(a=b);};end

Unmarked

Answer 34

Rexx:

arg n;a=1;b=1;do i=1 to n;say a b;a=a+b;b=a+b;end

Niveous

Answer 35

Lucid

f = 1 fby 1 fby f + prev f;

27 characters, including the spaces.

Briseno

Answer 36

Euphoria: 44 characters

object f=1&1 loop do f&=f[$]+f[$-1]until 0

Keeps on generating until RAM or doubles run out.

Fowlkes