Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

.pick on a large range needs more entropy #2633

Closed
p6rt opened this issue Feb 1, 2012 · 10 comments
Closed

.pick on a large range needs more entropy #2633

p6rt opened this issue Feb 1, 2012 · 10 comments

Comments

@p6rt
Copy link

p6rt commented Feb 1, 2012

Migrated from rt.perl.org#109586 (status was 'resolved')

Searchable as RT109586$

@p6rt
Copy link
Author

p6rt commented Feb 1, 2012

From @moritz

17​:26 < TimToady> nom​: say (^2**64).pick.fmt('%64b')
17​:26 <+p6eval> nom ce5cca​:
OUTPUT«1010100001010011111100101101011101010001000000010000000000000000␤»

17​:27 < TimToady> pick from a large range might need to generate more
  entropy than a single standard rand call provides; note
  the trailing 0's above

Repeated execution shows that it indeed always ends with many 0's. So,
not random enough. http://xkcd.com/221/ applies :-)

@p6rt
Copy link
Author

p6rt commented Nov 21, 2012

From @FROGGS

current result​:

<FROGGS> p6​: say (^2**64).pick.fmt('%64b')
<p6eval> rakudo bf472b​: OUTPUT«
1010000000000000000000000000000␤»
<p6eval> niecza v22-36-g19fa03a​:
OUTPUT«1111000110011001010111011001011011000111000100110000101000101111␤»

<FROGGS> p6​: say (^2**64).pick.fmt('%64b')
<p6eval> rakudo bf472b​: OUTPUT«
1010000000000000000000000000000␤»
<p6eval> niecza v22-36-g19fa03a​: OUTPUT«
111001010000000101111101011110100011101110110110100111100000010␤»

<FROGGS> p6​: say (^2**64).pick.fmt('%64b')
<p6eval> niecza v22-36-g19fa03a​: OUTPUT«
110100110110110011101001010010100100100010100000111100101001001␤»
<p6eval> rakudo bf472b​: OUTPUT«
1010000000000000000000000000000␤»

@p6rt
Copy link
Author

p6rt commented Nov 21, 2012

The RT System itself - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

p6rt commented Apr 7, 2016

From @diakopter

12​:52 < diakopter> m​: say (^2**64).pick.fmt('%64b')
12​:52 <+camelia> rakudo-moar 61d231​: OUTPUT« 100000000000000000000000000000000110010100010000011100011101000␤»
12​:52 < diakopter> m​: say (^2**64).pick.fmt('%64b')
12​:52 <+camelia> rakudo-moar 61d231​: OUTPUT«1111000000000000000000000000000001000110110101110111110101111010␤»
12​:52 < diakopter> m​: say (^2**64).pick.fmt('%64b')
12​:52 <+camelia> rakudo-moar 61d231​: OUTPUT« 1110100100100010101011001111111␤»
12​:52 -!- labster [~Adium@​miraheze/Vorticity] has quit [Quit​: Leaving.]
12​:52 < diakopter> heh, drops leading zeroes
12​:53 < diakopter> ... not to mention still exhibiting the same behavior as in #​109586

@p6rt
Copy link
Author

p6rt commented Apr 8, 2016

From @skids

This goes all the way down to libtommath.

I filed libtom/libtommath#56 upstream.

In the meantime xor'ing two mp_rand's with one of them shifted up 32 bits in Moar's rand_I would be one possible workaround.

@p6rt
Copy link
Author

p6rt commented Apr 8, 2016

From mt1957.2@gmail.com

Hi,

For the dropped leading zeros try .fmt('%064b')

Greetings
Marcel

On April 7, 2016 6​:53​:44 PM "Matthew Wilson via RT"
<perl6-bugs-followup@​perl.org> wrote​:

12​:52 < diakopter> m​: say (^2**64).pick.fmt('%64b')
12​:52 <+camelia> rakudo-moar 61d231​: OUTPUT«
100000000000000000000000000000000110010100010000011100011101000␤»
12​:52 < diakopter> m​: say (^2**64).pick.fmt('%64b')
12​:52 <+camelia> rakudo-moar 61d231​:
OUTPUT«1111000000000000000000000000000001000110110101110111110101111010␤»
12​:52 < diakopter> m​: say (^2**64).pick.fmt('%64b')
12​:52 <+camelia> rakudo-moar 61d231​: OUTPUT«
1110100100100010101011001111111␤»
12​:52 -!- labster [~Adium@​miraheze/Vorticity] has quit [Quit​: Leaving.]
12​:52 < diakopter> heh, drops leading zeroes
12​:53 < diakopter> ... not to mention still exhibiting the same behavior as
in #​109586

@p6rt
Copy link
Author

p6rt commented Apr 8, 2016

From @skids

On Thu Apr 07 21​:47​:26 2016, bri@​abrij.org wrote​:

This goes all the way down to libtommath.

I filed libtom/libtommath#56 upstream.

In the meantime xor'ing two mp_rand's with one of them shifted up 32
bits in Moar's rand_I would be one possible workaround.

There is now a workaround PR#​357 to MoarVM for this.

Proposed test code​:

$ perl6 -e 'use Test; my $v = 2; for (1..259) { is ([+|] ((^$v).pick for ^200)), $v - 1, "$v.base(16) .pick hits all bits"; $v +<= 1; }'

@p6rt
Copy link
Author

p6rt commented Oct 16, 2016

From @FROGGS

PR was merged and test got added​:
MoarVM/MoarVM#357
Raku/roast@67c494ced2

Thanks to all involved!

1 similar comment
@p6rt
Copy link
Author

p6rt commented Oct 16, 2016

From @FROGGS

PR was merged and test got added​:
MoarVM/MoarVM#357
Raku/roast@67c494ced2

Thanks to all involved!

@p6rt
Copy link
Author

p6rt commented Oct 16, 2016

@FROGGS - Status changed from 'open' to 'resolved'

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant