[c-cube]

They also do that, the post refers to their Quickcheck library. But how do you property test the Fibonacci function ? There isn't much to say about it...

[travisjungroth]

Properties of the Fibonacci function:

It is non-decreasing monotonic. fib(n) <= fib(n+1)

It is increasing monotonic after 1. fib(n) < fib(n+1)

Its domain and codomain are non-negative integers.

fib(n) + fib(n+1) == fib(n+2) Notice this is like the recursive solution except going the other way (addition not subtraction) and is missing the base case.

[xtagon]

It also converges closer and closer to the golden ratio. Implementing a property test for that would be interesting.

[travisjungroth]

    a, b, c = fib(n), fib(n+1), fib(n+2)
    assert abs(c / b - phi) < abs(b / a - phi)

[angio]

I believe the way to test it is to have a property like `n in integer | fib(n+2) == fib(n+1) + fib(n)`. This is close to the naive (but obviously correct?) implementation of fib and can be used to test the optimized version of the function.

You can also test that the sequence is increasing like `fib(n+2) > fib(n+1) > fib(n)`.

[avgcorrection]

You use the naive implementation as a test oracle, limit `n` to something small (through the property tester), and use the test oracle on your efficient implementation.

Unit testing elegant functions has no value.

(fib is often used as an example. But you asked how to test it.)

[davidgrenier]

In combinatorics the adjusted fibonacci numbers start with 1 instead and is more commonly used as it aligns with many other results. One might want to document in the code, via a test, which sequence is of interest.

This is just an example of course but elegant functions might need to be tested.

[eru]

In addition to what travisjungroth said, you can also check against a reference implementation.

Eg if you coded up an O(n) version of the Fibonacci calculation, you can check against the naive recursive one (or if you are feeling confident, you can check against the O(log n) solution via repeated squaring of matrices.)

[bottled_poe]

Actually, Fibonacci results can be fairly precisely tested with the golden ratio ratio.

[davidgrenier]

You could compare against a closed-form solution:

    let fib2 n =
        let sq5 = sqrt(5.0)
        ((1.0 + sq5)/2.0)**(float n)/sq5
        |> round |> int

[MereInterest]

The problem is that the closed-form solution is vulnerable to floating-point error. If the calculations are done in float32 (including all intermediate steps), then the 32nd fibonacci number is erroneously given as 2178310, instead of the correct value of 2178309. Using float64 does better, but still has an error at the 71st fibonacci number. (I made a quick plot of the error as a function of N at https://i.imgur.com/bbc9OFC.png. As soon as the error crossed ±0.5, the rounding results in the wrong result.)

These are fine for property-based testing, so long as you restrict yourself to the range in which you have a correct value. But at that point, you might as well just hard-code the first 93 fibonacci numbers (the most that will fit in a uint64_t) and be done with it.