Calculating a Luhn Check Digit

Question

I was able to find all kinds of examples that demonstrate how to validate a Luhn Checksum but very few that actually generated the check digit. Here is my attempt in base 10, based on the validation examples found at Wikipedia and Rosetta Code:

/// <summary>
/// Constructs the check digit for a given numeric string using the Luhn algorithm; also known as the "mod 10" algorithm.
/// </summary>
/// <param name="value">The string that a check digit will be calculated from.</param>
public static int Mod10(string value) {
    const int validCodePointCount = 10;
    const int validCodePointOffset = 48;

    var index = value.Length;
    var parity = true;
    var sum = 0;

    while (0 < index--) {
        var digit = (value[index] - validCodePointOffset);

        if (parity) {
            if ((validCodePointCount - 1) < (digit <<= 1)) {
                digit -= (validCodePointCount - 1);
            }
        }

        parity = !parity;
        sum += digit;
    }

    return ((validCodePointCount - (sum %= validCodePointCount)) % validCodePointCount);
}

Answer 1

All in all it seems OK to me. A couple of things though:

1)

  const int validCodePointCount = 10;
  const int validCodePointOffset = 48;

The names of these constants are hard to distinguish from each other and to understand in the context and they blur the behavior of the algorithm.

Better names could be:

const int numberBase = 10;
const int zero = '0';

Here I use '0' instead of 48 because the first is much more recognizable to programmers than the latter, and we instantly grasp the meaning. In fact in such a relatively small algorithm, I would prefer to use the literals directly in the code than the named constants like:

var digit = (value[index] - '0');

This is such a common operation and we all know what it's about immediately when seeing it.

In general it is wise to avoid magic numbers, but in some situations it is preferable in order to improve readability - IMO.

---

2)

You don't have to iterate backwards because you can determine the initial parity from the length of the input string:

var parity = value.Length % 2 != 0;

You can then iterate forward:

foreach (int n in value.Select(c => c - '0'))
{
  ...
  parity = !parity;
}

Answer 2

const int validCodePointCount = 10;
const int validCodePointOffset = 48;

Constants should be written in PascalCase, whether it is private or local.

