Proposals

Lynn H. Maxson lmaxson@pacbell.net
Thu, 29 Jun 2000 17:26:41 -0700 (PDT)


Jason Marshall wrote:

To Jason Marshall

You offer a accurate definition of "brute force".  
We have had some problems which have been amenable 
to no other method.  On the other hand we have 
found ways logically to keep us from going down 
"wasted" paths.  The fact that something produces 
the same result as brute force does not mean its 
application.  What I am describing is what occurs 
in every AI-based logic engine, an exhaustive 
true/false testing process.  No more, no less.

While certain problems have proven intractable to 
either brute force or more "intelligent" means, we 
have a host of them which have proven soluble, 
which we have certainly solved in reasonable time.  
In your example, the long running execution of the 
system may continue on forever, but that which 
allowed it to execute certainly has completed.

"...they are brute force testing a piece of 
information only 8 bytes long, against another 
piece of information only a couple of kilobytes 
long, looking for the single solution that is the 
correct one."

It's not up to me to question why someone has 
chosen a particular method.  I would probably 
respond that first I would get rid of 59,999 
machines.<g>  I haven't talk with Gene Amdahl (or 
his brother Lowell) in quite some time, but 
remembering the great debate on parallel computing 
that took place between him and the University of 
Urbana Illinous folks in the late sixties, I may 
not be that far off.<g>

Maybe I just don't understand what problem they are 
trying to solve as it sounds like something offered 
with IBM's ImagePlus family of products of 
detecting (matching) patterns of a source image 
against a database of much larger images.  I might 
suggest that the one group look to the other.<g>

"Are you familiar with the concepts surrounding the 
calculation of Order of Complexity of an 
algorithm?"

The answer is "maybe, but I'm not sure."  You see I 
make no claims to holding an "academic" interest in 
things which may find it "interesting", if not 
important, to have some measure of the "Order of 
Complexity" of an algorithm.  I'm not sure I would 
have had the temerity to ask either my management 
or the user if they knew it either.  For certain 
neither gave a damn.  They only wanted it solved.  
Though I may have done some research to have a 
better understanding of causes and conditions, they 
did not care if I used brute force and discovered 
it by chance in the process as long as I solved it 
in time.

I don't want to make light of academic pursuits nor 
those in pursuit.  I have been a member of the ACM 
since 1962 and a participant in computer-related 
matters in the IEEE since before it had formed the 
Computer Society.  For most of that time what was 
published under those societies meant absolutely 
zip to me.  That did not keep from understanding 
the importance of continuing a publishing outlet 
that from time to time did create a practical 
communication link with the "outside" world.

The point is that we have two different problems in 
mind.  You may pursue an academic interest in  
providing measures which may or may not have any 
practical significance except as a comparison among 
a class of examples.  I accept that every 
programming language I am familiar with has 
optimizing (not necessarily optimal) code 
generation embedded within it.  Very seldom do you 
run into a instance in which a valid statement in 
that language does not translate into a logically 
equivalent executable unit.  I accept that it works 
and that with experience it will probably improve 
as much or more in the future as it has in the 
past.

Instead I look at whatever result it produces to 
understand where (and why) it differs from the best 
code from the best assembly language programmer.  I 
focus on this because regardless of the why a 
solution is expressed or the language used to 
express it that the principle of logical 
equivalence exists.  That tells me that regardless 
of the "nature" of the source I should be able to 
arrive at the best solution, if for no other reason 
than it exists or is known to exist.

Now if I do that, I suspect that what I will find 
is not inefficient executable code.  There is 
simply more of it somehow executed.  That means I 
can skip over any concerns about code generation, 
because one way or another that one has been 
solved: an executable exists.  What I need to 
understand is why there is "extra" executable code.  
I say "extra" because it is not required in the 
"best" example that is logically equivalent.

Now if I examine the code, what will I discover?  I 
will discover that if it is a block structured 
language like C or PASCAL of procedures nested 
within other procedures the "nesting boundaries" 
will remain in the executable code.  For example, I 
will find references to the "stack" related to the 
preservation of those boundaries.  If I do the same 
analysis on OO applications with their objects and 
message passing, chances are I will still see this 
"source" view persevere throughout to the 
executable level.

Now if I am going to engage in reflective 
programming I ought to have enough reflection 
capability to know that once I am passed the 
source, which is my user interface, that I don't 
have to maintain that form if I can have a better 
performing logical equivalent one.  I don't want to 
shock anybody, but long before Smalltalk and OO 
appeared on the scene we successfully produced as 
complex and complicated software as has ever been 
produced by OO means.  Prior to that time as a 
vendor you caught hell if your code production did 
not come close to assembler.

"Because the order of complexity of the alternative 
makes people quake in their boots, laugh nervously, 
or roll around on the floor giggling insanely and 
pointing in your general direction?  It's a 
mindbogglingly large calculation."

Well, I'm happy if I provide some comic relief in 
these discussions.  It's only fair.  I have to 
admit to a fair amount of smiles resulting from 
reading the references suggested here.  Real 
guffaws happen when I run across "preliminary" and 
a belly whopper when "it needs more work" occurs.  
I would guess that if we cannot gain insight from 
all the material, that entertainment gives it some 
"social, redeeming value".<g>  Of course, why 
should anyone who writes as much vacuous and 
superfluous and empty of meaning material gain so 
much humor elsewhere when obviously I have an 
overabundant supply of my own.<g>

This old dog who has been solving computer-related 
problems since June of 1956 has not giving up on 
his joy in doing so.  I began with doing "actual" 
repair of failing computer logic and moved on to 
software "repair" from there when it started 
getting too small (and uneconomical) to repair.  My 
coding career began with actual (entering 
diagnostic programs from the switches on a console) 
through all the language generations up to now.

So "shoo if you must this old grey head, but watch 
your logical tack, he said".<g>