20
\$\begingroup\$

Your task is to find the nth Fibonacci number, but n is not necessarily an integer.

The Fibonacci sequence, 0-indexed, goes as follows:

0, 1, 2, 3, 4, 5,  6,  7, ...

1, 1, 2, 3, 5, 8, 13, 21, ...

However, what happens if we want the 2.4th number?

The 2.4th number is 0.4 times the difference between the 3rd and 2nd Fibonacci numbers plus the 2nd Fibonacci number. So, the 2.4th Fibonacci number is 2 + 0.4 * (3 – 2) = 2.4.

Similarly, the 6.35th Fibonacci number is 13 + 0.35 * (21 – 13) = 15.8.

Your task is to find the nth Fibonacci number, such that n is greater than or equal to 0.

You may do this zero- or one-indexed, just please say which one you are using.

This is , so shortest code in bytes wins!

Some more examples:

0        1
4.5    6.5
0.7      1
7       21
\$\endgroup\$
  • 2
    \$\begingroup\$ The operation you're doing here is called "linear interpolation". (Would you mind if I changed the title of the post to reflect that?) It does seem to have the Fibonacci property that f(n-2)+f(n-1)=f(n), so I guess this is a reasonable generalisation of the Fibonacci sequence. (I'm not sure if there's any standard generalisation.) \$\endgroup\$ – user62131 Apr 28 '17 at 16:17
  • \$\begingroup\$ @ais523, if you think it would improve the question then yes, you may change the title of the post. \$\endgroup\$ – Daniel Apr 28 '17 at 16:22
  • \$\begingroup\$ I think it'll make the question easier to find in future if someone asks something similar, and also makes it clearer what it's about in, say, the "Related" list. So it'll make the question better by helping get the answerers to the right place. \$\endgroup\$ – user62131 Apr 28 '17 at 16:25
  • 2
    \$\begingroup\$ @ais Looks like there's a generalisation of the Binet formula: mathworld.wolfram.com/FibonacciNumber.html \$\endgroup\$ – Neil Apr 28 '17 at 17:31
  • 1
    \$\begingroup\$ Although code golf doesn't have to justify the request (I guess), this seems like a weird operation; according to it, since F_0 = 0 and F_2 = 1, we should have F_1 = (1/2)(F_0 + F_2) = 1/2. \$\endgroup\$ – LSpice Apr 28 '17 at 22:43

11 Answers 11

7
\$\begingroup\$

Jelly, 5 bytes

_Ḟ1+¡

This is an iterative solution without built-ins. It uses the same indexing as the challenge spec.

Try it online!

Background

Let f be the function defined in the challenge spec and F the Fibonacci function defined as usual (i.e., with F(0) = 0). For a non-negative integer n, we have f(n) = F(n + 1). When 0 ≤ x < 1, the challenge spec defines f(n + x) as f(n) + (f(n + 1) - f(n))x.

Clearly, this just affects the base cases, but not the recursive formula, i.e., f(n) = f(n - 1) + f(n - 2) holds as it would for F. This means we can simplify the definition for non-integer arguments to the easier f(n) = f(n) + f(n - 1)x.

As others have noted in their answers, the recursive relationship also holds for non-integer arguments. This is easily verifiable, as

proof

Since f(0) = f(1) = 1, f in constant in the interval [0, 1] and f(0 + x) = 1 for all x. Furthermore, f(-1) = F(0) = 0, so f(-1 + x) = f(-1) + (f(0) - f(-1))x = 0 + 1x = x. These base cases cover in [-1, 1), so together with the recursive formula, they complete the definition of f.

How it works

As before, let n + x be the only argument of our monadic program.

¡ is a quick, meaning that it consumes some links to its left and turns them into a quicklink. ¡ in particular consumes either one or two links.

  • <F:monad|dyad><N:any> calls the link N, returning r, and executes F a total of r times.

  • <nilad|missing><F:monad|dyad> sets r to the last command-line argument (or an input from STDIN in their absence) and executes F a total of r times.

Since 1 is a nilad (a link without arguments), the second case applies, and will execute + n times (a non-integer argument is rounded down). After each call to +, the left argument of the quicklink is replaced with the return value, and the right argument with the previous value of the left argument.

As for the entire program, floors the input, yielding n; then _ subtract the result from the input, yielding **x, which becomes the return value.

1+¡ then calls – as described before – with left argument 1 = f(0 + x) and right argument x = f(-1 + x), which computes the desired output.

\$\endgroup\$
  • \$\begingroup\$ Ahh, how useful is for Fibonacci challenges. Was it purposeful to have ¡ work like fibonacci with dyads? \$\endgroup\$ – Erik the Outgolfer Apr 29 '17 at 8:59
  • \$\begingroup\$ Oooh - %1+¡: linear interpolation between n × F(n) at n and n × F(n-1) + F(n) at n-ε, and step up between n-ε and n. \$\endgroup\$ – Jonathan Allan Apr 30 '17 at 0:21
  • \$\begingroup\$ @EriktheOutgolfer Well, more or less. Since Jelly doesn't have variables, you'd lose access to the previous sequence members otherwise, so it made sense to implement it like this. \$\endgroup\$ – Dennis Apr 30 '17 at 1:18
  • \$\begingroup\$ @JonathanAllan I'm not sure I understand. What is %1+¡ supposed to do? \$\endgroup\$ – Dennis Apr 30 '17 at 1:18
  • \$\begingroup\$ @Dennis erm, meant, well \_o_/ ...but that is what it appears to do with experimentation :D \$\endgroup\$ – Jonathan Allan Apr 30 '17 at 1:24
5
\$\begingroup\$

Mathematica, 32 bytes

