Luhn checksum validation in Java

Question

I have to replicate the luhn algorithm in Java, the problem I face is how to implement this in an efficient and elegant way (not a requirement but that is what I want).

---

The luhn-algorithm works like this:

1. You take a number, let's say 56789

loop over the next steps till there are no digits left

2. You pick the left-most digit and add it to the total sum. sum = 5
3. You discard this digit and go the next. number = 6789
4. You double this digit, if it's more than one digit you take apart this number and add them separately to the sum. 2*6 = 12, so sum = 5 + 1 = 6 and then sum = 6 + 2 = 8.

Addition restrictions For this particular problem I was required to read all digits one at a time and do computations on each of them separately before moving on. I also assume that all numbers are positive.

---

The problems I face and the questions I have

As said before I try to solve this in an elegant and efficient way. That's why I don't want to invoke the toString() method on the number to access all individual digits which require a lot of converting. I also can't use the modulo kind of way because of the restriction above that states once I read a number I should also do computations on it right away. I could only use modulo if I knew in advance the length of the String, but that feels like I first have to count all digits one-for-once which thus is against the restriction. Now I can only think of one way to do this, but this would also require a lot of computations and only ever cares about the first digit*:

int firstDigit(int x) {
    while (x > 9) {
        x /= 10;
    }
    return x;
}

Found here: https://stackoverflow.com/a/2968068/3972558

*However, when I think about it, this is basically a different and weird way to make use of the length property of a number by dividing it as often till there is one digit left.

So basically I am stuck now and I think I must use the length property of a number which it does not really have, so I should find it by hand. Is there a good way to do this? Now I am thinking that I should use modulo in combination with the length of a number. So that I know if the total number of digits is uneven or even and then I can do computations from right to left. Just for fun I think I could use this for efficiency to get the length of a number: https://stackoverflow.com/a/1308407/3972558

This question appeared in the book Think like a programmer.

Answer 1

You can optimise it by unrolling the loop once (or as many times are you like) This will be close to twice as fast for large numbers, however make small numbers slower. If you have an idea of the typical range of numbers you will have you can determine how much to unroll this loop.

int firstDigit(int x) {
    while (x > 99)
        x /= 100;
    if (x > 9) 
        x /= 10;
    return x;
}

Answer 2

use org.apache.commons.validator.routines.checkdigit.LuhnCheckDigit . isValid()

Maven Dependency:

<dependency>
    <groupId>commons-validator</groupId>
    <artifactId>commons-validator</artifactId>
    <version>1.4.0</version>
</dependency>

Answer 3

As I understand, you will eventually need to read every digit, so what is wrong with convert initial number to string (and therefore char[]) and then you can easily implement the algorithm iterating that char array.

JDK implementation of Integer.toString is rather optimized so that you would need to implement your own optimalizations, e.g. it uses different lookup tables for optimized conversion, convert two chars at once etc.

final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                  99999999, 999999999, Integer.MAX_VALUE };

// Requires positive x
static int stringSize(int x) {
    for (int i=0; ; i++)
        if (x <= sizeTable[i])
            return i+1;
}

This was just an example but feel free to check complete implementation :)

Answer 4

Normally you would process the numbers from right to left using divide by 10 to shift the digits and modulo 10 to extract the last one. You can still use this technique when processing the numbers from left to right. Just use divide by 1000000000 to extract the first number and multiply by 10 to shift it left:

0000056789
0000567890
0005678900
0056789000
0567890000
5678900000
6789000000
7890000000
8900000000
9000000000

Some of those numbers exceed maximum value of int. If you have to support full range of input, you will have to store the number as long:

static int checksum(int x) {
    long n = x;
    int sum = 0;
    while (n != 0) {
        long d = 1000000000l;
        int digit = (int) (n / d);
        n %= d;
        n *= 10l;
        // add digit to sum
    }
    return sum;
}

Answer 5

I would first convert the number to a kind of BCD (binary coded decimal). I'm not sure to be able to find a better optimisation than the JDK Integer.toString() conversion method but as you said you did not want to use it :

List<Byte> bcd(int i) {
    List<Byte> l = new ArrayList<Byte>(10);  // max size for an integer to avoid reallocations
    if (i == 0) {
        l.add((byte) i);
    }
    else {
        while (i != 0) {
            l.add((byte) (i % 10));
            i = i / 10;
        }
    }
    return l;
}

It is more or less what you proposed to get first digit, but now you have all you digits in one single pass and can use them for your algorythm.

I proposed to use byte because it is enough, but as java always convert to int to do computations, it might be more efficient to directly use a List<Integer> even if it really wastes memory.