Re^3: Faster Luhn Check Digit Calculation?

... 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.

Give a man a fish: <%-{-{-{-<

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

Replies are listed 'Best First'.
Re^4: Faster Luhn Check Digit Calculation? by LanX (Saint) on Dec 02, 2018 at 02:01 UTC
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}	[reply] [d/l] [select]
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]

update