If[#<2,1~Max~#,#0[#-1]+#0[#-2]]&

Pure function taking a nonnegative real number as input and returning a real number. If 1~Max~# were replaced by 1, this would be the standard recursive definition of the 0-indexed Fibonacci numbers for integer arguments. But 1~Max~# is the correct piecewise linear function for real inputs between 0 and 2, and the recursion takes care of the rest. (Trivia fact: changing this to the 1-indexed Fibonacci numbers can be accomplished simply by changing the Max to a Min!)

The shortest I could get with the builtin is the 37-byte (b=Fibonacci)[i=Floor@#](#-i)+b[i+1]&.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 42 bytes

f=lambda n:n<3and max(1,n)or f(n-1)+f(n-2)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 30 bytes

f=x=>x<1?1:x<2?x:f(x-1)+f(x-2)
<input type=number value=2.4 oninput="O.value=f(value)"> <input id=O value=2.4 disabled>

Trivial modification of the zero-indexed recursive Fibonacci sequence definition. May give slight rounding errors for some inputs.

\$\endgroup\$
  • \$\begingroup\$ This is clever. I thought it didn't work. \$\endgroup\$ – Leaky Nun Apr 28 '17 at 16:39
1
\$\begingroup\$

Jelly, 17 12 bytes

’Ñ+Ñ
’»0‘ÇỊ?

Try it online!

Non-builtin solution.

Explanation

Helper function 1Ŀ

’Ñ+Ñ
 Ñ    Call the main program on
’       {the input} - 1;
   Ñ  Call the main program on {the input};
  +   Add those results{and return the result}

Main program

’»0‘ÇỊ?
’        Subtract 1
 »0      but replace negative results with 0
     Ị?  If the result is less than or equal to 1
   ‘     Return the result plus 1
    Ç    else return the result

An input in the range 0 to 1 will therefore saturated-subtract to 0, thus we add 1 to get F(0)=F(1)=1. An input in the range 1 to 2 will return itself. Those base cases are sufficient to do a typical Fibonacci recursion and calculate the other values from there.

\$\endgroup\$
1
\$\begingroup\$

Excel, 137 124 119 113 102 97 Bytes

Non-recursive/iterative approach. (Directly calculate the nth terms) This uses the one-indexed method. Adding +1 to =TRUNC(B1) changes it to zero-indexed.

=A7+(A8-A7)*MOD(B1,1)
=5^.5
=(1+A2)/2
=TRUNC(B1)
=A4+1
=-1/A3
=(A3^A4-A6^A4)/A2
=(A3^A5-A6^A5)/A2

The code snippet is intended to be placed starting in cell A1.

The input cell is B1. The output cell is A1.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 67 64 bytes

Has a few issues with rounding

n=>(i=(g=(z,x=1,y=0)=>z?g(--z,x+y,x):y)(++n|0))+n%1*(g(++n|0)-i)

Try It

f=
n=>(i=(g=(z,x=1,y=0)=>z?g(--z,x+y,x):y)(++n|0))+n%1*(g(++n|0)-i)
console.log(f(2.4))
console.log(f(6.35))
console.log(f(42.42))

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

PHP, 90 Bytes

for($f=[1,1];$i<$a=$argn;)$f[]=$f[+$i]+$f[++$i];echo$f[$b=$a^0]+($a-$b)*($f[$b+1]-$f[$b]);

Online Version

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

Jelly, 13 9 bytes

,‘ḞÆḞḅ%1$

This uses the same indexing as the challenge spec.

Try it online!

Background

Per the spec, we have F(n + x) = F(n) + (F(n + 1) - F(n))x, for natural n and 0 ≤ x < 1. Since F(n + 1) = F(n) + F(n - 1), this can be rewritten as F(n + x) = F(n) + F(n - 1)x.

Furthermore, the indexing used in the challenge spec defines a function f(n) = F(n + 1) (where F is the usual Fibonacci function, i.e., F(0) = 0), so we get the formula f(n + x) = F(n + 1) + F(n)x.

How it works

,‘ḞÆḞḅ%1$  Main link. Argument: n + x

 ‘         Increment; yield n + 1 + x.
,          Pair; yield [n + x, n + 1 + x].
  Ḟ        Floor; yield [n, n + 1].
   ÆḞ      Fibonacci; yield [F(n), F(n + 1)].
      %1$  Modulus 1; yield (n + x) % 1 = x.
     ḅ     Unbase; yield F(n)x + F(n + 1).
\$\endgroup\$
0
\$\begingroup\$

Perl 6,  48  38 bytes

48

{$/=(1,1,*+*...*)[$_,$_+1];$0+($_-.Int)*($1-$0)}

Try it

38

sub f(\n){3>n??max 1,n!!f(n-1)+f(n-2)}

Try it

Expanded:

48

{
  $/ =          # store here so we can use $0 and $1
  (
    1,1,*+*...* # Fibonacci sequence
  )[
    $_,         # get the value by using floor of the input
    $_ + 1      # and get the next value
  ];

    $0            # the first value from above
  +
    ( $_ - .Int ) # the fractional part of the input
  *
    ( $1 - $0 )   # the difference between the two values in the sequence
}

($0 and $1 is short for $/[0] and $/[1])

38

sub f (\n) {
    3 > n           # if n is below 3
  ??
    max 1, n        # return it if it is above 1, or return 1
                    # if it was below 1, the answer would be 1
                    # the result for numbers between 1 and 3
                    # would be the same as the input anyway
  !!
    f(n-1) + f(n-2) # the recursive way to get a fibonacci number
}

This was inspired by other Python, and Javascript solutions

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

Julia 0.5, 31 bytes

This is basically just Rod's answer translated.

f(n)=n<3?max(1,n):f(n-1)+f(n-2)

Try it online!

\$\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.