The Math Trick Hidden in Your Credit Card Number

​

All mainstream credit card numbers obey a mathematical trick designed to catch the most common typos. It’s called the Luhn algorithm, named after IBM researcher Hans Peter Luhn, who patented it in 1960.

 

The Math Trick Hidden in Your Credit Card Number
View attachment 354135​

I don't know that I would call it a math trick, though I supposed to the general public it probably seems like sophisticated magic.

Just adding up all of the digits and then tacking on whatever final digit is needed to make the result divisible by ten would catch all single-digit errors, which is the most likely error when manually entering a credit card number. But that check would not catch adjacent-digit transpositions, which are the second most common errors. So we need to do something different with adjacent digits so that the contributions to the final sum will be different if they are swapped. In this case, we double every other digit to break that symmetry. However, this implies that there is nothing special about doubling the digits -- that we could do almost anything to them, such as tripling them. But it's not that easy. We want whatever we do to contribute a different amount to the final sum for each possible digit value. Multiplying by two does this, but multiplying by three, for instance, would not. For example, if we multiply by 3, then a digit value of 2 would contribute 6 to the final sum, but so would 5 and 8.

Another feature we would like is that no modified digit contributes the same amount as it would if it were unmodified. If there were only one of these, then that wouldn't be a problem, but if we've accomplished the goal that having no two digits contribute the same amount to the final sum, then if we have one digit that contributes the same as when it's unmodified, we must have at least one other due to the pigeonhole principle. In the case of doubling, we have 0 and 9, which, when doubled, contribute 0 and 9, respectively. This means that transposing the two, entering 09 when 90 was meant, or vice versa, will not be caught.

Almost all data fields used in commerce have some kind of integrity check employed. In fact, in practice, the transmission of any digital data in a network generally has multiple integrity checks at various levels to permit errors to be caught, and in some cases corrected, locally. Most of these error-detection schemes are guards against non-malicious errors such as data-entry errors or noise on a transmission line. They are extremely weak against malicious errors.

 

This is an example of one of the classic fallacies in logical reasoning, namely that if A implies B, that B therefore implies A, generally known as the fallacy of affirming the consequent. The classic example used to illustrate this fallacy is usually something like:

If it is raining, then the ground is wet.

If we limit ourselves to a world where this is always true, namely that knowing that "is raining" is True, that we can infer that "the ground is wet" is also True, then affirming the consequent would be asserting that if we know that the ground is wet, then we also know that it is raining. But this is clearly not the case, since the ground might be wet because someone just poured a bucket of water on it.

Somewhat surprisingly, because it seems so obvious when a specific absurd counterexample is used, neither the fallacy itself nor the method of disproving a universal claim by showing a single counterexample were formalized until symbolic logic was established by people like George Boole, right around 1850. Prior to that, the focus had been (for literally thousands of years) on formalizing methods of proving that something was true by deductive and inductive reasoning, and not on categorizing and recognizing invalid ways of doing so. Boole's work and its implications on logical reasoning were profound, but profound changes are seldom accepted and adopted overnight or without a fight. So, while these were widely explored topics by the beginning of the 20th century, it's not hard to imagine that quite a few established thinkers were still wedded to older schools of thought.

Hi,

I guess one contradiction would be when it's raining in an area over the ocean.
Also, we can't say that when the ground is wet it is raining.
That's what I call a strong non sequitur.
My favorite is:
"It takes money to make money, so if we don't make any money we don't need any money".
That one is comical too.

It's almost like a system where the output is trying to drive the input rather than the input driving the output.

 

The Math Trick Hidden in Your Credit Card Number
View attachment 354135​

Hi,

How do we know what the "check digit" is?
Do they provide any statistical analysis?

 

Hi,

How do we know what the "check digit" is?
Do they provide any statistical analysis?

It actually doesn't matter which digit is the check digit -- whichever digit it is, it is set to the value such that the checksum of the entire thing, including the check digit, meets the criteria. This is how nearly all checksum systems work.

But there's no mystery as to which digit is the check digit -- the format of credit card numbers is well established via ISO/IED 7812.

 

How is it I've never heard of fractional calculus?

 

 

Hello there,

I've always been interested in interesting algorithms (no pun intended but it is kind of comical).

