CODEWITHSUNDEEP
language-agnosticcode-golffibonaccirosetta-stone
Claudiu
Claudiu

Reputation: 229341

Fibonacci Code Golf

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

Upvotes: 26

Views: 7949

Answers (30)

Andrea Ambu
Andrea Ambu

Reputation: 39516

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)

Upvotes: 7

mpeters
mpeters

Reputation: 4778

Perl 6 - 22 characters:

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

Upvotes: 14

user1469191
user1469191

Reputation:

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.

Upvotes: 6

user837350
user837350

Reputation:

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.

Upvotes: 1

BradC
BradC

Reputation: 39936

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.

Upvotes: 4

Eelvex
Eelvex

Reputation: 9133

J - 20 characters

First n terms:

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

Upvotes: 1

st0le
st0le

Reputation: 33545

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

Upvotes: 0

Tom H
Tom H

Reputation: 1316

BrainF**k:

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

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

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

Upvotes: 2

Callum Rogers
Callum Rogers

Reputation: 15829

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 :(

Upvotes: 29

C. K. Young
C. K. Young

Reputation: 223003

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.

Upvotes: 33

JUST MY correct OPINION
JUST MY correct OPINION

Reputation: 36107

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

Upvotes: 1

Eric Mickelsen
Eric Mickelsen

Reputation: 10377

Brainfuck, 33 characters:

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

Upvotes: 11

jfs
jfs

Reputation: 414179

@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

Upvotes: 3

Mark Rushakoff
Mark Rushakoff

Reputation: 258148

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 F24).

#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.

Upvotes: 2

Hellion
Hellion

Reputation: 1740

Rexx:

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

Upvotes: 0

Chris Dodd
Chris Dodd

Reputation: 2960

Lucid

f = 1 fby 1 fby f + prev f;

27 characters, including the spaces.

Upvotes: 0

I. J. Kennedy
I. J. Kennedy

Reputation: 25819

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

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

Upvotes: 11

Nican
Nican

Reputation: 7935

Lua - 49 chars

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

Upvotes: 2

Matt Lewis
Matt Lewis

Reputation: 531

Euphoria: 44 characters

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

Keeps on generating until RAM or doubles run out.

Upvotes: 0

Henk
Henk

Reputation: 3233

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

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

Upvotes: 5

Firas Assaad
Firas Assaad

Reputation: 25750

Ruby (30 characters):

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

Upvotes: 3

Francois G
Francois G

Reputation: 11985

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.

Upvotes: 3

leen
leen

Reputation: 9098

F#:

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

44 Chars

Upvotes: 5

Eclipse
Eclipse

Reputation: 45493

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; }

Upvotes: 14

BenAlabaster
BenAlabaster

Reputation: 39836

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) ;
}

Upvotes: 3

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

Language: dc, Char count: 20

Shorter dc solution.

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

Upvotes: 5

Lex
Lex

Reputation: 71

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)}

Upvotes: 1

Steve
Steve

Reputation: 6460

Delphi Prism (Delphi for .net)

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

49 chars

Upvotes: 1

Paulius
Paulius

Reputation: 5870

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

Upvotes: 6

Adam Rosenfield
Adam Rosenfield

Reputation: 400224

33 characters in C:

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

Upvotes: 1

Related Questions