InsideDarkWeb.com

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

2 Answers

2 Answers

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.

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

Add your own answers!

Related Questions

Microservice in Springboot

1  Asked on February 1, 2021 by forhadmethun

         

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

 

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

   

Cave explorer: using stack

0  Asked on January 21, 2021 by sherloock

   

Largest odd number

5  Asked on January 17, 2021 by neisy-sofa-vadori

   

Calculator Program improvements

2  Asked on January 16, 2021 by the

     

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

   

Sudoku Game with automatically generated Sudokus

2  Asked on January 9, 2021 by philipp-wilhelm

   

Ask a Question

Get help from others!

© 2021 InsideDarkWeb.com. All rights reserved.