Wrong-but-not-incorrect code

[CBFalconer]

Are there many card games that call for a deck one card short?

When one player keeps an Ace up his sleeve, yes.

 

[John Temples]

For the CLC readers:
Can you, by artifical construction or actual experience, come up with
something that's more Wrong and yet still manages to be correct code
that performs the intended task?

I once had a do loop:

do {
/* stuff */
} while (condition);

that I later decided needed to be a for loop. So I just edited the
top of the loop, forgetting about the bottom:

for (i = 42; condition; i++) {
/* stuff */
} while (condition);

When I later noticed what I had done, but that the code was still
working correctly, I first thought that the compiler had not noticed a
syntax error.

 

[Keith Thompson]

With a bit more reasonableness, since 13*7 is harder to recognise as
non-prime than 3*17...

Sure, but there's a trick for multiples of 7 as well. Take the last
digit, double it, and subtract from what's left. Iterate as needed.
If the final result is 0 or 7, it's a multiple of 7; if not, not.

9 - (2*1) == 7

(Unlike the multiples-of-3 and multiples-of-9 tricks, it doesn't tell
you the remainder for non-multiples.)

 

[Chris Croughton]

Sure, but there's a trick for multiples of 7 as well. Take the last
digit, double it, and subtract from what's left. Iterate as needed.
If the final result is 0 or 7, it's a multiple of 7; if not, not.

9 - (2*1) == 7

I've never heard of that one! What do you do with small numbers with
large digits on the right, though? It looks as though perhaps you just
ignore the sign (14 => 1 - 4*2 = -7, 35 => 3 - 5*2 = -7, 49 => 4 - 9*2 =
-14 => 14 as above...). I don't see how it works...

(Unlike the multiples-of-3 and multiples-of-9 tricks, it doesn't tell
you the remainder for non-multiples.)

True. OK, what about multiples of 13 and 17? <g>)

Chris C

 

[CBFalconer]

.... snip ...

Sure, but there's a trick for multiples of 7 as well. Take the last
digit, double it, and subtract from what's left. Iterate as needed.
If the final result is 0 or 7, it's a multiple of 7; if not, not.

9 - (2*1) == 7

(Unlike the multiples-of-3 and multiples-of-9 tricks, it doesn't tell
you the remainder for non-multiples.)

How does that work when you run into negative values. Ex: 427

42 - 2*7 = 28
2 - 2*8 = ???

and why?

 

[CBFalconer]

I once had a do loop:

do {
/* stuff */
} while (condition);

that I later decided needed to be a for loop. So I just edited
the top of the loop, forgetting about the bottom:

for (i = 42; condition; i++) {
/* stuff */
} while (condition);

When I later noticed what I had done, but that the code was still
working correctly, I first thought that the compiler had not
noticed a syntax error.

Yes, that does take at least a second look to see the effect. I
gather you had no urge to alter 'condition' at the same time.

 

[Martin Ambuhl]

Chris Croughton <[email protected]> writes:

Sure, but there's a trick for multiples of 7 as well. Take the last
digit, double it, and subtract from what's left. Iterate as needed.
If the final result is 0 or 7, it's a multiple of 7; if not, not.

9 - (2*1) == 7

(Unlike the multiples-of-3 and multiples-of-9 tricks, it doesn't tell
you the remainder for non-multiples.)

There are similar tricks with a multiplier of 5 (for divisibility by 17)
ot 5 (divisibility by 13), but negative numbers are frequent.

 

[Keith Thompson]

How does that work when you run into negative values. Ex: 427

42 - 2*7 = 28
2 - 2*8 = ???

and why?

2 - 2*8 = -14, which is a multiple of 7, so 28 is a multiple of 7, so
427 is a multiple of 7. (I mis-stated the condition before; I forgot
that the result can be negative.)

If you happen to know that 42 is a multiple of 7, you can omit the
final step.

 

[Chris Croughton]

How does that work when you run into negative values. Ex: 427

42 - 2*7 = 28
2 - 2*8 = ???

2 - 2*8 = -14, so ignore the sign and continue:

1 - 2*4 = -7, ignore the sign and it's a multiple of 7.

and why?

That's what puzzles me. It does work, it seems, but I don't understand
it...

Chris C

 

[Michael Wojcik]

That's what puzzles me. It does work, it seems, but I don't understand
it...

