The Trunk: Kernel-bf.899.mcz
Locked
 
|
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! |
Re: The Trunk: Kernel-bf.899.mcz
|
|
On 10.02.2015, at 15:37, [hidden email] 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. My fix just solves the immediate problem of running into infinite Floats. - Bert - |
smime.p7s (5K)
Re: The Trunk: Kernel-bf.899.mcz
|
|
On Tue, 10 Feb 2015, Bert Freudenberg wrote:
> On 10.02.2015, at 15:37, [hidden email] 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 - > > > > |
Re: The Trunk: Kernel-bf.899.mcz
|
|
Maybe adopt one of the ones from the Cryptography package?
On Thu, Feb 12, 2015 at 12:52 PM, Levente Uzonyi <[hidden email]> wrote: > On Tue, 10 Feb 2015, Bert Freudenberg wrote: > >> On 10.02.2015, at 15:37, [hidden email] 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 - >> >> >> >> > |
Re: The Trunk: Kernel-bf.899.mcz
|
|
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 <[hidden email]> wrote: >> On Tue, 10 Feb 2015, Bert Freudenberg wrote: >> >>> On 10.02.2015, at 15:37, [hidden email] 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 - >>> >>> >>> >>> >> > > |
Re: The Trunk: Kernel-bf.899.mcz
|
|
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 <[hidden email]> wrote: >>> On Tue, 10 Feb 2015, Bert Freudenberg wrote: >>> >>>> On 10.02.2015, at 15:37, [hidden email] 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 - >>>> >>>> >>>> >>>> >>> >> >> > > |
Re: The Trunk: Kernel-bf.899.mcz
|
|
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 <[hidden email]>: It seems like it only has csprngs. I see there one based on the Fortuna algorithm, and one based on SHA1 in counter mode. |
Re: The Trunk: Kernel-bf.899.mcz
|
|
2015-02-13 13:43 GMT+01:00 Nicolas Cellier <[hidden email]>:
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...
|
Re: The Trunk: Kernel-bf.899.mcz
|
|
In reply to this post by Levente Uzonyi-2
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 <[hidden email]> 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 <[hidden email]> wrote: >>>> >>>> On Tue, 10 Feb 2015, Bert Freudenberg wrote: >>>> >>>>> On 10.02.2015, at 15:37, [hidden email] 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 - >>>>> >>>>> >>>>> >>>>> >>>> >>> >>> >> >> > |
Re: The Trunk: Kernel-bf.899.mcz
|
|
In reply to this post by Nicolas Cellier
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 <[hidden email]>: > 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 <[hidden email]> wrote: > On Tue, 10 Feb 2015, Bert Freudenberg wrote: > > On 10.02.2015, at 15:37, [hidden email] 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 - > > > > > > > > > > > > > |
Re: The Trunk: Kernel-bf.899.mcz
|
|
In reply to this post by Chris Muller-3
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 <[hidden email]> 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 <[hidden email]> wrote: >>>>> >>>>> On Tue, 10 Feb 2015, Bert Freudenberg wrote: >>>>> >>>>>> On 10.02.2015, at 15:37, [hidden email] 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 - >>>>>> >>>>>> >>>>>> >>>>>> >>>>> >>>> >>>> >>> >>> >> > > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |