Code Chess: Fibonacci Sequence [closed]

Question

Building upon the proven success of Code Golf, I would like to introduce Code Chess.

Unlike Code Golf, which strives for concision, Code Chess will strive for cleverness.

Can you create a clever or unexpected Fibonacci generator?

Your code must print or return either the n^th Fibonacci number or the first n Fibonacci numbers.

Answer 1

OpenOffice Calc / MS Excel

A1: 1 A2: 1 A3: =A1 + A2:

Grab handle of A3

And fill down

Answer 2

int i = 0;
while(true)
{
  Console.WriteLine(i);
  Console.WriteLine(i);
  i = i + 1;
}

It should print the "first n Fibonacci numbers" (and some numbers more :-) ).

Answer 3

Maybe I read too literally?

std::string Fibonacci(unsigned n)
{
   return "either the nth Fibonacci number or the first n Fibonacci numbers.";
}

Answer 4

Regular expression

(I can't take credit for this thing of beauty - see source: perlmonks)

perl -le'$n=shift;$==0,(1x$_)=~/^(1|11(??{}))*$(?{$=++})^/,print$=for 0..$n-1' 7

Output:

1
1
2
3
5
8
13

Answer 5

Brainf*ck

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

Hex dump of output:

0101020305080d1522375990e97962db3d18556dc22ff12011314273b528dd05e2e7c9b07929a2cb
6d38a5dd825fe140216182e36548adf5a29739d009d9e2bb9d58f54d428fd1603191c25315687de5
6247a9f0998922abcd7845bd02bfc18041c102c3c5884dd522f719102939629bfd98952dc2efb1a0
51f1423375a81dc5e2a78930b9e9a28b2db8e59d821fa1c0612182a325c8edb5a257f9504999e27b
5dd8350d424f91e07151c213d5e8bda562076970d949226b8df8857d027f

The first n fibonacci numbers modulo 256, where n = 190.

Answer 6

C#

Who said constructors cannot be recursive?

struct FibonacciNumber {
    const int InitialValue = 1;

    public FibonacciNumber(int index) : this(index == 0 ? new FibonacciNumber() : new FibonacciNumber(index - 1)) { }
    public FibonacciNumber(FibonacciNumber previous) : this(previous.Current, previous.previous + previous.Current) { }
    FibonacciNumber(long previous, long current) { this.previous = previous; this.current = current - InitialValue; }

    readonly long previous;
    long current;
    public long Current { get { return current + InitialValue; } }

    public override string ToString() { return Current.ToString(); }
}

Answer 7

#!/usr/bin/env python3.1

from urllib.request import urlopen

print ("Please enter which Fibonacci number you wish to compute:", end=" ")
n = int(input())

seq = "A000045"

url = "http://www.research.att.com/~njas/sequences/?q=id%3a" + seq + "&p=1&n=10&fmt=3"
resp = urlopen(url)

values = []

for line in resp:
    if line[:2] in [b'%S', b'%T', b'%U']:
        numbers = line.split(b' ')[-1].split(b',')
        values += [int(val) for val in numbers if val != b'\n']


ordinal = "th"
if (1 <= n%10 <= 3) and not (11 <= n%100 <= 13):
    ordinal = ["st", "nd", "rd"][(n-1)%10]
ordinal = str(n)+ordinal

if n < len(values):
    print ("The", ordinal, "Fibonacci number is", values[n])
else:
    print ("The Internet is incapable of computing the", ordinal, "Fibonacci number yet, please come back later.")       

---

OK, the normal version:

import math

def fib(n):
   sqrt5 = math.sqrt(5)
   return int(round(((sqrt5+1)/2)**n / sqrt5))

Answer 8

Not clever, just have some fun :).

To run:

gcc the_file.c -DN=7
./a.out

Requires gcc and support for POSIX's printf positional specifier support.

---

