By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,910 Members | 1,625 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,910 IT Pros & Developers. It's quick & easy.

Wrong-but-not-incorrect code

P: n/a
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what
the reasonable reader would expect.)

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?
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
It is true that their choices are not always consonant with the choices _I_
would make, but that's because they're cats and I'm not.
--Mike Andrews in the scary devil monastery
Nov 14 '05 #1
Share this Question
Share on Google+
43 Replies


P: n/a


Dave Vandervies wrote:
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what
the reasonable reader would expect.)

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?


My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */

--
Er*********@sun.com

Nov 14 '05 #2

P: n/a
>
My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */

--
Er*********@sun.com
He obiously doesnt know his 3 time table above 3x10 ;-)
Allan

Nov 14 '05 #3

P: n/a
Dave Vandervies wrote:
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what
the reasonable reader would expect.)

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?
...


signed char direction; /* either -1 or +1 */
unsigned offset; /* absolute distance */
T* ptr;

...
ptr += direction * offset;
/* Moving the pointer in direction specified by 'direction' */

In general case the code does not do what it was intended to do, since
the right hand side will be promoted and evaluated within the bounds of
'unsigned' type. However, on a 32 bit platform the code "worked" - the
pointer value wrapped around and ended up exactly where it would be if
code worked as intended. On a 64 bit platform (32-bit 'unsigned' and
64-bit pointers) the code started to fail for obvious reasons.

--
Best regards,
Andrey Tarasevich
Nov 14 '05 #4

P: n/a
Dave Vandervies wrote:
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what
the reasonable reader would expect.)

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?


Your example itself could easily be made Worse. That sprintf call, for
example, is missing some casts, innit? And both that and the ReadImage
call could used a (void), innit?
Nov 14 '05 #5

P: n/a
In article <d1**********@rumours.uwaterloo.ca>
Dave Vandervies <dj******@csclub.uwaterloo.ca> wrote:
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 have no idea how to rate the "wrongness" on a scale that
affords comparisons, but I once put a typo in my code so
that instead of:

if (expr && var)

I had:

if (expr &*& var)

The code still worked because the expression (whatever it was)
produced either 0 or 1 as its result -- it was perhaps something
like "a == b" -- and "var" was also logically boolean, holding
only either 0 or 1. Hence:

if (a == b &*& c)

was:

if ((a == b) & (*&c))

which was:

if ((a == b) & c)

which meant the same thing as the intended line.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 14 '05 #6

P: n/a
Dave Vandervies wrote:
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what the reasonable reader would expect.)

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?


This isn't technically wrong but I thought I'd mention it. I knew this
chap who really loved GOTO statements, but upon entering a job he
realized the company's coding practices didn't allow them. So instead
he dropped a bunch of JUMPahead and JUMPbehind statemetns in his code
as a replacement. In a header file he hid the following:

jumpcommands.h
===============

#define JUMPahead goto
#define JUMPbehind goto

-------------------------

Makes you wonder why I.Q. tests are given to job applicants anymore.
BTW, this chap had a lot of fancy -qualifications-. If you ask me, the
onyl qualification that matters is the one between someone's ears.

Nov 14 '05 #7

P: n/a
Eric Sosman wrote:
.... snip ...
My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */


A few years ago, in this very newsgroup, 91 enjoyed similar fame.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #8

P: n/a
Eric Sosman wrote:

Dave Vandervies wrote:
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what
the reasonable reader would expect.)

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?


My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */

"If 91 were prime, it would be a counterexample to your conjecture."
-- Bruce Wheeler

--
+----------------------------------------------------------------+
| Charles and Francis Richmond It is moral cowardice to leave |
| undone what one perceives right |
| richmond at plano dot net to do. -- Confucius |
+----------------------------------------------------------------+
Nov 14 '05 #9

P: n/a
Allan Bruce wrote:

My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */

--
Er*********@sun.com


He obiously doesnt know his 3 time table above 3x10 ;-)
Allan


I add up the digits to see if a number is divisible by 3.
(5 + 1) % 3 == 0

--
pete
Nov 14 '05 #10

P: n/a
In article <d1********@news1.newsguy.com>,
Chris Torek <no****@torek.net> wrote:
In article <d1**********@rumours.uwaterloo.ca>
Dave Vandervies <dj******@csclub.uwaterloo.ca> wrote:
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 have no idea how to rate the "wrongness" on a scale that
affords comparisons,


