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 large ranges returns binary-sparse result #5734

Closed
p6rt opened this issue Oct 7, 2016 · 11 comments
Closed

.pick on large ranges returns binary-sparse result #5734

p6rt opened this issue Oct 7, 2016 · 11 comments

Comments

@p6rt
Copy link

p6rt commented Oct 7, 2016

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

Searchable as RT129829$

@p6rt
Copy link
Author

p6rt commented Oct 7, 2016

From @ajs

From IRC​:

[15​:12] <harmil_wk> m​: say ((2**80) ..^ (2**81)).pick.base(2)
[15​:12] <+camelia> rakudo-moar 605f27​:
OUTPUT«100011101100100110010000000000000000000000000000000000010101111110101101010011001␤»

The middle part is always a large number of zeros, but it's my
understanding that it should be a more uniform and continuous range of
results.

--
Aaron Sherman, M.​:
P​: 617-440-4332 Google Talk, Email and Google Plus​: ajs@​ajs.com
Toolsmith, developer, gamer and life-long student.

@p6rt
Copy link
Author

p6rt commented Oct 7, 2016

From @pmichaud

On Fri, Oct 07, 2016 at 12​:18​:43PM -0700, Aaron Sherman wrote​:

[15​:12] <harmil_wk> m​: say ((2**80) ..^ (2**81)).pick.base(2)
[15​:12] <+camelia> rakudo-moar 605f27​:
OUTPUT«100011101100100110010000000000000000000000000000000000010101111110101101010011001␤»

The middle part is always a large number of zeros, but it's my
understanding that it should be a more uniform and continuous range of
results.

Awesome catch! The current implementation of Range.pick() is based on
Range.roll(), which uses nqp​::rand_I() to choose a random value from
an integer range.

I'm guessing nqp​::rand_I() is returning a 32-bit number, and so Range.pick/
Range.roll are actually only returning values from 2**80 to 2**80+2**32-1 .

Pm

@p6rt
Copy link
Author

p6rt commented Oct 7, 2016

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

@p6rt
Copy link
Author

p6rt commented Oct 8, 2016

From @lizmat

On 07 Oct 2016, at 21​:28, Patrick R. Michaud <pmichaud@​pobox.com> wrote​:

On Fri, Oct 07, 2016 at 12​:18​:43PM -0700, Aaron Sherman wrote​:

[15​:12] <harmil_wk> m​: say ((2**80) ..^ (2**81)).pick.base(2)
[15​:12] <+camelia> rakudo-moar 605f27​:
OUTPUT«100011101100100110010000000000000000000000000000000000010101111110101101010011001␤»

The middle part is always a large number of zeros, but it's my
understanding that it should be a more uniform and continuous range of
results.

Awesome catch! The current implementation of Range.pick() is based on
Range.roll(), which uses nqp​::rand_I() to choose a random value from
an integer range.

I'm guessing nqp​::rand_I() is returning a 32-bit number, and so Range.pick/
Range.roll are actually only returning values from 2**80 to 2**80+2**32-1 .

$ 6 'use nqp; say "$_​: {nqp​::rand_I(2**$_,Int).base(2)}" for 58 .. 65'
58​: 1111001001001110101010001110011
59​: 1001111001110100011111001011100
60​: 11001111001100000101100000011
61​: 10110000111000000101110101010
62​: 1000000000000000000000000000000111100110101101101110111001101
63​: 101000000000000000000000000000000001010101010110011001001111000
64​: 1001000000000000000000000000000000101100110111100001110010111100
65​: 10100000000000000000000000000000001101111110111111010001100001100

