current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 16 down vote favorite

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

share|improve this question
    
No. Mine wants you to support negative numbers too. – Roman Gräf 12 hours ago
5  
I think this is not a dupe. Of the answers on the first page of the existing Fibonacci challenge, only 1 can handle negatives, and all the rest would need to be significantly changed to go backwards too. – xnor 12 hours ago
    
Added some. Feel free to add more. @Flip – Roman Gräf 11 hours ago
    
Read this meta post about formatting test cases: try to avoid fancy tables – FlipTack 11 hours ago
    
and by CSV you mean SSV (semicolon separated values)? – NH. 9 hours ago
up vote 12 down vote

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.

share|improve this answer
1  
(How) Does this also work for negative input? – Roman Gräf 12 hours ago
    
yes, explanation coming... – flawr 12 hours ago
    
is ans(-6) meant to be positive? – FlipTack 12 hours ago
    
@FlipTack Sorry, it might have been because of the index shift. I used 1-based, while the question used 0-based, I fixed it now. – flawr 12 hours ago
up vote 7 down vote

Mathematica, 9 bytes

Fibonacci

Yes, this built-in function supports negative numbers.

share|improve this answer
    
This is almost word-for-word the answer I was coming to post :D – Greg Martin 2 hours ago
up vote 5 down vote

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
share|improve this answer
up vote 3 down vote

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

share|improve this answer
    
I really like your function. I had a suggestion here, but I overlooked a -, so it wouldn't work... – L. Serné 9 hours ago
up vote 3 down vote

Maxima, 3 bytes

 fib

supports positive and negative numbers

share|improve this answer
up vote 2 down vote

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!

share|improve this answer
up vote 1 down vote

JavaScript (ES7) 37 bytes

Uses Binet's Formula.

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

This outputs the nth Fibonacci number +- 0.0000000000000005.

share|improve this answer
    
** requires ES7. – Neil 7 hours ago
    
Oh, thought it was part of ES6, but you're right. Changed it. I also used another version of Binet's Formula for a 1B save. – L. Serné 5 hours ago
    
Now that I think about it, just using 1-p instead of -1/p should have worked for the same saving. – Neil 5 hours ago
up vote 1 down vote

Jolf, 2 bytes

mL

Try it here!

The fibonacci builtin, implemented using the phi formula.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.