Velocity Reviews > Wrong-but-not-incorrect code

# Wrong-but-not-incorrect code

Walter Roberson
Guest
Posts: n/a

 03-22-2005
In article <(E-Mail Removed)>,
Chris Croughton <(E-Mail Removed)> 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.

Keith Thompson
Guest
Posts: n/a

 03-22-2005
Chris Croughton <(E-Mail Removed)> writes:
> On 21 Mar 2005 13:38:09 -0800, Old Wolf
> <(E-Mail Removed)> 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) http://www.velocityreviews.com/forums/(E-Mail Removed) <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.

Tim Rentsch
Guest
Posts: n/a

 03-23-2005
(E-Mail Removed) (Richard Bos) writes:

> John Temples <(E-Mail Removed)> 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

</amusement>

CBFalconer
Guest
Posts: n/a

 03-23-2005
Chris Croughton wrote:
> <(E-Mail Removed)> 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