The simplest view of the Laplace Transform is a spiral in 3d space. It can be viewed as a spiral in 3d, but when we look at the projection onto a plane in 2d space we can see (most generally) a damped exponential. It's kind of like taking a spring and pulling both ends apart and then looking at it from any side from a distance. We see a sine wave, with the only difference is it can be a spring with a diameter that goes from larger to smaller and the diameter may not be symmetrical relative to the axis.

Back to interesting algorithms, after years and years I finally found my numerical sine algorithm. This was an algorithm I found back in the 1980's and lost it somehow. This is not like other algorithms for this because it is not a series, it's iterative and the solution gets better and better by 2x digits for each pass.
For example, if the solution to sine(x) was 0.12345678 and on the first pass we got 0.1, then the next pass we would get 0.12, then the next pass 0.1234, then the next pass 0.12345678, and this means we get 2x the accurate digits from the previous pass.
I checked the algorithm but unfortunately, I cannot remember how I developed it. I actually explained this to a member here I think in PM's but I can't remember the name of the member either. It was someone studying circuit analysis I think.
All I can remember now is that I started by thinking about the series for a numerical sine, then for a numerical inverse sine, and thinking that if we could check the numerical sine with the inverse sine, we would have to get a match because they are the inverse functions of each other. So if y=sin(x) was y=1, then asin(1) must equal sin(x), and that is of course simple. All we had to do is find a way to get these two to converge somehow. Once they converge, the solution must be right.
What else I can't remember is if I stuck with that or diverged from that thinking somewhere along the way.
In any case, it turned out to be an amazing formula but I'd like to remember how it was developed. It was not really that complicated so it's a b**** that I can't remember how it was done. The development was even more interesting than the result.
I'll post the result at some point but I'd at least like to break it down into the individual parts so the function of each part is understood. Otherwise, it's just a flaccid set of instructions. I was lucky to find that though I thought it might be lost forever.

 

Just for comparison:

Taylor series for sin, first 3 terms:

sin(x) = x - x^3/3! + x^5/5! …

x = arcsin(.12345678) = 0.12377256

sin0(x) = x = 0.12377256

sin1(x) = sin0(x) - x^3/3! = .12345654

sin2(x) = sin1(x) + x^5/5! = .12345678

Edited to clarify the three successive approximations.

 

One of my favorite videos describing how Euler solved the Basel Problem also does a great job of explaining how the Taylor series relates to derivatives and (in a roundabout kind of way) the sine function:

 

Just for comparison:

Taylor series for sin, first 3 terms:

sin(x) = x - x^3/3! + x^5/5! …

x = arcsin(.12345678) = 0.12377256

sin0(x) = x = 0.12377256

sin1(x) = sin0(x) - x^3/3! = .12345654

sin2(x) = sin1(x) + x^5/5! = .12345678

Edited to clarify the three successive approximations.

Hello,

I've compared many different sin(x) algorithms in the past and that's why I came up with the more unusual algorithm.

For small numbers like 0.1 the Taylor series converges somewhat fast, but as x gets larger, we need more and more terms to get fast convergence. If we look at the error, it actually increases very fast as we get close to 1. Any higher and we need even more terms, and more terms means slower processing speed. If we need 2x the number of terms to get 2x number of digits, that would be a lot compared to getting 2x the number of digits from ONE more pass of a simple algorithm. And with the 2x for 1 algorithm it does not matter how many digits we have, it's always only one more pass to get 2x the number of digits.

Now consider taking the sine of 1 instead of a number close to 0.1 and see how that works out, or higher numbers for x.
Also consider calculating 100's of digits which I needed in the past, or maybe just 32 digits.

These algorithms are always about comparing them to one another. For example, the Chebyshev series has better error distribution than the Taylor series.

 

For small numbers like 0.1 the Taylor series converges somewhat fast, but as x gets larger, we need more and more terms to get fast convergence. If we look at the error, it actually increases very fast as we get close to 1.

Yes, this is why range reduction is needed in computing many functions.

Take a look at one cycle of sin. Divide it into 8 equal regions of π/4. On each of the 8 regions, the sin is equivalent to either a sin or cosine of an adjusted argument in the range of 0 to π/4, either negated or not.

An optimized polynomial with, I think, 5 terms, will give you 8 digits. The two polynomials (sin and cos) over 0 to π/4 can therefore give you the sin and cos of any angle.