Let's see. It's easy to prove it works for the case where N/10 is
a multiple of 7, just by considering three cases: the one's digit is
0, 2*0 is 0, and you're left with N/10; the one's digit is 7, you
subtract a multiple of 7 from another multiple of 7, and their
difference must then also be a multiple of 7; or anything else (you
subtract a non-multiple of 7 from a multiple of 7, their difference
cannot be a multiple of 7).

The cases where N/10 is not a multiple of 7 are a bit trickier, but
not that much.

Consider the two-digit case:

N has digits a and b, so N == 10*a + b.

Hypothesis: 10*a + b == 0 (mod 7) iff a - 2*b == 0 (mod 7). (Note
that the case where you're left with 7 as the sole remaining digit is
just the other case, in base 10, of 0 mod 7 as a single digit.)

Now, this is the same as saying that a mod 7 == 2*b mod 7, so that
when we subtract 2*b from a, we cancel out the noncongruency to 0 (I
think - I am most definitely not a mathematician). In other words,
if a is, say, 3 "away" from a multiple of 7, then 2*b also must be 3
"away" from a multiple of 7.

Now think about a mod 7. This is the penultimate remainder you'd
have if you were dividing 7 into a number using long division. To
have a 0 remainder for the whole division process, ten times that
penultimate remainder (ie 10*(a mod 7)) plus the final digit (b) must
be a multiple of 7. If a mod 7 == 2, then b must be 1 or 8, for
example.

Equivalently, whatever 10*a is congruent to mod 7, b must be
congruent to 7 minus that value. If 10*a == 0 (mod 7), b must also
== 0 (mod 7); if 10*a == 1, b == 6, and so forth.

Make a table comparing a mod 7 with 10a mod 7. If 10a mod 7 is 1, a
mod 7 will be 3 (eg 10 mod 7 == 3, 80 mod 7 == 3, etc). So we want
the mapping between b mod 7 (must equal 10a mod 7) to 2b mod 7 (must
equal a mod 7) to be the converse of that between 10a and a. If
going from 10a to a gives us 1, going from b to 2b must give us 6,
and so forth:

And it is. If 10a is 1, a is 5; if b is 1, 2b is 2. 5 + 2 == 0.
And so on, for 0 through 6. You can write out the tables (of
congruencies mod 7):

10a | a b | 2b a + 2b
-------- ------- ------
0 | 0 0 | 0 0+0=0
1 | 5 1 | 2 5+2=0
2 | 3 2 | 4 3+4=0
3 | 1 3 | 6 1+6=0
4 | 6 4 | 1 6+1=0
5 | 4 5 | 3 4+3=0
6 | 2 6 | 5 2+5=0

(What's the term for the relationship between a and 2b in this case?
I can't remember.)

And I think that's why it works.

--
Michael Wojcik (e-mail address removed)

_
| 1
| _______ d(cabin) = log cabin + c = houseboat
| (cabin)
_| -- Thomas Pynchon

 

[Richard Harter]

2 - 2*8 = -14, so ignore the sign and continue:

1 - 2*4 = -7, ignore the sign and it's a multiple of 7.


That's what puzzles me. It does work, it seems, but I don't understand
it...

It's a bit of modular arithmetic. Suppose our number is 10*a + b.
Then

10a+b %7 = 3a+b %7 = 3a-6b %7 = 3(a-2b)%7

If 10a+b=0%7 then 3(a-2b)=0%7, and dividing by 3, (a-2b)=0%7;



Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.

 

[Richard Harter]

On Sat, 19 Mar 2005 14:51:43 +0000, Chris Croughton


It's a bit of modular arithmetic. Suppose our number is 10*a + b.
Then

10a+b %7 = 3a+b %7 = 3a-6b %7 = 3(a-2b)%7

If 10a+b=0%7 then 3(a-2b)=0%7, and dividing by 3, (a-2b)=0%7;

more simply 10a+b=0%7 => 10a-20b%7 => a-2b=0%7


Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.

 

[Michael Wojcik]

more simply 10a+b=0%7 => 10a-20b%7 => a-2b=0%7

Thanks, Richard - that's a lot simpler than my version (though you
accidentally left out the "=0" in the second step). Still, I'm happy
to have puzzled it out on my own.

