February 2000
- datagram protocol design theory? (Question about multithreaded servers) Ola Fosheim Grøstad
- Library error J C Lawrence
- Semi-OT: Linux support in commercial MUDs? Ola Fosheim Grøstad
- From the Apache Referrer logs J C Lawrence
- From the Apache Referrer logs Kris Van Hees
- good muds for ai programming? Robert Zubek
- good muds for ai programming? J C Lawrence
- Event Scheduling Phillip Lenhardt
- Event Scheduling J C Lawrence
- Event Scheduling cg@ami-cg.GraySage.Edmonton.AB.CA
- Event Scheduling J C Lawrence
- Event Scheduling Phillip Lenhardt
- Event Scheduling J C Lawrence
- Event Scheduling Hans-Henrik Staerfeldt
- Event Scheduling Cynbe ru Taren
- Event Scheduling Hans-Henrik Staerfeldt
- Event Scheduling Cynbe ru Taren
- Event Scheduling Hans-Henrik Staerfeldt
- Event Scheduling Miroslav Silovic
- Event Scheduling Jp Calderone
- Event Scheduling Ola Fosheim Grøstad
- Event Scheduling Miroslav Silovic
- Event Scheduling J C Lawrence
- Event Scheduling Cynbe ru Taren
- Event Scheduling Hans-Henrik Staerfeldt
On Sat, 12 Feb 2000, Cynbe ru Taren wrote:
> > 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.
Well, if we cannot assume that log_2(N) single-bit operations takes
O(1) time on a computer, it would be dead-wrong to assume that things
like addition does either. After all, you need to make O(log_2(N))
bitwise additions to actually make an addition of two numbers that is
O(N). Yet, addition is considered O(1) by all other algorithm designers!
Why not make bitwise or the same? And use it?
> 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! :)
They would have if the algorithm ran on O(2^N) space, yes, but the size
of the largest integer/float your computer can hold in a register is not
equal to the size of your memory for bins, which is why they undeline
that the algorithm runs in O(N) space as well :-)
> 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.
Well, as many other implementations, N is limited by the register that
holds it. Your argument holds as well to any algorithm that uses addition
in (1) time. If you implement any algorithm using addition, that will
scale beyond the register size you run into exactly the same problem,
which is why this 'hack' is defendable. Or rather just as defendable as
any algorithm using addition in O(1) time.
I'm not at all sure what you mean by the values rises as log(N) in
'any practical situation'. <tease> Judgeing from your very theoretical
point of view, i would guess you would be against practical situations
</tease>
> 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.
I would say, that they solve the largest problems that can be solved by
any days computer more eficiently than those problems that cannot be
solved by any days computers.
I agree that bounding N to be contained in a register is very much
against the Knuthian notion of asymptotic analysis, but so would
constant time addition be, which would sort-of screw up big-oh analysis
as we know it, if we did not allow it.
> 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... :(
To my knowledge this is not his PHD thesis. Being on the commitee of both
STOC and ICALP is no small feat either.
Hans Henrik Stærfeldt | bombman@diku.dk | work: hhs@cbs.dtu.dk |
address: |___ +45 40383492 __|__ +45 45252425 __|
Dybendalsvej 74 2. th, | Scientific programmer at Center for Biological |
2720 Vanløse, Danmark. | Sequence Analysis, Technical University of Denmark|
- Event Scheduling Hans-Henrik Staerfeldt
- IO Speed Suggestions Christopher Kohnert
- IO Speed Suggestions J C Lawrence
- Couple of articles Koster, Raph
- Couple of articles Dr Richard A. Bartle
- OT: Soliciting advice from Canadians Alex Oren
- MUD Specific Building pages MichelleThompson
- MUD Specific Building pages J C Lawrence
- Embedding Python icecube@ihug.co.nz
- Embedding Python icecube@ihug.co.nz
- Embedding Python J C Lawrence
- Embedding Python Todd McKimmey
- Embedding Python Oliver Jowett
- Embedding Python Todd McKimmey
- ADMIN: List post rejections J C Lawrence
- distributed objects Kevin Littlejohn
- distributed objects Vijay Weasel Prabhakar
- distributed objects Brandon J. Rickman
- distributed objects J C Lawrence
- distributed objects Koster, Raph
- distributed objects Vijay Weasel Prabhakar
- distributed objects David Bennett
- distributed objects Phillip Lenhardt
- distributed objects cjones@one.net
- distributed objects F. Randall Farmer
- distributed objects Ola Fosheim Grøstad
- distributed objects Kevin Littlejohn
- distributed objects J C Lawrence
- distributed objects Gary Whitten
- distributed objects Balthazaar
- distributed objects J C Lawrence
- distributed objects Ola Fosheim Grøstad
- distributed objects Eli Stevens {Grey}
- distributed objects Jon A. Lambert
- distributed objects Charles Hughes
- distributed objects Caliban Tiresias Darklock
- distributed objects Charles Hughes
- distributed objects J C Lawrence
- distributed objects J C Lawrence
- distributed objects Charles Hughes
- distributed objects Charles Hughes
- distributed objects Laurent Bossavit
- distributed objects Kevin Littlejohn
- distributed objects markm@caplet.com
- distributed objects KevinL
- Distributed Objects Justin Rogers
- Security J C Lawrence
- commercial muds and cable TV (was code base inquiry ) Sellers, Michael
- commercial muds and cable TV (was code base inquiry ) Matthew Mihaly
- commercial muds and cable TV (was code base inq uiry ) Sellers, Michael
- commercial muds and cable TV (was code base inq uiry ) Matthew Mihaly
- business models Matthew Mihaly
- business models Daniel.Harman@barclayscapital.com
- business models Vincent Archer
- business models Dave Rickey
- a shrinking pool of players? Johan J Ingles-le Nobel
- a shrinking pool of players? Matthew Mihaly
- a shrinking pool of players? Sellers, Michael
- a shrinking pool of players? Bryce Harrington
- a shrinking pool of players? Travis S. Casey
- a shrinking pool of players? PartyG2816@aol.com
- a shrinking pool of players? J C Lawrence
- a shrinking pool of players? Sellers, Michael
- a shrinking pool of players? Sellers, Michael
- a shrinking pool of players? PartyG2816@aol.com
- a shrinking pool of players? Ryan P.
- a shrinking pool of players? J C Lawrence
- a shrinking pool of players? Koster, Raph
- a shrinking pool of players? Matthew Mihaly
- a shrinking pool of players? Koster, Raph
- a shrinking pool of players? Chris Turner
- a shrinking pool of players? Matthew Mihaly
- a shrinking pool of players? Chris Turner
- a shrinking pool of players? Draymoor
- a shrinking pool of players? Koster, Raph
- The Endeavour Map and MUD Applications Michael Hohensee
- The Endeavour Map and MUD Applications Ted Milker
- The Endeavour Map and MUD Applications David Bennett
- The Endeavour Map and MUD Applications Ted Milker
- The Endeavour Map and MUD Applications John Bertoglio
- The Endeavour Map and MUD Applications Justin Rogers
- The Endeavour Map and MUD Applications Eli Stevens {Grey}
- The Endeavour Map and MUD Applications John Bertoglio
- The Endeavour Map and MUD Applications Koster, Raph
- The Endeavour Map and MUD Applications Lo, Kam
- The Endeavour Map and MUD Applications Justin Rogers
- The Endeavour Map and MUD Applications Joel Dillon
- The Endeavour Map and MUD Applications Justin Rogers
- Next gen MUD wishlist Bryce Harrington
- Next gen MUD wishlist Bruce
- Next gen MUD wishlist Bryce Harrington
- Next gen MUD wishlist Bruce
- Next gen MUD wishlist J C Lawrence
- Next gen MUD wishlist Chris Jones
- Next gen MUD wishlist adam@treyarch.com
- Next gen MUD wishlist Sellers, Michael
- Next gen MUD wishlist adam@treyarch.com
- Next gen MUD wishlist Bruce
- Next gen MUD wishlist Bryce Harrington
- Codebase Ideas punitac@prodigy.net
- Codebase Ideas Bryce Harrington
- Codebase Ideas Aaron Mitchell
- OT: Money as motivator (was code base inquiry ) J C Lawrence
- OT: Money as motivator (was code base inquiry ) Matthew Mihaly
- Guide Applicant : Player Ratio Geoffrey A. MacDougall
- Guide Applicant : Player Ratio Matthew Mihaly
- MUD-Dev digest, Vol 1 #286 - 13 msgs Dr. Cat
- MUD-Dev digest, Vol 1 #286 - 13 msgs Caliban Tiresias Darklock
- MUD-Dev digest, Vol 1 #286 - 13 msgs Koster, Raph
- voice vs. text Matthew Mihaly
- voice vs. text Justin Rogers
- voice vs. text John Bertoglio
- voice vs. text Lovecraft
- voice vs. text Lo, Kam
- voice vs. text Hans-Henrik Staerfeldt
- Client side prediction Ola Fosheim Grøstad
- Client side prediction Koster, Raph
- Client side prediction Ola Fosheim Grøstad
- Client side prediction Justin Rogers
- Client side prediction Ola Fosheim Grøstad
- Client side prediction Koster, Raph
- Client side prediction Ola Fosheim Grøstad
- Dynamic help files, was code base inquiry Richard Woolcock
- OpenSource licenses for game rules? J C Lawrence
- To all the devoted! (fwd) J C Lawrence
- Newbies Johan J Ingles-le Nobel
- MUD-Dev digest, Vol 1 #288 - 9 msgs Dr. Cat
- (fwd) Commercial-use Restrictions on Code Bases (was: help me find 100% free graphical mud) J C Lawrence
- (fwd) ADMIN: "A Classification Of Muds" [was 'In defence of stock muds...'] J C Lawrence
- Distribution Geir Harald Hansen
- player persistence Matthew Mihaly
- [Off-topic] GDC-2000 Derek Snider
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] GDC-2000 Justin Lockshaw
- [Off-topic] GDC-2000 Christopher Allen
- [Off-topic] GDC-2000 Matthew Mihaly
- [Off-topic] GDC-2000 Joe Andrieu
- [Off-topic] GDC-2000 Kristen L. Koster
- [Off-topic] GDC-2000 Richard A. Bartle
- [Off-topic] GDC-2000 Bruce
- [Off-topic] GDC-2000 David Bennett
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] AAAI symposium (was: GDC-2000) Robert Zubek
- MSP Richard Ross
- Privateer-style mu*? Bobby Bailey
- Minimum community sizes Dan Root
- Minimum community sizes Koster, Raph
- Minimum community sizes Dan Root
- Minimum community sizes adam@treyarch.com
- Minimum community sizes Matthew Mihaly
- Minimum community sizes David Bennett
- Minimum community sizes Matthew Mihaly
- Pike codebase Daniel Podlejski
- chil@gate.net Joel Kelso