lkml.org 
[lkml]   [2009]   [Aug]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
DateSat, 8 Aug 2009 14:19:22 +0200
FromPavel Machek <>
SubjectRe: CONFIG_VFAT_FS_DUALNAMES regressions
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


\
 
 \ /
  Last update: 2009-08-08 14:21    [from the cache]
©2003-2010