C Question --- Stumped on Solution to Exercise from a Book (KN King)

Hi All,

I have a question that is related to Arduino on the periphery. (C for beginner’s is related, right?)

I have been teaching myself C with the 1st Edition of this book by KN King. https://www.amazon.com/Programming-Approach-K-N-King/dp/0393969452/ref=asap_bc?ie=UTF8

I am currently on chapter 7, and I am really stumped on the question I pasted below.

I found a solution that works (tested the output in Visual Studio) from this discussion topic that took place over 10 years ago: Re: [C] Reading and arithmetic with getchar()

The solution definitely works, but I am unsure what the reasoning is for the line with the statement that goes "digit = ch - ‘0’; " The solver provided some sparse notes. I do understand that you can look at charts converted numbers to ASCII character values, and that 0 is indeed 48 in ASCII.

I am just scratching my head why he’s subtracting ‘0’ from the input variable ch.

Can someone walk me through what’s happening in that While loop?

I pasted the question and solution below. And to preserve formatting, I also attached a word Doc with formatting

Many thanks in advance!!!


Question Text
11). Airline tickets are assigned lengthy identifying numbers, such as 47715497443. To be valid, the last digit of the number must match the remainder when the other digits—as a group—are divided by 7

Example: (4 + 7 + 7 + 1 + 5 + 4 + 9 + 7 + 4 + 4) % 7 = 3 /* modulo, not division */

For example, 4771549744 divided by 7 yields the remainder of 3.

Write a program that checks whether or not an airline ticket number is valid
Hint: Don’t attempt to read the number in a single step.

Instead, use getchar to obtain its digits one by one. Carry out the division one digit at a time, being careful not to include the last digit in division.


Solution from: Re: [C] Reading and arithmetic with getchar()

#include <stdio.h>
			#include <ctype.h>           /* for access to the toupper function */
			
			main()
			{
				char ch;                                 /*char is the ticket number */
				int digit;                               /*digit represents the last digit in ticket number */
				int dividend;
				int remainder = 0;                       /*remainder is the remainder of (sum of all but last digit) % 7 */
			
				printf("Enter ticket number: ");
			
				while ((ch = getchar()) != '\n')  {       /* 1 is 49 in ASCII.   0 is 48 in ASCII.    49 - 48 = 1  */
					
					digit = ch - '0';                    /* equivalent to ch - 48  */
			
					dividend = (remainder * 10) + digit;
					
					if (dividend >= 7)
						remainder = dividend % 7;
					else
						remainder = dividend;
				}
			
				remainder = (dividend - digit) / 10;       /* We recover the reminder before using the check digit */
			
				if (remainder == digit)
					printf("VALID\n");
				else
					printf("INVALID\n");
			
				printf("ch: %d\n", ch);
				printf("digit: %d\n", digit);
				printf("dividend: %d\n", dividend);
				printf("remainder: %d\n", remainder);
			
				return 0;
			}

Airline ticket question.pdf (561 KB)

The solution definitely works, but I am unsure what the reasoning is for the line with the statement that goes "digit = ch - ‘0’; " The solver provided some sparse notes. I do understand that you can look at charts converted numbers to ASCII character values, and that 0 is indeed 48 in ASCII.

Suppose that ch contains ‘7’. What is the ASCII value for 7? What is that value minus 48? Is it not 7?

The solution relies on the fact that the ASCII characters are ordered and that ‘0’ to ‘9’ are consecutive ASCII codes. So if you want to know the value of ‘7’ you simply subtract the value ‘0’ from it to get 7, as has already been stated.

The same is true for the letters ‘a’ to ‘z’ and ‘A’ to ‘Z’, they are all in alphabetic order

PaulS: Suppose that ch contains '7'. What is the ASCII value for 7? What is that value minus 48? Is it not 7?

The ASCII value for 7 is 55. 55 minus 48 is indeed 7, but I'm still having trouble mentally connecting that to the loop.

I would try tracing the program, but Visual Studio is giving me a weird error message when I enter the debugger

I’m still having trouble mentally connecting that to the loop

Examine each step one by one and figure out what the author intended. If 7 is the result ‘7’ - ‘0’, then how is that result used in the very next program line, and why?

potomac: Can someone walk me through what's happening in that While loop?

Do you remember in school when you learned to do division by putting the divisor (7) outside a bracket, and then inside the bracket you wrote the dividend (4771549744).

Then, you'd go, "7 goes into 4 zero times with 4 left over."

"7 goes into 47 6 times, with 5 left over."

"7 goes into 57 8 times with 1 left over."

"7 goes into 11 1 time with 4 left over" . . . "7 goes into 24 3 times with 3 left over".

That's what the while loop is doing.

marco_c: The same is true for the letters 'a' to 'z' and 'A' to 'Z', they are all in alphabetic order

The range '0' - '9' is contiguous and ordered. The range 'A' - 'Z' is contiguous and ordered. The range 'a' - 'z' is contiguous and ordered.

But the union of these three ranges is not contiguous. That's important to remember when doing conversions, you have to test which range the value is in first before doing your math.

I could not believe what I was seeing in the question posed by the poster! Back in the 1970's, I worked for a computer service company owned by a large Oregon Bank. It was later absorbed by other banks. The checking account numbers for the bank consisted of the 5 digit number plus a "check digit", mod 7. Just like in the original question. The bank would occasionally send over an order for us to print several hundred more account numbers for them.

On one order, I returned comments with the new numbers to the effect they only had a few hundred usable numbers left. They could not comprehend that only 70% of the 99,999 numbers could be used and began a program to issue new numbers with "real" mod check digits.

So, the book example given is actually a real-life example. The bank was never able to find who came up with the original mod 7 scheme.

