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  
Share this Question
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 oneliner a colleague
found many years ago:
#define HASHSIZE 51 /* a small prime */
 Er*********@sun.com  
P: n/a

> My personal favorite is this oneliner 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  
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 (32bit 'unsigned' and
64bit pointers) the code started to fail for obvious reasons.

Best regards,
Andrey Tarasevich  
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?  
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.

InRealLife: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.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.  
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.  
P: n/a

Eric Sosman wrote:
.... snip ... My personal favorite is this oneliner 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  
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 oneliner 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 
++  
P: n/a

Allan Bruce wrote: My personal favorite is this oneliner 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  
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 welldefined 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  
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 oneliner 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
nonprime than 3*17...
Chris C  
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 oneliner 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  
P: n/a

Allan Bruce wrote: My personal favorite is this oneliner 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*****@acmdotorg.invalid  
P: n/a

Chris Dollin <ke**@hpl.hp.com> writes: Eric Sosman wrote: My personal favorite is this oneliner 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 p1;putchar(p[i]\
);}return 0;}  
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.  
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  
P: n/a

Ben Pfaff wrote: Chris Dollin <ke**@hpl.hp.com> writes:
Eric Sosman wrote: My personal favorite is this oneliner 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 threehanded games
where allbutone of the cards are dealt out, leaving the players
with 17 each. The leftover 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 NinetyNine.

Chris "electric hedgehog" Dollin  
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>  
P: n/a

Ben Pfaff wrote: Chris Dollin <ke**@hpl.hp.com> writes: Eric Sosman wrote:
My personal favorite is this oneliner 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  
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 oneliner 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 threehanded games where allbutone of the cards are dealt out, leaving the players with 17 each. The leftover 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 fourhand (the 'Hearts'
program distributed with Windows is one of the latter, but I first
played the same game fourhanded some 30 years ago using the name "Black
Maria").
and Nullos. (Stares into space.) And NinetyNine.
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 threehand version of Whist with the remaining card
being used to determine which suit was trumps. That was 30odd years
ago as well (it was in a card games book which was at least 20 years
older than that)...
Chris C  
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  
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 oneliner 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 nonprime 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 multiplesof3 and multiplesof9 tricks, it doesn't tell
you the remainder for nonmultiples.)

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.  
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 oneliner 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 nonprime 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 multiplesof3 and multiplesof9 tricks, it doesn't tell you the remainder for nonmultiples.)
True. OK, what about multiples of 13 and 17? <g>)
Chris C  
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 multiplesof3 and multiplesof9 tricks, it doesn't tell you the remainder for nonmultiples.)
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  
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  
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 multiplesof3 and multiplesof9 tricks, it doesn't tell you the remainder for nonmultiples.)
There are similar tricks with a multiplier of 5 (for divisibility by 17)
ot 5 (divisibility by 13), but negative numbers are frequent.  
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 multiplesof3 and multiplesof9 tricks, it doesn't tell you the remainder for nonmultiples.)
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 misstated 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.  
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 multiplesof3 and multiplesof9 tricks, it doesn't tell you the remainder for nonmultiples.)
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  
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 nonmultiple 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 twodigit 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  
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 multiplesof3 and multiplesof9 tricks, it doesn't tell you the remainder for nonmultiples.)
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 = 3a6b %7 = 3(a2b)%7
If 10a+b=0%7 then 3(a2b)=0%7, and dividing by 3, (a2b)=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.  
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 = 3a6b %7 = 3(a2b)%7
If 10a+b=0%7 then 3(a2b)=0%7, and dividing by 3, (a2b)=0%7;
more simply 10a+b=0%7 => 10a20b%7 => a2b=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.  
P: n/a

In article <42****************@news.sbtc.net>, cr*@tiac.net (Richard Harter) writes: more simply 10a+b=0%7 => 10a20b%7 => a2b=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  
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 => 10a20b%7 => a2b=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  
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 => 10a20b%7 => a2b=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.  
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 ??  
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  
P: n/a

John Temples <us****@xargsspam.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  
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  
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 => 10a20b%7 => a2b=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  
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.  
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.  
P: n/a
 rl*@hoekstrauitgeverij.nl (Richard Bos) writes: John Temples <us****@xargsspam.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>  
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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1579
 replies: 43
 date asked: Nov 14 '05
