Improvement to Luhn-Checksum Algorithm in Java

Question

I just made a small Luhn Checksum validator Description of Luhn Checksum

Every number in the Integer gets added individually together, but every second digit gets instead doubled and added. If the doubled number is over ten each individual digit gets added.

It works, but is there a way to make it more elegant and maybe more efficient, while maintaining readability?

The while loop seems a bit ugly to me, and I'm not completely satisfied with the name getLuhn but I don't know how else to name it.

public class Luhn {
 public static void main(String[] args) {
 System.out.println(validate(1762483));
 }
 public static boolean validate(int id){
 int totalSum = 0;
 while(id>0){
 totalSum += id%10;
 id /= 10;
 if(id>0){
 totalSum += getLuhn(id%10);
 id /= 10;
 }
 }
 return (totalSum%10 == 0);
 }
 private static int getLuhn(int id){
 id *= 2;
 return id%10 + id/10;
 }
}

Every comment is appreciated <3 From cleaner code, over more idiomatic Java, to improvements in performance.

• tgdavies: As the parameter to getLuhn is in the range [0..9] you could replace it with a lookup table, or memoize it. That might be faster.
• tgdavies: You could also look at java.lang.Integer.toString() for some tricks to convert a number to individual digits more efficiently.

Answer 1

There is not much to improve in your code, it's compact and efficient. These are few suggestions:

Input validation

When the input number is negative the result is always true. To avoid confusion you can launch an exception.

public static boolean validate(int id) {
 if (id < 0) {
 throw new IllegalArgumentException("Input cannot be negative.");
 }
 // ..
}

Clarity

The Luhn Checksum algorithm is described very well on Wikipedia and by you on your question, but your implementation is not easy to follow. For example:

totalSum += id%10;

Here the last digit of id is added to totalSum. Adding a method (with the explanation of the operation in the name) makes it more readable:

totalSum += getRightMostDigit(id);

Same for:

id /= 10;

This operation removes the last digit of id, which can be changed to:

id = dropRightMostDigit(id);

I would also change the input variable name from id to number, but this is personal taste.

Perfomance

It's hard to improve performance and keep readability for your method. The only change I would suggest is to replace the getLuhn method with a static array.

This change makes it two times faster on my machine and gets rid of the additional method.

Code refactored

public static boolean validate(int number) {
 if (number < 0) {
 throw new IllegalArgumentException("Input cannot be negative.");
 }
 // Array containing:
 // - for index in [0,4]: the double of the index value 
 // - for index in [5,9]: the sum of the digits of the doubled index value. E.g. index = 6 -> 6*2 = 12 -> 1+2 = 3
 int[] luhn = new int[] { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
 
 int totalSum = 0;
 while (number > 0) {
 totalSum += getRightMostDigit(number);
 number = dropRightMostDigit(number);
 if (number > 0) {
 totalSum += luhn[getRightMostDigit(number)];
 number = dropRightMostDigit(number);
 }
 }
 return totalSum % 10 == 0;
}
private static int getRightMostDigit(int number) {
 return number % 10;
}
private static int dropRightMostDigit(int number) {
 return number / 10;
}

Personal opinion

Many implementations of the Luhn Checksum accept a String as input, so they can be used to validate credit cards or simply to operate on numbers bigger than an int. What is the use case of your algorithm?

The purpose of your implementation can also be included as a comment, it will help others to understand whether they need it or not.

• elauser: Thank you for the answer, really appreciate it. For clarity, what do you mean by the behaviour doesn't match the description?
• Marc: @elauser I updated my answer
• elauser: Great Idea to extract the % and / to functions. Uncle Bob would be proud ;) I'd say that's the max amount of readability. And The perfect use case for a useful comment.
• Marc: @elauser thanks. Please consider picking an answer when you are satisfied ;)

Answer 2

Extracting each digit of a number is very similar to the operations performed by the JDK when a number is converted to a String. As many smart people must have spent time optimising this, I used the same code as used by Integer.toString().

As they did, I used a lookup table to avoid arithmetic operations where the range of input values was small.

This takes a third of the time on my machine as the original code.

It is certainly not easier to read or understand, trading clarity for speed.

package org.example;
public class Luhn {
 /*
 * A table which translates integers from 0..99 to the 10s place digit
 * with the 'Luhn' function applied to it
 */
 static final int[] LuhnDigitTens = {
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
 } ;
 static final int[] DigitOnes = {
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 };
 static final int[] Luhn = {
 0, 2, 4, 6, 8,
 1, 3, 5, 7, 9
 };
 public static void main(String[] args) {
 // check results are the same
 for (int i = 0; i < 176248300; i++) {
 if (validate2(i) != validate(i)) {
 throw new RuntimeException("Different at " + i);
 }
 }
 long start = System.currentTimeMillis();
 for (int i = 0; i < 176248300; i++) {
 validate(i);
 }
 System.out.println(System.currentTimeMillis() - start);
 start = System.currentTimeMillis();
 for (int i = 0; i < 176248300; i++) {
 validate2(i);
 }
 System.out.println(System.currentTimeMillis() - start);
 }
 public static boolean validate(int id){
 int totalSum = 0;
 while(id>0){
 totalSum += id%10;
 id /= 10;
 if(id>0){
 totalSum += getLuhn(id%10);
 id /= 10;
 }
 }
 return (totalSum%10 == 0);
 }
 private static int getLuhn(int id){
 id *= 2;
 return id%10 + id/10;
 }
 public static boolean validate2(int i){
 int q, r;
 int totalSum = 0;
 i = -i;
 // Generate two digits per iteration
 while (i <= -100) {
 q = i / 100;
 r = (q * 100) - i;
 i = q;
 totalSum += DigitOnes[r];
 totalSum += LuhnDigitTens[r];
 }
 // We know there are at most two digits left at this point.
 q = i / 10;
 r = (q * 10) - i;
 totalSum += r;
 // Whatever left is the remaining digit.
 if (q < 0) {
 totalSum += Luhn[-q];
 }
 return (totalSum%10 == 0);
 }
}

• dariosicily: Welcome to Code Review. At the moment you are providing an alternate solution with no explanation or justification and your answer could be deleted, see how-to-answer for further informations. To avoid this possibility you could explain you reasoning, moreover I have seen you already made significative comments in the OP's question explaining the reason of your implementation.
• tgdavies: Thanks @dariosicily, I have improved the explanation.
• dariosicily: You are welcome.
• user33306: There is a further minor optimization for your algorithm. Place the values in DigitTens in the same order they are in Luhn, then call DigitTens[r] instead of Luhn[DigitTens[r]].
• tgdavies: Thanks @tinstaafl, I've added that.