Paul Millar wrote:
>
> On Wed, 20 Mar 2002, Allan Whiteford wrote:
> [snip]
> > I think there are conceptual differences.
>
> We'll probably end up arguing over semantics, but here's my spin on it ...
>
Yeah - I think we agree on all practical levels.
> > The algorithm would be as follows:
> >
> > "Set the total to zero. Go through each of the elements in turn and add
> > it's value to the total".
>
> ... call this X for brevity
>
> > 2 possible implementations of this are:
> >
> > total=0;
> > for (i=0;i<=9;i++)
> > {
> > for (j=0;j<=9;j++)
> > {
> > total=total+array[i][j];
> > }
> > }
>
> .. we'll call this Y1
>
> > total=0;
> > for (i=0;i<=9;i++)
> > {
> > for (j=0;j<=9;j++)
> > {
> > total=total+array[j][i];
> > }
> > }
>
> .. and this Y2;
>
> > The first solution will be faster but the algorithm hasn't changed. It's
> > just about knowing the language/compiler.
>
> Yep, Y1 and Y2 both implement X (I've been hanging around Java programmers
> too long;), but there's another layer to this.
>
> Call Y1 "the algorithm", you can implement Y1 as:
>
Stuff I didn't really read or understand. Sorry, Paul.
> .. we'll call this monstrosity Z1-1. We could also implement Y1 as:
>
Some more stuff.
>
> .. and we'll call this tidier code Z1-2.
>
> The point is both Z1-1 and Z1-2 implement Y1, but Z1-2 will be much
> faster.
I once made a PIC flash some LEDs, you seem to collect them. I'll take
your word for all things assembly related :).
>
> At a larger scale, you can have problem W
> "Alterations are made to a matrix, maintain the correct total".
>
> Algorithm X will do this, but a better way is:
>
> static first_time=TRUE;
>
> if( first_time) {
> total = algorithmX( matrix);
> first_time = FALSE;
> }
> else
> total += diff;
>
> Saving 100 array memory accesses and 99 additions on subsequent calls.
>
> A compiler is able to produce Z1-2 instead of Z1-1 (in fact gcc did ;) and
> a _really_ smart compiler might be able to produce Y2 instead of Y1, but
> there's no way a compiler can produce the above algorithm instead of
> always using algorithm X.
I think what you are suggesting here is a completely new algorithm which
of course no compiler could get because they aren't smart - they are
just good at tedious tasks.
>
> The cut-off is because there's a limit to how smart a compiler can be. The
> cut-off from a human's point of view is how much time they're willing to
> spend (and how much they know about the target platform). If the two
> cut-offs are at the same "depth" of complexity, then optimal code is
> produced.
>
Yep - as I said, I think we agree on a practical level. Do the broad
outline using your own brain and let the fiddly little details be washed
up inside -On.
I think my main argument is that an algorithm is something you can
optimise without worrying about what sort of language/computer you are
going to use whereas the order of "i"s and "j"s is a purely
computational issue.
When you go down to the problem of how to actually add a number to your
total then you hit the same two types of problem, what is algorithm and
what is just computation. This means, I guess, that below the purely
computational issues of one layer sits algorithmic issues in the layer
below.
My original statement only applies if we limit ourself to one "layer".
(Which, admittedly I never thought about when I first said it).
I think this means I sort of agree with you now... but yeah, it's all
semantics :).
>
> Now, what about code morphing and Transmeta's Crusoe chips ...
>
Nah, quantum computation next...
Thanks,
Allan
--
Scientists have shown that the moon is moving away at a tiny yet
measurable distance from the earth every year. If you do the maths, you
can calculate that 85 million years ago the moon was orbiting the earth
at
a distance of about 35 feet from the earth's surface. This would explain
the death of the dinosaurs. The tallest ones, anyway.
--------------------------------------------------------------------
http://www.lug.org.uk http://www.linuxportal.co.uk
http://www.linuxjob.co.uk http://www.linuxshop.co.uk
--------------------------------------------------------------------
