Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Faster Luhn Check Digit Calculation?

by kschwab (Vicar)
on Nov 30, 2018 at 17:13 UTC ( #1226543=perlquestion: print w/replies, xml ) Need Help??
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).

Replies are listed 'Best First'.
Re: Faster Luhn Check Digit Calculation?
by BrowserUk (Pope) 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.
    "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
    In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit

      It is a little faster than my previous Perl attempts...

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

        Sorry. I didn't account for 0-based indices! This produces the correct result:

        #! 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.
        "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
        In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit
Re: Faster Luhn Check Digit Calculation?
by AnomalousMonk (Chancellor) 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:  <%-{-{-{-<

      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; }

        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:  <%-{-{-{-<

      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.

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

        ... 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:  <%-{-{-{-<

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

      > Hopefully I didn't miss any of you in the CREDITS section

      Corian ? ;-)

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

Re: Faster Luhn Check Digit Calculation?
by kschwab (Vicar) on Nov 30, 2018 at 17:48 UTC

    Found a slightly different implementation here: https://github.com/bdlightner/luhn-implementation-Perl-

    But, it's a little slower:

    $ 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:
      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; }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1226543]
Approved by dorko
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (2)
As of 2018-12-14 04:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    How many stories does it take before you've heard them all?







    Results (64 votes). Check out past polls.

    Notices?