Re: hacker challenge - traverse a list

On Mar 4, 10:39 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
spinoza1111<spinoza1...@xxxxxxxxx> writes:
On Mar 4, 7:10 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
spinoza1111<spinoza1...@xxxxxxxxx> writes:
On Mar 3, 7:11 pm, "Clive D. W. Feather" <cl...@on-the-
train.demon.co.uk> wrote:
In article
<3d782936-6a2d-4016-85f9-e475d98c6...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,spinoza1111<spinoza1...@xxxxxxxxx> writes

OK: any O(1) solution can use a stack of arbitrary bounds by mapping
that stack to a long integer and packing its values, perhaps adding
one to integer values to disambiguate them from zero.

No it can't. If the maximum value you are going to push is M, and the
maximum value that can be stored in a long integer is L, then you can
only push P values where P = floor (log L / log M) (the base used for
the logarithms doesn't matter).

Arbitrary in the sense of fixed. My poor choice of words. I realized
it is small: that's why I said that you can increase this fixed bound
by using a fixed (constant) number of stack objects, each bounded in
the way you say, to create a truly arbitrary, but limited and bounded,
stack for each new edition of the code.

It's obvious to all of us that a stack represented as powers of N in
an integer is bounded. You don't have to belabor the point with
pretentious mathematics.

If an algorithm has some internal bound that means that it only works
on a finite set of inputs (trees in this case) then it can have no
"big O" complexity bounds at all.

By this reasoning, Ben, then no actual (physically executable)
programs have complexity bounds.

Of course.  But note that I was talking about algorithms, not programs.
I was giving you the benefit of the doubt -- I was assuming you were

You need give me no such benefit. You don't judge me, I don't judge
you.

"All scientists are candidates for posts" (Adorno) - on the job. But
here, we're talking about a problem, not looking for a frigging job.

suggesting an algorithm for the problem, not just a bounded program.
Your algorithm, in abstract, is either bounded (and thus does not solve
the problem in any general algorithmic sense) or it does not use O(1)
extra storage -- you choose.  It depends on how you define your
integers.

OK, you claim my hack is an algorithm. You do me too much credit.

But we CAN abstract "representing a stack in code when you can use
either only one or a finite number K of integers" as an algorithm, and
your apparent conclusion, that if in the Platonic world we have
unlimited precision then stacks are O(1), is true.

But it's also nonsense. It's like assuming we have cold fusion and
then proving we have it. O(1) memory complexity assumes cells of
finite precision.

So my solution provides no gain in terms of the Vulgar Misapplication
of Complexity Theory that seems to be on tap here, over a malloc'd
stack. Both solutions are O'(1) where the prime operator indicates
"Vulgar Misapplication".



This argument -- about the bounds in physical programs -- is old and
pointless.  We can get round it by talking about algorithms in this
case.  I suggest that is what we all do.  We can talk about programs,
provided we think of these as abstract illustrations of algorithms --

There is no need to do so. Algorithms represent themselves since they
are nothing more than their appearance...their explanation...their
perspicuous explanation.

Programs, far from being "abstract" illustrations, are CONCRETE
attempts in the real world (including social facts) to realize
algorithms. In many cases, especially in MIS, they are a Platonist
attempt at bedazzlement so that people are reconciled to miserable
lives: Saul Bellow's fictional Tommy Wilhelm, in Seize the Day,
ruminates even in the 1950s why it is companies must print these bills
on their computers, and men must lie awake wondering how to pay them.
Of course, the Platonic precision of those bills often concealed
software errors.

Consider a "straight line" drawn in Microsoft Paint. It isn't what
Euclid meant because it necessarily has dimensions of one pixel,
whereas a Euclidean line has no thickness. If one would teach a child
about straight lines, one would do better to NOT use Paint, and
instead, take him sailing on a calm day and point to the horizon: the
horizon on a day of infinite visibility is Euclidean since it's the
dimensionless point at which sea turns into sky.

In fact, because of the limitations of Euclid's tools, it was obvious
to his adepts that he was talking about idealizations that do not
exist in concrete instances except, in St Paul's words, "through a
glass darkly".

This point was made by Dijkstra: the very precision of computation,
which is always a false precision (whether because of the bit size of
floating point numbers or the limits of virtual storage), fills men
with illusions in which they confuse a concretion with an abstraction.

It's when those illusions change to the rage of mobs, pursuing The
Chosen One, that "darkness falls".

I think this is why Leonard Smith, in "Chaos: A Very Short
Introduction" makes the point: what we see in "computer models of
chaos" is never chaos. A simple example in my experience occured in
1995 when two clowns from a somewhat fraudulent "research institute"
funded by oil companies claimed in the Wall Street Journal that their
"climate model" disproved "global warming" because it showed a cooling
trend since 1981.

Upon investigation, these academic hosebags had created an Excel
spreadsheet and removed average temperatures until the data set was
sufficiently small for the trend line to reverse direction for each
removal, and a "cooling trend" appeared. I added the numbers for 1980
to my copy of their spreadsheet and the trend line flipped towards
warming.

[Their tirade, on the editorial page of the WSJ, contained some
interesting language about the unscientific girliemen who in 1995 were
making unfounded claims that human activity was causing climate
change.]

[Later that year, 600 people died in the 1995 Chicago heat disaster
including a lonely man on my floor of my building. His body was
discovered after the smell emerged, and his flat was filled with
flesh, flies and maggots: his body has exploded.]

[As should any illusion that technology is value-neutral.]

This reminds me of others' (and not your) arguments about
computational complexity such as the silly claim that strlen(s) is bad
style and K-1 is not...not from the standpoint of readability, where
it's good style in both cases not to confuse the program reader in
extempore C meant as pseudocode, but from that of a foolish confusion
of algorithms and programs.

unbounded by the real constraints we know they would have if we
compiled and ran them.  If we don't do this, we can't have these sorts
of debate at all.

This may not be a useful way to spend our time. We'll all get
different numbers...perhaps on the same machine.


That indeed was my point: that for
somewhat the same reason John von Neumann said "anyone who says he
obtained a random number from a computer is in a state of sin",
computational complexity is about algorithms, which don't run at all
on computers.

Our crap runneth on computers, not pure or *reinen* abstract
algorithms.

Even if a program implements the stack in a linked list, sooner or
later (same as a solution that represents the stack in a packed
integer) it work ONLY for a finite set of inputs because its storage
is finite.

Thus we should discuss the merits and demerits of algorithms, not
programs on our limited computers.  We may illustrate these with code,
but we should talk about the algorithms.

Well, the problem here is that we have to know, every man jack of us,
how to write mathematical proofs, an occupation which leaves even less
time than programming for snipping at each other like little baby
girls, or, like me, responding wearily like a man to constant
harassment.

The last time I wrote mathematical proofs, for shits and for giggles,
was when I proved the doability of recursion in Quine's system of "Set
Theory and its Logic" and some of the theorems concerning abstract
automata in Hopcroft and Ullman's "Formal Languages and their Relation
to Automata". This was in 1970. Before that was in high school
geometry. Oh, yeah, I did some proofs in my class on automata theory
in 1978 in grad school.

But hey, I'm game.



<snip>

The discussion needs to be about algorithms not programs.  In

Yes, it does.

Note this.

addition, all big O notation needs to have an agreed notion of what is
being measured (in particular, what are the "units").  If

I couldn't agree more.

and this.

arithmetically unbounded integers are the units of space, your stack
is O(1) and can handle any depth.  You realise that is unreasonable,
but putting a bound on the stack size, probably means that you can't
solve the problem in a way that allows the algorithm to be analysed.

I can build hardware with "unlimited" integer lengths for the same
reason Prince Hamlet could be bound in a nutshell and count himself
king of infinite space. Indeed such hardware existed. The IBM 1401
midsize-mainframe, announced in 1959, had "unlimited" integers that
were bounded in essentially C string fashion: an extra bit, a "word
mark" was placed at the end, and calculating 100 factorial EXACTLY was
a few lines of assembler code.

So why are you talking about all this?  I was trying to get you to
talk about your algorithm and its serious flaws.  You agreed, but keep

It's not my algorithm, it is a part of the common treasury of
humanity. It's a vanishingly trivial microtruth that "you can simulate
stacks on a platform without the ability to malloc or to allocate
arrays such as the Texas Instruments TI-79 calculator", but it's still
true: since even a linked list stack is limited by available RAM, both
solutions are equivalent *sub specie aeternitatis*. Here, you turn
towards the language of the thugs, in which "all scientists" are
reminded, in Adorno's words, that they are technical serfs and wage
slaves, "candidates for posts".

This is a very efficient way to stop thought in its tracks, but
useless in getting at the truth, and Adorno happened to be on his way
to showing that the white collar cannot do the task to which they are
set: the detailed administration of society under the sign of truth
(from where we get simple justice in all cases).

When nobody can be excluded by virtue of the technical structure of
usenet, it is an irony that there has always been, on usenet, a moral
panic about people who don't belong, which is constituted by
psychological transfer in isolated men who have been taught, on the
job, to fear and hate the secret and feminine contour of their
weakness.

The petty bourgeois programmer will always, in Adorno's model, do a
bad job that makes him unhappy. The pressure to short-circuit is
always there, not for technical reasons, but because if no compromises
are made, the system will contradict the intention of its funders.

talking about machines.  If you don't want to talk about algorithms,
don't post in threads where the only meaningful contribution is an
algorithmic one.

Now, that's bullshit. I haven't seen mathematical proofs here,
although some writers approach that level. Harter asked for code, and
most of the responses speculate about code.

I announced my trivial "discovery" as a coding point which undercuts
any claim that a C program which represents the stack as a linked list
is not "O(1)" in the misuse of the term. It can be rephrased to say
that from the abstract standpoint, the machine running the code must
be a Turing machine for there to be any difference between the stack-
as-integer hack.

On a hypothetical (and nonexistent) Turing machine that ACTUALLY RUNS
C CODE in the physical world, the linked list stack would not be O(1).
But in any real computer, it is "O(1)" in the sloppy and misleading
sense that formula is used here.

[I have gone on record as saying you can simulate a TM. But this isn't
the same thing.]

Note that as soon as your language turns minatory...as soon as you
recall to yourself that you are talking to The Chosen One, the
Carthaginian (who must be destroyed)...you science falls apart. Ponder
that.

You don't give me the benefit of the doubt: I don't accept your right
to harm or benefit me. Instead, you now need to show me where my
reasoning, to the conclusion that all solutions are O'(1) memory
complex, is false.


If the thread asks about O(1) space (as this one does) it really does
not help to say, "do it how you like -- big O means nothing on finite
hardware".  We know from experience that there are real advantages,
even on our poor finite hardware to using certain algorithms.

What are these advantages?

Sure, it's good to know how to avoid having to build a REAL linked-
list stack while performing a tree operation, especially in modern
embedded applications. If we can rotate and avoid a stack, cool.
That's a productive result! Thanks Julienne! I'm not worthy!

But this isn't a MATHEMATICAL result, nor even an engineering result.
It's a programming result.

It has no more dignity *sub specie aeternitatis*, as a result, than my
1974 realization that despite the very limited storage available on an
8K 1401, running compiled Fortran code interpretively such that the 8K
was divided between the interpreter and the code, I could do a
reasonable version of John Conway's "Game of Life" with a one-
dimensional small array of integers by representing cells as multiples
of powers of ten.

It has no more dignity, as a result, than my 1979 realization, after
reading the Byte magazine article about "The Mouse Programming
Language" that although with two kids I couldn't afford an Apple II, I
could nonetheless write a compiler by representing the runtime stack
in a floating point number.

Writing C code, and timing it, is simply not a good way to do
complexity theory! It's like the Turing Machine simulator I wrote for
shits and giggles on the TI-79 and which amused my prof. It is
NONCREDIT work.



<snip>

I think I've made my point. Computational complexity is outside
Plato's cave, but like Aristotle we have to realize that it is present
physically only in imperfect shadows, our programs.

Not as far as I can see.  You answered a post about the complexity
bounds that might be possible for some problem with a part-solution.
How can your point be now that such talk is meaningless?  If this is
your point of view, please don't post in threads about algorithms and
their asymptotic bounds.  Or, at least, limit it to one post saying
that you don't care about these things because real programs are
finite.  You seem confused about whether you will talk about
algorithms or not.

The confusion is in the things I talk about. Like T. S. Eliot's
Apeneck Sweeney, I gotta use words when I talk to you, and I am
talking to people who believe that they can get abstract results by
writing C code. As in the case of Clive's disorganized and almost
incoherent rant against Schildt, which reads like it was written in
one draft, as a laundry list and charge sheet, we are in a twittering
world.

This is the world of people with little real programming experience
(building largeish systems as a single developer, and NOT
circumventing the hard parts by declaring victory prematurely while
leaving them for some "low level coder", and NOT trashing their
coworkers using girlyboy gossip). Nor are these people skilled enough
as writers to write a coherent mathematical proof. Reasonable
arguments have been produced, especially by Julienne, but I haven't
seen any proofs.

This world creates a confusion which then is easily blamed on The
Chosen One.

At this point, you seem to have joined, against the better angels of
your nature, to have joined the cybernetic mob who, as Malcolm has
pointed out, don't care about the truth, only "who is to be master" by
a Survivor like process of group voting, not for the master directly,
but by exclusion. As such, you have very little to tell me...no
insight at all. I'd stick to programming, not writing.


If the red slayer thinks he slays,
Or if the slain thinks that he is slain,
They know not well the subtle ways
I keep, and pass, and turn again.

Fear or forgot to me is near;
Shadow and sunlight are the same;
The vanished gods to me appear;
And one to me are shame and fame.

They reckon ill who leave me out;
When me they fly, I am the wings;
I am the doubter and the doubt;
And I the hymn the Brahmin sings.

The strong gods pine for my abode,
And pine in vain the sacred Seven;
But thou, meek lover of the good!
Find me, and turn thy back on heaven.

Ralph Waldo Emerson, Brahma





--
Ben.- Hide quoted text -

- Show quoted text -

.

Relevant Pages