[104857] in Cypherpunks
Re: Random array
daemon@ATHENA.MIT.EDU (David R. Conrad)
Thu Oct 29 22:46:45 1998
Date: Thu, 29 Oct 1998 21:07:09 -0500 (EST)
From: "David R. Conrad" <drc@adni.net>
To: coderpunks@toad.com
In-Reply-To: <199810291633.RAA26784@replay.com>
Reply-To: "David R. Conrad" <drc@adni.net>
On Thu, 29 Oct 1998, Anonymous wrote:
> A couple responders have said there is no SWAP_TIMES
> which would work. But I don't understand why the
> following wouldn't work:
>
> [M]ake sure that x and y can't be equal, since
> there's no point in swapping an element with itself.
>
> Now, simply calculate how many SWAP_TIMES it would take for it
> to be equally as likely that an element would not be touched as
> it would to land in its original spot.
>
> (255/256)^(t*2) = 1/256
> or
> t = ln(1/256)/(2*ln(255/256))
> or
> 708.3955
Even assuming that you can safely trust this number (I wouldn't), why
would you bother with an algorithm that required more than 256 iterations
when there is one which only requires 256?
Someone else already posted the well-known O(n) algorithm to which I'm
referring, so I won't repeat it here, but I would commend it to you.
David R. Conrad <drc@adni.net>
