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

[Cerebus]

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 at 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 at lists.squeakfoundation.org
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>