#include<stdio.h>
int main() {
    int n = N;
    if (n >= 2) {
        int r, t;
        char x[34],*s =
        "#include<stdio.h>%2$c"
        "int main() {"
            "int n = N;"
            "if (n >= 2) {"
                "int r, t;"
                "char x[34],*s = %3$c%1$s%3$c;"
                "sprintf(x, %3$cgcc -DN=%%d -x c -%3$c, n-1);"
                "FILE* f = popen(x, %3$cw%3$c);fprintf(f,s,s,10,34);pclose(f);"
                "f = popen(%3$c./a.out%3$c, %3$cr%3$c);fscanf(f,%3$c%%d%3$c, &r);pclose(f);"
                "sprintf(x, %3$cgcc -DN=%%d -x c -%3$c, n-2);"
                "f = popen(x, %3$cw%3$c);fprintf(f,s,s,10,34);pclose(f);"
                "f = popen(%3$c./a.out%3$c, %3$cr%3$c);fscanf(f,%3$c%%d%3$c, &t);pclose(f);"
                "n = r+t;"
            "}"
            "printf(%3$c%%d%3$c, n);puts(%3$c%3$c);"
            "return 0;"
        "}";
        sprintf(x, "gcc -DN=%d -x c -", n-1);
        FILE* f = popen(x, "w");fprintf(f,s,s,10,34);pclose(f);
        f = popen("./a.out", "r");fscanf(f,"%d", &r);pclose(f);
        sprintf(x, "gcc -DN=%d -x c -", n-2);
        f = popen(x, "w");fprintf(f,s,s,10,34);pclose(f);
        f = popen("./a.out", "r");fscanf(f,"%d", &t);pclose(f);
        n = r+t;
    }
    printf("%d", n);puts("");
    return 0;
}

Answer 9

I once did this in Word field codes, but I'm not sure how to post it. (Ctrl+C will not copy Word field codes)

EDIT: Here's a screenshot:

Once it gets past 1023341553, Word crashes.

EDIT: I uploaded the original document.

Answer 10

C++ Template Language

Nth Fibonacci number calculated at compilation time:

template<int N> struct Fib {
  static const int result = Fib<N-1>::result + Fib<N-2>::result;
};

template<> struct Fib<0> {
  static const int result = 0;
};

template<> struct Fib<1> {
  static const int result = 1;
};

#include <iostream>
int main(void){
  std::cout << "Fib(10) = " << Fib<10>::result << std::endl;
  return 0;
}

Answer 11

Using Binet's formula (though not the original version rather a slightly altered one) you can calculate the nth fibonacci number directly - no recursion, no iteration:

PHI = (1 + 5**0.5) / 2 # golden ratio

def F(n):
    return int(PHI**n / 5**0.5)

Important to note that due to Loss of Significance you can't calculate really large numbers (dependent on floating point implementation).

Answer 12

int Fib(int n)
{
   if(n > 46)
      throw new ArgumentOutOfRangeException("n");
   if(n == 46)
      return 1836311903;
   else if(n == 45) 
      return 1134903170;
   else
      return Fib(n + 2) - Fib(n + 1);
}

This will probably blow your stack.

Fibonacci numbers n > 46 will overflow a 32 bit int.

Answer 13

C#

Just one statement!

Enumerable.Repeat(new List<long>(32){ 1, 1 }, 1)
    .First(fib => Enumerable.Range(0, 32).Aggregate(true, (u1, u2) => { fib.Add(fib.Last() + fib[fib.Count - 2]); return true; }))

Answer 14

AntiChess: Windows cmd

This is probably the slowest, least elegant, most resource intensive of the answers. It works for 0 to full disk.

type fibo.cmd

@echo off
type nul>a
if "%1"=="0" goto :done
type nul>b
<nul (set/p z=1) >a
<nul (set/p z=1) >i
:loop
copy /b a c >nul
copy /b b+c a >nul
copy /b c b >nul
<nul (set/p z=1) >>i
call :size i
if /i %s% LSS %1 goto loop
:done
call :size a
echo The %1th Fibonacci number is %s%
del a
if exist b del b
if exist c del c
if exist i del i
:size
set s=%~z1

C:\fibo>fibo 20
The 20th Fibonacci number is 6765

Yes, I know SET /A:

