[MUD-Dev] Event Scheduling

[Cynbe ru Taren]

> Hans-Henrik Staerfeldt <hhs at cbs.dtu.dk> wrote:

| Now, making log_2(N) single-bit operations takes O(1) time on a computer,

*chuckle*

One of the great things about math is that you can prove
anything you want, merely by making the appropriate
assumptions.

Yes, if you posit a machine which gets faster as the problems get
bigger, beating the O( N * log( N )) bound isn't hard.

They in fact explicitly assume the size of the numbers being sorted
stays bounded as N increases, which as I pointed out in my previous
letter immediately trivializes the problem -- reduces it to O(N) in
the asymptotic limit merely by treating it as a counting or binning
problem.

So by only going to O( N * log( log( N ) ) ) they are
missing the boat by a fair fraction! :)

If one were to be somewhat honest about the entire hack they are
working on -- which is not without intrinsic interest -- one would
concede that in any practical situation, the size of the values being
sorted rises as log(N), and that the bit-parallel capabilities of a
particular machine are fixed at the time it is made, rather than
conveniently varying as N varies: You would then be able to do bit
parallel hacks on (say) quadruples of values at a time when they were
small, pairs of values later on, and finally only individual values:
The natural O(N*log(N)) value would then re-appear, knocked down by a
constant factor due to the fixed additional parallelism being
employed.

In honest analytical terms, what they are doing is solving small
problems less efficiently than larger problems, and then conveniently
cutting off the scaling (at considerable violence to the entire
Knuthian notion of asymptotic analysis -- it didn't really originally
mean "ending at the first inconvenient value"!) in order to get an
artificially flat "asymptotic" formula.

Still, anything that gets you a PhD, I suppose!

It was this sort of BS that eliminated in me any
temptation to go through the PhD circus... :(

 Cynbe



_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev