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

Levente Uzonyi leves at elte.hu
Sun Feb 15 21:12:53 UTC 2015


Yes, I expect them to be too slow to be used as a general purpose 
generator.
Here's a small benchmark with the Fortuna generator, Random, and MTRandom:

f := Fortuna key: (1 to: 32) asArray asByteArray.
[ f nextBytes: 4 ] bench. '7,480 per second.'. "32 bits"

r := Random new.
[ r nextValue ] bench. '5,740,000 per second.'. "31 bits"

r := MTRandom new.
[ r nextValue ] bench. '5,770,000 per second.'. "30 bits"

The comparison is not absolutely fair, because of the number of generated 
bits (see the comments), but it still shows, that Fortuna (as it is 
implemented in the Cryptography package) is 2-3 magnitudes slower than a 
well optimized PRNG.

Levente

On Fri, 13 Feb 2015, Chris Muller wrote:

> Well, is a csprng (I had to look that acronym up) a problem?  Do you
> mean its too slow?  Speed is important for the general case.
> Hopefully we'll find a solution that does not need to compromise
> randomness for speed.
>
> On Thu, Feb 12, 2015 at 1:46 PM, Levente Uzonyi <leves at elte.hu> wrote:
>> 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