|
kschwab has asked for the wisdom of the Perl Monks concerning the following question:
Trying to see if there's a faster way to generate the LUHN check digit that goes at the end of a credit card number. At the moment, I'm using this, cribbed from Algorithm::LUHN, only change was removing some not-needed input verification.
my %map = map { $_ => $_ } 0..9;
sub check_digit {
my @buf = reverse split //, shift;
my $totalVal = 0;
my $flip = 1;
foreach my $c (@buf) {
my $posVal = $map{$c};
$posVal *= 2 unless $flip = !$flip;
while ($posVal) {
$totalVal += $posVal % 10;
$posVal = int($posVal / 10);
}
}
return (10 - $totalVal % 10) % 10;
}
# example use
for (401135000000000..401135000000099) {
my $cd=check_digit($_);
print "$_$cd\n";
}
You give it the first 15 digits of a credit card number, and it calculates the 16th digit. It's reasonably fast now, calculating about 135,000 cc numbers per second (older i7), but would like to see if there's anything that might speed it up, other than running more than one instance (already doing that, but trying to focus on just the single core speed here). |
Re: Faster Luhn Check Digit Calculation?
by AnomalousMonk (Archbishop) on Dec 01, 2018 at 06:37 UTC
|
I agree Inline::C will be fastest, but lookup tables can help a pure-Perl implementation a lot.
LUHN.pm:
test_LUHN_1.pl:
Output:
c:\@Work\Perl\monks\kschwab>perl test_LUHN_1.pl
tested cc number range kschwab vs. AnomalousMonk ok
tested cc number range kschwab vs. BrowserUk ok
Rate cd_kschwab cd_BrowserUk cd_AM
cd_kschwab 52764/s -- -40% -62%
cd_BrowserUk 88033/s 67% -- -37%
cd_AM 139999/s 165% 59% --
Update: My solution and some of the others are hard-wired for generating a checksum for a 15-digit string. Here's a generalized variation. Caution: this is not well tested. Also, I don't know that I like the @check_digit look-up array all that much; it might chew up a lot of space in certain circumstances. BrowserUk's $total *= 9; return chop $total; eats less space and is only very slightly slower than the lookup.
sub cd_AM_HOP { # iterator solution
my ($n_digits, # n of digits for which to generate luhn checksum
) = @_;
my $order = $n_digits & 1;
my @straight = grep +($_ & $order), 0 .. $n_digits-1; # dd '---',
+ \@straight;
my @adjusted = grep !($_ & $order), 0 .. $n_digits-1; # dd '===',
+ \@adjusted;
my @check_digit = map { (10 - $_ % 10) % 10 } 0 .. 9 * $n_digits;
return sub {
my $ccn = shift; # digits for which to generate checksum
my $total = 0;
for (@straight) {
$total += substr($ccn, $_, 1);
}
for (@adjusted) {
$total += $x2_cast_out_9[ substr($ccn, $_, 1) ];
}
# return $check_digit[ $total ]; # return check digit
$total *= 9;
return chop $total; # return check digit
}; # end sub iterator
}
Give a man a fish: <%-{-{-{-<
| [reply]
[d/l]
[select] |
|
|
Converted a hardcoded version of yours to Inline::C, and it's pretty much the same performance as BrowserUK's Inline::C:
$ perl ./script
Benchmark: timing 500 iterations of Inline::C (AnomalousMonk), Inline::C (BrowserUK)...
Inline::C (AnomalousMonk): 6 wallclock secs ( 6.21 usr + 0.00 sys = 6.21 CPU) @ 80.52/s (n=500)
Inline::C (BrowserUK): 6 wallclock secs ( 6.14 usr + 0.00 sys = 6.14 CPU) @ 81.43/s (n=500)
Appreciate it! Conversion below:
int cd4( char *ccn ) {
int total = 0;
int i;
int co9[]={0,2,4,6,8,1,3,5,7,9};
int straight[]={1,3,5,7,9,11,13};
int adjusted[]={0,2,4,6,8,10,12,14};
for (i=0;i<7;i++) {
total += ccn[straight[i]]-48;
}
for (i=0;i<8;i++) {
total += co9[ccn[adjusted[i]]-48];
}
total *=9;
return total %10;
}
| [reply]
[d/l] |
|
|
Here's another twist that might squeeze out a few more computrons: use array literals (if that's the correct terminology; introduced with C99 IIRC; I assume Inline::C supports C99) to compile the arrays rather than building local arrays on each subroutine call (if you don't want to just declare the arrays static| static const, which also works | should work). I haven't looked at the assembler output, but the idea (the hope?) is that the compiler would make these statics. There are two versions of the function below; both work. One is more heavily macro-ized because I wanted to see how far I could push this approach; for reasons of maintainability, I'm not sure I'd want it in production code. Only minimal testing has been done; I leave that to you :).
t_array_literal_1.c:
Give a man a fish: <%-{-{-{-<
| [reply]
[d/l]
[select] |
|
|
| [reply] |
|
|
... 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: <%-{-{-{-<
| [reply]
[d/l]
[select] |
|
|
|
|
|
Re: Faster Luhn Check Digit Calculation?
by BrowserUk (Patriarch) on Nov 30, 2018 at 19:40 UTC
|
I doubt it'll beat the C version, but I think it should beat the Perl versions and the algorithm (which I think is correct but haven't verified) would readily convert to C:
sub luhn {
my $total = 0;
for my $i ( 0 .. length $_[0] ) {
my $d = substr $_[0], $i, 1 );
if( $i & 1 ) {
$d *= 2;
$s -=9 if $d > 10;
}
$total += $d;
}
$total *= 9;
return substr $total, -1
}
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
In the absence of evidence, opinion is indistinguishable from prejudice.
Suck that fhit | [reply]
[d/l] |
|
|
Benchmark: timing 100 iterations of BrowserUK, Inline::C, Algorithm::LUHN...
BrowserUK: 46 wallclock secs (46.03 usr + 0.00 sys = 46.03 CPU) @ 2.17/s (n=100)
Inline::C: 1 wallclock secs ( 1.28 usr + 0.00 sys = 1.28 CPU) @ 78.12/s (n=100)
Algorithm::LUHN: 49 wallclock secs (48.58 usr + 0.00 sys = 48.58 CPU) @ 2.06/s (n=100)
But, it's not producing the right checksum digit. It should produce:
4011350000000008
4011350000000016
4011350000000024
4011350000000032
4011350000000040
4011350000000057
4011350000000065
4011350000000073
4011350000000081
4011350000000099
...
But, it's producing:
4011350000000000
4011350000000019
4011350000000028
4011350000000037
4011350000000046
4011350000000055
4011350000000064
4011350000000073
4011350000000082
4011350000000091
...
| [reply] |
|
|
#! perl -slw
use strict;
my @samples = qw[
4011350000000008
4011350000000016
4011350000000024
4011350000000032
4011350000000040
4011350000000057
4011350000000065
4011350000000073
4011350000000081
4011350000000099
];
sub luhn {
my $total = 0;
for my $i ( 0 .. length( $_[0] ) -1 ) {
my $d = substr( $_[0], $i, 1 );
unless( $i & 1 ) {
$d *= 2;
$d -=9 if $d > 9;
}
$total += $d;
}
$total *= 9;
return substr $total, -1
}
for ( @samples ) {
print "$_ : ", luhn( substr $_, 0, 15 );
}
__END__
C:\test>luhn
4011350000000008 : 8
4011350000000016 : 6
4011350000000024 : 4
4011350000000032 : 2
4011350000000040 : 0
4011350000000057 : 7
4011350000000065 : 5
4011350000000073 : 3
4011350000000081 : 1
4011350000000099 : 9
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
In the absence of evidence, opinion is indistinguishable from prejudice.
Suck that fhit | [reply]
[d/l] |
|
|
|
|
|
|
|
Re: Faster Luhn Check Digit Calculation?
by kschwab (Vicar) on Nov 30, 2018 at 19:14 UTC
|
Ok, so I tried Inline::C and it blows everything else away. Using the same 10 iterations, it doesn't run long enough for a decent benchmark. So changed to 100 iterations and it's under 2 seconds, where my best Perl implementation is taking 51 seconds.
Benchmark: timing 100 iterations of Inline::C, Algorithm::LUHN...
Inline::C: 2 wallclock secs ( 1.26 usr + 0.00 sys = 1.26 CPU) @ 79.37/s (n=100)
Algorithm::LUHN: 51 wallclock secs (51.57 usr + 0.00 sys = 51.57 CPU) @ 1.94/s (n=100)
| [reply]
[d/l] |
Up on CPAN
by kschwab (Vicar) on Dec 02, 2018 at 22:19 UTC
|
Made this into an XS module, and it's up on CPAN as Algorithm::LUHN_XS. Hopefully I didn't miss any of you in the CREDITS section. It's using one of the slower C implementations because of some unique requirements like handling non-numeric data, but still significantly faster than the original.
Thanks again all.
| [reply] |
|
|
> Hopefully I didn't miss any of you in the CREDITS section
Corian ? ;-)
| [reply] |
|
|
| [reply] |
Re: Faster Luhn Check Digit Calculation?
by kschwab (Vicar) on Nov 30, 2018 at 17:48 UTC
|
$ perl ./script
Benchmark: timing 10 iterations of Algorithm::LUHN, bdlightner...
Algorithm::LUHN: 7 wallclock secs ( 6.89 usr + 0.00 sys = 6.89 CPU) @ 1.45/s (n=10)
bdlightner: 8 wallclock secs ( 7.69 usr + 0.00 sys = 7.69 CPU) @ 1.30/s (n=10)
The benchmark code and both implementations:
| [reply]
[d/l] |
|
|
Noticible improvement from simplifying what was in Algorithm::LUHN with "use integer"
Benchmark: timing 10 iterations of Algorithm::LUHN, Tweaked Algorithm::LUHN, bdlightner...
Algorithm::LUHN: 6 wallclock secs ( 6.63 usr + 0.00 sys = 6.63 CPU) @ 1.51/s (n=10)
Tweaked Algorithm::LUHN: 5 wallclock secs ( 5.25 usr + 0.00 sys = 5.25 CPU) @ 1.90/s (n=10)
bdlightner: 8 wallclock secs ( 7.81 usr + 0.00 sys = 7.81 CPU) @ 1.28/s (n=10)
# tweaked Algorithm::LUHN with "use integer" and some simplification
sub cd3 {
use integer;
my $total = 0;
my $flip = 1;
foreach my $c (reverse split //, shift) {
$c *= 2 unless $flip = !$flip;
while ($c) {
$total += $c % 10;
$c = $c / 10;
}
}
return (10 - $total % 10) % 10;
}
| [reply]
[d/l] |
|
|
