Validating card credit numbers

Question

I've been trying to create a program that can check if a credit card number is valid or not based on Hans Peter Luhn's algorithm. However, I can only get it to work for some inputs.

// Loop through every digit in the card number
for ( int i = 0; i < intlen (num); ++i )
{
    nextDigit = getDigit (num, i);

    // If every other number...
    if ( i % 2 )
    {
        nextDigit *= 2;

        // ...times by two and add the individual digits to the total
        for ( int j = 0; j < intlen (nextDigit); ++j )
        {
            total += getDigit (nextDigit, j);
        }
    }
    else
    {
        total += nextDigit;
    }
}

When I use the AMEX card number 378282246310005 it works fine and tells the user it's valid. However, once I try the VISA card number 4012888888881881 it says it's invalid. I tried to do a sanity check and do it manually to see if my program was wrong but I deduced the same result. These card number were taken from the Paypal test credit card numbers page so I know they are valid.

So what am I doing wrong?

---

To clarify the details by the program, if total modulo 10 == 0 then the card number is valid.

Functions called:

// Function to return length (number of digits) of an int

int intlen (long long n)
{
    int len = 1;

    // While there is more than 1 digit...
    while ( abs (n) > 9 )
    {
       // ...discard leading digits and add 1 to len
       n /= 10;
       ++len;
    }

    return len;
}

// Function to return a digit in an integer at a specified index

short getDigit (long long num, int index)
{
    // Calculating position of digit in integer
    int pos = intlen (num) - index;

    // Discard numbers after selected digit
    while ( pos > 1 )
    {
        num /= 10;
        --pos;
    }

    // Return right-most digit i.e. selected digit
    return num % 10;
}

Answer 1

While I was looking at this to find the bug, I re-wrote the program to make it a bit simpler. As a side-effect this will be much faster.

We need to grab digits from the right anyway. We don't even need to count the digits; just keep pulling off the right-most digit until the number becomes 0. If the number starts out as 0, the checksum is trivially 0 and the code is still correct.

I grabbed all the numbers from the test page. This seems to be correct, except for one number: 76009244561 (listed as "Dankort (PBS)" in the test page). I tried this number with the Python code from the Wikipedia page, and again this number is rejected. I don't know why this number is different from the others.

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

bool check_one(long long num)
{
    int checksum = 0;
    int i = 1;

    for (int i = 1; num; num /= 10, ++i)
    {
        int d = num % 10;

        if (i % 2 == 0)
        {
            // even digit: double and add digits of doubled value
            d *= 2;
            if (d < 10)
            {
                // only one digit: we doubled a 0-4 so number is 0-8
                checksum += d;
            }
            else
            {
                // two digits: we doubled a 5-9 so number is 10-18
                checksum += (d % 10);
                checksum += (d / 10);
            }
        }
        else
        {
            // odd digit: just add
            checksum += d;
        }
    }
    return (checksum % 10) == 0;
}

static long long const valid_nums[] = 
{
    378282246310005,
    371449635398431,
    378734493671000,
    5610591081018250,
    30569309025904,
    38520000023237,
    6011111111111117,
    6011000990139424,
    3530111333300000,
    3566002020360505,
    5555555555554444,
    5105105105105100,
    4111111111111111,
    4012888888881881,
    4222222222222,
    76009244561,
    5019717010103742,
    6331101999990016,
};

static size_t len_valid_nums = sizeof(valid_nums) / sizeof(valid_nums[0]);

static long long const non_valid_nums[] = 
{
    378282246310006, // add 1 to valid
    371449635398432,
    378734493671001,
    5610591081018205, // swap last two digits
    30569309025940,
    38520000023273,
    601111111111111, // delete last digit
    601100099013942,
    353011133330000,
};

static size_t len_non_valid_nums =
        (sizeof(non_valid_nums) / sizeof(non_valid_nums[0]));


main()
{
    bool f;

    for (int i = 0; i < len_valid_nums; ++i)
    {
        long long num = valid_nums[i];
        f = check_one(num);
        if (!f)
        {
            printf("Number %lld considered invalid but should be valid\n", num);
        }
    }

    for (int i = 0; i < len_non_valid_nums; ++i)
    {
        long long num = non_valid_nums[i];
        f = check_one(num);
        if (f)
        {
            printf("Number %lld considered valid but should be invalid\n", num);
        }
    }
}

Answer 2

You'll want to change i % 2 to i % 2 == intlen (num) % 2 or similar; you should double every second digit, but starting from the right; i.e. excluding the final check digit:

From the rightmost digit, which is the check digit, moving left, double the value of every second digit; …

The reason the AMEX number you tried validated anyway is because it's an odd number of digits; the same digits get doubled regardless of whether you skip from the front or the back.