Tuesday, August 4, 2009

Extremely Fast Luhn Function for C# (Credit Card Validation)

If you want to validate that a credit card number is valid, you need to use the Luhn algorithm. It uses the last digit in the card number and calculates a checksum to ensure the number is valid. (Obviously this doesn't ensure that the card actually works, only that the number seems real.)

Everyone and their mother has posted a .NET/C# version of Luhn, but they were all really drawn out and slow. I initially settled on this one by Paul Ingles hosted on CodeProject., since at least his code was commented and readable. I shortened it up and eliminated some blocks of code and variables, making it easier for me to follow, but without any change in performance. Then I swapped in some tricks to speed it up about 4x (cast char to int and subtract 48 to get the integer version of a number that starts as a char string).

I felt this was good enough, but then I stumbled upon this pseudo code for Luhn algorithm by Cliff L. Biffle. Not only is it much, much shorter, but it was about another 8x faster than my code! I went from validating 100,000 numbers in 550ms to 100,000 in 15ms, a 37x speed increase!

I wrote a C# function implementing the pseudocode, and here it is below.


/// Extremely fast Luhn algorithm implementation, based on
/// pseudo code from Cliff L. Biffle (http://microcoder.livejournal.com/17175.html)
///
/// Copyleft Thomas @ Orb of Knowledge:
/// http://orb-of-knowledge.blogspot.com/2009/08/extremely-fast-luhn-function-for-c.html

///

private static bool IsValidNumber(string number)
{
int[] DELTAS = new int[] { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 };
int checksum = 0;
char[] chars = number.ToCharArray();
for (int i = chars.Length - 1; i > -1; i--)
{
int j = ((int)chars[i]) - 48;
checksum += j;
if (((i - chars.Length) % 2) == 0)
checksum += DELTAS[j];
}

return ((checksum % 10) == 0);
}

That's it!

16 comments:

Anonymous said...

First, let me say... freakin' brilliant! As I was reading it, my OCD-brain went into optimizer mode and tweaked it even more. Theoretically I got about another 8% speed increase (and added a little error checking), and thought I'd share. :)

// Moved the declaration outside the loop just in case the compiler decides to do something stupid
int j = 0;
bool bOdd = true;

for (int i = chars.Length - 1; i > -1; i--)
{
j = ((int)chars[i]) - 48;

// If the character wasn't numeric, then just return false
if ((j < 0) || (j > 9)) return false;

checksum += j;

// This loses us the subtraction and mod operations on each iteration and switches to a bitwise/logic operator
if (bOdd) checksum += DELTAS[j];
bOdd = !bOdd;
}

Anonymous said...

I love it when a somebody says "I made a lot of optimizations, it's xxx times faster now." and somebody else takes a quick look and says "What about this <> operation?" / "What about this declaration inside the loop?" I really love this. Congratulations, Anonymous!

Steve said...

somewhere in the modified version is a bug. it isn't generating the correct checksum. If I get a chance, I'll try to track it down.

Anonymous said...

If i understand the algorithm correctly, it adds up each alternate digit starting from the right most digit.

I think there are two solutions to the bug:

1) bool bOdd = false;
2) if (!bOdd) checksum += DELATS[j]

Either of these should fix teh bug.

.

I Think that will fix the error.

Alexandar Velkov said...

@Thomas, if you take the DELTAS and checksum variables out of the method it will perform faster because it wouldn't have to allocate those variables for each time the method is used.

Anonymous said...

how about cutting some time off the (redundant) checks for the alternate digits? we know it's every two digits, so:

