[Newbies] Re: Tim's Fix for LargeIntger>>AtRandom

[Jerome Peace]

Re: Tim's Fix for LargeIntger>>AtRandom
was: [Newbies] Re: What's wrong with this statement?


Hi Tim,

Glad you are working on a fix.

I looked at your first pass.  
It looks like it would work but maybe eat performance. 
As Randal mentioned it goes thru Randoms
 siz and a half times faster than necessary.

What happens if you try it with the oddity test I put in the report?
Does it work well enough to pass that test? 
(The data looks ok. Some even some odd. Cool). 


Feel free to strengthen the test by adding more cases.


I would leave the method in Integer as it was but add one in LargePositiveInteger.
This would use the heirarchy of classes to make the distinction that is needed.
SmallInts and negative large ints would use the current method.

The method for large ints would look similar to the way you broke it down.
Do a small piece and then the remaining piece.

Instead of converting to byte arrays I would just use arithmetic for the recursion.

We can choose a large power of two for the radix because each random contains
 about 2^50 bits of information.  
LargeInt can probably divide efficiently by powers of two.
We don't have to worry about this on 
  the first (uhm, second pass. You did a first pass :-).

Once you have a pass that works we could test the next one against it
 by using a separate generator and noting a beginning seed. 
 (waves hands in the air.) I think I am getting ahead of myself here.

outline of nem method:

LargePositiveInteger>>atRandom

radix := <a truly randomizable power of 2>

self > radix ifFalse: [ ^ aGenerator nextInt: self ] .

loBits := self \\ radix .
hiBits := self // radix .
^ hiBits atRandom * radix + loBits atRandom .

(this is a gedanken code to sketch things out.
 You may have to vary it to get it to work.)

I would get something like the above working first.
 Test it against at least the oddity test.
Then maybe play with performace IF you suspected that would be important.

If the number is negative the interger method will handle that as it already does.

If any of the numbers become Smallints thats covered by what gets done now.

For large ints the problem gets broken down to reasonable levels and dealt with.

Should work.

Hth,

Yours is curiosity and service, --Jerome Peace

***
>Somebody check me out here, 'cause I think I'm close but something
>doesn't seem quite right.
>
>Attached is a new Integer>atRandom I'm playing with.  I break the
>integer into a ByteArray and call #atRandom for every byte, using 255
>as the bounding value for all but the first byte.  The bounding value
>for the first byte is itself minus 1.  Concatenated together we get a
>byte array representing a random value less than the bounding value.
>
>I think.  Maybe I'm doing this wrong.  I feel like the first byte
>treatment is wrong but I don't know how to achieve the same
>result--without it the random value often exceeds the bounding value.
>
>I went this route as it avoids doing a bunch of bit shifts I'd
>probably get wrong anyway.
>
>10 timesRepeat: [Transcript show: ((2 raisedTo: 128) atRandom hex); cr]
>
>gives:
>
>CFE72E55A8C35387C9932D3235937FE6
>A1760C4F27B161A4D2431C94751A2E65
>D9EC4066D2DBD7A00B17B6FC16D985DC
>D3140D928C14D8EA7AEB0CC814A2CA8C
>EFB37CECB90EFDCF2F93BC34245118C
>1B215016A0812E04A5600FA88373BD7B
>7B52EB7F11C0DC822B272B70DCE61890
>1D165F2BAF12E8596D496745A41A4BF4
>E8C62D390B69B26CD9FEAF58BD68C17
>3FBEA83CCB11EEDF6993E9BB60171F35
>
>-- Tim
>
>On Sat, Aug 2, 2008 at 11:00 AM, Cerebus <cerebus2 at gmail.com> wrote:
>> Bug submitted.
>>
>> http://bugs.squeak.org/view.php?id=7142
>>
>> I may even attempt a fix.  :)
>>
>> -- Tim
>>
***