1
\$\begingroup\$

Question

This is an assignment for a Coursera course.

enter image description here

This is the algorithm I wrote.

import java.util.*;

public class FibonacciPartialSum {
    private static long getFibonacciPartialSumNaive(long from, long to) {
        if (to <= 1)
            return to;

        long prev = 0;
        long cur = 1;
        long sum;

        if(from == 1) {
            sum = 1;
        }
        else {
            sum = 0;
        }

        for (long i = 2; i <= to; i++) {
            long temp_prev = prev;
            prev = cur;
            cur = (cur + temp_prev) % 10;

            if (i >= from) {
                sum = (sum + cur) % 10;
            }

        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long from = scanner.nextLong();
        long to = scanner.nextLong();
        //long from = 1234;
        //long to = 12345;
        System.out.println(getFibonacciPartialSumNaive(from, to));
        scanner.close();
    }
}

When I submit it to auto grader in Coursera it states that I failed the time test.

Failed case #8/12: time limit exceeded Input: 1 10000000000

Your output:

stderr:

(Time used: 3.03/1.50, memory used: 26427392/536870912.)
\$\endgroup\$
2
  • \$\begingroup\$ This is an assignment - and a trivial one: what do you know/can you find out about F₁+…+Fₙ? \$\endgroup\$ Commented Aug 3, 2017 at 12:13
  • \$\begingroup\$ @greybeard This is one of 8 questions for a weekly assignment. I figured out that to get the correct final answer you don't have to add the total numbers. Just adding the last digit (hence use %10) is enough. I didn't figure out anything else. \$\endgroup\$ Commented Aug 3, 2017 at 12:35

2 Answers 2

Reset to default
4
\$\begingroup\$

Runtime improvement

If you take a look at the last digit of the first few fibonacci numbers you will see that the digits are repeated after 60 numbers. As the digits in this range have a sum of 0 you can calculate the sum for [from%60,to%60] instead.

Bug

The task states that the given integer are non-negative, 0 is a valid value. Currently you are returning i.e. 1 for the range [0,2] as 0 is treated as 2, the initialization of sum has to be changed to:

if (from <= 1) {
    sum = 1;
} else {
    sum = 0;
}

(I would initialize sum with a ternary operator long sum = from <= 1 ? 1 : 0 instead.)

Types

As the values of sum, prev and cur are always in the range [0,10), you can use int instead of long for these variables, int arithmetic is likely to be faster than long arithmetic.

Alternative implementation

The remaining range is quite small -> you could cache the results for every number in the range [0,60) to avoid calculating the sum on each invocation.

private static final byte[] DIGIT_SUM = {
        0, 1, 2, 4, 7, 2, 0, 3, 4, 8,
        3, 2, 6, 9, 6, 6, 3, 0, 4, 5,
        0, 6, 7, 4, 2, 7, 0, 8, 9, 8,
        8, 7, 6, 4, 1, 6, 8, 5, 4, 0,
        5, 6, 2, 9, 2, 2, 5, 8, 4, 3,
        8, 2, 1, 4, 6, 1, 8, 0, 9, 0};

private static int fibonacciPartialSum(long m, long n) {
    assert m <= n & (m | n) >= 0;
    int v = fibSumLastDigit(n);
    return m == 0 ? v : (v -= fibSumLastDigit(m - 1)) + (10 & v >> -1);
}

private static int fibSumLastDigit(long n) {
    return DIGIT_SUM[(int) (n % 60)];
}
\$\endgroup\$
1
  • \$\begingroup\$ look at [the] first few Fibonacci numbers [: last] digits are repeated after 60 numbers. MMD \$\endgroup\$ Commented Aug 4, 2017 at 5:15
3
\$\begingroup\$

The most interesting optimisation I can think of is making use of the pisano period.

This says that the sum of the first N fib numbers mod 10 is cyclic with period 60.

This means that the SumF(1) = sumF(61) = sumF(121) ...

So if we add the following lines to the start of the method:

from = from%60;
to = to%60;

we get a really great improvement ... but also introduced an error. This will only work if the new to is still larger than the new from.

This can easily be fixed though:

if(to < from){
    to += 60;
}

The rest of your method can remain the same.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.