Re: Faster Luhn Check Digit Calculation?

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:

#!/usr/bin/perl
use Benchmark;
my %map = map { $_ => $_ } 0..9;
# cd1 is from https://metacpan.org/pod/Algorithm::LUHN
sub cd1 {
  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;
}
# cd2 is from: https://github.com/bdlightner/luhn-implementation-Perl-
sub cd2 {
    my($number) = @_;
    my($i, $sum, $ch, $num, $twoup, $len);
    $len = length($number);
    $sum = 0;
    $twoup = 1;
    for ($i = $len - 1; $i >= 0; --$i) {
        $ch = substr($number, $i, 1);
        $num = unpack('c', $ch) - 0x30;
        $num += $num if ($twoup);
        $num = int($num / 10) + ($num % 10) if ($num > 9);
        $sum += $num;
        $twoup = (++$twoup) & 1;
    }
    $sum = 10 - ($sum % 10);
    $sum = 0 if ($sum == 10);
    return $sum;
}
# example use:
my @range=(401135000000000..401135000099999);
timethese(10, {
    'Algorithm::LUHN' => sub { for(@range){cd1($_)} },
    'bdlightner' => sub { for(@range){cd2($_)} },
});
[download]

Comment on Re: Faster Luhn Check Digit Calculation? Download Code

Replies are listed 'Best First'.
Re^2: Faster Luhn Check Digit Calculation? by kschwab (Vicar) on Nov 30, 2018 at 18:08 UTC
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; }` [download]	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: Faster Luhn Check Digit Calculation?
by kschwab (Vicar) on Nov 30, 2018 at 18:08 UTC

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;
}
[download]

[reply]
[d/l]