3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$
  • 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
\$\endgroup\$
  • \$\begingroup\$ So just to be sure that I understood you correctly: the difference between LuhnPeilList and LuhnPeilTables came from getting rid of the if? \$\endgroup\$ – AlexV Jun 12 at 6:22
  • \$\begingroup\$ 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). \$\endgroup\$ – AlexV Jun 12 at 7:13
  • \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Jun 12 at 8:22
  • \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Jun 12 at 8:24
  • \$\begingroup\$ 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. \$\endgroup\$ – AlexV Jun 12 at 9:23
1
\$\begingroup\$

Peilonrayz was so kind to show and explain some of the steps he has 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 his 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

His conclusion on this 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 he also 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

And his reasoning:

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.

He also goes on to mention that luhn_peil_without_if_mod_enumerate is found in his answer as LuhnPeilAltTables (mine, his) and lead him to his conclusion that

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for writing this up for me. :) I've commented here so if anyone disagrees with this analysis they can ping me. \$\endgroup\$ – Peilonrayz Jun 23 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.