Firstly, I write a few test case. I am using JUnit 4, and the assertThat Hamcrest-style assertion:
public class FibonacciTest {
static final Fibonacci fib = new Fibonacci();
// ...
@Test
public void testLastDigit40() {
assertThat(fib.lastDigitNaive(40), is(5));
}
@Test
public void testLastDigit327305() {
assertThat(fib.lastDigit(327_305), is(5));
}
@Test
public void testLastDigit100mio() {
assertThat(fib.lastDigit(100_000_000), is(5));
}
It is reasonably easy to calculate Fibonacci(40) = 102_334_155 and, trust me, both Fibonacci(327_305) and Fibonacci(100_000_000) have also a five as their last digit.Then I write a first implementation for lastDigit() method in my class Fibonacci:
public int lastDigit(int n) {
if (n < 2) // 1
return n;
int previous = 0; // 2
int current = 1;
for (int i = 1; i < n; ++i) { // 3
int older = previous;
previous = current;
current = (older + previous) % 10; // 4
}
return current;
}
1. Accordingly to the modern definition of this sequence, Fibonacci(0) is 0 and Fibonacci(1) is 1.2. To calculate the current Fibonacci number we need to keep track of the latest two ones.
3. Let's loop until we reach our target. The previous value will be discarded, current one will become previous, and the current one is calculated.
4. We are lucky, we don't need to store the actual Fibonacci number, it's last digit is enough.
Not a bad solution, however we could do better. We just have to notice that after 60 numbers, the final number in the sequence enter in a loop and repeat the first value. The is an interesting thread on math stackexchange that gives more details on this curious feature.
Let's exploit it to get a better solution:
public int lastDigit(int n) {
int[] fibLast = new int[60]; // 1
fibLast[0] = 0;
fibLast[1] = 1;
for (int i = 2; i < 60; ++i) { // 2
fibLast[i] = (fibLast[i - 1] + fibLast[i - 2]) % 10;
}
return fibLast[n%60]; // 3
}
1. I am going to do the same job as in the first implementation, however I cache the first sixty values in a raw array.2. Notice the despicable use of the magic number 60 here and in (1). It should be a well commented constant instead!
3. Thanks to the looping nature of the last cypher in Fibonacci numbers, I just have to apply to modulo operator to extract the correct index in my cached values.
As an obvious performance improvement we should initialize the cache only the first time the method is called. In any case, I think the point is made, so I commit the Fibonacci Java class and its JUnit tester to github.