while (0 < index--) {
var digit = (value[index] - validCodePointOffset);

What is this? A reverse foreach which could be written as foreach(var c in value.Reverse()). Also, the community standard for bracket placement is generally vertically aligned. (Although, this is more a question of style that you or your team follow.)

var digit = (value[index] - validCodePointOffset); // validCodePointOffset -> 48

A int.Parse could be used instead. While we are at it, there is no argument guard that ensures value will always be a string of digits.
edit: If you look to support an arbitrary set of characters, you can use a lookup table to map the character to its "numerical" value.

if ((validCodePointCount - 1) < (digit <<= 1)) {
    digit -= (validCodePointCount - 1);
}

It it really hard to understand what this code is trying to do. The wiki says: "If the result of this doubling operation is greater than 9, then add the digits of the product." This could be added as a comment to explain this bit of code. I wouldn't recommend using bit-shifting for simple multiplication. It adds an unnecessary layer in this case, when *= 2 could be used. Or, use code that is easier to read:

digit *= 2;
if (digit >= @base)
    digit = digit % @base + 1;

return ((validCodePointCount - (sum %= validCodePointCount)) % validCodePointCount);

10 - (x mod 10) can never exceed 10, so the last modulo operation is completely unnecessary. I would suggest replacing the validCodePointCount constant with its value. Unless there is a better variable name, which I have a lack of word for.
Again quoting the wiki: "The check digit (x) is obtained by computing the sum of the other digits (third row) then subtracting the units digit from 10."

---

private static readonly Dictionary<char, int> CharacterMap = 
    "0123456789"
        .Select((x,i) => (x,i))
        .ToDictionary(x => x.x, x => x.i);

public static int GetLuhnCheckSum(string value)
{
    if (!value.All(CharacterMap.ContainsKey))
        throw new ArgumentException("Value contains invalid characters", nameof(value));

    int @base = CharacterMap.Count;
    var parity = true;
    var sum = 0;

    // process the number from right to left
    foreach (var c in value.Reverse())
    {
        var digit = CharacterMap[c];

        // From the rightmost digit, which is the check digit, and moving left, double the value of every second digit.
        if (parity)
        {
            digit *= 2;

            // If the result of this doubling operation is greater than 9, then add the digits of the product.
            if (digit >= @base)
                digit = digit % @base + 1;
        }

        parity = !parity;
        sum += digit;
    }

    // The check digit (x) is obtained by computing the sum of the other digits then subtracting the units digit from 10
    return (@base - (sum % @base)) % @base;
}

---

edit: fixed check sum can be base instead of 0
edit: updated the code to support different base system

Answer 3

Review

Most tips and issues have already been addressed by fellow reviewers. I would like to add or re-iterate:

• when implementing an algorithm, you should always include unit tests
• when providing a public API, you should handle argument checks; in this case, check value against null and check each of its code points against the specified entropy - in this case ['0'-'9']
• when checking a string for a missing character, return a char rather than an int. Return '0' instead of 0, and so on.
• use clear and compact variable names to enhance readability
• develop for human beings rather than a computer to read your code: avoid statements that could introduce ambiguity for a human reader; while (0 < index--) makes people think about the order of operations (first comparison, or first decrementation)
• develop for extensibility; this algorithm only works for base 10, and it can't be reused for entropies where characters are not only digits and aren't necesseraly consecutive code points, as allowed by Luhn mod N generic case

---

Luhn mod N

Following the instructions at wikipedia, we can implement Luhn mod N as follows:

A converter is required, so we are not restricted to base 10 or digits only.

interface ICodePointConverter
{
    int CodePointFromCharacter(char character);
    char CharacterFromCodePoint(int codePoint);
    int NumberOfValidInputCharacters();
}

A default implementation could use lookup maps for both directions (int -> char and char -> int).

class MemoryCodePointConverter : ICodePointConverter
{
    IDictionary<int, char> characterByCodePointMap;
    IDictionary<char, int> codePointByCharacterMap;

    public int NumberOfValidInputCharacters() => characterByCodePointMap.Count;

    public static MemoryCodePointConverter FromEntropy(string entropy)
    {
        entropy = entropy ?? throw new ArgumentNullException(nameof(entropy));
        return new MemoryCodePointConverter(
            Enumerable.Range(0, entropy.Length).Select(i => (i, entropy[i])));
    }

    public MemoryCodePointConverter(
        IEnumerable<(int codePoint, char character)> entries)
    {
        entries = entries ?? throw new ArgumentNullException(nameof(entries));
        characterByCodePointMap = new Dictionary<int, char>();
        codePointByCharacterMap = new Dictionary<char, int>();

        foreach (var entry in entries)
        {
            characterByCodePointMap.Add(entry.codePoint, entry.character);
            codePointByCharacterMap.Add(entry.character, entry.codePoint);
        }
    }

    public char CharacterFromCodePoint(int codePoint)
    {
        if (!characterByCodePointMap
            .TryGetValue(codePoint, out var character))
        {
            throw new ArgumentException(
                $"Invalid code point {codePoint}", nameof(codePoint));
        }

        return character;
    }

    public int CodePointFromCharacter(char character)
    {
        if (!codePointByCharacterMap
            .TryGetValue(character, out var codePoint))
        {
            throw new ArgumentException(
                $"Invalid character {character}", nameof(character));
        }

        return codePoint;
    }
}

The algorithm can then be implemented given the pseudo code at wikipedia:

static class LuhnCheck
{
    public static char GenerateCheckCharacter(string input, ICodePointConverter converter)
    {
        converter = converter ?? throw new ArgumentNullException(nameof(converter));
        input = input ?? throw new ArgumentNullException(nameof(input));

        int factor = 2;
        int sum = 0;
        int n = converter.NumberOfValidInputCharacters();

        // Starting from the right and working leftwards is easier since 
        // the initial "factor" will always be "2" 
        for (int i = input.Length - 1; i >= 0; i--)
        {
            int codePoint = converter.CodePointFromCharacter(input[i]);
            int addend = factor * codePoint;

            // Alternate the "factor" that each "codePoint" is multiplied by
            factor = (factor == 2) ? 1 : 2;

            // Sum the digits of the "addend" as expressed in base "n"
            addend = (addend / n) + (addend % n);
            sum += addend;
        }

        // Calculate the number that must be added to the "sum" 
        // to make it divisible by "n"
        int remainder = sum % n;
        int checkCodePoint = (n - remainder) % n;

        return converter.CharacterFromCodePoint(checkCodePoint);
    }
}

Unit tests show us the results are the same for the luhn test mod 10 from OP.

[TestMethod]
public void Fixture()
{
    var input = "7992739871";
    var converter = MemoryCodePointConverter.FromEntropy("0123456789");

    // + '0' is required to get the character from the resulting code point
    var m1 = LuhnCheckOP.Mod10(input) + '0';
    var m2 = LuhnCheck.GenerateCheckCharacter(input, converter);

    Assert.AreEqual(m1, m2);
}