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
***
Interestingly, UUIDGenerator creates 16 bytes of random using Random one bit at a time.
I suspect there are entropy issues all through the image.
-- Tim
On Mon, Aug 4, 2008 at 2:16 AM, Jerome Peace peace_the_dreamer@yahoo.com wrote:
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
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
beginners@lists.squeakfoundation.org