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

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Fri Feb 13 18:39:43 UTC 2015


2015-02-13 13:43 GMT+01:00 Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com>:

> 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).
>
>
And as an example of unfair dice, let's generate an integer in [0,5] using
3 bits (8 solutions):
If the bit generator is fair, then the restriction in [0,5] is not:

((0 to: 7) collect: [:e | (e *6) bitShift: -3]) sorted
-> #(0 0 1 2 3 3 4 5)

0 and 3 have a probability of 25% while the others only 12.5%.
Of course, fairness improves when N grow.

An alternative algorithm would be to draw the fair bits and reject those
greater than 4
Indeed (0 to: 7) select: [:e | e < 6] is fair...
But we can reject up to half the toss when drawing a number in [0,2^(N-1)]
with N bits...


>
> 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 -
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20150213/4a907c44/attachment.htm


More information about the Squeak-dev mailing list