Re: Letter to US Sen. Byron Dorgan re unpaid overtime

From: Ian Woods (newspub2_at_wuggyNOCAPS.org)
Date: 12/23/03 

Date: Tue, 23 Dec 2003 15:39:17 +0000 (UTC)

spinoza1111@yahoo.com (Edward G. Nilges) wrote in
news:f5dda427.0312221931.122266f2@posting.google.com:

> Ian Woods <newspub2@wuggyNOCAPS.org> wrote in message
> news:<Xns9459CFA734973newspubwuggyorg@217.32.252.50>...
>> spinoza1111@yahoo.com (Edward G. Nilges) wrote in
>> news:f5dda427.0312221032.2d6ad4f1@posting.google.com:
>>
>> > Richard Heathfield <dontmail@address.co.uk.invalid> wrote in
>> > message news:<bs5f83$53q$1@hercules.btinternet.com>...
>> >>
>> >> Well, I'm a great believer in personal choice. I don't believe in
>> >> imposing /any/ language on /anyone/. C happens to be /my/ language
>> >> of choice. That doesn't mean it's right for everybody.
>> >
>> > A computer language is not a lifestyle, and the very idea of
>> > transferable expertise seems to be beyond you. Instead, you judge
>> > people by fabricated metrics which inappropriately foreground
>> > transient issues, like a poor head-hunter.
>> >
>> > Richard, I was frankly shocked to learn that you are unclear on the
>> > very idea of a runtime instruction that would scan a string for a
>> > Nul character, and I was also shocked by Willem's belief that this
>> > instruction as implemented would consume the same sort of cycles
>> > consumed in the execution of an instruction by passing over
>> > characters, typically in firmware.
>> >
>> > You need to learn to cease using random posts to judge people's
>> > capabilities since it reflects badly on you.
>>
>> Alternatively, it might just be obvious that whether it's performed
>> 'in firmware' as you say or elsewhere that scanning for the first
>> occurance of a certain value in an array is not an O(1) operation.
>>
>> On all of the microprocessors I've used which have had instructions
>> which can do such scanning, the runtime of the instruction itself is
>> O(n) not O (1). It being a single microprocessor instruction doesn't
>> make it an O(1) operation.
>
> It is order n, but if implemented in firmware, it is n*c where c is
> smaller than the cycle time of the instruction...usually, much
> smaller.

It matters not where it's implemented: it's still O(n). If I have special
hardware to do it, all I change is the constant. This really is very
basic computer science.

>> >> The line count increment is necessary because the value is used as
>> >> an offset into the array. The preincrement is not non-standard at
>> >> all. The Standard defines the behaviour perfectly. The condition
>> >> is evaluated before each loop iteration, not after. You really
>> >> don't understand this language at all, do you?
>> >
>> > Not true. The increment is NOT performed before each loop iteration
>> > in the code
>>
>> Where in the above paragraph does it say that the increment /is/
>> performed before each loop iteration? It says clearly that:
>>
>> "The condition is evaluated before each loop iteration, not after."
>
> Because of Richard's discourtesy, there was some confusion.

Odd, I thought it was because you'd misread the above. It's nothing new:
reading is a complex skill and no matter how well practiced a person is
mistakes can and do happen from time to time. I'd have thought something
along the lines of:

"Whoops! I misread it."

would have been sufficient to explain the confusion.

> I said,
> repeatedly, that I hoped my understanding of his understanding was
> wrong. It was, and Richard made it clear that he understands the order
> of evaluation of a for loop. But at the same time, he claims that the
> for loop condition is "just an expression" and does not, apparently,
> even know what the code generated for the for loop looks like and the
> compiler mechanisms needed.

The 'compiler mechanisms' for handlng for loops in various languages, and
in C, are trivial. I'm sure Richard can, if he cared to and by now
probably has, sit down with a *** of paper and devise the obvious
working scheme for C-like and integer only for-loops.

<snip>

> He prides himself on "knowing" that using strlen in the for loop
> terminating condition is bad...but the knowledge cannot be
> generalized, outside C.

This is nonsense: the generallisation, and why it is bad, isn't about
using strlen but using an O(n*n) algorithm when there is a trivial O(n)
algorithm. I don't care what language is being used, if I see a colleague
or even a student of mine using an O(n*n) algorithm when it takes no more
programmer effort to use the trivial O(n) algorithm, I'll tell them so.

> In most other languages the terminating
> condition is an end value and in these languages the strlen value
> would be copied before entrance to the for.

In most of most other languages, the loop can only iterate over values of
a single type, typically integers. In the languages which aren't part of
the "most other languages" set, the programmer can choose what type, what
kind of condition, and whether or not to re-evaluate expensive functions
used in that condition.

You chose to make an O(n*n) algorithm out of an O(n) algorithm by /not/
using knowledge trivially available to you as a programmer which isn't
available (or trivially available) to the optimiser. You then argued
about the time complexity of the operation. This shows at best that you
have a misplaced trust in the tools at hand, or at worst that you
shouldn't be programming.

> His knowledge is a deviant knowledge of deviant, and passive
> aggressive language design by Ritchie in which the trivial becomes
> important.

I don't call using an O(n*n) algorithm where there is a trivial O(n)
algorithm and then arguing about the time complexity and how awful the
behaviour of the construct you used to be 'trivial'.

Back to the front though. Obviously then, this Algol-60 for loop is also
"deviant and passive agressive":

for NewGuess := Improve(OldGuess)
  while abs(NewGuess - OldGuess) > 0.0001
  do OldGuess := NewGuess;

It wasn't, of course, designed by Ritchie unless he secretly snuck into
the committee room without anyone noticing. C certainly doesn't have a
monopoly on for loops which re-evaluate the condition once per iteration.

> But what is more important than the order of evalution of a for loop
> is the fact that each time Richard spots a genuine error on my part
> (which have in most cases been typos and not cognitive events on my
> part), he then launches into a tirade about my abilities. I then
> respond, and this creates bad feelings. He is an example of why
> structured walkthroughs can no longer be conducted.
>
> Richard needs to follow my lead,

<quote>dickwad</quote>

> and courteously refrain from
> identifying as errors what are usually typos. He does not do so
> because he feels threatened by broader, "off topic" postings which tax
> his abilities and which threaten his dominant position.
>
> For example, what is "off topic" to him is any reference about which
> he is uninformed.

Mr Nilges, this is nonsense.

> I have not at this late date learned a single useful thing about C
> from Richard, because I'll be damned if I start creating extra
> variables, creating points of potential failure in new versions of
> code to no end except microscopic efficiency.

Using a trivial O(n) algorithm instead of an O(n*n) algorithm isn't
micro-efficiency.

> It was discovered in the
> 1970s that nearly all considerations of efficiency should be postponed
> until the code works because slow code is caused, in nearly all cases,
> by one or two tight loops; therefore, fretting globally about
> micro-efficiency is a waste of time.

One or two tight loops, like those which were examples in this thread. If
you write all the trivial O(n) algorithms as O(n*n) right from the start,
'optimising' the code is going to be a rather painfull experience.

Ian Woods