Negative Fibonacci Numbers

Question

You probably all know the fibonacci sequence:

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
fibonacci(0)=0
fibonacci(1)=1

Your task is as simple as it could be:

• Given integer N compute fibonacci(n)

but here is the twist:

• Also do negative N

Wait. What?

fibonacci(1)=fibonacci(0)+fibonacci(-1)

so

fibonacci(-1)=1

and

fibonacci(-2)=fibonacci(0)-fibonacci(1)=-1

and so on...

• This is a code-golf so shortest programm in bytes win.
• You may submit a function or a full programm
• N is in [-100,100]

Testcase(s) in CSV:

-9;-8;-7;-6;-5;-4;-3;-2;-1;0;1;2;3;4;5;6;7;8
34;-21;13;-8;5;-3;2;-1;1;0;1;1;2;3;5;8;13;21

Hint:

n<0 and n&1==0:

fibonacci(n)=fibonacci(abs(n))*-1

Answer 1

Mathematica, 9 bytes

Fibonacci

Yes, this built-in function supports negative numbers.

Answer 2

Octave, 20 bytes

 @(n)([1,1;1,0]^n)(2)

Try it online!

Explanation

This makes use of the fact that the fibonacci sequence f(n) can be written as (this should be a matrix vector notation):

Recursively:

[f(n+1)]  = [1  1] * [f(n)  ]
[f(n)  ]    [1  0]   [f(n-1)]

Explicitly:

[f(n+1)]  = [1  1] ^n * [1]
[f(n)  ]    [1  0]      [0]

This means that the top right entry of this matrix to the power of n is the value f(n) we're looking for. Obviously we can also invert this matrix as it has full rank, and the relationship still describes the same recurrence relation. That means it also works for negative inputs.

Answer 3

Maxima, 3 bytes

 fib

supports positive and negative numbers.

Try it (paste) on CESGA - Maxima on line

Answer 4

Python, 43 bytes

g=5**.5/2+.5
lambda n:(g**n-(1-g)**n)/5**.5

A direct formula with the golden ratio g. With f the above function:

for n in range(-10,11):print f(n) 

-55.0
34.0
-21.0
13.0
-8.0
5.0
-3.0
2.0
-1.0
1.0
0.0
1.0
1.0
2.0
3.0
5.0
8.0
13.0
21.0
34.0
55.0

Same length alt, only aliasing the square root of 5:

a=5**.5
lambda n:((a+1)**n-(1-a)**n)/a/2**n

I didn't see a way to make a recursive function that could compete with these. A mildly-golfed attempt for 57 bytes:

f=lambda n:n<0and(-1)**n*f(-n)or n>1and f(n-1)+f(n-2)or n

For comparison, an iterative method (60 bytes in Python 2):

n=input()
a,b=0,1;exec"a,b=b,a+b;"*n+"a,b=b-a,a;"*-n
print a

Or, for 58 bytes:

n=input()
a,b=0,1;exec"a,b=b,a+cmp(n,0)*b;"*abs(n)
print a

Answer 5

JavaScript (ES6), 42 bytes

f=n=>n<2?n<0?f(n+2)-f(n+1):n:f(n-2)+f(n-1)

Test

f=n=>n<2?n<0?f(n+2)-f(n+1):n:f(n-2)+f(n-1)

for(i = -9; i < 9; i++) {
  console.log(i, f(i))
}

Answer 6

MATL, 11 9 bytes

I'm happy about the [3,2], which surely could be golfed, if anyone knows a way please let me know=) (It would also work with [1,3].) Thanks @LuisMendo for -2 bytes=)

IHhBiY^2)

This is using the same approach as the Octave annswer. But to generate the matrix

[1,1]
[1,0]

we just conver the number 3 and 2 from decimal to binary (i.e. 11 and 10).

Try it online!

Answer 7

JavaScript (ES7) 37 bytes

Uses Binet's Formula.

n=>((1+(a=5**.5))**n-(1-a)**n)/a/2**n

This outputs the n^th Fibonacci number +- 0.0000000000000005.

Answer 8

Jolf, 2 bytes

mL

Try it here!

The fibonacci builtin, implemented using the phi formula.

Answer 9

Haskell, 51 bytes

s=0:scanl(+)1s;f z|even z,z<0= -f(-z);f z=s!!abs z

Answer 10

Lithp, 88 bytes

#N::((if(< N 2)((if(< N 0)((-(f(+ N 2))(f(+ N 1))))((+ N))))((+(f(- N 2))(f(- N 1))))))

My look at all those parentheses.

Try it online!

Not very small really. There's currently a parsing bug that requires one to use (get N) or (+ N) instead of simply N. I chose the smaller one. However I don't think there's anything that can be done further to golf this.

Answer 11

PowerShell, 112 Bytes

function f($n){$o=('-','+')[$n-lt0];&(({$a,$b=(2,1|%{f("$n$o$_"|iex)});"$a- $o$b"|iex},{$n*$n})[$n-in(-1..1)])}

Demo Call:

-9..9 | %{"{0,2}`t=> {1,3}" -f $_,(f($_))} 

Output of Demo:

-9  =>  34
-8  => -21
-7  =>  13
-6  =>  -8
-5  =>   5
-4  =>  -3
-3  =>   2
-2  =>  -1
-1  =>   1
 0  =>   0
 1  =>   1
 2  =>   1
 3  =>   2
 4  =>   3
 5  =>   5
 6  =>   8
 7  =>  13
 8  =>  21
 9  =>  34