# Improvement to Luhn-Checksum Algorithm in Java

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.

Code Review Asked by elauser on November 11, 2021

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

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.

Answered by Marc on November 11, 2021

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

Answered by tgdavies on November 11, 2021

## Related Questions

### 10 Kinds of People

1  Asked on January 29, 2021 by martin-york

### Generating product variants in Ruby

1  Asked on January 29, 2021 by dcangulo

### Structuring code logic for events on laravel controller

2  Asked on January 28, 2021 by grey

### Handling Circular References Without Recursion

2  Asked on January 27, 2021 by kittoes0124

### vector<tuple > to map

1  Asked on January 25, 2021 by valerij

### naming convention for atomic design

0  Asked on January 23, 2021 by irohitbhatia

### An Implementation of Two Dimensional Plane as Monochromic Image Container with std::unique_ptr in C++

1  Asked on January 21, 2021 by jimmyhu

### Cave explorer: using stack

0  Asked on January 21, 2021 by sherloock

### Calculate the free electron concentration and drift speed in a segment of wire

2  Asked on January 18, 2021 by mode77

### List of Happy Numbers in scala

3  Asked on January 18, 2021 by vikrant

### Calculator Program improvements

2  Asked on January 16, 2021 by the

### JavaScript async/await function performance improvement

0  Asked on January 14, 2021 by nmsdvid

### Is this good c++ code for a pin/socket for a node editor?

1  Asked on January 12, 2021 by apoqlite

### Arduino-based darkroom timer

0  Asked on January 12, 2021 by marcellothearcane

### Finding the possible number of equal pairs in an array

1  Asked on January 11, 2021 by alaa-jabre

### Python : adding a columns with count of missing values by row

1  Asked on January 10, 2021 by lcrmorin

### Parallelized web crawler using goroutines and channels

1  Asked on January 10, 2021 by snowbody

### Sudoku Game with automatically generated Sudokus

2  Asked on January 9, 2021 by philipp-wilhelm