The Luhn Algorithm

While I was working on barcode recognition software, I suddenly realized that in many barcode symbologies, the Luhn algorithm is used for check digit creation or verification. In the barcode context it is often called “mod 10 checksum”. There is a very nice article http://en.wikipedia.org/wiki/Luhn_algorithm on Wikipedia explaining the algorithm. Another particularly nice article written by Oz can be found at http://nextbit.blogspot.com/2007/06/doing-luhn-checksum-simply.html. I have taken his code and ported it to C++.

I had a short look into the U.S. patent 2950048 that Hans Peter Luhn has filed in 1954. I have not read I fully, but it appears that he invented a mechanical computer – he called it handheld then – to check whether a number had the correct check digit.

The Luhn algorithm not only is used in many barcode symbologies, but is also used with credit card numbers. The last digit of a credit card number is calculated with the Luhn algorithm.

While my barcode experiments had nothing to do with credit cards, I still found it worthwhile to test the algorithm with credit card numbers. I found a bunch of credit card numbers on Graham King’s blog at http://www.darkcoding.net/credit-card-numbers. As Graham King puts it: “These are NOT valid credit card numbers. You can’t buy anything with these. They are random numbers that happen to conform to the MOD 10 algorithm. They are a technical resource for programmers – that’s all.“ The numbers can be found in the luhn sample application.

Here is a step by step description of how the Luhn algorithm works.

And here is the code that verifies if a number has a correct check digit according to the Luhn formula.

/// Check a string according to the Luhn formula.
//!
//! The Luhn formula describes a checksum method that is widely used in
//! various applications, such as credit card numbers or barcodes. It is
//! described at http://en.wikipedia.org/wiki/Luhn_algorithm.
//!
//! This code has been ported from a version written in C by Oz that can be
//! found at
//! http://nextbit.blogspot.com/2007/06/doing-luhn-checksum-simply.html.
//!
//! /return true if the number is valid according to the Luhn formula,
//! false otherwise.
inline bool check_luhn_formula(
  /// The number in the form of a string. No spaces are allowed in the string.
  std::string const& number)
{
  int ltab[10] = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };

  if (number.size() < 2)
    return false;

  std::string::const_iterator i = number.begin();
  int sum = 0;

  if (number.size() & 1)
    sum = *i++ - '0';

  while (i!=number.end())
  {
    sum += ltab[*i++ - '0'];
    sum += *i++ - '0';
  }

  return 0 == (sum % 10);
}