$ 6 'use nqp; say "$_​: {nqp​::rand_I(2**$_,Int).base(2)}" for 120 .. 130'
120​: 1011010110010100011000000000010000000000000000000000000000000010000000101100000000111011111
121​: 1101110011110100000000010011101000000000000000000000000000000001011101111100111110000010101
122​: 11000000000000000000000000000000001011101110000000000100001110000000000000000000000000000001011101010011010100010000100100
123​: 101000000000000000000000000000001111100100000101100100000010100000000000000000000000000000001101110000111011101100011101000
124​: 1000110000101010010001010110101000000000000000000000000000000010101100110011011110100000101
125​: 1111000000000000000000000000000000101001001101011110000111111000000000000000000000000000000000010000100001100111010111101011
126​: 100001000000000000000000000000000001010000101011010110011100110000000000000000000000000000000000101000010100011010100110110001
127​: 1101111000000000000000000000000000001010111001110011101110110000000000000000000000000000000000000010111111111010010101100111101
128​: 100100000000000000000000000000000001001001011000011110111101111011000000000000000000000000000000111100101100011001100111100000
129​: 111111100000000000000000000000000000001110010111010100011101000100111000000000000000000000000000001101111100100000001000101100001
130​: 10111001000000000000000000000000000001111101011011110000101011100001000000000000000000000000000000000101001100110111101000011101

Feels slightly more complicated than that. But there’s definitely some 32bitness involved.

Liz

@p6rt
Copy link
Author

p6rt commented Oct 8, 2016

From @lizmat

On 07 Oct 2016, at 21​:28, Patrick R. Michaud <pmichaud@​pobox.com> wrote​:

On Fri, Oct 07, 2016 at 12​:18​:43PM -0700, Aaron Sherman wrote​:

[15​:12] <harmil_wk> m​: say ((2**80) ..^ (2**81)).pick.base(2)
[15​:12] <+camelia> rakudo-moar 605f27​:
OUTPUT«100011101100100110010000000000000000000000000000000000010101111110101101010011001␤»

The middle part is always a large number of zeros, but it's my
understanding that it should be a more uniform and continuous range of
results.

Awesome catch! The current implementation of Range.pick() is based on
Range.roll(), which uses nqp​::rand_I() to choose a random value from
an integer range.

I'm guessing nqp​::rand_I() is returning a 32-bit number, and so Range.pick/
Range.roll are actually only returning values from 2**80 to 2**80+2**32-1 .

Actually, this appears to be a MoarVM specific issue​:

$ ./perl6 -e 'use nqp; say "$_​: {nqp​::rand_I(2**$_,Int).base(2)}" for 58 .. 65'
58​: 100100000001000010110110001000100000101010110001100111101
59​: 11110010110000101100000101001101011110011011001011000110110
60​: 1111001100010111000110101010101100001101100100011011100001
61​: 11101111011010011101111000101010100101101010011010010000100
62​: 11101100100111100101000000100101010010000110011011001111111011
63​: 1011110010011000010110101111110100110001000100010011101000111
64​: 110111111011110110110000101011110111100111100110101110101100011
65​: 10101010010101100111111000001100111100110001001010001101000011

$ ./perl6 -e 'use nqp; say "$_​: {nqp​::rand_I(2**$_,Int).base(2)}" for 120 .. 130'
120​: 101100000000100000100100110101010001010010101000010011011001000100110101111001010110001111110111100101011110110010001101
121​: 1111011110001010100110101000110110001001001100100101111101001101100010101110000111111110011000011000010100011000100110011
122​: 11101011010101110110110111011000101111100111011000111000001001101000111001010101011000010110110101101111100011001111000010
123​: 11101101010011111001110101101100110011000110100110011110011001011101111011111001010110111111111111110011010100011110001001
124​: 1101100101110101010100001011100101001111111100000011101011101000110100010111001001111101110001100101110001101000010011100010
125​: 10011000110001001101001001000000011101101000111101111110100111001001000101100111100001111001101001001000110001101111011001011
126​: 110100010001010011010100010000000111011100101011011001101010011100000001100111110000111110100101100000111100010110111010011
127​: 10010000010011000101010000000110101101110000111101111011001111000111011000010110111100100110000110001101001110000101001010010
128​: 11110010000001100110010000101111111000101101111000011001101001100001110010110101110101101010101110100011010110001001000000111000
129​: 100001010110011010110110001110011000000100011110111011010110100000011110000001011100100000110110111101010011111001000001111001
130​: 1101111101010101110001010000000000101100010100110100110000110011101100110111100010111111111111111011110011001010100111100101011000

@p6rt
Copy link
Author

p6rt commented Oct 8, 2016

From @lizmat

On 07 Oct 2016, at 21​:28, Patrick R. Michaud <pmichaud@​pobox.com> wrote​:

On Fri, Oct 07, 2016 at 12​:18​:43PM -0700, Aaron Sherman wrote​:

[15​:12] <harmil_wk> m​: say ((2**80) ..^ (2**81)).pick.base(2)
[15​:12] <+camelia> rakudo-moar 605f27​:
OUTPUT«100011101100100110010000000000000000000000000000000000010101111110101101010011001␤»

The middle part is always a large number of zeros, but it's my
understanding that it should be a more uniform and continuous range of
results.

Awesome catch! The current implementation of Range.pick() is based on
Range.roll(), which uses nqp​::rand_I() to choose a random value from
an integer range.

I'm guessing nqp​::rand_I() is returning a 32-bit number, and so Range.pick/
Range.roll are actually only returning values from 2**80 to 2**80+2**32-1 .

Digging deeper into the rabbit hole, I wind up at​:

MVM_bigint_rand in src/math/bigintops.c​:

and there the mp_rand and mp_mod calls feel suspect to me. But then I’m out of my league, so I hope that someone else will be able to pick up from here.

Liz

@p6rt
Copy link
Author

p6rt commented Oct 8, 2016

From @timo

Apparently libtommath is known to leave some bits 0 when specific
conditions for the defines are met; i haven't looked but i suspect we
are hitting exactly this problem​:

libtom/libtommath#56

not sure why it's been quiet since april.

@p6rt
Copy link
Author

p6rt commented Oct 10, 2016

From @zoffixznet

Looks like libtommath has now been fixed​: libtom/libtommath#57

On Sat Oct 08 14​:47​:40 2016, timo wrote​:

Apparently libtommath is known to leave some bits 0 when specific
conditions for the defines are met; i haven't looked but i suspect we
are hitting exactly this problem​:

libtom/libtommath#56

not sure why it's been quiet since april.

@p6rt
Copy link
Author

p6rt commented Oct 10, 2016

From @lizmat

On 10 Oct 2016, at 05​:19, Zoffix Znet via RT <perl6-bugs-followup@​perl.org> wrote​:

Looks like libtommath has now been fixed​: libtom/libtommath#57

On Sat Oct 08 14​:47​:40 2016, timo wrote​:

Apparently libtommath is known to leave some bits 0 when specific
conditions for the defines are met; i haven't looked but i suspect we
are hitting exactly this problem​:

libtom/libtommath#56

not sure why it's been quiet since april.

Great!

But what is the policy on 3rdparty module updates? Do we wait for the next libtommath release now? Or do we patch it in the MoarVM repo now?

@p6rt
Copy link
Author

p6rt commented Sep 23, 2017

From @skids

On Mon, 10 Oct 2016 04​:29​:33 -0700, elizabeth wrote​:

On 10 Oct 2016, at 05​:19, Zoffix Znet via RT <perl6-bugs-
followup@​perl.org> wrote​:

Looks like libtommath has now been fixed​:
libtom/libtommath#57

On Sat Oct 08 14​:47​:40 2016, timo wrote​:

Apparently libtommath is known to leave some bits 0 when specific
conditions for the defines are met; i haven't looked but i suspect
we
are hitting exactly this problem​:

libtom/libtommath#56

not sure why it's been quiet since april.

Great!

But what is the policy on 3rdparty module updates? Do we wait for
the next libtommath release now? Or do we patch it in the MoarVM repo
now?

MoarVM commit 6d5ea042fda removed the original workaround from PR#​357
in May, and nobody has complained (tests have been in for the original
RT#​109586 and passing for a long time.) I think this is finally behind
us, so I'm resolving this ticket.

@p6rt
Copy link
Author

p6rt commented Sep 23, 2017

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

@p6rt p6rt closed this as completed Sep 23, 2017
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