Hello:
I am using a lot of Randoms lately, and something strange has happened a couple of times today: I get Randoms which after a while produce an unending sequence of 1.0s. The instance variables of these Randoms are:
seed: 2.147483647e9 a: 16807.0 m: 2.147483647e9 q: 127773.0 r: 2836.0
It is quite annoying. I do not know the details of the random number generation algorithm. Is there a way to avoid it besides explicit testing for 1.0 in Random>>next?
Thanks, Juan.
Hi.
I am using a lot of Randoms lately, and something strange has happened a couple of times today: I get Randoms which after a while produce an unending sequence of 1.0s.
This is quite strange indeed... I also remember having noticed that Color atRandom produced triplets of about the same color. I even made a graph with the RGB values of such colors and it didn't look atRandom to me.
Andres.
You could use my dire hack below which should avoid the the problem (though your interval will now be (0,1]), but I haven't tested what effects it might have on the random number generation in general. YMMV.
-- Dwight
'From Squeak 2.4c of May 10, 1999 on 25 May 1999 at 1:41:28 pm'!
!Random methodsFor: 'as yet unclassified' stamp: 'dwh 5/25/1999 13:34'! next " This method generates random instances of Float in the interval 0 to 1. " seed := self nextValue. (seed = m) ifTrue: [seed := seed - 1.0]. ^seed / m! !
Juan Cires Martinez wrote:
Hello:
I am using a lot of Randoms lately, and something strange has happened a couple of times today: I get Randoms which after a while produce an unending sequence of 1.0s. The instance variables of these Randoms are:
seed: 2.147483647e9 a: 16807.0 m: 2.147483647e9 q: 127773.0 r: 2836.0It is quite annoying. I do not know the details of the random number generation algorithm. Is there a way to avoid it besides explicit testing for 1.0 in Random>>next?
Thanks, Juan.
Juan Cires Martinez wrote:
I am using a lot of Randoms lately, and something strange has happened a couple of times today: I get Randoms which after a while produce an unending sequence of 1.0s. The instance variables of these Randoms are:
seed: 2.147483647e9 a: 16807.0 m: 2.147483647e9 q: 127773.0 r: 2836.0
It is quite annoying. I do not know the details of the random number generation algorithm. Is there a way to avoid it besides explicit testing for 1.0 in Random>>next?
Most random number generators perform their internal computations on integers only. Squeak's RNG algorithm certainly appears to be based on such a system... so can anyone explain why the calculations are all being done in floating point? I would expect this to cause trouble with roundoff. (The integer-based origins of the algorithm can be glimpsed at least in the seed initialization, Random>>seed: anInteger. So what's going on here, exactly?)
It seems to me the correct solution is to take out all the asFloat stuff, and apply it instead to the return value of Random>>next. That way, all calculations are performed internally with integers, which shouldn't cause the problem described above, and would be more amenable to producing various random integer distributions.
Um, does that mean I'm elected?
-Jesse Welton
Juan Cires Martinez wrote: Most random number generators perform their internal computations on integers only. Squeak's RNG algorithm certainly appears to be based on such a system... so can anyone explain why the calculations are all being done in floating point? I would expect this to cause trouble with roundoff. (The integer-based origins of the algorithm can be glimpsed at least in the seed initialization, Random>>seed: anInteger. So what's going on here, exactly?)
It seems to me the correct solution is to take out all the asFloat stuff, and apply it instead to the return value of Random>>next. That way, all calculations are performed internally with integers, which shouldn't cause the problem described above, and would be more amenable to producing various random integer distributions.
Indeed, this random number generator is based on a veru well-known 32-bit integer random number generator. However, since Squeak's integers have two fewer bits than an unsigned C ints (one for the "integer" bit, one for the sign bit), the first version of this 32-bit generator frequently overflowed into LargePositiveIntegers. It got the right answer, but it was quite slow. Thus, someone (either David N. Smith or Dan Ingalls, I think) re-wrote it using Squeak's Floats, which are 64 bit double precision Floats with more than enough bits of mantissa. This was much faster, since all the arithmetic used the float primitives.
That's the history.
I wonder if this problem of getting stuck in a cycle is a side effect of floating point roundoff and/or normalization? I would expect the integer version of the algorithm to be free of this problem; it was a well-tested and studied choice of parameters, which is why we chose it.
-- John
At 12:33 -0400 6/11/99, John.Maloney@disney.com wrote:
...SNIP... I wonder if this problem of getting stuck in a cycle is a side effect of floating point roundoff and/or normalization? I would expect the integer version of the algorithm to be free of this problem; it was a well-tested and studied choice of parameters, which is why we chose it.
I don't think it should have any effect since only the integer part of the float should ever be used. IE, using floats there is a trick to get long fast integers. The fraction part 'should' never be non-zero.
Dave _______________________________ David N. Smith IBM T J Watson Research Center Hawthorne, NY _______________________________ Any opinions or recommendations herein are those of the author and not of his employer.
John.Maloney@disney.com wrote:
It seems to me the correct solution is to take out all the asFloat stuff, and apply it instead to the return value of Random>>next. That way, all calculations are performed internally with integers, which shouldn't cause the problem described above, and would be more amenable to producing various random integer distributions.
Indeed, this random number generator is based on a veru well-known 32-bit integer random number generator. However, since Squeak's integers have two fewer bits than an unsigned C ints (one for the "integer" bit, one for the sign bit), the first version of this 32-bit generator frequently overflowed into LargePositiveIntegers. It got the right answer, but it was quite slow. Thus, someone (either David N. Smith or Dan Ingalls, I think) re-wrote it using Squeak's Floats, which are 64 bit double precision Floats with more than enough bits of mantissa. This was much faster, since all the arithmetic used the float primitives.
Yes, experimenting with changing the generator to use integers, I found it to be much slower, and figured that must be why it was changed to use floats. If I recall correctly, it was almost 50 times as slow, which puzzled me. That it runs into LargePositiveIntegers helps explain that, but I'm still not sure why it should be so *much* slower.
Here's a question: If the algorithm were changed to use a modulus which fits into Squeak's 30-bit integers, would the resulting code run any faster than the float version, or still slower?
I wonder if this problem of getting stuck in a cycle is a side effect of floating point roundoff and/or normalization? I would expect the integer version of the algorithm to be free of this problem; it was a well-tested and studied choice of parameters, which is why we chose it.
I did try some long runs of the generator with both integer and float computations, both seeded identically, and they were in complete agreement after a million or so iterations. The kinds of calculations involved look like they would tend to avoid roundoff errors, too, so my guess is the float calculations are probably exact.
-Jesse Welton
Re:
Here's a question: If the algorithm were changed to use a modulus which fits into Squeak's 30-bit integers, would the resulting code run any faster than the float version, or still slower?
Probably quite a bit faster. But finding a set of parameters that have all the desirable properties may not be trivial. The nice thing about the Park-Miller parameters is that they have been studied and deemed "good".
I wonder if this problem of getting stuck in a cycle is a side effect of floating point roundoff and/or normalization? I would expect the integer version of the algorithm to be free of this problem; it was a well-tested and studied choice of parameters, which is why we chose it.
I did try some long runs of the generator with both integer and float computations, both seeded identically, and they were in complete agreement after a million or so iterations. The kinds of calculations involved look like they would tend to avoid roundoff errors, too, so my guess is the float calculations are probably exact.
Thanks for trying this. I'm pretty certain that the bug is due to my "improved" initialization code (see the thread "Re: More on Random").
-- John
At 15:08 -0400 6/11/99, Jesse Welton wrote:
...SNIP... Here's a question: If the algorithm were changed to use a modulus which fits into Squeak's 30-bit integers, would the resulting code run any faster than the float version, or still slower?
This would require redoing the extensive testing that makes the Park-Miller generator worth using. Such testing is difficult, time consuming, and best done by an expert.
It would probably make more sense to compute the value in a primitive and use the C version of the code.
Dave _______________________________ David N. Smith IBM T J Watson Research Center Hawthorne, NY _______________________________ Any opinions or recommendations herein are those of the author and not of his employer.
Jesse Welton wrote:
Yes, experimenting with changing the generator to use integers, I found it to be much slower, and figured that must be why it was changed to use floats. If I recall correctly, it was almost 50 times as slow, which puzzled me. That it runs into LargePositiveIntegers helps explain that, but I'm still not sure why it should be so *much* slower.
Although you see primitives in the LargeInteger methods, they are only placeholders -- they all map to primitiveFail in the VM. So LargeInteger code actually runs entirely in Smalltalk.
-- Dwight
squeak-dev@lists.squeakfoundation.org
-
Andres Valloud -
David N. Smith (IBM) -
Dwight Hughes -
Jesse Welton -
John.Maloney＠disney.com -
Juan Cires Martinez