I'm trying to code a program that can tell apart real and fake credit card numbers using Luhn's algorithm in C, which is
- Multiply every other digit by 2, starting with the number’s second-to-last digit, and then add those products’ digits together.
- Add the sum to the sum of the digits that weren’t multiplied by 2.
- If the total’s last digit is 0 (or, put more formally, if the total modulo 10 is congruent to 0), the number is valid!
Then I coded something like this (I already declared all the functions at the top and included all the necessary libraries)
//Luhn's Algorithm
int luhn(long z)
{
int c;
return c = (sumall(z)-sumodd(z)) * 2 sumall(z);
}
//sum of digits in odd position starting from the end
int sumodd(long x)
{
int a;
while(x)
{
a = a x % 10;
x /= 100;
}
return a;
}
//sum of all digits
int sumall(long y)
{
int b;
while(y)
{
b = b y % 10;
y /= 10;
}
return b;
}
But somehow it always gives out the wrong answer even though there's no error or bug detected. I came to notice that it works fine when my variable z stands alone, but when it's used multiple times in the same line of code with different functions, their values get messed up (in function luhn). I'm writing this to ask for any fix I can make to make my code run correctly as I intended.
I'd appreciate any help as I'm very new to this, and I'm not a native English speaker so I may have messed up some technical terms, but I hope you'd be able to understand my concerns.
CodePudding user response：
sumall is wrong.
It should be sumeven from:
Add the sum to the sum of the digits that weren’t multiplied by 2.
Your sumall is summing all digits instead of the non-odd (i.e. even) digits.
You should do the * 2 inside sumodd as it should not be applied to the other [even] sum. And, it should be applied to the individual digits [vs the total sum].
Let's start with a proper definition from https://en.wikipedia.org/wiki/Luhn_algorithm
The check digit is computed as follows:
- If the number already contains the check digit, drop that digit to form the "payload." The check digit is most often the last digit.
- With the payload, start from the rightmost digit. Moving left, double the value of every second digit (including the rightmost digit).
- Sum the digits of the resulting value in each position (using the original value where a digit did not get doubled in the previous step).
- The check digit is calculated by
10 − ( s mod 10 )
Note that if we have a credit card of 9x where x is the check digit, then the payload is 9.
The correct [odd] sum for that digit is: 9 * 2 --> 18 --> 1 8 --> 9
But, sumodd(9x) * 2 --> 9 * 2 --> 18
Here's what I came up with:
// digsum -- calculate sum of digits
static inline int
digsum(int digcur)
{
int sum = 0;
for (; digcur != 0; digcur /= 10)
sum = digcur % 10;
return sum;
}
// luhn -- luhn's algorithm using digits array
int
luhn(long z)
{
char digits[16] = { 0 };
// get check digit and remove from "payload"
int check_expected = z % 10;
z /= 10;
// split into digits (we use little-endian)
int digcnt = 0;
for (digcnt = 0; z != 0; digcnt, z /= 10)
digits[digcnt] = z % 10;
int sum = 0;
for (int digidx = 0; digidx < digcnt; digidx) {
int digcur = digits[digidx];
if ((digidx & 1) == 0)
sum = digsum(digcur * 2);
else
sum = digcur;
}
int check_actual = 10 - (sum % 10);
return (check_actual == check_expected);
}
// luhn -- luhn's algorithm using long directly
int
luhn2(long z)
{
// get check digit and remove from "payload"
int check_expected = z % 10;
z /= 10;
int sum = 0;
for (int digidx = 0; z != 0; digidx, z /= 10) {
int digcur = z % 10;
if ((digidx & 1) == 0)
sum = digsum(digcur * 2);
else
sum = digcur;
}
int check_actual = 10 - (sum % 10);
return (check_actual == check_expected);
}
CodePudding user response：
You've invoked undefined behavior by not initializing a few local variables in your functions, for instance you can remove your undefined behaviour in sumodd() by initializing a to zero like so:
//sum of digits in odd position starting from the end
int sumodd(long x)
{
int a = 0; //Initialize
while(x)
{
a = x % 10; //You can "a = b" instead of "a = a b"
x /= 100;
}
return a;
}
It's also important to note that long is only required to be a minimum of 4-bytes wide, so it is not guaranteed to be wide enough to represent a decimal-16-digit-integer. Using long long solves this problem.
Alternatively you may find this problem much easier to solve by treating your credit card number as a char[] instead of an integer type altogether, for instance if we assume a 16-digit credit card number:
int luhn(long long z){
char number[16]; //Convert CC number to array of digits and store them here
for(int c = 0; c < 16; c){
number[c] = z % 10; //Last digit is at number[0], first digit is at number[15]
z /= 10;
}
int sum = 0;
for(int c = 0; c < 16; c = 2){
sum = number[c] number[c 1] * 2; //Sum the even digits and the doubled odd digits
}
return sum;
}
...and you could skip the long long to char[] translation part altogether if you treat the credit card number as an array of digits in the whole program
CodePudding user response：
This expression:
(sumall(z)-sumodd(z)) * 2 sumall(z);
Should be:
((sumall(z)-sumodd(z)) * 2 sumodd(z));
Based on your own definition.
But how about:
(sumall(z) * 2 - sumodd(z))
If you're trying to be smart and base off sumall(). You don't need to call anything twice.
Also you don't initialise your local variables. You must assign variables values before using them in C.
Also you don't need the local variable c in the luhn() function. It's harmless but unnecessary.
As others mention in a real-world application we can't recommend enough that such 'codes' are held in a character array. The amount of grief caused by people using integer types to represent digit sequence 'codes' and identifiers is vast. Unless a variable represents a numerical quantity of something, don't represent it as an arithmetic type. More issue has been caused in my career by that error than people trying to use double to represent monetary amounts.
#include <stdio.h>
//sum of digits in odd position starting from the end
int sumodd(long x)
{
int a=0;
while(x)
{
a = a x % 10;
x /= 100;
}
return a;
}
//sum of all digits
int sumall(long y)
{
int b=0;
while(y)
{
b = b y % 10;
y /= 10;
}
return b;
}
//Luhn's Algorithm
int luhn(long z)
{
return (sumall(z)*2-sumodd(z));
}
int check_luhn(long y,int expect){
int result=luhn(y);
if(result==expect){
return 0;
}
return 1;
}
int check_sumodd(long y,int expect){
int result=sumodd(y);
if(result==expect){
return 0;
}
return 1;
}
int check_sumall(long y,int expect){
int result=sumall(y);
if(result==expect){
return 0;
}
return 1;
}
int main(void) {
int errors=0;
errors =check_sumall(1,1);
errors =check_sumall(12,3);
errors =check_sumall(123456789L,45);
errors =check_sumall(4273391,4 2 7 3 3 9 1);
errors =check_sumodd(1,1);
errors =check_sumodd(91,1);
errors =check_sumodd(791,8);
errors =check_sumodd(1213191,1 1 1 1);
errors =check_sumodd(4273391,15);
errors =check_luhn(1234567890,((9 7 5 3 1)*2 (0 8 6 4 2)));
errors =check_luhn(9264567897,((9 7 5 6 9)*2 (7 8 6 4 2)));
if(errors!=0){
printf("*ERRORS*\n");
}else{
printf("Success\n");
}
return 0;
}