Re^2: Faster Luhn Check Digit Calculation?

[LanX]

Lookup tabled were my first idea too ... but why not a string of digits together at the same time?

Am I missing something?

6 digits are 1 million entries, probably using substr is even faster than array lookup, for sure it's demanding less memory.

[AnomalousMonk]

... why not a string of digits together at the same time?

If I correctly understand what you're saying, something like
    my $check_digits = join '', map { chr((10 - $_ % 10) % 10) } 0 .. 9 * $n_digits;
    ...
    return substr $check_digits $total, 1;
(returning the check digit as a character) certainly would be a more memory-conservative approach than using an array of, e.g., 136 numbers. However, my suspicion is that when you get through with the substr call, you've burned about as much time as with the just-as-simple  $total *= 9;  return chop $total; calls.

6 digits are 1 million entries ...

I don't understand this point: where do the 1 million entries come from? Would you be building a lookup string from every possible 6-digit combination? The OPed question posited 15 digits; that's a really long string.

[LanX]

To be clearer, I suppose that

L("XXYY") = ( L("XX") + L("YY") ) % 10

for all even length substrings XX and YY

=> a divide and conquer could be applied

=> computation complexity replaced with memory complexity.

> The OPed question posited 15 digits; that's a really long string.

One would do 3 lookups, leading zeros of the left most chunk shouldn't influence the checksum.

L("XX") = L("0XX") = L("00XX") ) = ...

> where do the 1 million entries come from?

6 digits sound like a good compromise, you'd need even amount and 100 Meg for 8 digits sound exaggerated. (A Perl array has an factor 10 overhead IIRC)

Anyway a C algorithm which fits into the line cache of the processor might still be faster.

Not sure if a 10k string for a 4 digit partition would always fit into the L1 cache.

update

the best approach might be a C program which dynamically benchmarks different chunk sizes to test the effect of line caches before building the lookup table.

[AnomalousMonk]

L("XXYY") = ( L("XX") + L("YY") ) % 10

for all even length substrings XX and YY ...

I think I see where you're going, and I think you're right. Even with just a 0 .. 9999 / 10K character lookup string, a 13-16 digit number's Luhn checksum character could be found with four substr lookups, three adds and a mod; likely quite fast. Going to six digits would only reduce by one lookup and one add; I'm not sure it would be worth the memory. Looks like you've found a nice project to occupy your Sunday :)