This is the mail archive of the
libc-help@sourceware.org
mailing list for the glibc project.
Re: strfry does not always give a uniform distribution
- From: Matt Turner <mattst88 at gmail dot com>
- To: Steve Ward <planet36 at gmail dot com>
- Cc: libc-help at sourceware dot org
- Date: Fri, 24 Sep 2010 23:18:02 -0400
- Subject: Re: strfry does not always give a uniform distribution
- References: <AANLkTinfN3NV8QccvoKq2Ggib549S_7=j-wvP2R0u7EL@mail.gmail.com>
On Fri, Sep 24, 2010 at 10:55 PM, Steve Ward <planet36@gmail.com> wrote:
> The strfry function does not always give a uniform distribution. ?Run
> the attached program and you can see that (once every few tries)
> strfry is biased toward some permutations of the input string. ?I
> modified strfry to not use a custom prng state. ?It seems to behave
> much more fairly.
>
>
> Example output:
>
>
> DEFAULT_STR: ab
>
> max_iterations: 50000000
>
> getpid: 2862
>
> (1285379699) strfry...
> (1285379709) strfry_mod...
>
> strfry_histogram
> ab => 27952756 ?(55.9055%)
> ba => 22047244 ?(44.0945%)
>
> strfry_mod_histogram
> ab => 25002087 ?(50.0042%)
> ba => 24997913 ?(49.9958%)
>
>
>
> DEFAULT_STR: abc
>
> max_iterations: 25000000
>
> getpid: 3336
>
> (1285381555) strfry...
> (1285381561) strfry_mod...
>
> strfry_histogram
> abc => 3610465 ?(14.4419%)
> acb => 4723913 ?(18.8957%)
> bac => 3607390 ?(14.4296%)
> bca => 4726172 ?(18.9047%)
> cab => 4723147 ?(18.8926%)
> cba => 3608913 ?(14.4357%)
>
> strfry_mod_histogram
> abc => 4163372 ?(16.6535%)
> acb => 4165675 ?(16.6627%)
> bac => 4165102 ?(16.6604%)
> bca => 4170281 ?(16.6811%)
> cab => 4166255 ?(16.665%)
> cba => 4169315 ?(16.6773%)
>
>
>
> Steve Ward
Oh man, here we go.
http://sourceware.org/bugzilla/show_bug.cgi?id=4403