Optimizing Luhn check digit algorithm

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:

1. Computing the double and then subtract 9 if above 9 of every second digit seems to cry for a lookup-table.
2. 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.

• List lookup is faster than dict lookup:

$python -m timeit -s "c = {i: i for i in range(10)}" "c[3]" 10000000 loops, best of 5: 30 nsec per loop$ python -m timeit -s "c = {i: i for i in range(10)}" "c[9]"
10000000 loops, best of 5: 30.2 nsec per loop

$python -m timeit -s "c = [i for i in range(10)]" "c[3]" 10000000 loops, best of 5: 26.3 nsec per loop$ python -m timeit -s "c = [i for i in range(10)]" "c[9]"
10000000 loops, best of 5: 26.6 nsec per loop

• Removing the if and instead using zip yields a speed up too.

It doesn't matter too much whether you build the list with [] * len(input_) or using itertools.cycle.

It does matter that the tables be the second item in the zip, otherwise the speed can fluctuate to being slower than 'Overkill'.

• Replacing reversed with a slice is the same speed, even though it removes a function call.
• It doesn't look like tuple lookup is faster than list lookup.

And so this is the fastest I could get:

import itertools

class Luhn:
CHECK_DIGIT_LUT = ("0", "9", "8", "7", "6", "5", "4", "3", "2", "1")
SUM_MOD10_LUT = [
{str(j): (i + j) % 10 for j in range(10)}
for i in range(10)
]
SUM_DOUBLE_MOD10_LUT = [
{str(j): (i + (0, 2, 4, 6, 8, 1, 3, 5, 7, 9)[j]) % 10 for j in range(10)}
for i in range(10)
]

@classmethod
def calculate_lut_overkill(cls, input_):
"""Calculate the check digit using Luhn's algorithm"""
sum_ = 0
for digit, table in zip(
reversed(input_),
itertools.cycle([
cls.SUM_DOUBLE_MOD10_LUT,
cls.SUM_MOD10_LUT,
]),
):
sum_ = table[sum_][digit]
return cls.CHECK_DIGIT_LUT[sum_]


My timings were:

LuhnBase 0.581
LuhnOverkill 0.279
LuhnPeilList 0.271
LuhnPeilTables 0.201
LuhnPeilAltTables 0.202
LuhnPeilItertools 0.207
LuhnPeilAltItertools 0.203
LuhnPeilSlice 0.204

• So just to be sure that I understood you correctly: the difference between LuhnPeilList and LuhnPeilTables came from getting rid of the if? Jun 12, 2019 at 6:22
• Seems like it's a combination of enumerate, i % 2, and if that makes up the time difference. Just throwing in an unneccessary enumerate in your fastest solution slows it down about 25-30% on my laptop (4.5µs → 5.8µs). Jun 12, 2019 at 7:13
• @AlexV Yes Table removed enumerate, i % 2 and if, Alt means the positions of the zip are reversed. Itertools means the argument to zip uses itertools rather than a list. Jun 12, 2019 at 8:22
• @AlexV You should perform all timeits multiple times and take the minimum, as LuhnPeilTables randomly went from 0.2 to 0.35, because I had other things running on my PC. I repeated each timeit 10 times. Jun 12, 2019 at 8:24
• I cannot guarantee that I really did 10 runs of each timeit, but definitely between 5 to 10 with short pauses in between to give the laptop some time for other workloads to happen. The negative effect of enumerate seemed to persist. Jun 12, 2019 at 9:23

Peilonrayz was so kind to show and explain some of the steps taken in the optimization process for me to better follow along in chat. I wanted to preserve them if the chat room ever goes to die.

The following code pieces are supposed to be used with the Luhn class as presented in the question or Peilonrayz' answer to be able to access the look-up tables.

def luhn_peil_list(cls, input_):
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_]

def luhn_peil_without_if(cls, input_):
tables = [cls.SUM_DOUBLE_MOD10_LUT, cls.SUM_MOD10_LUT]
sum_ = 0
for i, digit in enumerate(reversed(input_)):
sum_ = tables[i % 2][sum_][digit]
return cls.CHECK_DIGIT_LUT[sum_]

def luhn_peil_without_if_enumerate(cls, input_):
tables = [cls.SUM_DOUBLE_MOD10_LUT, cls.SUM_MOD10_LUT]
sum_ = 0
for digit, i in zip(reversed(input_), range(len(input_))):
sum_ = tables[i % 2][sum_][digit]
return cls.CHECK_DIGIT_LUT[sum_]


With the following timings:

LuhnPeilList 0.281
LuhnPeilWithoutIf 0.254
LuhnPeilWithoutIfEnumerate 0.29


The conclusion of these results were:

This shows that removing the if leads to a 0.027 speedup. Changing from enumerate to zip however is slower than with the speedup. So enumerate is faster.

In the following discussion if enumerate was to blame for those major performance differences between the different versions, Peilonrayz went on to produce the following variants:

def luhn_peil_without_if_mod(cls, input_):
tables = [cls.SUM_DOUBLE_MOD10_LUT, cls.SUM_MOD10_LUT] * ((len(input_) + 1) // 2)
sum_ = 0
for i, digit in enumerate(reversed(input_)):
sum_ = tables[i][sum_][digit]
return cls.CHECK_DIGIT_LUT[sum_]

def luhn_peil_without_if_mod_enumerate(cls, input_):
tables = [cls.SUM_DOUBLE_MOD10_LUT, cls.SUM_MOD10_LUT] * ((len(input_) + 1) // 2)
sum_ = 0
for digit, table in zip(reversed(input_), tables):
sum_ = table[sum_][digit]
return cls.CHECK_DIGIT_LUT[sum_]


Timing:

LuhnPeilWithoutIfMod 0.23
LuhnPeilWithoutIfModEnumerate 0.208


The difference between LuhnPeilWithoutIfMod and LuhnPeilWithoutIfModEnumerate is that table[i] is slow in Python, but fast in C. The speed increase outweighs the speed increase enumerate has over zip.

Further mentioning that luhn_peil_without_if_mod_enumerate is found the same as LuhnPeilAltTables (mine, Peilonrayz') and concluding that

"It doesn't matter too much whether you build the list with [] * len(input_) or using itertools.cycle."

• Thank you for writing this up for me. :) I've commented here so if anyone disagrees with this analysis they can ping me. Jun 23, 2019 at 21:53
• Hey, @AlexV I've removed all the pronouns from this post. There should be no loss of content, as pronouns are short hand for nouns but mostly unneeded. I hope this change is ok with you. Thank you :) Mar 6, 2020 at 2:04