help with random numbers?

I profiled this simple program

Eval [
     | n k r |
     r := Random new.
     n := 100000.
     k := 500.
     (1 to: n) select: [:x |
         (r between: 1 and: n) <= k
             ifTrue: [ n := n - 1. k := k - 1] ifFalse: [n := n - 1];
             yourself ]
]

and I noticed that it spends 75% of the time generating random numbers.
  Bytecode-wise it's not bad (30 bytecodes per random number), but
floating point causes a large number of garbage collections.  Anybody
wants to give a shot at reimplementing Random with a good, fast rng?
Remember that on 32-bit machines SmallIntegers are only from -2^30 to
2^30-1.

FWIW, here is a "more optimized" version of the above:

     o := OrderedCollection new.
     1 to: n do: [:x |
         ((r between: 0 and: (n := n - 1)) < k
             ifTrue: [o add: x. k := k - 1]) notNil ]

Either program is a good benchmark for your rng.

Paolo

_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk

Eons ago I generated a bug report on Random numbers.
If my memory is correct as part of the report I pointed out that
(Random>nextValue) asInteger generates a LargeInteger 50% of the time.
Since I need random small integers I use the following code:

    nextSmallIntegerUpdatingSeed
            seed := self nextValue.
            ^seed asInteger // 2.


Regards,

Ralph Boland



Original post:

Eval [
   | n k r |
   r := Random new.
   n := 100000.
   k := 500.
   (1 to: n) select: [:x |
       (r between: 1 and: n) <= k
           ifTrue: [ n := n - 1. k := k - 1] ifFalse: [n := n - 1];
           yourself ]
]

and I noticed that it spends 75% of the time generating random
numbers.  Bytecode-wise it's not bad (30 bytecodes per random number),
but floating point causes a large number of garbage collections.
Anybody wants to give a shot at reimplementing Random with a good,
fast rng? Remember that on 32-bit machines SmallIntegers are only from
-2^30 to 2^30-1.

FWIW, here is a "more optimized" version of the above:

   o := OrderedCollection new.
   1 to: n do: [:x |
       ((r between: 0 and: (n := n - 1)) < k
           ifTrue: [o add: x. k := k - 1]) notNil ]

Either program is a good benchmark for your rng.

Paolo

_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk

On 07/31/2010 08:18 PM, Ralph Boland wrote:
>      nextSmallIntegerUpdatingSeed
>    seed := self nextValue.
>    ^seed asInteger // 2.
>

Since #nextValue is not in GNU Smalltalk, I strongly suspect you're
confusing it with Squeak's random number generator class. :)

Paolo

_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk