search

Raku / old-issue-tracker

Tickets from RT
https://github.com/Raku/old-issue-tracker/issues
2 stars 1 forks source link

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

Closed p6rt closed 7 years ago

p6rt commented 8 years ago

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

Searchable as RT129829$

p6rt commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

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

p6rt commented 8 years ago

From @lizmat

On 07 Oct 2016, at 21​:28, Patrick R. Michaud \pmichaud@&#8203;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 commented 8 years ago

From @lizmat

On 07 Oct 2016, at 21​:28, Patrick R. Michaud \pmichaud@&#8203;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 commented 8 years ago

From @lizmat

On 07 Oct 2016, at 21​:28, Patrick R. Michaud \pmichaud@&#8203;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 commented 8 years ago

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​:

https://github.com/libtom/libtommath/pull/56

not sure why it's been quiet since april.

p6rt commented 8 years ago

From @zoffixznet

Looks like libtommath has now been fixed​: https://github.com/libtom/libtommath/pull/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​:

https://github.com/libtom/libtommath/pull/56

not sure why it's been quiet since april.

p6rt commented 8 years ago

From @lizmat

On 10 Oct 2016, at 05​:19, Zoffix Znet via RT \perl6\-bugs\-followup@&#8203;perl\.org wrote​:

Looks like libtommath has now been fixed​: https://github.com/libtom/libtommath/pull/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​:

https://github.com/libtom/libtommath/pull/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 commented 7 years ago

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​: https://github.com/libtom/libtommath/pull/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​:

https://github.com/libtom/libtommath/pull/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 commented 7 years ago

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