Avoiding recursive stack overflow in C on Unix/Linux?

[robertwessel2]

Odd, in order to reduce actual recursion (and do tail recursion
instead), and to keep locality of reference tight, I'd handle the
smaller part first were I to use an actual quicksort. Not that I'd
do that, being more of a fan of heapsort in situations where I want
an acceptable worst-case big-Oh for reasons such as availability.

The usual approach for the semi-recursive implementation is to recurse
on the smaller partition, and then loop (or allow tail recursion,
assuming your implementation language supports that) on the bigger
one. If you do a fully iterative version (managing your own stack),
you need to “push” the smaller partition last, so that you sort it
first. If you do it the other way, you can't bound your stack size
to log(N). A fully recursive implementation is stuck with order-N
worst case stack requirements (no matter which order you process the
partitions), unless you can guarantee tail recursion elimination.

Nope, reduces the constant, that's all. If the median is selected
from 3 random (i.e. unpredicatable to an attacker) elements, then
the worst case behaviour can not be forced, and you would average
to the theoretical average. But then you have to secure information
about your (P)RNG state.

And producing large quantities of good random numbers with low
overhead is much harder than the problem you wanted to solve in the
first place.

 

[Rainer Weikusat]

[...]

And producing large quantities of good random numbers with low
overhead is much harder than the problem you wanted to solve in the
first place.

In theory. In practice, all this takes is linking with OpenSSL,
assuming that some source of good randomness will always be available/
nobody except the person who wrote the code will ever bother to check
it with that much detail (especially, since the chances that anyone who
is at least remoteley superior insofar job positions go both
understands the issue and cares about it in absence of a pending
customer lawsuit are extremly slim) and then go on a happy, four week
holiday somewhere in the sun with the pleasant conviction that an
inherently wrong solution for some problem can always be turned
into something which gives a 'good enough' appearance of working for
all practical purposes by making the implementation complicated
enough to hide its deficiencies.

 

[robertwessel2]

[...]

And producing large quantities of good random numbers with low
overhead is much harder than the problem you wanted to solve in the
first place.

In theory. In practice, all this takes is linking with OpenSSL,
assuming that some source of good randomness will always be available/
nobody except the person who wrote the code will ever bother to check
it with that much detail (especially, since the chances that anyone who
is at least remoteley superior insofar job positions go both
understands the issue and cares about it in absence of a pending
customer lawsuit are extremly slim) and then go on a happy, four week
holiday somewhere in the sun with the pleasant conviction that an
inherently wrong solution for some problem can always be turned
into something which gives a 'good enough' appearance of working for
all practical purposes by making the implementation complicated
enough to hide its deficiencies.

Open SSL (or whichever crypto library is handy on your platform) will
fairly easy produce a stream of high quality random bits. It will,
however, have very high overhead. So much so that I’d expect a
straight Heapsort to be faster, which would be simpler than the
Quicksort implementation (just counting the sort part of the code).
Poor quality “random” numbers are much easier to generate.

Your point about an apparently good enough (which all too often
equates to "no demonstrated fatal flaws"), but cheap, solution
frequently satisfying the bosses, is of course, a general truth.

 

[Kenny McCormack]

yep. Kenny seems to be of the oft-stated opinion that the only
topic suitable for comp.lang.c is standard C (specifically discussions
of the standard itself, rather than using the langauge) and I'm not
sure that he is aware that for the most part, unix == linux from an
application development standpoint.

It ain't me, babe!

(sing the rest of this old Turtles tune to yourself...)

--
Is God willing to prevent evil, but not able? Then he is not omnipotent.
Is he able, but not willing? Then he is malevolent.
Is he both able and willing? Then whence cometh evil?
Is he neither able nor willing? Then why call him God?
~ Epicurus

 

[Michael Press]

It ain't me, babe!

(sing the rest of this old Turtles tune to yourself...)

They might have covered it, but it ain't theirs, babe.

 

[ImpalerCore]

They might have covered it, but it ain't theirs, babe.

Bob Dylan, as are many of the classic remix hits like the Byrds "Mr.
Tambourine Man", Hendrix "All Along the Watchtower", and others. The
best use of Bob Dylan music is to annoy pop-culture teenager
passengers while driving.

 

[Michael Press]

Bob Dylan, as are many of the classic remix hits like the Byrds "Mr.
Tambourine Man", Hendrix "All Along the Watchtower", and others. The
best use of Bob Dylan music is to annoy pop-culture teenager
passengers while driving.

"Don't put on any airs when you're down on Rue Morgue Avenue."