On Fri, Sep 12, 2003 at 05:29:58PM -0400, Niels Provos wrote:
> On Fri, Sep 12, 2003 at 11:13:50AM +0100, David Laight wrote:
> > You need to:
> > a) read the code
> > b) understand what it it doing
> That is a good suggestion.  So, please let me provide you with my
> own understanding of this source code:
> 
> Out of every 15-bit block you select 30,000 non-repeating numbers.
> Afterwards, we switch to a new number space out of which we select
> another 30,000 non-repeating numbers.
> 
> So, the minimal distance is at least 30,000 IDs before you can expect
> any collision.

Nearly (remember Itojun said that 36000 was twice RU_MAX though).

Look closer and you see that 0 to 3 values are discared from the LCG
before the value that is used as m in the final k ** m mod n sum.
These are counted into the 30,000 - so each id uses 2.5 values from
the LCG and it switches to a new number space at 30000/25 = 12000.

> > RU_MAX itself is 30000, the worst case repeat is after 7500 numbers.
> > The average block contains 12000 numbers, so after that you start
> > getting a chance of a collision with the block before it.
> > On average 150 numbers into a block there is a 50% chance of a repeat
> > in the last 150 numbers of the block before the last.
> > 
> > Practically you have to assume repeats after 12000 numbers.
> I have no idea where you are getting these numbers from.

The 150 is from the following:
Take k different numbers from n, then a random number from the same n.
The chance that the random one is different from the k is (n - k)/n
The chance that k random ones are different is ((n - k)/n)**k
For n = 32768 and k 150 this is about 1/2.
(this isn't quite the correct sum, but is close enough and easier to
calculate)

> Ps: Obviously, I am biased in this discussion, as Itojun is my
> declared open-source hero.

Try a different hero :-)

	David

-- 
David Laight: david@l8s.co.uk