Re: need help ...

From: Eric Sosman (Eric.Sosman_at_sun.com)
Date: 05/17/04 

Date: Mon, 17 May 2004 14:08:49 -0400

Michael Wojcik wrote:
> In article <40A50D01.301@sun.com>, Eric Sosman <Eric.Sosman@sun.com> writes:
>
>> The algorithm I'm thinking of actually needs N distinct
>>values. Simply knowing that the range of generated numbers
>>contains more than N values is not good enough, nor is knowing
>>that the period of the PRNG exceeds N. You actually need a
>>"no duplicates among the first N values" guarantee.
>
>
> The "reservoir sampling" algorithm, on the other hand, doesn't need
> this guarantee. It just needs an unbiased PRNG (and since one can
> be constructed from a biased PRNG, that's pretty easy to do). There
> was a nice writeup on RS in _Dr Dobb's Journal_ a while back, but
> it's not available free at the DDJ site. No doubt it could be found
> on Google with little trouble.
>
> I don't have Knuth v2 here to compare the algorithm you mention with
> RS.

     Knuth's description of RS requires distinct values.
Each item enters the reservoir iff its associated random
value is greater than the smallest already present (and
bumps the smallest out). If equality occurs an ambiguity
arises, and it's not clear how to resolve the ambiguity
without introducing a bias.

     I don't have DDJ here to compare the algorithm you
mention with RS ;-) 

-- 
Eric.Sosman@sun.com

Relevant Pages

  • Re: need help ...
    ... Simply knowing that the range of generated numbers ... The "reservoir sampling" algorithm, on the other hand, doesn't need ... It just needs an unbiased PRNG (and since one can ... was a nice writeup on RS in _Dr Dobb's Journal_ a while back, ...
    (comp.lang.c)
  • Re: New Encryption Idea
    ... long before the 66.7 years you have claimed, this is a very real security ... so your algorithm is at best redundant. ... > time (it can take more in the MEAS encryption mode). ... RSA won't have the pRNG requirements ...
    (sci.crypt)
  • Re: your assistance is requested
    ... I take this proof that chicks don't know shit about computers? ... Park-Miller PRNG has an even smaller range of internal states, ... and the RC5 algorithm is far more involved ... should try to publish in a crypto conference or journal. ...
    (comp.compression)
  • Re: Alternative rand()-algorithm?
    ... > But you, or any competent attacker, could find out with little ... > matter of iterating the shuffling algorithm through seed values. ... And each output from that PRNG will leak some of that state. ... > Periodic reseeding compensates for the entropy lost in the PRNG ...
    (comp.lang.c)
  • Re: your assistance is requested
    ... I take this proof that chicks don't know shit about computers? ... Park-Miller PRNG has an even smaller range of internal states, ... and the RC5 algorithm is far more involved ... hardware and likely crack it in a couple days. ...
    (comp.compression)