31
\$\begingroup\$

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

\$\endgroup\$
6
  • \$\begingroup\$ No. Mine wants you to support negative numbers too. \$\endgroup\$ Dec 31, 2016 at 10:52
  • 8
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Dec 31, 2016 at 11:01
  • \$\begingroup\$ Added some. Feel free to add more. @Flip \$\endgroup\$ Dec 31, 2016 at 12:02
  • 1
    \$\begingroup\$ Read this meta post about formatting test cases: try to avoid fancy tables \$\endgroup\$
    – FlipTack
    Dec 31, 2016 at 12:08
  • \$\begingroup\$ and by CSV you mean SSV (semicolon separated values)? \$\endgroup\$
    – NH.
    Dec 31, 2016 at 13:55

12 Answers 12

23
\$\begingroup\$

Mathematica, 9 bytes

Fibonacci

Yes, this built-in function supports negative numbers.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ This is almost word-for-word the answer I was coming to post :D \$\endgroup\$ Dec 31, 2016 at 20:13
18
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ (How) Does this also work for negative input? \$\endgroup\$ Dec 31, 2016 at 10:57
  • \$\begingroup\$ yes, explanation coming... \$\endgroup\$
    – flawr
    Dec 31, 2016 at 10:57
  • \$\begingroup\$ is ans(-6) meant to be positive? \$\endgroup\$
    – FlipTack
    Dec 31, 2016 at 11:02
  • \$\begingroup\$ @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. \$\endgroup\$
    – flawr
    Dec 31, 2016 at 11:09
13
\$\begingroup\$

Maxima, 3 bytes

 fib

supports positive and negative numbers.

Try it (paste) on CESGA - Maxima on line

\$\endgroup\$
3
  • \$\begingroup\$ Can you add a link to the language? \$\endgroup\$
    – Pavel
    Jan 1, 2017 at 0:38
  • \$\begingroup\$ Of course added a link to an online calculator! \$\endgroup\$
    – rahnema1
    Jan 1, 2017 at 3:49
  • \$\begingroup\$ Also works on WolframAlpha \$\endgroup\$
    – Thunda
    Mar 24, 2017 at 6:58
12
\$\begingroup\$

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
\$\endgroup\$
10
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ I really like your function. I had a suggestion here, but I overlooked a -, so it wouldn't work... \$\endgroup\$
    – Luke
    Dec 31, 2016 at 13:43
6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ ** requires ES7. \$\endgroup\$
    – Neil
    Dec 31, 2016 at 15:39
  • \$\begingroup\$ 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. \$\endgroup\$
    – Luke
    Dec 31, 2016 at 17:30
  • \$\begingroup\$ Now that I think about it, just using 1-p instead of -1/p should have worked for the same saving. \$\endgroup\$
    – Neil
    Dec 31, 2016 at 17:41
5
\$\begingroup\$

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!

\$\endgroup\$
0
4
\$\begingroup\$

Jolf, 2 bytes

mL

Try it here!

The fibonacci builtin, implemented using the phi formula.

\$\endgroup\$
3
  • \$\begingroup\$ Uncaught SyntaxError: Unexpected token | at new Function (<anonymous>) at p (math.min.js:27) at Object (math.min.js:27) at typed (eval at p (math.min.js:27), <anonymous>:36:14) at Object.n [as factory] (math.min.js:45) at t (math.min.js:27) at f (math.min.js:27) at Object.get [as median] (math.min.js:27) at clone (rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf.js:902) at rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf.js:2128 (Latest Google Chrome, version 55.0.2883.87m) \$\endgroup\$ Jan 2, 2017 at 0:05
  • \$\begingroup\$ @IsmaelMiguel This should only work on firefox \$\endgroup\$ Jan 2, 2017 at 1:08
  • \$\begingroup\$ I had no idea, it isn't anywhere \$\endgroup\$ Jan 2, 2017 at 1:17
2
\$\begingroup\$

Haskell, 51 bytes

s=0:scanl(+)1s;f z|even z,z<0= -f(-z);f z=s!!abs z
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Multiple tests within a guard can be combined with , instead of &&: even z,z<0. \$\endgroup\$
    – nimi
    Jan 2, 2017 at 23:54
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 2 bytes

ÆḞ

Try it online!

Boring builtin answer, Jelly’s Fibonacci builtin handles negative inputs just fine

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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