There are more complex methods to reduce the range further and use even a smaller numbers of terms, but the range reduction then takes enough compute to erase the advantage.

I have written math libraries that, in software, rivaled the old original 8087 coprocessor in performance (when using the 8087 for the basic operations.)

 

To illustrate my point from the previous point, here is the taylor series for π/4.

π/4 = .78537816

sin(π/4) = .70710678

Here are the taylor series first five terms:

.78539816
.70465265
.70714304
.70710647
.70710678

So 5 terms, as I said gives you 8 digits over the entire range.

Note that each term of the Taylor series requires only 1 multiplication and division by a constant, which can be done by a multiplication by the inverse, so basically two multiplies and an add.

 

Yes, this is why range reduction is needed in computing many functions.

Take a look at one cycle of sin. Divide it into 8 equal regions of π/4. On each of the 8 regions, the sin is equivalent to either a sin or cosine of an adjusted argument in the range of 0 to π/4, either negated or not.

An optimized polynomial with, I think, 5 terms, will give you 8 digits. The two polynomials (sin and cos) over 0 to π/4 can therefore give you the sin and cos of any angle.

There are more complex methods to reduce the range further and use even a smaller numbers of terms, but the range reduction then takes enough compute to erase the advantage.

I have written math libraries that, in software, rivaled the old original 8087 coprocessor in performance (when using the 8087 for the basic operations.)

Hi again,

What do you mean by an 'adjusted argument' ?

 

For starters, sin(-x) = - sin(x)

So any sin can be the sin of a positive number possibly negated. That is the first reduction of range.

Next, As you know, sin(x) is periodic with a period of 2π. So the next step in reducing the argument is to write the argument in the form

x = n * 2π + r

Now sin(x) = sin(r)

where n is an integer and

0 ≤ r ≤ 2π

Next we divide the 2π range into 8 equal parts of width 2π/8 or π/4. Draw this and it is easy to see the rest of it graphically.

Based on sin(x) = cos(x-π/4), and the first identity above, we can see that sin(x) in each of these regions is equal to either sin or cos of an equivalent angle between 0 and π/4.

So every sin(x) is equal to either a sin or cos of an angle x’ such that

0 ≤ x’ ≤ π/4

You can look up the book “Approximation of Functions” by Rice et al, 1964. Rice was my numerical analysis prof in grad school, and would have been my thesis advisor had I continued to a PhD in that specialty.

As I showed before, the Taylor series needs only 5 terms to get 8 digits over that range.

But you can do even better. Chebyshev polynomials can be used to optimize the coefficients for even smaller error. But that is beyond the scope of this post (not to mention that I would have to look it up.)

 

For starters, sin(-x) = - sin(x)

So any sin can be the sin of a positive number possibly negated. That is the first reduction of range.

Next, As you know, sin(x) is periodic with a period of 2π. So the next step in reducing the argument is to write the argument in the form

x = n * 2π + r

Now sin(x) = sin(r)

where n is an integer and

0 ≤ r ≤ 2π

Next we divide the 2π range into 8 equal parts of width 2π/8 or π/4. Draw this and it is easy to see the rest of it graphically.

Based on sin(x) = cos(x-π/4), and the first identity above, we can see that sin(x) in each of these regions is equal to either sin or cos of an equivalent angle between 0 and π/4.

So every sin(x) is equal to either a sin or cos of an angle x’ such that

0 ≤ x’ ≤ π/4

You can look up the book “Approximation of Functions” by Rice et al, 1964. Rice was my numerical analysis prof in grad school, and would have been my thesis advisor had I continued to a PhD in that specialty.

As I showed before, the Taylor series needs only 5 terms to get 8 digits over that range.

But you can do even better. Chebyshev polynomials can be used to optimize the coefficients for even smaller error. But that is beyond the scope of this post (not to mention that I would have to look it up.)

Years ago , I wrote a 3D API, it was for a low speed 68008 CPU. To do trig, I simply populated an array, 180 slots, giving 0.5 degree resolution. Runtime calculations were therefore lighting fast (but I did have to build the table at startup).

An alternative is to memoize results, calculate sin(x) on demand and then put the value in the table. Of course for arbitrary mathematics this won't do, but for 3D it was fine, the resolution of 0.5 degrees fine, no visual degradation in the computed images were visible.

 

