[Newbies] LargeIntegers atRandom more analysis
Jerome Peace
peace_the_dreamer at yahoo.com
Sat Aug 9 02:34:09 UTC 2008
LargeIntegers atRandom more analysis
Hi Tim, Hi Randal
Nothing like a little coding to go
>From confident Ignorance:
http://www.sacred-texts.com/tarot/pkt/img/ar00.jpg
To humble Understanding:
http://www.sacred-texts.com/tarot/pkt/img/ar01.jpg
Playing and trying to debug my notion of large integer randoms,
show that what I had proposed as a decomposition for the problem
had bigger problems than I first thought.
I did not get far enough to blame the generator.
But ran into problems with convincing myself
that with the decomposition I could get an evenly distributed probility
for numbers from 1 to large n.
I still believe that LargeInteger has the responsibility for giving back a good random.
Along the way, or actually while I slept,
I realized that the limitation is not necessarily in the generator
but in the combining of the floating point and large integer in nextInt: .
This is a problem.
24 factorial + 1000000 = (24 factorial * 1.0)
will answer true.
while
( 24 factorial - (24 factorial * 1.0 ) asInteger ) = 0
will answer false.
There is a truncation difficulty with floats.
I say difficulty rather than bug because it is not spec'ed to work otherwise.
With this knowledge some relief can be had by gening up a large random number
and treating it as a fraction.
So a step towards the solution would be to define:
LargePositiveInteger>>
atRandom: aGenerator
"Answer a random integer from 1 to self picked from aGenerator.
To handle Large integers the arithmetic must use integer arithmetic.
This will work if the generator is up to multiple uses."
| nHigits numerator radix maxSigBits nextLargeInteger denominator |
maxSigBits := 53 . " aGenerator class maxSignificantBits. "
radix := radix := ( 2 raisedTo: maxSigBits ) .
nHigits :=
(self highBit // maxSigBits ) + 1 .
numerator := 0 .
nextLargeInteger := [ ( aGenerator next * radix ) asInteger ] .
nHigits timesRepeat: [ numerator := numerator * radix + nextLargeInteger value ] .
denominator := radix raisedTo: nHigits .
^ self * numerator // denominator + 1 .
This leaves the problem of the usable/reusalbe generator to be solved.
I would also want a way for the generator classes to return maxSigBits.
The pleasing thing about the above code is that with the method in place
I did not have to change anything else to get atRandom to work better.
So #atRandom: proves itself a useful hook.
This solution passes the oddity test. That is a very low threshold test.
This is also a fragile solution.
There are probably some places that it fails.
It would be interesting to find a test that it couldn't pass.
Then use that to vet the next iteration of the fix.
Yours in curiosity and service, --Jerome Peace
More information about the Beginners
mailing list