[squeakdev] The Trunk: Kernelbf.899.mcz
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Fri Feb 13 18:39:43 UTC 2015
20150213 13:43 GMT+01:00 Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com>:
> Also look into SciSmalltalk, 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^N1], where for example N is a
> multiple of 32 for simple PRNG.
> Then we perform Max * X // (2^N) for generating in interval [0,Max1].
> 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^(N1)]
with N bits...
>
> 20150212 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/Kernelbf.899.mcz
>>>>>>>
>>>>>>> ==================== Summary ====================
>>>>>>>
>>>>>>> Name: Kernelbf.899
>>>>>>> Author: bf
>>>>>>> Time: 10 February 2015, 4:37:05.988 pm
>>>>>>> UUID: 1cc7d0c60a3d457f9609fa508d11310e
>>>>>>> Ancestors: Kerneleem.898
>>>>>>>
>>>>>>> Fix random for Really Large Integers.
>>>>>>>
>>>>>>> =============== Diff against Kerneleem.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/squeakdev/attachments/20150213/4a907c44/attachment.htm
More information about the Squeakdev
mailing list
