<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Event Scheduling -->
<!--X-From-R13: Qlaor eh Fnera <plaorNzhd.bet> -->
<!--X-Date: Sat, 12 Feb 2000 23:06:35 -0800 -->
<!--X-Message-Id: 200002130245.UAA08298#laurel,actlab.utexas.edu -->
<!--X-Content-Type: text/plain -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Event Scheduling</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:cynbe#muq,org">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00299.html">Previous</a>
| <a href="msg00300.html">Next</a>
]
Thread:
[ <a href="msg00295.html">Previous</a>
| <a href="msg00307.html">Next</a>
]
Index:
[ <A HREF="author.html#00302">Author</A>
| <A HREF="#00302">Date</A>
| <A HREF="thread.html#00302">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Event Scheduling</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Subject</em>: Re: [MUD-Dev] Event Scheduling</LI>
<LI><em>From</em>: Cynbe ru Taren <<A HREF="mailto:cynbe#muq,org">cynbe#muq,org</A>></LI>
<LI><em>Date</em>: Sat, 12 Feb 2000 20:45:40 -0600</LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Sender</em>: <A HREF="mailto:mud-dev-admin#kanga,nu">mud-dev-admin#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
> Hans-Henrik Staerfeldt <hhs#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#kanga,nu
<A HREF="http://www.kanga.nu/lists/listinfo/mud-dev">http://www.kanga.nu/lists/listinfo/mud-dev</A>
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<ul compact><li><strong>Follow-Ups</strong>:
<ul>
<li><strong><A NAME="00307" HREF="msg00307.html">Re: [MUD-Dev] Event Scheduling</A></strong>
<ul compact><li><em>From:</em> Hans-Henrik Staerfeldt <hhs#cbs,dtu.dk></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00299.html">Re: [MUD-Dev] MUD Specific Building pages</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00300.html">Re: [MUD-Dev] Raph's collection of MUD design Laws</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00295.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00307.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00302"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00302"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>Re: [MUD-Dev] Event Scheduling</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00285" HREF="msg00285.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#muq,org">cynbe#muq,org</a>, Wed 09 Feb 2000, 04:38 GMT
<UL>
<LI><strong><A NAME="00289" HREF="msg00289.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Hans-Henrik Staerfeldt <a href="mailto:hhs#cbs,dtu.dk">hhs#cbs,dtu.dk</a>, Wed 09 Feb 2000, 17:44 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00290" HREF="msg00290.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#muq,org">cynbe#muq,org</a>, Wed 09 Feb 2000, 19:02 GMT
<UL>
<LI><strong><A NAME="00295" HREF="msg00295.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Hans-Henrik Staerfeldt <a href="mailto:hhs#cbs,dtu.dk">hhs#cbs,dtu.dk</a>, Sun 13 Feb 2000, 00:10 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00302" HREF="msg00302.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#muq,org">cynbe#muq,org</a>, Sun 13 Feb 2000, 07:06 GMT
<UL>
<LI><strong><A NAME="00307" HREF="msg00307.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Hans-Henrik Staerfeldt <a href="mailto:hhs#cbs,dtu.dk">hhs#cbs,dtu.dk</a>, Mon 14 Feb 2000, 17:21 GMT
</LI>
</UL>
</LI>
</ul>
</LI>
<LI><strong><A NAME="00271" HREF="msg00271.html">[MUD-Dev] good muds for ai programming?</A></strong>,
Robert Zubek <a href="mailto:rob#ils,nwu.edu">rob#ils,nwu.edu</a>, Sun 06 Feb 2000, 01:33 GMT
<UL>
<LI><strong><A NAME="00272" HREF="msg00272.html">Re: [MUD-Dev] good muds for ai programming?</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Sun 06 Feb 2000, 02:22 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00270" HREF="msg00270.html">[MUD-Dev] From the Apache Referrer logs</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Sat 05 Feb 2000, 18:48 GMT
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>