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

11 Answers 11

22
\$\begingroup\$

Mathematica, 9 bytes

Fibonacci

Yes, this built-in function supports negative numbers.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is almost word-for-word the answer I was coming to post :D \$\endgroup\$ – Greg Martin Dec 31 '16 at 20:13
17
\$\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\$
  • 1
    \$\begingroup\$ (How) Does this also work for negative input? \$\endgroup\$ – Roman Gräf Dec 31 '16 at 10:57
  • \$\begingroup\$ yes, explanation coming... \$\endgroup\$ – flawr Dec 31 '16 at 10:57
  • \$\begingroup\$ is ans(-6) meant to be positive? \$\endgroup\$ – FlipTack Dec 31 '16 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 '16 at 11:09
13
\$\begingroup\$

Maxima, 3 bytes

 fib

supports positive and negative numbers.

Try it (paste) on CESGA - Maxima on line

\$\endgroup\$
  • \$\begingroup\$ Can you add a link to the language? \$\endgroup\$ – Pavel Jan 1 '17 at 0:38
  • \$\begingroup\$ Of course added a link to an online calculator! \$\endgroup\$ – rahnema1 Jan 1 '17 at 3:49
  • \$\begingroup\$ Also works on WolframAlpha \$\endgroup\$ – Thunda Mar 24 '17 at 6:58
11
\$\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\$
  • \$\begingroup\$ I really like your function. I had a suggestion here, but I overlooked a -, so it wouldn't work... \$\endgroup\$ – Luke Dec 31 '16 at 13:43
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\$
5
\$\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\$
  • \$\begingroup\$ ** requires ES7. \$\endgroup\$ – Neil Dec 31 '16 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 '16 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 '16 at 17:41
3
\$\begingroup\$

Jolf, 2 bytes

mL

Try it here!

The fibonacci builtin, implemented using the phi formula.

\$\endgroup\$
  • \$\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\$ – Ismael Miguel Jan 2 '17 at 0:05
  • \$\begingroup\$ @IsmaelMiguel This should only work on firefox \$\endgroup\$ – Conor O'Brien Jan 2 '17 at 1:08
  • \$\begingroup\$ I had no idea, it isn't anywhere \$\endgroup\$ – Ismael Miguel Jan 2 '17 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
    \$\begingroup\$ Multiple tests within a guard can be combined with , instead of &&: even z,z<0. \$\endgroup\$ – nimi Jan 2 '17 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\$

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.