I was implementing an algorithm to check the validity for a tax id (Brazilian). I discovered that another coder had already implemented this, but the algorithm was different. On the examples I have tried, the results are the same but I don’t know how to prove they are equivalent.
The number in question is 11 digits long. In the first algorithm, you multiply the first nine digits by their index starting from 1 and sum them together, i.e. digit1 * 1 + digit2 * 2 + … + digit9 * 9. You then mod the sum with 11 and if the value is 10, make it 0 and that should equal the 10th digit.
In the second algorithm, the sum is like this: digit1 * 10 + digit2 * 9 + … + digit9 * 2. You then mod it with 11, but then you subtract the result from 11 (and then if that result is 10, make it 0) to get the 10th digit.
Something similar is done to get the 11th digit, but I want to know if the above two algorithms are equivalent.
Are you sure that’s right? I’m not finding very many cases with the same result.
ETA: Nevermind, spelling counts in programming. The problem is in the second form after the mod you get a result of 0, and 11-0 is 11, so those are the only cases that don’t work. Was it really 10- instead of 11-?
The first algorithm: A * 1 + B * 2 + C * 3 + …, mod 11
The second algorithm: 11 - (A * 10 + B * 9 + C * 8 + …), mod 11.
The equivalence: 11 = 0, 1 = -10, 2 = -9, 3 = -8, …, mod 11. [Put another way, if you subtract the second from the first, you end up with -11 + 11 * (A + B + C + …), which is 0, mod 11, so the two are equal.]
Yes, that’s true. Let’s charitably assume a result of 11 is as good as a result of 0, since we’re working modulo 11. Then they’re equivalent.
In other words, I’m looking at “mod 11” not as an operation that returns integers, but as an operation that returns (integers modulo 11), such that we no longer care to distinguish between 0 and 11 in the land where the results land.
(Addendum to my last post: Of course, to turn these into digits, we need a function from (integers modulo 11) to digits, and that’s where we send 11x + d to d for d in {0, …, 9}, and send 11x + 10 to 0)
But yes, for a programmer, he should have worded it with the “mod” later.
I was just joking of course. But I could see that as a cause of an eventual bug as a programmer is likely to believe taking the least significant digit is sufficient and end up with the wrong result. But there’s plenty of room for charity in a quick description like in the OP. Far more coherent than me trying to describe a complex math operation.
)