_Ḟ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](../../I/static/images/2173fbdfcf14c2497be2024dace37fc43d2e84c39b632662849dc134d11adf38.png)
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.
2The 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.) – None – 2017-04-28T16:17:51.013
@ais523, if you think it would improve the question then yes, you may change the title of the post. – Daniel – 2017-04-28T16:22:47.950
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. – None – 2017-04-28T16:25:29.627
@ais523, those are all good things :) – Daniel – 2017-04-28T16:28:03.593
2
@ais Looks like there's a generalisation of the Binet formula: http://mathworld.wolfram.com/FibonacciNumber.html
– Neil – 2017-04-28T17:31:55.330A few test cases in an easy-to-use format would be nice, especially for edge cases like integers and numbers between 0 and 1. – Dennis – 2017-04-28T17:53:15.530
@ais523: I'm not sure if there's any standard generalization. —I guess this doesn't really qualify as a generalization since the exact Fibonacci numbers aren't included, but 1/sqrt(5) * (golden ratio)^n describes the the asymptotic growth. I don't believe there is any standard true generalization. – Julian Wolf – 2017-04-28T18:17:22.197
@JulianWolf Binet's formula is exact for integer arguments. – orlp – 2017-04-28T22:38:42.393
1Although code golf doesn't have to justify the request (I guess), this seems like a weird operation; according to it, since
F_0 = 0
andF_2 = 1
, we should haveF_1 = (1/2)(F_0 + F_2) = 1/2
. – LSpice – 2017-04-28T22:43:55.837@orlp: huh, good to know. That's the sort of tidbit that I should probably know from some or other discrete maths course but have no memory whatsoever of. Thanks. – Julian Wolf – 2017-04-28T23:14:07.297
@LSpice That is true. However, that isn't how the linear interpolation works because it's like drawing a line segment between each point on a graph; the line segments don't form a straight line. – HyperNeutrino – 2017-04-29T01:30:43.360