@set a=1&set b=0&for /l %%i in (2,1,%1)do @set/ac=a&set/aa=b+c&set/ab=c
@echo %a%

Answer 15

dc in stack

?k1d[sBdlBrlB+zK>L]dsLxf

Instead of printing the numbers as they are calculated, it adds them in order to the stack and dumps the whole stack at the end.

dc uses bignum arithmetic. I tested with 10,000 numbers. The 10,000th number is 2,090 digits long.

Works for n > 2.

And it's only 24 chars long.

dc -f fibo.dc
15
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1

Answer 16

Here is one in C# which uses the fact that 5f^2 +- 4 is a perfect square if and only if f is a fibonacci number. This one prints a list of fibonacci numbers in sequence.

void PrintFib(int n) {
    if (n < 1) return;

    Dictionary<int, int> squares = new Dictionary<int, int>();

    int count = 1;
    Console.WriteLine("1");

    int i = 1;
    while (count < n) {
        int sqr = i * i;

        int x = -1;

        if ((sqr - 4) % 5 == 0) {
            x = (sqr - 4) / 5;
        }

        if ((sqr + 4) % 5 == 0) {
            x = (sqr + 4) / 5;
        }

        if (squares.ContainsKey(x)) {
            Console.WriteLine(squares[x]);
            count++;
        }

        squares[sqr] = i;
        i++;
    }

Answer 17

As in the fibonacci code golf, i would like to suggest some examples from the haskell webpage.

One from the link above:

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

one with nice code:

fibs = scanl (+) 0 (1:fibs)
fibs = 0 : scanl (+) 1 fibs

and one with good old math:

fib n = round $ phi ** fromIntegral n / sq5
  where
    sq5 = sqrt 5 :: Double
    phi = (1 + sq5) / 2

Answer 18

In assembler, wrapped into a C/C++ function (compiled with DevStudio 2005):

int Fibonacci (int i)
{
  __asm
  {
    mov eax,0
    mov ebx,1
    mov ecx,i
l1: add eax,ebx
    xchg eax,ebx
    loop l1
  }
}

Answer 19

Now you procedural code monkeys have finished at your typewriters... time for some Shakespeare (no, not the language based on keywords like "codpiece")

It's a recursive set based operation

DECLARE @Limit int

SELECT @Limit = 10

;WITH cFoo AS
(
    SELECT 0 as n, CAST(0 as bigint) AS x, CAST(1 as bigint) AS y
    UNION ALL
    SELECT n+1, y, x + y FROM cFoo WHERE n+1 < @Limit
)
SELECT
    cFoo.x
FROM
    cFoo
OPTION (MAXRECURSION 0)

Edit: SQL Server 2005+. It can be done in other dialects too

Answer 20

Shortest C# solution so far

Enumerable.Range(0, n).Aggregate(new { a = 1, b = 0 },
    (a, b) => new { a = a.b, b = a.a + a.b }).b;

I know this is not code golf. I thought it was clever nonetheless :)

Answer 21

public class FibonacciSequence : IEnumerable<ulong>
{

    public IEnumerator<ulong> GetEnumerator()
    {
        yield return 0;
        yield return 1;
        ulong a = 0;
        ulong b = 0;
        ulong c = 1;
        checked
        {
            while (true)
            {
                a = b;
                b = c;
                try
                {
                    c = a + b;
                }
                catch (OverflowException)
                {
                    yield break;
                }
                yield return c;
            }
        }
    }

    System.Collections.IEnumerator 
         System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Answer 22

This my favorite solution:

private readonly static double rootOfFive = Math.Sqrt(5); 
private readonly static double goldenRatio = (1 + rootOfFive) / 2; 

internal static int GetFinbonacciValue(int number) 
{ 
    return Convert.ToInt32((Math.Pow(goldenRatio, number) - Math.Pow(-goldenRatio, -number)) / rootOfFive); 
}

Answer 23

A less common way to calculate Fibonacci numbers:

def fib(n):
   i = j = 1.0
   for _ in range(n):
      j *= i
      i = 1 / i + 1
   return int(j)

Answer 24

PHP

<?php
$cache = array(0, 1, 1);
function fib($n) {
    global $cache;

    return (isset($cache[$n])) ? $cache[$n] : ($cache[$n] = fib($n - 2) + fib($n - 1));
}
?>

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

Answer 25

Here's one that uses memoization (a common functional technique) to recursively calculate and cache intermediate values. It uses lambdas and higher order functions to generate the Nth number in the sequence. When you do something like Fib(50) this can make a big difference:

