Smalltalk › Pharo › Pharo Smalltalk Developers

atRandom & integer agnosticism

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

5 messages Options

David Richards

atRandom & integer agnosticism

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.

Nicolas Cellier

Re: atRandom & integer agnosticism

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

Henrik Sperre Johansen

Re: atRandom & integer agnosticism

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

David Richards

Re: atRandom & integer agnosticism

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:

http://xoshiro.di.unimi.it/#intro

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

Nicolas Cellier

Re: atRandom & integer agnosticism

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:

http://xoshiro.di.unimi.it/#intro

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