Coursera: Calculating sum of numbers in the fibonacci sequence between two specific points in the series

Question

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.)

• greybeard: This is an assignment - and a trivial one: what do you know/can you find out about F1+...+Fn?
• Enzio: @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.

Answer 1

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)];
}

• greybeard: look at [the] first few Fibonacci numbers [: last] digits are repeated after 60 numbers. MMD

Answer 2

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.