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

YAL10CI (Yet Another LUHN-10 Checksum Implementation)

by larryl (Scribe)
on Mar 12, 2001 at 07:23 UTC ( #63727=snippet: print w/ replies, xml ) Need Help??

Description:

This snippet does a LUHN-10 checksum calculation for testing credit card numbers. I did this a while ago when I was trying to eke a bit more oomph out of some e-commercey scripts I've got.

It benchmarks about three times faster than the implementations in both Jon Orwant's Business::CreditCard and Sean Burke's luhn_lib.pl. Anyone got any ideas to make it even faster?

Note: I hear chop() may be deprecated in Perl 6. If so, you could always use substr() instead to pick off the last digit, but chop() benchmarks faster for me than substr() in this case.

# Pre-define a mapping for the alternate digits
# (rather than calculate sums in the loop every time):
my @LUHN10_map = ( 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 );

# Return 1 if input number passes LUHN-10
# checksum test, otherwise return 0.
sub LUHN10
{
   # NOTE: Assumes input consists only of digits.
   my $number = shift;
   my $sum = 0;
   my $length = length $number;

   # Sum the digits working from right to left.
   # Replace with mapped values for alternate
   # digits starting with second from right:
   while ( $length > 1 ) {
      $sum += chop $number;
      $sum += $LUHN10_map[ chop $number ];
      $length -= 2;
   }
   $sum += $number if $length;  # one digit left
                                # if length was odd

   # Result for valid number must end in 0:
   return ( ( $sum % 10 ) == 0 ) ? 1 : 0;
}
Comment on YAL10CI (Yet Another LUHN-10 Checksum Implementation)
Download Code
Re: YAL10CI (Yet Another LUHN-10 Checksum Implementation)
by johannz (Hermit) on Mar 12, 2001 at 10:56 UTC
    This isn't faster (Actually, ~50% slower), but it is smaller. I found it interesting that the entire LUHN10 function you wrote was faster then doing a split on the number and using 'for' to only sum it, without the real math thrown in. With that kind of speed advantage that chop offers you over array processing, I can't see any OBVIOUS ways of making this any faster. And I tried. You might get some incremental increases from golfing the problem, but this seems to be a tight algorithm. I was using perl 5.6.0 from activestate for my testing.
    my @LUHN10_map = ( 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 ); sub johannz_LUHN10 { my @number = split('', shift); my ($sum, $pos) = (0, scalar(@number)); $sum += $pos--%2 ? $_ : $LUHN10_map[$_] for (@number); ($sum % 10 == 0) ? 1 : 0; }
(dkubb) Re: (2) YAL10CI (Yet Another LUHN-10 Checksum Implementation)
by dkubb (Deacon) on Mar 12, 2001 at 15:47 UTC

    Your algorythm is very fast. Congratulations! I tried to come up with something close in speed to what you have, but I could not. Instead I will submit my attempt in the hopes that it might spawn off an idea for someone else:

    sub dkubb_LUHN10 { my $number = shift; my $sum; ($sum += chop $number) ... ($sum += $LUHN10_map[chop $number]) while $number ne ''; ($sum % 10 == 0) || 0; }

    Update: The last line was: $sum % 10 || 0;

      This algorith fails on '49927398716' in my test case. That was the code given on the LUHN-10 website. It comes up with a sum of 62 when it should be a sum of 70 per the original algorithm.

      I am curious if you can explain how the

      ($sum += chop $number) ... ($sum += $LUHN10_map[chop $number]) while $ +number ne '';
      logic works. I just (like 1 minute ago) learned about the bi-stable operator.


      While typing this, I figured out why this failed my test case. The call to '...' is persistant across subroutine calls. In my test case, I use

      ('125', '49927398716', '4992739872')
      and it failed on '49927398716'. When I used
      ('125', '49927398716', '49927398716','4992739872')
      it failed on the 1st '49927398716' and on '4992739872' so I can only assume this operator maintains its state.

      UPDATE: This also fails on '620' since the bi-stable does not flip state if the side that is being evaluated returns false(or 0). So a number ending in '0' will not be processed correctly.

        johannz you are right! I had no idea the range operator (...) was persistent across subroutine calls. I expected it to maintain it's state while inside the while loop, but reset itself each time the subroutine was called.

        perlop gives an explanation of the ... operator. It's definately something I have not used much before, or seen used, so I wanted to give it a try.

        While I was trying to figure out why my example didn't work in all cases, I came up with the following that returned the correct values during testing:

        sub dkubb_LUHN10 { my $number = shift || return 0; my $sum; $sum += chop($number) + $LUHN10_map[chop $number] while "$number"; ($sum % 10 == 0) || 0; }
YYAL10CI
by gryng (Hermit) on Mar 12, 2001 at 22:09 UTC
    When in doubt add another table:

    my @luhnmap_1 = (0,2,4,6,8,1,3,5,7,9); my @luhnmap_2 = (); for my $x (0..9) { for my $y (0..9) { @luhnmap_2[$y*10+$x]=$luhnmap_1[$y]+$x; } } sub LUHN10 { my $num = shift; my $sum = 0; while ($str = substr $num, -2, 2, "") { $sum+=$bigmap[$str]; } return $sum % 10 ? 0 : 1; }

    As bonus, if you don't count the additional table code (aw, come on, please :) ), it's shorter! You can increase this speed some more if you want, but the only way to get a huge increase is to create a bigger table (instead of 10 or 100 elements, try 10,000!). Not sure if it's worth going the next step (the memory and upfront cost).

    Enjoy,
    Gryn

Re: YAL10CI (Yet Another LUHN-10 Checksum Implementation)
by petral (Curate) on Mar 13, 2001 at 01:36 UTC
    Isn't
    return not chop $sum
    faster than
    return $sum % 10...
    Or does it fail in some cases I'm not thinking of?

    p

Back to Snippets Section

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: snippet [id://63727]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (5)
As of 2014-12-20 05:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (95 votes), past polls