I was thinking along the lines of "invokes a `That can't POSSIBLY be
what it's supposed to say!' response, optionally accompanied by sever
aesthetic revulsion". Not well-defined or objective enough to make a
competition out of it, but comparing according to how well it matches
that is useful enough for war stories or language lawyering.

but I once put a typo in my code so
that instead of:

if (expr && var)

I had:

if (expr &*& var)

The code still worked because the expression (whatever it was)
produced either 0 or 1 as its result -- it was perhaps something
like "a == b" -- and "var" was also logically boolean, holding
only either 0 or 1.


Impressive. (But not nearly as impressive as if you'd had a plausible
reason for writing it that way intentionally.)
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
If the committee members can't agree over it, what chance have I got of
defending /either/ position?
--Richard Heathfield in comp.lang.c
Nov 14 '05 #11

P: n/a
On Fri, 18 Mar 2005 02:44:41 GMT, CBFalconer
<cb********@yahoo.com> wrote:
Eric Sosman wrote:

... snip ...

My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */


A few years ago, in this very newsgroup, 91 enjoyed similar fame.


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

Chris C
Nov 14 '05 #12

P: n/a
Eric Sosman wrote:


Dave Vandervies wrote:
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what
the reasonable reader would expect.)

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?


My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */


The writer clearly didn't play enough card games.

--
Chris "electric hedgehog" Dollin
Nov 14 '05 #13

P: n/a
Allan Bruce wrote:
My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */
--
Er*********@sun.com


He obiously doesnt know his 3 time table above 3x10 ;-)
Allan


Or perhaps he was writing in decimal but thinking
in octal. "3x10 -- that's two dozen, right?"

(Exculpatory note: The colleague I mention was the
finder of the bug, not its author.)

--
Eric Sosman
es*****@acm-dot-org.invalid
Nov 14 '05 #14

P: n/a
Chris Dollin <ke**@hpl.hp.com> writes:
Eric Sosman wrote:
My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */


The writer clearly didn't play enough card games.


Are there many card games that call for a deck one card short?
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 14 '05 #15

P: n/a
dj******@csclub.uwaterloo.ca (Dave Vandervies) wrote in message news:<d1**********@rumours.uwaterloo.ca>...
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what
the reasonable reader would expect.)

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?
dave


There is some particularly contorted code in the message cracker
header windowsx.h in MS Windows that works. For instance:-

#define HANDLE_WM_INITDIALOG(hwnd, wParam, lParam, fn) \
(LRESULT)(DWORD)(UINT)(BOOL)(fn)((hwnd), (HWND)(wParam), lParam)

Not that this is totally wrongheaded unlike the code you mentioned
above. It's just mildly derranged.

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.
Nov 14 '05 #16

P: n/a
In article <87************@benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:
#define HASHSIZE 51 /* a small prime */
The writer clearly didn't play enough card games.
Are there many card games that call for a deck one card short?


When you deal a pack of 52 cards between three players, you have one
left over.

-- Richard
Nov 14 '05 #17

P: n/a
Ben Pfaff wrote:
Chris Dollin <ke**@hpl.hp.com> writes:
Eric Sosman wrote:
My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */


The writer clearly didn't play enough card games.


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


I don't know about "many", but there are several three-handed games
where all-but-one of the cards are dealt out, leaving the players
with 17 each. The left-over card may be left concealed, or it may
be exposed, or may be exchanged; it may determine the trump suit.

The two that immediately come to mind are Black Maria aka Hearts,
and Nullos. (Stares into space.) And Ninety-Nine.

--
Chris "electric hedgehog" Dollin
Nov 14 '05 #18

