[squeak-dev] The Trunk: Kernel-bf.899.mcz

Levente Uzonyi leves at elte.hu
Sun Feb 15 21:02:18 UTC 2015


Thanks for the pointer. It indeed has an implementation of MT, but it's 
not very efficient (I suspect that it was written by a student, who was 
new to Smalltalk, or Squeak), and it also has a few bugs. I decided to 
roll my own version, which can be found in the Inbox as Kernel-ul.903.

Levente

On Fri, 13 Feb 2015, Nicolas Cellier wrote:

> Also look into Sci-Smalltalk, there are several PRNG there.
> For large integers, we need to construct them by chunk anyway.
> 
> We construct a large X in interval [0,2^N-1], where for example N is a multiple of 32 for simple PRNG.
> Then we perform Max * X // (2^N) for generating in interval [0,Max-1].
> Some guard must be taken with N > highbit(Max) so as to obtain a fair distribution (uniform).
> 
> 
> 2015-02-12 20:46 GMT+01:00 Levente Uzonyi <leves at elte.hu>:
>       It seems like it only has csprngs. I see there one based on the Fortuna algorithm, and one based on SHA1 in counter mode.
>
>       Levente
>
>       On Thu, 12 Feb 2015, Levente Uzonyi wrote:
>
>             IIRC it has a mersenne twister (which is a quite common choice for prngs). We should check the implementation and see if it's efficient enough.
>
>             Levente
>
>             On Thu, 12 Feb 2015, Chris Muller wrote:
>
>                   Maybe adopt one of the ones from the Cryptography package?
>
>                   On Thu, Feb 12, 2015 at 12:52 PM, Levente Uzonyi <leves at elte.hu> wrote:
>                         On Tue, 10 Feb 2015, Bert Freudenberg wrote:
>
>                               On 10.02.2015, at 15:37, commits at source.squeak.org wrote:
> 
>
>                                     Bert Freudenberg uploaded a new version of Kernel to project The Trunk:
>                                     http://source.squeak.org/trunk/Kernel-bf.899.mcz
>
>                                     ==================== Summary ====================
>
>                                     Name: Kernel-bf.899
>                                     Author: bf
>                                     Time: 10 February 2015, 4:37:05.988 pm
>                                     UUID: 1cc7d0c6-0a3d-457f-9609-fa508d11310e
>                                     Ancestors: Kernel-eem.898
>
>                                     Fix random for Really Large Integers.
>
>                                     =============== Diff against Kernel-eem.898 ===============
>
>                                     Item was changed:
>                                      ----- Method: Random>>nextInt: (in category 'accessing') -----
>                                      nextInt: anInteger
>                                             " Answer a random integer in the interval [1, anInteger].
>                                     anInteger should be less than 16r80000000. "
>
>                                             anInteger strictlyPositive ifFalse: [ self error: 'Range must be
>                                     positive' ].
>                                     +       "avoid Float arithmetic in #next to work with LargeInts"
>                                     +       ^ ((seed := self nextValue) asInteger * anInteger // M asInteger)
>                                     + 1!
>                                     -       ^ (self next * anInteger) truncated + 1!
> 
> 
> 
>
>                               We might want to do something better if anInteger > 16r80000000, because
>                               that's the maximum number of different random integers we can produce. We
>                               would need to call nextValue twice (or more times) to produce enough
>                               randomness.
> 
> 
>
>                         Fetching more bits from the generator won't be better. This generator has 31
>                         bits internal state, so it can't generate longer random numbers.
>                         We need a better PRNG.
>
>                         Levente
> 
> 
>
>                               My fix just solves the immediate problem of running into infinite Floats.
>
>                               - Bert -
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
>


More information about the Squeak-dev mailing list