Re: CONFIG_VFAT_FS_DUALNAMES regressions

[Pavel Machek]

Hi!

>  > >   - Similarly, there is a small chance that chkdsk on Windows will
>  > >     rename one file in a directory if they happen to have the same 11
>  > >     byte dummy values. The probability of this happening is
>  > >     approximately 80x lower than with the previous patch.
>  > 
>  > The "small chance" seems to be 90% for 30000 files in directory. And
>  > no, it is probably not 80x lower. Do the math.
> 
> Perhaps you could double check my math? 
> 
> The number of combinations available with the current patch is 
> 35^6 * 7 * 8 for files (for directories there are more combinations, 
> but lets ignore that for now).
> 
> That comes to 102942875000 combinations.
> 
> Now we can do the exponential birthday approximation, which is:
> 
>   p = 1.0 - exp(-(n * (n-1)) / (2 * m))
> 
> where n is the number of entries in the directory, and m is the total
> number of combinations.
> 
> That comes to about 0.0052 for 32767 files in a directory
> (ie. maximully full), or about 0.5%.
> 
> With the previous patch we had 2^30 combinations, which came to 0.393,
> or about 39%. So the new patch has about 75x lower chance of a single
> collision than the old one.
> 
> Similarly for 100 files, the old patch gave a probability of
> 4.6*10^-6, whereas the new one gives 4.8x10^-8, which is about 96x
> lower chance of a single collision. 

I guess I should apologize here. I did not do the math. It just seemed
to me that from the paradox of twins, difference should be
greater. Sorry for confusion.
									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/