# Question

This is an assignment for a Coursera course.

This is the algorithm I wrote.

import java.util.*;

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

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

stderr:

(Time used: 3.03/1.50, memory used: 26427392/536870912.)

• This is an assignment - and a trivial one: what do you know/can you find out about F₁+…+Fₙ? – greybeard Aug 3 '17 at 12:13
• @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. – Enzio Aug 3 '17 at 12:35

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

• look at [the] first few Fibonacci numbers [: last] digits are repeated after 60 numbers. MMD – greybeard Aug 4 '17 at 5:15

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.