Re^4: Faster Luhn Check Digit Calculation?

[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 :)

[LanX]

> Looks like you've found a nice project to occupy your Sunday :)

Nay!

You know the saying: mathematicians are like eunuchs. ;)

I leave the "fun" - especially with C - to the engineers here ...

> six digits would only reduce by one 

Well you were the one talking about a general approach with unknown input length.

[LanX]

> 10k lookup string

FWIW this could be halved to 5k by addressing nibbles instead of bytes.

4 bits are more than enough to encode 10 digits.