The internet as a whole and Code Review in special already provide a decent amount of implementations of the Luhn check digit algorithm. They often follow a relatively “naive” strategy, in that they are mostly straightforward translations of the algorithm’s pseudo-code (as found e.g. on Wikipedia), like below:

`class Luhn: @staticmethod def calculate_naive(input_): """Calculate the check digit using Luhn's algorithm""" sum_ = 0 for i, digit in enumerate(reversed(input_)): digit = int(digit) if i % 2 == 0: digit *= 2 if digit > 9: digit -= 9 sum_ += digit return str(10 - sum_ % 10) `

I chose `6304900017740292441`

(the final `1`

is the actual check digit) from this site about credit card validation as example to validate the coming changes. The mini-validaton and timing of this implementation generated the following results:

`assert Luhn.calculate_naive("630490001774029244") == "1" %timeit -r 10 -n 100000 Luhn.calculate_naive("630490001774029244") 13.9 µs ± 1.3 µs per loop (mean ± std. dev. of 10 runs, 100000 loops each) `

This algorithm IMHO lends itself to some optimizations. I came up with the following ones:

- Computing the double and then subtract 9 if above 9 of every second digit seems to cry for a lookup-table.
- The string-to-int and int-to-string conversion also seem like low hanging fruits for a lookup-table too, since the number of values is relatively limited.

This lead to the following code:

`class Luhn: DOUBLE_LUT = (0, 2, 4, 6, 8, 1, 3, 5, 7, 9) # CHECK_DIGIT_LUT = tuple(str(10 - i) for i in range(10)) CHECK_DIGIT_LUT = ("0", "9", "8", "7", "6", "5", "4", "3", "2", "1") # STR_TO_INT_LUT = {str(i): i for i in range(10)} STR_TO_INT_LUT = { '0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9 } @classmethod def calculate_lut1(cls, input_): """Calculate the check digit using Luhn's algorithm""" sum_ = 0 for i, digit in enumerate(reversed(input_)): digit = int(digit) sum_ += digit if i % 2 else cls.DOUBLE_LUT[digit] return str(10 - sum_ % 10) @classmethod def calculate_lut12(cls, input_): """Calculate the check digit using Luhn's algorithm""" sum_ = 0 for i, digit in enumerate(reversed(input_)): digit = cls.STR_TO_INT_LUT[digit] sum_ += digit if i % 2 else cls.DOUBLE_LUT[digit] return cls.CHECK_DIGIT_LUT[sum_ % 10] `

This piece of code was also validated and timed:

`assert Luhn.calculate_lut1("630490001774029244") == "1" %timeit -r 10 -n 100000 Luhn.calculate_lut1("630490001774029244") 11.9 µs ± 265 ns per loop (mean ± std. dev. of 10 runs, 100000 loops each) assert Luhn.calculate_lut12("630490001774029244") == "1" %timeit -r 10 -n 100000 Luhn.calculate_lut12("630490001774029244") 7.28 µs ± 166 ns per loop (mean ± std. dev. of 10 runs, 100000 loops each) `

I found the second result especially suprising, decided to go full berserk and went on to try to precompute as much as possible.

Since all digits of the sum apart from the last one are irrelevant, the possible intermediate results can all be pre-computed $ mod\,10$ .

Enter this behemoth:

`class Luhn: # ... other code from above, e.g. CHECK_DIGIT_LUT SUM_MOD10_LUT = { i: {str(j): (i + j) % 10 for j in range(10)} for i in range(10) } SUM_DOUBLE_MOD10_LUT = { i: {str(j): (i + (0, 2, 4, 6, 8, 1, 3, 5, 7, 9)[j]) % 10 for j in range(10)} # ^ I don't like this. But doesn't seem to work with DOUBLE_LUT for i in range(10) } @classmethod def calculate_lut_overkill(cls, input_): """Calculate the check digit using Luhn's algorithm""" sum_ = 0 for i, digit in enumerate(reversed(input_)): if i % 2: sum_ = cls.SUM_MOD10_LUT[sum_][digit] else: sum_ = cls.SUM_DOUBLE_MOD10_LUT[sum_][digit] return cls.CHECK_DIGIT_LUT[sum_] `

`assert Luhn.calculate_lut_overkill("630490001774029244") == "1" %timeit -r 10 -n 100000 Luhn.calculate_lut_overkill("630490001774029244") 5.63 µs ± 200 ns per loop (mean ± std. dev. of 10 runs, 100000 loops each) `

This is were I stopped, shivered, and decided to go to The Happy Place.

Leaving aside the old wisdom on “premature optimization”: What I would like to know now is if there are any aspects that might be optimized further that I haven’t thought?

Would you let the later stages of the code pass in a code review? Especially the last one seems to be a good candidate for confusion. Should there be more explanation on how the lookup-tables came to be?

Of course all thoughts and feedback whatsoever are much appreciated.

This post is part of a (developing?) mini-series on check digit algorithms. You may also want to have a look at part 1 *Verhoeff check digit algorithm*.