Last digit of a Fibonacci number

The Fibonacci sequence leads rapidly to such huge values that it gets difficult even to think to a monster like Fibonacci of one million. However, let's say that we have a less mind-boggling problem, calculating just the last digit of it, even if for large input, like one hundred million. This is not a big issue, in the worst case it is to spot a linear time complexity solution, and if we check closely the properties of the sequence, we could devise a costant time one.

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.

Go to the full post

Add testing to a Maven project

This post was not so obsolete as the previous two ones, however it referred to JUnit 4, while the most interesting point in the argument, I feel, is in the fact that we should use a recent Surefire Maven plugin if we want the test run on build work with JUnit 5.

So, again, so long my outdated post. If interested, you could get its new version on my other blog: https://thisthread.blogspot.com/2020/05/test-on-build-with-maven.html.

Go to the full post

Adding Logback to a Maven Project

If you have written a Java project, maybe using Eclipse as IDE, but fundamentally using Maven as build manager, and you ask yourself how to add dependencies to it and, even more importantly, how to tell Maven to include your dependencies in the resulting jar, making it "fat" but also so more easily usable. This post was for you.

I used Logback as sample library, but the story is the same any dependency you are putting in your app.

Unfortunately it aged badly, so I had to ditch it.

Still, I decided to rewrite it and I put the new version in my other blog. Follow the link if interested in it. https://thisthread.blogspot.com/2020/05/jar-with-dependencies-through-maven.html

Go to the full post

Simple Maven Eclipse Project

As the title hints, this post was about creating a tiny little Java desktop apps on the Eclipse IDE using Maven as building tool.

I say "was" because, unfortunately, it was too obsolete to survive.

My first idea was just to clean it a bit and make it more fit for the current time. Then I found out that it was simpler for me, and clearer for the reader, if I rewrote it from scratch. Along the way, I have also refactored the code and rearrange the repository on GitHub.

Moreover, I moved it to my other blog, this thread, that I plan to keep as the only one active. If interested, please follow the link https://thisthread.blogspot.com/2020/05/simple-maven-eclipse-project.html

Go to the full post