int[] DELTAS = new int[] { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
int checksum = 0;
char[] chars = number.ToCharArray();

for (int i = chars.Length - 1; i > 0; i = i - 2)
{
checksum += ((int)chars[i]) - 48;
}

for (int i = chars.Length - 2; i > -1; i = i - 2)
{
checksum += DELTAS[((int)chars[i]) - 48];
}

return ((checksum % 10) == 0);


try it, i think it shaves some more time off.
TTHEO

Anonymous said...

TTHEO, your solution seems to work on 16 digit cards, but it doesn't work for AMEX.

Anonymous said...

I think there is an optimization available...

The % 2 is a drag. Should probably re-write to set a bool with initial value false, and just check that - every time through the loop toggle.

private static bool IsValidNumber(string number)
{
int[] DELTAS = new int[] { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 };
int checksum = 0;
bool doubleDigit = false;

char[] chars = number.ToCharArray();
for (int i = chars.Length - 1; i > -1; i--)
{
int j = ((int)chars[i]) - 48;
checksum += j;

if (doubleDigit)
{
checksum += DELTAS[j];
}
doubleDigit = !doubleDigit;
}

return ((checksum % 10) == 0);
}

Adam Schaible said...

Actually, two more minor enhancements...

checksumAnswers is an array similar to deltas, but has true at every index divisible by 10, and false at all others. This is probably not helpful if you want to check in the scope of a web page request or something .. but if you are writing a program that will be able to store the checksumAnswers into RAM and keep it there, that will get you out of the expensive mod operation (and it's still better than the compiler tricks that will change the mod into division with a constant denominator).

The other change: xor 48 seems to be about 10% faster than - 48... small but worthwhile.

private static bool IsValidNumber(string number)
{
int[] DELTAS = new int[] { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 };
int checksum = 0;
bool doubleDigit = false;

char[] chars = number.ToCharArray();
for (int i = chars.Length - 1; i > -1; i--)
{
int j = chars[i] ^ 0x30;

checksum += j;

if (doubleDigit)
{
checksum += DELTAS[j];
}
doubleDigit = !doubleDigit;
}

return checksumAnswers[checksum];
}

KevinS said...

Just noting some numbers and a comment.

The currently posted alg in blog: 82 ticks

Adam Schaible's alg: 82 ticks

Adam Schaible's alg minus checksumAnswers (use %10): 79 ticks

These timings were gotten through the Stopwatch class.

If you want to try the checksumAnswers way, you only need an array 145 long. (assuming a 16 digit credit card number of all 9's)

private static bool[] m_abChecksumAnswers = null;

private static void BuildChecksumAnswers()
{
List abChecksumAnswers = new List();

for( int i=0; i < 145; i++ )
{
abChecksumAnswers.Add( i % 10 == 0 );
}

m_abChecksumAnswers = abChecksumAnswers.ToArray();
}

Thank you all for your work in making this fast. I'll keep looking myself, but I think to make it faster would take a revolutionary approach. This path has probably hit an evolutionary dead end. ;)

KevinS said...

LOL

Ok I said it was at an evolutionary dead end, and then I immediately see a way to speed it up.

Move deltas to a static readonly class variable.

private static readonly int[] m_anDELTAS = new int[] { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 };

And the tick cost of the method goes down to 61.

---

And then I go, wait, I wonder if using checksumAnswers from a static readonly variable would help...

Here are the results avging over a 1000

Blogs alg: 70.273 ticks
Adams Alg minus checksumAnswers: 69.458 ticks
+static readonly DELTAS: 45.624 ticks
+static readonly checksumAnswers: 31.878 ticks

---

Here is my final alg as it stands.

private static readonly int[] m_anDELTAS = new int[] { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 };

private static readonly bool[] m_abChecksumAnswers = new bool[] { true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true,
false,false,false,false,false,false,false,false,false,true};

private static bool IsCreditCardNumberValid( string strCreditCardNumber )
{
int checksum = 0;
bool doubleDigit = false;

char[] chars = strCreditCardNumber.ToCharArray();
for( int i = chars.Length - 1; i > -1; i-- )
{
int j = chars[i] ^ 0x30;

checksum += j;

if( doubleDigit )
{
checksum += m_anDELTAS[j];
}

doubleDigit = !doubleDigit;
}

return m_abChecksumAnswers[checksum];
}

Enjoy all!!!

Hugh said...
This comment has been removed by the author.
Hugh said...
This comment has been removed by the author.
Hugh said...

I should learn to read properly... I think I might try to replicate this in a line myself :)

Anonymous said...

what about card type?

Anonymous said...

Here are a few additional ones, featuring partly unrolled loops, just for kicks. Both fix the issue with card numbers longer than 16 digits, if such are allowed/possible. If you don't require this, remove the last if.. for an additional minimal speed bump


public static bool Luhn2(string cardNumber)
{
int checksum = 0;
int i = 0;

char[] chars = cardNumber.ToCharArray();
int len = chars.Length;

bool evenLength = len % 2 == 0;

// odd length -> count the first char separately
if (!evenLength)
{
i = 1;
checksum = chars[0] ^ 0x30;
}

int j;
for(; i < len; i += 2)
{
j = chars[i] ^ 0x30;
checksum += j;
checksum += Deltas[j];

j = chars[i + 1] ^ 0x30;
checksum += j;
}

if (checksum >= ChecksumAnswers.Length)
return checksum % 10 == 0;

return ChecksumAnswers[checksum];
}

public static bool Luhn4(string cardNumber)
{
int checksum = 0;
int i = 0;

char[] chars = cardNumber.ToCharArray();
int len = chars.Length;

int quadMod = len % 4;

int j;

// odd length -> count the first char separately
switch ( quadMod )
{
case 0:
break;

case 1:
i = 1;
checksum = chars[0] ^ 0x30;

break;

case 2:
i = 2;
checksum = chars[0] ^ 0x30;

j = chars[1] ^ 0x30;
checksum += j;
checksum += Deltas[j];

break;

case 3:
i = 3;
checksum = chars[0] ^ 0x30;

j = chars[1] ^ 0x30;
checksum += j;
checksum += Deltas[j];

checksum += chars[2] ^ 0x30;
break;
}

for ( ; i < len; i += 4 )
{
j = chars[i] ^ 0x30;
checksum += j;
checksum += Deltas[j];

j = chars[i + 1] ^ 0x30;
checksum += j;

j = chars[i + 2] ^ 0x30;
checksum += j;
checksum += Deltas[j];

j = chars[i + 3] ^ 0x30;
checksum += j;
}

if (checksum >= ChecksumAnswers.Length)
return checksum % 10 == 0;

return ChecksumAnswers[checksum];
}