Re: Possible F77 Code Improvement ??

<nmm1@xxxxxxxxx> wrote in message
news:gpaop6$fg2$1@xxxxxxxxxxxxxxxxxxxxxxxxxxx

This is one of the places where Knuth and almost all of the other
standard references fall down badly, because computer scientists
have more trouble with probability and statistics than physicists!
There is a vastly better way, which I reinvented in the 1970s after
looking that that section, but which is much older.

Elementary probability will give you a rigorous estimate of a quantile
and its error bounds from a sample. You then pass through the data,
separating it into below the lower bound, in the middle, and above
the upper - and keeping a random sample of points in each range.

Then recalculate which range you want, the quantile in that range,
and repeat. If I recall, that is strictly O(N) with probability one.
Knuth almost certainly knows what that term means, but I can witness
that very few computer scientists do.

Also, the changeover point where it is faster than a good sort is
c. 100 items - which means that it isn't worth it for the median and
two quartiles until c. 1,000,000 items, and is a completely stupid
idea for deciles. Unless you are doing it for out-of-memory data,
when it can be better.

On a previous remark in this thread, the same lack of understanding
causes the 'standard' analyses of the complexity of things like
addressing sorts to be flawed. Typically, they rely on the data's
distribution having a mean, often having a moment of |X|^(1+e) for
some strictly positive e, and occasionally a variance.

I can't understand fully what your post is saying. Are you saying
that an algorithm for finding the median that relies on random
factors to be faster than O(N**2) is to be recommended over the
more well-known O(N) method that takes about 6*N comparisons to do
the deed?

E.g.,

http://home.comcast.net/~kmbtib/Fortran_stuff/order_stat.i90
http://home.comcast.net/~kmbtib/Fortran_stuff/order_stat_test.f90

--
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end


.

Relevant Pages

  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > What is the probability that the ad verecundiam fallacy is not an error of reasoning? ... * Expert community may in fact agree that X is true. ... responses that have been given to you. ... computer scientists who responded to you have a poorer understanding ...
    (comp.theory)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > What is the probability that the ad verecundiam fallacy is not an error of reasoning? ... * Expert community may in fact agree that X is true. ... responses that have been given to you. ... computer scientists who responded to you have a poorer understanding ...
    (comp.lang.cpp)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > What is the probability that the ad verecundiam fallacy is not an error of reasoning? ... * Expert community may in fact agree that X is true. ... responses that have been given to you. ... computer scientists who responded to you have a poorer understanding ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... Peter Olcott wrote: ... >> What is the probability that all of the computer scientists who ... >> responded to you have a poorer understanding of the problem than ...
    (comp.lang.cpp)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... Peter Olcott wrote: ... >> What is the probability that all of the computer scientists who ... >> responded to you have a poorer understanding of the problem than ...
    (sci.logic)