Paul

What is unbelievable about it? VINs and credit card numbers have check digits for verifying that they are correct and a type wasn't made when transcribing one.

Jiggy-Ninja: What is unbelievable about it? VINs and credit card numbers have check digits for verifying that they are correct and a type wasn't made when transcribing one.

Real check digits detect transpositions as well as incorrect digits. A mod 7 detects nothing. Credit cards imbed the check digit within the number, not append it on the end, so people are not aware it has a check digit. At least, MAstercard did.

Paul

Paul_KD7HB: Real check digits detect transpositions as well as incorrect digits. A mod 7 detects nothing. Credit cards imbed the check digit within the number, not append it on the end, so people are not aware it has a check digit. At least, MAstercard did.

Paul

Good point. In calculating a VIN's check digit (which is also buried in the middle of the number), after the letters are converted to the appropriate number each number is multiplied be a weighting factor that is different for each position, and then they are summed and the mod 11 is taken. Transposing two digits will put them at different weights and possibly change the sum.

It's not the best check scheme since they only use 11 digits instead of the full 33 if they used every letter and number, so the chance of collision after a change is still high.

Thanks all. I see know why the subtraction of ‘0’ is there. It was staring at me the entire time in the ASCII chart. See highlighting in pink below

However, I’m still confused on the rest of the loop that comes after it.

Is Getchar starting running each digit (from left to right) and running it through the While loop?

For example, in the output picture below for the airline ticket number 55554, would it run 5 through the loop, then 5, then 5, then 5, then 4? All through this, the previous digit that was read affects the remainder variable?

output.png

potomac: For example, in the output picture below for the airline ticket number 55554, would it run 5 through the loop, then 5, then 5, then 5, then 4? All through this, the previous digit that was read affects the remainder variable?

I'm not quite sure what you are not getting here - maybe it's the way that the modulo operation obeys the distributive law. It might be easier to understand it with 10 than with 7.

Let's say we have a series of numbers,

8
5
28
345
19

and your job is to add them together and work out the remainder of that sum when you divide it my 10. This particular set of numbers sums to 405, and so you are after 5 as the solution.

Ok, first I'll put some zeros on the front:

008
005
028
345
019

Now, I hope you can see that all your really need to do is worry about that final digit. 8+5+8+5+9 is 35, which has a final digit of 5. Furthermore, you can just keep a running sum and discard any 10s as you go: 8, +5 is 13, remainder is 3, +8 is 11 remainder is 1, +5 is 6, +9 is 15 remainder 5. We are just keeping that final digit.

Now, here's the thing: mathematically, there is nothing special about the number ten. Oh sure, it's special to the way we customarily write numbers down. But it's not special to the nunbers themselves. The method of keeping a running sum of just the remainder works for any number, including seven.

Paul_KD7HB: Real check digits detect transpositions as well as incorrect digits. A mod 7 detects nothing. Credit cards imbed the check digit within the number, not append it on the end, so people are not aware it has a check digit. At least, MAstercard did.

Paul

Have any evidence for that? Luhn check digits go at the end.

https://web.eecs.umich.edu/~bartlett/credit_card_number.html

MarkT: Have any evidence for that? Luhn check digits go at the end.

https://web.eecs.umich.edu/~bartlett/credit_card_number.html

I had to meditate on this for quite a while! Way back, in the 1970s, I was on the bank card committee of the Oregon bank. They were trying to decide on visa or Mastercard. We studied everything about the cards. The bank would accept the paper transactions from merchants. So, I recall distinctly the check digit was not at the end of the number on the card.

Looking at your link, I see we are both right! What I was seeing was the 2 digit member number following the account number. My card was 01, my wife's card was 02. The link shows the check digit at the end of the primary account number and it is. then comes the two digit member number.

As an aside, I recall one funny thing that happened. The committee had to review all the advertising and info sent to customers. When Mastercard began to use pseudo checks with the card number on them, the bank had stuffers printed up to tell the checking account holders about the new product and how these "checks" could be used ANYWHERE a regular check could be used. I studied the paper, then asked if they really could be used anywhere a normal check could be used? They said "sure". I pointed out a regular check could be used to pay their Mastercard bill and did they really want to allow this? They quickly put more language on the ad to exclude card payment.

Paul

the other digits---as a group---are divided by 7 Example: (4 + 7 + 7 + 1 + 5 + 4 + 9 + 7 + 4 + 4) % 7 = 3 /* modulo, not division */ For example, 4771549744 divided by 7 yields the remainder of 3.

I'm finding the question really ambiguous. I would not interpret "digits as a group" and "sum of the digits" as meaning the same thing. The last two sentences above will yield (in general) different results. (that PARTICULAR string of digits happens you yield 3, either way. But consider "10", for example. (1+0)%7 = 1 and 10%7 = 3)

Most of the respondees have been assuming "sum of digits", which I think is somewhat easier. "as a group" will in fact detect at least some mis-ordering as well (01 and 10 have different remainders.)

(Ah, memories. Once, I wrote a check-digit function for a TI SR52 programmable calculator (the one that read programs from little magnetic cards.) Doing the sort of "per digit" math involved on a calculator without integer math was ... amusing.)

westfw: I'm finding the question really ambiguous. I would not interpret "digits as a group" and "sum of the digits" as meaning the same thing. The last two sentences above will yield (in general) different results. (that PARTICULAR string of digits happens you yield 3, either way. But consider "10", for example. (1+0)%7 = 1 and 10%7 = 3)

I agree westfw. I believe that the check that is supposed to be done there is this:

  1. The number (sans its final digit) must match its own digit sum : modulo 7.
  2. The modulo 7 result from the above is stored as the final digit.