atRandom & integer agnosticism

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

atRandom & integer agnosticism

David Richards
Hello community.

Kindly consider:

| n i r |
n := ( 2 ** 256 ) - 1 .  "the largest 256-bit value"
i := ( 0 to: n ) .  "the interval 0 to 2**256-1"
"Produce three sets of computed test results."
3 timesRepeat: [
   Transcript show: ( r := i atRandom ) ; cr .
   Transcript show: ( r asByteArray hex ) ; cr . ]

According to comments in Pharo library code, atRandom fails for integer magnitudes greater than 2**30 .  A reason for this limitation is not given, and it's not clear to a novice such as myself why the computed result of atRandom is permitted to sometimes be in conflict with the semantics of atRandom .

Can anyone provide a basic explanation of the rationale for a 'broken' atRandom ?

Alternatively, is this a known bug?

Thanks.
dr
Reply | Threaded
Open this post in threaded view
|

Re: atRandom & integer agnosticism

Nicolas Cellier
Try it in Squeak and pick the relevant methods. Open a bug report and commit the fix. Of course, original authorship will somehow be spoiled, so be kind and cite them in commit message.

Le lun. 11 févr. 2019 à 07:59, David Richards <[hidden email]> a écrit :
Hello community.

Kindly consider:

| n i r |
n := ( 2 ** 256 ) - 1 .  "the largest 256-bit value"
i := ( 0 to: n ) .  "the interval 0 to 2**256-1"
"Produce three sets of computed test results."
3 timesRepeat: [
   Transcript show: ( r := i atRandom ) ; cr .
   Transcript show: ( r asByteArray hex ) ; cr . ]

According to comments in Pharo library code, atRandom fails for integer magnitudes greater than 2**30 .  A reason for this limitation is not given, and it's not clear to a novice such as myself why the computed result of atRandom is permitted to sometimes be in conflict with the semantics of atRandom .

Can anyone provide a basic explanation of the rationale for a 'broken' atRandom ?

Alternatively, is this a known bug?

Thanks.
dr
Reply | Threaded
Open this post in threaded view
|

Re: atRandom & integer agnosticism

Henrik Sperre Johansen
In reply to this post by David Richards
The "random" index for atRandom is, basically, computed prngOutput mod:
selectionRange.

For large selection ranges, it fails because the period of the PRNG used by
atRandom is 2^30th, with the output an integer in the range 1 - 2^30th. (in
other words, the prng is a repeating sequence of every number between 1 and
2^30th)

That means:
- There will be bias when the range you pick from approaches 2^30th.
- There will be gaps (indexes that won't ever be picked) once you pass
2^30th.

The reason is techical; the default RNG is a reasonable compromise between
speed, memory, and usable range.
If the intended use requires a larger range, an appropriate random number
generator can be provided using atRandom:
It certainly could give an error and/or select another RNG automatically if
outside applicable range, but no one has been bothered enough to do either,
yet.

Cheers,
Henry



--
Sent from: http://forum.world.st/Pharo-Smalltalk-Developers-f1294837.html

Reply | Threaded
Open this post in threaded view
|

Re: atRandom & integer agnosticism

David Richards
In reply to this post by Nicolas Cellier
Thanks Nicolas and Henry,

For now, simple alternative expressions can easily generate the values I need for my project, such as:

(String new: 32) collect: [ :each | '0123456789abcdef' atRandom ]

Maybe in a few months (or years!) from now I will have acquired enough ambient familiarity with Pharo to attempt a fix. But, for the time being, I'll just avoid stepping on the landmine.

In doing some research on this problem I spotted this, which seemed to possibly point a way toward a cutting edge RNG implementation for Pharo:


image.png

David

On Sun, 10 Feb 2019 at 23:21, Nicolas Cellier <[hidden email]> wrote:
Try it in Squeak and pick the relevant methods. Open a bug report and commit the fix. Of course, original authorship will somehow be spoiled, so be kind and cite them in commit message.

Le lun. 11 févr. 2019 à 07:59, David Richards <[hidden email]> a écrit :
Hello community.

Kindly consider:

| n i r |
n := ( 2 ** 256 ) - 1 .  "the largest 256-bit value"
i := ( 0 to: n ) .  "the interval 0 to 2**256-1"
"Produce three sets of computed test results."
3 timesRepeat: [
   Transcript show: ( r := i atRandom ) ; cr .
   Transcript show: ( r asByteArray hex ) ; cr . ]

According to comments in Pharo library code, atRandom fails for integer magnitudes greater than 2**30 .  A reason for this limitation is not given, and it's not clear to a novice such as myself why the computed result of atRandom is permitted to sometimes be in conflict with the semantics of atRandom .

Can anyone provide a basic explanation of the rationale for a 'broken' atRandom ?

Alternatively, is this a known bug?

Thanks.
dr
Reply | Threaded
Open this post in threaded view
|

Re: atRandom & integer agnosticism

Nicolas Cellier
Thanks for this link.
Note that there are quite good classical PRNG already programmed for Pharo in package Polymath including a Mersenne twister and Marsaglia KISS as used in gfortran...
(I did not check recently but there should be a catalog entry for Polymath).
The one programmed in Squeak is a Mersenne Twister I think, carefully written for maximizing performance for 32bits VM (with 31bit SmallIntegers).

IMO, the Park-Miller PRNG was a good default choice in the 70s when it was introduced in Smalltalk.
But now, we have fast enough machines to not bother with its limitations.

Le lun. 11 févr. 2019 à 15:58, David Richards <[hidden email]> a écrit :
Thanks Nicolas and Henry,

For now, simple alternative expressions can easily generate the values I need for my project, such as:

(String new: 32) collect: [ :each | '0123456789abcdef' atRandom ]

Maybe in a few months (or years!) from now I will have acquired enough ambient familiarity with Pharo to attempt a fix. But, for the time being, I'll just avoid stepping on the landmine.

In doing some research on this problem I spotted this, which seemed to possibly point a way toward a cutting edge RNG implementation for Pharo:


image.png

David

On Sun, 10 Feb 2019 at 23:21, Nicolas Cellier <[hidden email]> wrote:
Try it in Squeak and pick the relevant methods. Open a bug report and commit the fix. Of course, original authorship will somehow be spoiled, so be kind and cite them in commit message.

Le lun. 11 févr. 2019 à 07:59, David Richards <[hidden email]> a écrit :
Hello community.

Kindly consider:

| n i r |
n := ( 2 ** 256 ) - 1 .  "the largest 256-bit value"
i := ( 0 to: n ) .  "the interval 0 to 2**256-1"
"Produce three sets of computed test results."
3 timesRepeat: [
   Transcript show: ( r := i atRandom ) ; cr .
   Transcript show: ( r asByteArray hex ) ; cr . ]

According to comments in Pharo library code, atRandom fails for integer magnitudes greater than 2**30 .  A reason for this limitation is not given, and it's not clear to a novice such as myself why the computed result of atRandom is permitted to sometimes be in conflict with the semantics of atRandom .

Can anyone provide a basic explanation of the rationale for a 'broken' atRandom ?

Alternatively, is this a known bug?

Thanks.
dr