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
On Fri, Sep 24, 2010 at 23:18, Matt Turner <mattst88@gmail.com> wrote:
> 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
>
I know. That's why I didn't write a bug. ;-)