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

Answer 1

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

Answer 2

Delphi Prism (Delphi for .net)

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

49 chars

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.