P: n/a
"Dave Vandervies" <dj******@csclub.uwaterloo.ca> wrote in message
news:d1**********@rumours.uwaterloo.ca...
Seen in a chunk of code I was looking at recently (not mine!):
--------
char* imgfilename[100];
sprintf((char*)imgfilename, "mask%d.dib", params.profile);
ReadImage((char*)imgfilename);
--------
(ReadImage is another part of the program's code that does exactly what the reasonable reader would expect.)

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?


Did a code audit once, of a program that had passed the integration
testing phase. It was a 3000 liner in a single source file. Well, that
happens... after scanning through +200 lines of globals.. I finally came
to the main.. puuuh!

The main() function was a +1500 liner, full of duplicate and
complicated rollback code....

Oh no... this wasn't any student code, the programmer had a CS
master degree and multiple years of C/C++ programming
experience. He had spent 3 months on this module. <g>

--
Tor <torust AT online DOT no>

Nov 14 '05 #19

P: n/a
Ben Pfaff wrote:
Chris Dollin <ke**@hpl.hp.com> writes:
Eric Sosman wrote:

My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */


The writer clearly didn't play enough card games.


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


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

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #20

P: n/a
On Fri, 18 Mar 2005 16:26:33 +0000, Chris Dollin
<ke**@hpl.hp.com> wrote:
Ben Pfaff wrote:
Chris Dollin <ke**@hpl.hp.com> writes:
Eric Sosman wrote:
My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */

The writer clearly didn't play enough card games.
Are there many card games that call for a deck one card short?


I don't know about "many", but there are several three-handed games
where all-but-one of the cards are dealt out, leaving the players
with 17 each. The left-over card may be left concealed, or it may
be exposed, or may be exchanged; it may determine the trump suit.

The two that immediately come to mind are Black Maria aka Hearts,


One of a number of games by both names, some are four-hand (the 'Hearts'
program distributed with Windows is one of the latter, but I first
played the same game four-handed some 30 years ago using the name "Black
Maria").
and Nullos. (Stares into space.) And Ninety-Nine.


There's also at least a couple where 16 cards are dealt to each player,
with 4 being left to exchange.

I've also played a three-hand version of Whist with the remaining card
being used to determine which suit was trumps. That was 30-odd years
ago as well (it was in a card games book which was at least 20 years
older than that)...

Chris C
Nov 14 '05 #21

P: n/a
In article <d1**********@rumours.uwaterloo.ca>, Dave Vandervies wrote:
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.

--
John W. Temples, III
Nov 14 '05 #22

P: n/a
Chris Croughton <ch***@keristor.net> writes:
On Fri, 18 Mar 2005 02:44:41 GMT, CBFalconer
<cb********@yahoo.com> wrote:
Eric Sosman wrote:

... snip ...

My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */


A few years ago, in this very newsgroup, 91 enjoyed similar fame.


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.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #23

P: n/a
On Fri, 18 Mar 2005 19:53:46 GMT, Keith Thompson
<ks***@mib.org> wrote:
Chris Croughton <ch***@keristor.net> writes:
On Fri, 18 Mar 2005 02:44:41 GMT, CBFalconer
<cb********@yahoo.com> wrote:
Eric Sosman wrote:

... snip ...

My personal favorite is this one-liner a colleague
found many years ago:

#define HASHSIZE 51 /* a small prime */

A few years ago, in this very newsgroup, 91 enjoyed similar fame.
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


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
Nov 14 '05 #24

P: n/a
Keith Thompson wrote:
.... 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?

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #25

P: n/a
John Temples wrote:
Dave Vandervies wrote:
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.


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.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #26

P: n/a
Keith Thompson wrote:
Chris Croughton <ch***@keristor.net> 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.
Nov 14 '05 #27

P: n/a
CBFalconer <cb********@yahoo.com> writes:
Keith Thompson wrote:

... 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?


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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #28

P: n/a
On Fri, 18 Mar 2005 21:29:07 GMT, CBFalconer
<cb********@yahoo.com> wrote:
Keith Thompson wrote:
... 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 = ???


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
Nov 14 '05 #29

P: n/a

In article <sl******************@ccserver.keris.net>, Chris Croughton <ch***@keristor.net> writes:
Keith Thompson wrote:

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.


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 mi************@microfocus.com

_
| 1
| _______ d(cabin) = log cabin + c = houseboat
| (cabin)
_| -- Thomas Pynchon
Nov 14 '05 #30

P: n/a
On Sat, 19 Mar 2005 14:51:43 +0000, Chris Croughton
<ch***@keristor.net> wrote:
On Fri, 18 Mar 2005 21:29:07 GMT, CBFalconer
<cb********@yahoo.com> wrote:
Keith Thompson wrote:

... 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 = ???


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...


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, cr*@tiac.net
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.
Nov 14 '05 #31

P: n/a
On Sun, 20 Mar 2005 06:13:21 GMT, cr*@tiac.net (Richard Harter) wrote:
On Sat, 19 Mar 2005 14:51:43 +0000, Chris Croughton
<ch***@keristor.net> wrote:

[snip]
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;


more simply 10a+b=0%7 => 10a-20b%7 => a-2b=0%7
Richard Harter, cr*@tiac.net
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.
Nov 14 '05 #32

P: n/a

In article <42****************@news.sbtc.net>, cr*@tiac.net (Richard Harter) writes:

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...)

--
Michael Wojcik mi************@microfocus.com
Nov 14 '05 #33

P: n/a
On 20 Mar 2005 18:11:55 GMT, Michael Wojcik
<mw*****@newsguy.com> wrote:

In article <42****************@news.sbtc.net>, cr*@tiac.net (Richard Harter) writes:

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.


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
Nov 14 '05 #34

P: n/a
On Sun, 20 Mar 2005 22:36:50 +0000, Chris Croughton
<ch***@keristor.net> wrote:
On 20 Mar 2005 18:11:55 GMT, Michael Wojcik
<mw*****@newsguy.com> wrote:

In article <42****************@news.sbtc.net>, cr*@tiac.net (Richard Harter) writes:

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.


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?


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.
(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, cr*@tiac.net
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.
Nov 14 '05 #35

P: n/a
Keith Thompson wrote:

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 ??

Nov 14 '05 #36

P: n/a
In article <1a**************************@posting.google.com >,
Rob Thorpe <ro***********@antenova.com> wrote:
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

--
Dave Vandervies dj******@csclub.uwaterloo.ca
Philosophers don't have to worry about special cases, so they make lousy C
programmers.
--Ben Pfaff in comp.lang.c
Nov 14 '05 #37

P: n/a
John Temples <us****@xargs-spam.com> wrote:
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
Nov 14 '05 #38

P: n/a
On 21 Mar 2005 13:38:09 -0800, Old Wolf
<ol*****@inspire.net.nz> wrote:
Keith Thompson wrote:

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 ??


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
Nov 14 '05 #39

P: n/a
On Mon, 21 Mar 2005 04:43:55 GMT, Richard Harter
<cr*@tiac.net> wrote:
On Sun, 20 Mar 2005 22:36:50 +0000, Chris Croughton
<ch***@keristor.net> wrote:
On 20 Mar 2005 18:11:55 GMT, Michael Wojcik
<mw*****@newsguy.com> wrote:

In article <42****************@news.sbtc.net>, cr*@tiac.net (Richard Harter) writes:

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.


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?


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
Nov 14 '05 #40

P: n/a
In article <sl******************@ccserver.keris.net>,
Chris Croughton <ch***@keristor.net> wrote:
:(long division uses O(n^2) time or worse for large n),

And much *much* worse time when dividing by 0 ;-)
--
Usenet is like a slice of lemon, wrapped around a large gold brick.
Nov 14 '05 #41

P: n/a
Chris Croughton <ch***@keristor.net> writes:
On 21 Mar 2005 13:38:09 -0800, Old Wolf
<ol*****@inspire.net.nz> wrote:
Keith Thompson wrote:

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 ??


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)).


But you don't need to use long division when dividing by 7 (unless
you're using a base smaller than 7).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #42

P: n/a
rl*@hoekstra-uitgeverij.nl (Richard Bos) writes:
John Temples <us****@xargs-spam.com> wrote:
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.

<amusement>

For an increase in transmogrification factor, may I suggest using the
infamous "do while while" construction:

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

Include both 'break;' and 'continue;' statements in the loop body for
additional hilarity.

</amusement>
Nov 14 '05 #43

P: n/a
Chris Croughton wrote:
<ol*****@inspire.net.nz> wrote:
Keith Thompson wrote:

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 ??


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)).


I can do the division by 7 much more easily and reliably than the
other method. The primary difference is you start the scan from
the left. I can discard everything except the remainder when
dividing a max 2 digit value by 7. I can always discard any
leftmost zeroes, and only need worry about dividends in the range 7
through 69.

--
"I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously
no deficiencies and the other way is to make it so complicated
that there are no obvious deficiencies." -- C. A. R. Hoare
Nov 14 '05 #44

This discussion thread is closed

Replies have been disabled for this discussion.