If anyone doesn't understand the second step, note that -20 is
congruent to 1 mod 7. (-20 plus 21 = 1.) That means multiplying by
-20 is the same as multiplying by 1, as far as congruence modulo 7
goes, so we can freely multiply b by -20. And we choose -20 because
it's the closest multiple of 10 that's 1 mod 7, so that we can divide
out the common factor 10 and simplify the LHS of the equation.

(Clearly I should have started with the modular algebra and not with
drawing up tables of congruences, then working backward from those...)

 

[Chris Croughton]

Thanks, Richard - that's a lot simpler than my version (though you
accidentally left out the "=0" in the second step). Still, I'm happy
to have puzzled it out on my own.

I understood yours!

If anyone doesn't understand the second step, note that -20 is
congruent to 1 mod 7. (-20 plus 21 = 1.) That means multiplying by
-20 is the same as multiplying by 1, as far as congruence modulo 7
goes, so we can freely multiply b by -20. And we choose -20 because
it's the closest multiple of 10 that's 1 mod 7, so that we can divide
out the common factor 10 and simplify the LHS of the equation.

Ah, thanks, I wondered where the 20 came from. I'm not happy about
factoring out the 10 in the last step, though, is that valid in modulo
arithmetic? 14 % 7 == 0, but 1.4 % 7 == 1.4, no?

(Clearly I should have started with the modular algebra and not with
drawing up tables of congruences, then working backward from those...)

Doing it multiple ways confirms the correctness...

Chris C

 

[Richard Harter]

I understood yours!


Ah, thanks, I wondered where the 20 came from. I'm not happy about
factoring out the 10 in the last step, though, is that valid in modulo
arithmetic? 14 % 7 == 0, but 1.4 % 7 == 1.4, no?

Good question. In this instance, yes. 10 and 7 are relatively prime,
so 10 has an inverse modulo 7. (The inverse is 5) We can multiply
both sides by the inverse, which is equivalent to dividing both sides
by 10.

For an example where you can't cancel, take

2x = 0 %6

Cancelling gives us x=0, but x=3 is also a valid solution.

1.4 isn't an integer. The rules for modular arithmetic don't all
apply to non integers.

Doing it multiple ways confirms the correctness...

Chris C

Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.

 

[Old Wolf]

Sure, but there's a trick for multiples of 7 as well. Take the last
digit, double it, and subtract from what's left. Iterate as needed.
If the final result is 0 or 7, it's a multiple of 7; if not, not.

9 - (2*1) == 7

Isn't it easier to just divide by 7 ??

 

[Dave Vandervies]

It's difficult looking at pieces of code like that you posted.
Sometimes pieces work, but are bad style, others work but are
undefined behaviour, still others are bugs but just happen to work.
When code is contorted it's very hard to tell which is which.

Yep. But when you're not trying to work out why the code you're looking
at isn't doing what it's supposed to, it's both fun and good mental
exercise to sort out which is which and work out why.

(And the code I posted goes beyond bad style; it's definitely wrong -
but it's a type of wrongness that is actually guaranteed to work for
what it's being used for.)


dave

 

[Richard Bos]

for (i = 42; condition; i++) {
/* stuff */
} while (condition);

When I later noticed what I had done, but that the code was still
working correctly, I first thought that the compiler had not noticed a
syntax error.

Gorgeous. You can even do this:

while (condition) {
/* stuff */
} while (condition);

For bonus points, make sure that you leave the first loop with break -
at the precise moment that the condition is false.

Richard

 

[Chris Croughton]

Isn't it easier to just divide by 7 ??

If you can divide 1639657633472406784 by 7 in your head reliably, go for
it! I can't, reliably, so I prefer rules which are simple and use O(n)
time (long division uses O(n^2) time or worse for large n), like the sum
of the digits modulo 3 == 0 for multiples of 3 (multiples of 2, 5 and 10
are even faster, being O(1)).

Chris C

 

[Chris Croughton]

Good question. In this instance, yes. 10 and 7 are relatively prime,
so 10 has an inverse modulo 7. (The inverse is 5) We can multiply
both sides by the inverse, which is equivalent to dividing both sides
by 10.

For an example where you can't cancel, take

2x = 0 %6

Cancelling gives us x=0, but x=3 is also a valid solution.

1.4 isn't an integer. The rules for modular arithmetic don't all
apply to non integers.

Thanks to you and the other posters, I think I may just about understand
it. I don't remember that we covered modulo arithmetic at school or
university (except mod2), but that was over 30 years ago so I might have
forgotten...

Chris C