    static long Fib(long number)
    {
        Func<long,long> fib=null;

        fib=Memorize<long,long>(value=>
        {
            if(value==0) return 0;
            if(value==1) return 1;

            return fib(value-1)+fib(value-2);
        });

        return fib(number);
    }

    static Func<T,R> Memorize<T,R>(Func<T,R> lookup)
    {
        Dictionary<T,R> cache=new Dictionary<T,R>();

        Func<T,R> memo=value=>
        {
            R result;
            if(cache.TryGetValue(value,out result)==false)
            {
                result=lookup(value);
                cache.Add(value,result);
            }

            return result;
        };

        return memo;
    }

Answer 26

Here is another one in C# using the fact that

f(2n) = (2f(n-1) + f(n))* f(n)

f(2n-1) = f(n)^2 + f(n-1)^2.

Gives an O(logn) time algo to find just the nth fibonacci number (and some extra as a side effect), just like the matrix version.

// Computes fib(n) and fib(n-1).
void FibPair(int n, out int Fn, out int Fn_minus_1) {
    Fn = 1;
    Fn_minus_1 = 1;
    if (n <= 2) return;

    int f_n, f_n1;

    if ((n % 2) == 0) {

        FibPair(n / 2, out f_n, out f_n1);
        Fn = (2 * f_n1 + f_n) * f_n;
        Fn_minus_1 = f_n * f_n + f_n1 * f_n1;
        return;
    }

    FibPair((n + 1) / 2, out f_n, out f_n1);

    Fn = f_n * f_n + f_n1 * f_n1;
    Fn_minus_1 = (2 * f_n - f_n1)*f_n1;
}

Answer 27

go:

package main

import fmt "fmt"

func halfFib(co, out chan int) {
    a := 0
    for {
        a += <-co
        out <- a
        co <- a
    }
}

func main() {
    co := make(chan int)
    out := make(chan int)
    go halfFib(co, out)
    go halfFib(co, out)
    co <- 1
    n := <-out
    for n > 0 {
        fmt.Println(n)
        n = <-out
    }
}

Answer 28

IPython, O(log n) with exact bigint results (by matrix powers), lambda-style. Who said python ought to be readable?

In [1]: mult = lambda ((a,b),(c,d)),((e,f),(g,h)):((a*e+b*g, a*f+b*h), (c*e+d*g, c*f+d*h))

In [2]: power = lambda m,n:(m) if (n==1) else (power(mult(m,m), n/2) if (n%2==0) else mult(power(mult(m,m), n/2), m))

In [3]: map(lambda n:power(((0,1),(1,1)), n), xrange(1,10))
Out[3]: 
[((0, 1), (1, 1)),
 ((1, 1), (1, 2)),
 ((1, 2), (2, 3)),
 ((2, 3), (3, 5)),
 ((3, 5), (5, 8)),
 ((5, 8), (8, 13)),
 ((8, 13), (13, 21)),
 ((13, 21), (21, 34)),
 ((21, 34), (34, 55))]

Answer 29

Python generator:

def fibonacci():
    n, m = 0, 1
    while True:
        yield n
        n, m = m, n + m

Called n times.

Answer 30

In F#, using an infinite tail-recursive sequence.

let fibseq =    
    let rec fibseq n1 n2 = 
        seq { let n0 = n1 + n2 
              yield n0
              yield! fibseq n0 n1 }
    seq { yield 1I ; yield 1I ; yield! (fibseq 1I 1I) }

let fibTake n = fibseq |> Seq.take n //the first n Fibonacci numbers
let fib n = fibseq |> Seq.nth (n-1) //the nth Fibonacci number