Re: Tim's Fix for LargeIntger>>AtRandom

>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
>>

> 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
> [hidden email]
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>

>>>>>> "Jerome" == Jerome Peace <[hidden email]> writes:
>
> Jerome> The objection Randal raised is that now it is using too many.
> Jerome> That's IMO a red herring.
>
> No, it's not.  Multiple calls to a PRNG generate correlated numbers,
> which can be used for an attack.
>
> You need to use a PRNG that in a single call gives enough bits.  And
> if you don't know that about PRNGs, you're not the one to be fixing this.
>
> I talked about it in terms of entropy because that's the easiest way to see
> that you're not gaining anything except the illusion of gain, which will bite
> back some day.  You can't get 112 bits of entropy by calling a 56-bit PRNG
> twice.
>
> It's not progress if it breaks it.
>
> --
> Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
> <[hidden email]> <URL:http://www.stonehenge.com/merlyn/>
> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
> See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>

> From: Randal L. Schwartz <[hidden email]>
> Subject: Re: [Newbies] Re: Tim's Fix for LargeIntger>>AtRandom
> To: "Jerome Peace" <[hidden email]>
> Cc: [hidden email]
> Date: Tuesday, August 5, 2008, 6:18 PM
> >>>>> "Jerome" == Jerome Peace
> <[hidden email]> writes:
>
> Jerome> The objection Randal raised is that now it is
> using too many.
> Jerome> That's IMO a red herring.
>
> No, it's not.  Multiple calls to a PRNG generate
> correlated numbers,
> which can be used for an attack.
>
> You need to use a PRNG that in a single call gives enough
> bits.  And
> if you don't know that about PRNGs, you're not the
> one to be fixing this.
>