Re^4: Faster Luhn Check Digit Calculation?

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.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery
FootballPerl is like chess, only without the dice}

Comment on Re^4: Faster Luhn Check Digit Calculation? Select or Download Code

Replies are listed 'Best First'.
Re^5: Faster Luhn Check Digit Calculation? by AnomalousMonk (Archbishop) on Dec 02, 2018 at 02:47 UTC
`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 :) Give a man a fish: `<%-{-{-{-<`	[reply] [d/l] [select]
Re^6: Faster Luhn Check Digit Calculation? by LanX (Saint) on Dec 02, 2018 at 02:59 UTC
> 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. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]
Re^6: Faster Luhn Check Digit Calculation? by LanX (Saint) on Dec 02, 2018 at 03:09 UTC
> 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. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]