Newton Raphson is impressive how fast it converges, but if you prime it with a fairly low-res look-up table, it’s Even quicker.

 

For starters, sin(-x) = - sin(x)

So any sin can be the sin of a positive number possibly negated. That is the first reduction of range.

Next, As you know, sin(x) is periodic with a period of 2π. So the next step in reducing the argument is to write the argument in the form

x = n * 2π + r

Now sin(x) = sin(r)

where n is an integer and

0 ≤ r ≤ 2π

Next we divide the 2π range into 8 equal parts of width 2π/8 or π/4. Draw this and it is easy to see the rest of it graphically.

Based on sin(x) = cos(x-π/4), and the first identity above, we can see that sin(x) in each of these regions is equal to either sin or cos of an equivalent angle between 0 and π/4.

So every sin(x) is equal to either a sin or cos of an angle x’ such that

0 ≤ x’ ≤ π/4

You can look up the book “Approximation of Functions” by Rice et al, 1964. Rice was my numerical analysis prof in grad school, and would have been my thesis advisor had I continued to a PhD in that specialty.

As I showed before, the Taylor series needs only 5 terms to get 8 digits over that range.

But you can do even better. Chebyshev polynomials can be used to optimize the coefficients for even smaller error. But that is beyond the scope of this post (not to mention that I would have to look it up.)

Hello again,

That sounds interesting, but 8 digits means almost nothing to me. Even 80 digits or 800 digits is still not enough.
Here's a result from my simple calculator I did years back:
0.7071067811865475244008443621048490392848359376884740365883398689409498

and that is still far too short.

I think the main confusion here is just how different algorithms can be. Series are just series, and any kind of adjustment beforehand can be done with any algorithm, so the basic properties of an algorithm do not include the pre-adjustments in most cases simply because they do not help to characterize the algorithm. If there are pre-adjustments that can work only with a particular algorithm, that could be entirely different. They may be designed for that particular algorithm, and it may even be the advantage to be able to use them and that would be a large part of why the algorithm would be so successful.
Another example is table lookup. If table lookup works for one algorithm, it works for another most likely.
The algorithms are compared based on their basic structure.
This is why the Taylor series is known to be a slow to converge algorithm, its basic structure is inherently slow, and anything you do to speed it up with also speed up any algorithm, so the speedups don't play a part in comparing algorithms, at least in most cases with the most basic speedup strategies.

An even better example is the use of half angle formulas. If you can compute x/2 rather than x, the algorithm goes faster in most cases especially with Taylor.

Check this out for example for x=pi/4:
sin(x)=3*sin(x/3)-4*sin(x/3)^3

 

Hello again,

That sounds interesting, but 8 digits means almost nothing to me. Even 80 digits or 800 digits is still not enough.
Here's a result from my simple calculator I did years back:
0.7071067811865475244008443621048490392848359376884740365883398689409498

and that is still far too short.

Maybe you already mentioned this previously, but I couldn't spot it quickly. What was the application where 800 digits wasn't enough?

A proton's diameter is approximately 0.84 fm (0.84 x 10^-15 m).

The diameter of the visible universe is about 93 billion light-years, which is about 880 Ym (0.88 x 10^27 m).

To represent that distance to the resolution of the diameter of a proton would thus require just 42 digits.

Number all of the fundamental particles in the known universe would require about 80 digits.

So what application needs more than 800 digits?

And how do you know how many digits in whatever result you get are truly significant?

 

Hello again,

That sounds interesting, but 8 digits means almost nothing to me. Even 80 digits or 800 digits is still not enough.
Here's a result from my simple calculator I did years back:
0.7071067811865475244008443621048490392848359376884740365883398689409498

and that is still far too short.

The question of how you know how many digits are truly significant takes on added emphasis given your example.

The sine(π/4) = √2 / 2

Your result and the result from Wolfram Alpha:

0.7071067811865475244008443621048490392848359376884740365883398689 409498
0.7071067811865475244008443621048490392848359376884740365883398689 953662392310535194251937671638207864

As we can see, the match for 65 sig figs, but part company after that. So there's no point using whatever approach you used beyond that.

I think that, for high-precision computation of trig functions, that the preferred approach is to use algebraic/geometric means and elliptic integrals.