Incorrect results for Fibonacci sequences

[jolkdarr]

Incorrect value is returrned for "big" n values (n > 92) because of the encoding limitation of the used primary type (long). Either an IllegalArgumentException should be raised or a zero value returned for all algorithms.

Fibonacci sequence tests

algorithm: FibonacciSequenceUsingLoop

f(25) =                75025 [    4.157 µs]
f(26) =               121393 [    5.207 µs]
f(27) =               196418 [    5.023 µs]
...
f(90) =  2880067194370816120 [   18.408 µs]
f(91) =  4660046610375530309 [   18.718 µs]
f(92) =  7540113804746346429 [   18.741 µs]
f(93) = -6246583658587674878 [   19.363 µs] KO
f(94) =  1293530146158671551 [   18.479 µs] KO
f(95) = -4953053512429003327 [   19.053 µs] KO

algorithm: FibonacciSequenceUsingRecursion

f(25) =                75025 [    1.581 ms]
f(26) =               121393 [    2.671 ms]
f(27) =               196418 [    4.328 ms]
f(28) =               317811 [    7.032 ms]
f(29) =               514229 [    9.708 ms]
f(30) =               832040 [   15.432 ms]
f(31) =              1346269 [   24.880 ms]
f(32) =              2178309     time out

algorithm: FibonacciSequenceUsingMatrixMultiplication

f(25) =                75025 [   23.856 µs]
f(26) =               121393 [   29.692 µs]
f(27) =               196418 [   30.164 µs]
...
f(90) =  2880067194370816120 [   88.054 µs]
f(91) =  4660046610375530309 [   88.248 µs]
f(92) =  7540113804746346429 [   89.123 µs]
f(93) = -6246583658587674878 [  114.994 µs] KO
f(94) =  1293530146158671551 [   91.361 µs] KO
f(95) = -4953053512429003327 [   92.010 µs] KO

algorithm: FibonacciSequenceUsingBinetsFormula

f(25) =                75025 [    5.359 µs]
f(26) =               121393 [    4.295 µs]
f(27) =               196418 [    4.476 µs]
...
f(90) =  2880067194370825216 [    3.210 µs]
f(91) =  4660046610375544832 [    3.850 µs]
f(92) =  7540113804746369024 [    3.288 µs]
f(93) =  9223372036854775807 [    3.637 µs] KO
f(94) =  9223372036854775807 [    3.654 µs] KO
f(95) =  9223372036854775807 [    3.752 µs] KO

[phishman3579]

Can you share your testing code?

[phishman3579]

@jolkdarr Thanks again. I've added exception handling to all the fibonaaci calculations. I like your timing code, if you'd like to share it then I'll add it to the repo.

faa1ef5

[jolkdarr]

I have added, in the Sequences class, the following test method to compare all Fibonacci algorithms:

@Test
public void fibonacciBenchmarks() {
    // display benchmarks (output format: markdown):
    System.out.println("# Fibonacci sequence tests");
    final long time_out = 30000;
    final float k = 1000f;
    final Fibonacci[] instances = { FibonacciSequenceUsingLoop.INSTANCE,
                                    FibonacciSequenceUsingRecursion.INSTANCE,
                                    FibonacciSequenceUsingMatrixMultiplication.INSTANCE,
                                    FibonacciSequenceUsingBinetsFormula.INSTANCE };
    for (final Fibonacci f : instances) {
        System.out.println("\n### algorithm: **" + f.getClass().getSimpleName() + "**\n```");
        for (int n = 25; n < 96; n++)
            if (n < 28 || n >= 90 || f == FibonacciSequenceUsingRecursion.INSTANCE)
                try {
                    if (n == 90)
                        System.out.println("...");
                    System.out.print("f(" + n + ") = ");
                    final long t0 = System.nanoTime();
                    final long r = f.fibonacciSequence(n);
                    final float dt = (System.nanoTime() - t0) / k;
                    if (dt <= time_out) {
                        if (dt < k)
                            System.out.print(String.format("%20d [%9.3f µs]", r, dt));
                        else
                            System.out.print(String.format("%20d [%9.3f ms]", r, dt / k));
                        if (n <= 92)
                            System.out.println();
                        else
                            System.out.println(" KO");
                    }
                    else {
                        System.out.println(String.format("%20d %12s", r, "time out"));
                        break;
                    }
                }
                catch (final Throwable t) {
                    System.out.println("?");
                    break; // try next algorithm
                }
        System.out.println("```");
    }
}

Notes:

1. This snippet is not directly compliant with your repository but it may be adapted easily.
   I made some refactoring in my fork by using the Strategy design pattern. I can provide the modified files.
2. The output format is markdown. Maybe results ought to be printed in a file (fibonacci_benchmarks.md for instance).

[phishman3579]

Thanks @jolkdarr , I will try and include this into the timing package. By the way, if you pull the latest version of fibonacciSequenceUsingRecursion it should be significantly faster. I've added memoization to the function.

[jolkdarr]

Ok, I need to rebase quickly then.
Test method (using reflection) adapted for you :)

@Test
public void fibonacciBenchmarks_ref() throws NoSuchMethodException, SecurityException {
    // display benchmarks (output format: markdown):
    System.out.println("# Fibonacci sequence tests");
    final long time_out = 30000;
    final float k = 1000f;
    final Method[] instances = FibonacciSequence.class.getDeclaredMethods();
    for (final Method f : instances) {
        System.out.println("\n### algorithm: **" + f.getName() + "**\n```");
        for (int n = 25; n < 96; n++)
            if (n < 28 || n >= 90 || "fibonacciSequenceUsingRecursion".equals(f.getName()))
                try {
                    if (n == 90)
                        System.out.println("...");
                    System.out.print("f(" + n + ") = ");
                    final long t0 = System.nanoTime();
                    final long r =(Long) f.invoke(null, n);
                    final float dt = (System.nanoTime() - t0) / k;
                    if (dt <= time_out) {
                        if (dt < k)
                            System.out.print(String.format("%20d [%9.3f µs]", r, dt));
                        else
                            System.out.print(String.format("%20d [%9.3f ms]", r, dt / k));
                        if (n <= 92)
                            System.out.println();
                        else
                            System.out.println(" KO");
                    }
                    else {
                        System.out.println(String.format("%20d %12s", r, "time out"));
                        break;
                    }
                }
                catch (final Throwable t) {
                    System.out.println("?");
                    break; // try next algorithm
                }
        System.out.println("```");
    }
}