Rnd2 disscussion

[Gary Ramey]

Back to noParams and what it takes to get the maximum value 0.99...9 (all nines).
When we "!FILD eq" and then use "!FABS" to handle the sign conversion, we do not need eq to start as all binary 1's to get the maximum output. I suppose that was already the case with the AND masking. What do I mean? Using John's present "divisor" and the FPU's default internal rounding, we will see all nines starting at eq = &h0 7FFF FFFF FFFF FFFB. I didn't catch the nuance that when we FILD to the FPU, our maximum positive values can occur when the first mwcRandom is exactly 7FFF FFFF instead of FFFF FFFF.

I haven't yet thought my way through the scenarios for (a) togScope=0 and results near zero, (b) togScope<>0 and results at or near zero, or (c) togScope<>0 and results near -1.

Now just a comment to clarify my previous allusions to a second mwc generator. I was not thinking anything about the +/- sign of the value. I'm looking at separate generators for eq's upper DWORD and lower DWORD. For an overview of the concept see: http://www.pgbiom.ufrpe.br/docentes/~borko/reprints/2008/random_CommStatSimComp_2008.pdf . This can be something to ponder for future development of the next generation of RND2.

Added: I think that I should have also rem'd out the " !lea ecx, eq "statement in post 178 above.

[Gary Ramey]

I whipped out a fast 64-bit ver. that does all those values correctly,

John, I'd like to see this, even if we don't decide to incorporate it.

[John Gleason]

John, I'd like to see this, even if we don't decide to incorporate it.

Absotively posilutely. This is just the multiply part. As I was doing it, the realization that it requires several other mods hit me. Namely 1) all new mwcSophs, 2) All quad variables or 8-byte string segments, 3) 24-byte initialization, and 4) a bit over 4x as much time per use, even if we only need 4 bytes for a quick rnd2Long. All this would need to be incorporated into the X-params code and retested, which is nearly like a rewrite from scratch. Whoof.

MACRO multiply64()
                 '1st load multipliers
   !mov eax, x         ;low dword of quad
   !mov ebx, x[4]      ;hi        "
   !mov esi, y
   !mov edi, y[4]
                 'let's go
   !mul esi            ;lo x * lo y
   !lea ecx,     ans2  ;answer ptr
   !mov [ecx],   eax   ;answer lo
   !mov [ecx+4], edx   ;answer 2 of 4
   !mov eax,     x
   !mul edi            ;lo x * hi y
   !mov dword ptr[ecx+12], 0 ;zero previous loop's top dword
   !add [ecx+4], eax   ;add to answer 2
   !mov [ecx+8], edx   ;answer 3 of 4
   !mov eax,     esi   ;look ahead to next mul
   !adc dword ptr[ecx+8], 0 ;answer 3
   !mul ebx            ;lo y * hi x
   !add [ecx+4], eax   ;add to answer 2
   !adc [ecx+8], edx   ;     "        3
   !mov eax,     edi   ;look ahead to next mul
   !adc dword ptr[ecx+12],0 ;answer 4
   !mul ebx            ;hi y * hi x
   !add [ecx+8], eax   ;add to answer3
   !adc [ecx+12],edx   ;final answer 4
END MACRO

[David Roberts]

I looked at a macro gsRandomLong with the early versions of 'revisited' and there was no measurable increase in speed. However, a few more Gosubs have been introduced since then. If all Gosubs are replaced with macros then this, along with Gary's !fabs inclusion, sees a 6% increase in speed. Rnd2 is now well inside RND. If this doesn't persuade Bob Zale to complement RND with a Rnd2 in the next versions of the compilers then nothing will.

Your link in post #181 was an interesting read, Gary. Last year we had a long thread on comparing binary files and, if I remember correctly, a MMX implementation pipped the post first but only just. I cannot remember if it was John Gleason or Paul Dixon who brought MMX into the the thread. Anyway, MMX aside, using a separate generator for each Dword of eq shouldn't be problematic and shouldn't impact on speed much, if at all.

[John Gleason]

Regarding RangeNotMax, we're having to load and add 0.5 and later subtract it to get around the FPU's default rounding regime. Would it be faster to set the FPU control register for integer truncation instead of the default rounding? I believe we can flip two control bits to modify the rounding behavior.

Right, this can be done via the control word, but loading and then storing it is some 25 ticks. I'd bet that's significantly slower than the quick add/sub we're doing now.

[John Gleason]

Ok, I updated the !fabs code in the beta code post. I didn't seem to improve the speed for me, but it absolutely *hehe* isn't any slower.

Re. adding back in a second generator: I have a hunch that the drawbacks will far outweigh any benefits. It's not just for neg. nums now and will need to be seeded and tracked separately. I think that'll be a significant speed hit.

I would ask that a variable be added so that we can have access to the current mwcSoph INDEX when the noParams code gets updated. The sections that "re-initialize" or "re-seed" mwcSoph will need to save that 0-383 index value.

Gary, I'm not sure what you mean here. Can you elaborate on this?

[David Roberts]

Went back to basics for a while.

A few posts back John showed how a mwcRandom and mwcCarry of zero will terminate a sequence.

John used r*prime + c. Instead of prime if we used m for multiplier then the mwc algorithm can be written

newr = (oldr*m + oldc) mod 2^32
newc = Int((oldr*m + oldc)/2^32)

with oldr and oldc taking on newr and newc iteratively.

If oldr = 2^32 - 1 and oldc = m - 1 then ..... [1]

newr = ((2^32 - 1)*m + m - 1) mod 2^32
     = (2^32*m - 1) mod 2^32
     = 2^32 - 1 for any positive m

ie newr = oldr

newc = Int(((2^32 - 1)*m + m - 1)/2^32)
     = Int((2^32*m - 1)/2^32)
     = Int(m - 1/2^32)
     = m - 1

ie newc = oldc

So, [1] will also terminate a sequence.

The above applies to mwcRandom being a Dword.

If mwcRandom is a long then oldr = -1 and oldc = m - 1 will also terminate a sequence since -1 is represented internally as &hffffffff just as a Dword is for 2^32-1.

The issue for mwcRandom then is not when it is 2^32-1 if a Dword is used or -1 if a Long is used but when it is &hffffffff internally.

In the code for the default sequence we have mwcRandom = &ha5b218da ' can be any LONG except &hffffffff and 0

which is correct.

From post #137 John wrote

mwcRandom can be any DWORD as long as mwcCarry is not 0 or mwcSoph - 1.

That is also correct except, of course, we are using Long for mwcRandom.

Next we have

IF mwcCarry = mwcSoph - 1 THEN mwcRandom must <> &hffffffff
AND
IF mwcCarry = 0 THEN mwcRandom must <> 0

That is correct as well and &hffffffff is used as opposed to either 2^32-1 or -1.

The next bit bothers me.

So I just check mwcCarry for those 2 values and don't allow them, and thereby let mwcRandom ride.

In the CASE 6 code we have

If mwcCarry = 0 GoTo reSeedCrypt     'odds are less than 1 in 4.2 billion
If mwcCarry = mwcSoph - 1 GoTo reSeedCrypt '  "          "           "

That 4.2 billion is, of course, 2^32.

That may seem very large odds but by rejecting mwcCarry = 0 we are also rejecting 2^32 possible mwcRandoms when only mwcRandom = 0 will be problematic. Similarly with mwcCarry = mwcSoph - 1. Here we are rejecting 2^32 possible mwcRandoms when only mwcRandom = &hffffffff will be problematic.

The same logic is used in CASE 1.

CASE 1 and CASE 6 are seeders. The above logic only allows acces to 2^32-2 instead of 2^64 - 2.

Rejection should only occur then when both mwcRandom and mwcCarry are zero or mwcRandom = &hffffffff and mwcCarry = mwcSoph - 1.

[John Gleason]

The above logic only allows access to 2^32-2 instead of 2^64 - 2.

I can understand how that might cause a good deal of consternation! But the bright side is I think the "decimal point" got shifted too far. It should be The above logic only allows access to 2^63-2 instead of 2^64 - 2. Because we're rejecting 2^32 * 2 = 2^33 possibilities out of 2^64 - 2 total. This is ~ 2^64 - 2^33 = greater than 2^63? Somewhere around 2^63 or 64.

[David Roberts]

I was in mwcCarry looking at mwcRandom and thinking about what I cannot use in mwcCarry. For some reason my logic goes skew whiff. If I go to mwcRandom and now ask what I cannot use in mwccarry I get 2^32 [mwcRandom] * (2^32-2) [mwcCarry] = 2^64 - 2^33.

Your 2^32*2 should be 2^32 - 2.

When I was in mwcCarry I should have asked what I cannot use in mwcRandom. Of course now we go to reSeedCrypt if mwcRandom = 0 or &hffffffff with the same 2^64 - 2^33 odds.

2^64-2^33 = 2^63.9999999993282

So, no consternation there then.

However, we still have 2^32 - 2 which cannot get a look in.

So, Rnd2Randomize and Rnd2RandomizeCrypto are being denied access to 4,294,967,294 pairings.

I've just spotted Tru© in your description of Rnd2Randomize. Magic!

Anyway, how can you use that and kick out 4,294,967,294?

OK my arithmetic was out but I still think that

"Rejection should only occur then when both mwcRandom and mwcCarry are zero or mwcRandom = &hffffffff and mwcCarry = mwcSoph - 1."

[Gary Ramey]

Regarding posts 187-189... For those of us who think of RND2(6) as a good source for occasional but not continuous re-seeding, there is not much time penalty for being more specific as David suggested about rejections.

I'm still pondering RND2() noParams issues. The documentation has places saying it is not good for cryptographic purposes except on the next call after a secure re-seeding. We really need that warning. Without elaborating much, there are several critical points in our one-celled MWC series where a few collected values are all that is needed to decode all parameters. If someone needs security, they should use something besides RND2().

I suggest we add documentation that our current version of RND2() will not generate a zero value, and is highly unlikely to generate +/- 0.99..99 all nines. Our current version seems limited to about 11 to 13 leading 0's or leading 9's after the decimal point. About 7 to 9 is the usual observation for a few million values from RND2().

One of you asked me to clarify comments about saving an index value into the mwcSoph table when re-seeding. Don't worry about doing that at this time. I was just thinking about contingencies for a second mwc generator in RND2(). If we could do something like use a different mwcSoph or whatever in lieu of an identical second call to gsRandomLong, that would be best. But even rotating bits or byte swapping as we come out of the second gsRandomLong call seems preferable to using the 32-bits exactly as generated.

[David Roberts]

If we could do something like use a different mwcSoph or whatever in lieu of an identical second call to gsRandomLong, that would be best. But even rotating bits or byte swapping as we come out of the second gsRandomLong call seems preferable to using the 32-bits exactly as generated.

> that would be best

> preferable

In what sense Gary?

Are you talking about the randomness or the security?

[David Roberts]

As a side note there is a vulnerability in Win2000 CryptGenRandom which found its way into WinXP. It did not find its way into Vista and it was fixed in WinXP SP3. Win2000 is still at risk. However, MS whilst acknowledging the flaw reckoned that an exploitation required exceptional if not nigh on impossible circumstances; but then they would, wouldn't they?

CryptGenRandom is used in IE for SSL purposes and such like. If it is not to be used in a secure environment then the risk is obviously academic.

I must confess that security had not crossed my mind with regard to Rnd2. Having said that if anyone asked me if it was OK to use in a secure environment it wouldn't take long for me to say no.

[John Gleason]

Dave said: Anyway, how can you use that and kick out 4,294,967,294?

It is something again maybe with far jumps, alignment, or maybe some floats get placed in there, but when I add an IF...THEN structure to the crypto CASE section, the WHOLE function, all the calls, slow by up to a whopping 29% (rnd2Long). I removed the IF and right back up to speed it went. I thought, I'll take a hundredth of a % hit on the seed range to regain that 29%.

Gary said: If someone needs security, they should use something besides RND2().

There should be no problem tho with Rnd2(7). People could use that, couldn't they?

[David Roberts]

> slow by up to a whopping 29% (rnd2Long)

This is what I have in CASE 6

If (mwcCarry = 0 And mwcRandom = 0) Or ((mwcCarry = mwcSoph -1) And mwcRandom = &hffffffff) GoTo reSeedCrypt

and this is a typical run.



Compare that with my last image.



CASE 6 is slower but then it would be - a bit of asm will sort that out.

Rnd2Long is a shade faster in the top image.

Check out Rnd2[0,1) with the gs converted to macros.

[John Gleason]

If (mwcCarry = 0 And mwcRandom = 0) Or ((mwcCarry = mwcSoph -1) And mwcRandom = &hffffffff) GoTo reSeedCrypt

There's your answer! Works fine--even sped up Rnd2Long some. Crypto(-1,1) was equal too. Now those previously wayward 4GB of seeds can enjoy Halloween too. "Help the poor! My pants are tore. Gimme some money I'll buy some more!" Maybe a few of the more industrious little guys'll even get out and vote in a couple weeks.

[David Roberts]

I don't understand. What were you doing to slow things down by 29%?

[David Roberts]

I've got Crypto(-1,1) back to what it used to be before adding that big If statement.

I was a dab hand at MC68000, and Z80 before that, but I do very little Intel asm so anything I write in asm is highly suspect. Would you run an eye on the following for me John. I've borrowed heavily from your code anyway. Ta much.

Case 6                   ' Rnd2RandomizeCrypto
  oneTime = 1
  !fld tbyte rndE        ;Save rndE For a moment
reSeedCrypt:
  GetCrypto.Bytes(rndE)  'Use rndE as a temporary buffer and populate with 10 cryptographic bytes.
  !lea esi, rndE
  !mov eax, [esi]
  !mov mwcRandom, eax
  !mov eax, [esi+4]
  !mov mwcCarry, eax
  !mov ax, [esi+8]            ; the last two Of the 10 collected
  !mov mwcSoph, ax
  !mov eax, mwcSoph
  !mov ecx, 384               ; 384 possible sophie-germain multipliers
  !mov edx, 0                 ; Clear edx For division
  !div ecx                    ; Random remainder (Mod 384) In edx now
  !lea ecx, multiplier        ; CodePtr To 384 multipliers
  !mov ecx, [ecx+edx*4]       ; got Rnd soph germain multiplier now
  !mov mwcSoph, ecx
  !Sub ecx, 1                 ; mwcSoph - 1
  !cmp mwcCarry, ecx          ; does mwcCarry = mwcSoph - 1
  !je short mwcCarrySophFail  ; yes
  !cmp mwcCarry, 0            ; Is mwcCarry = 0
  !jne short OK               ; no, Not interested In mwcRandom now
  !cmp mwcRandom, 0           ; Is mwcRandom = 0
  !je short reSeedCrypt       ; we now have both mwcCarry & mwcRandom = 0
  !jmp short OK               ; mwcCarry = 0 but mwcRandom Is Not
mwcCarrySophFail:
  !cmp mwcRandom, &hffffffff  ; does mwcRandom = &hffffffff
  !je short reSeedCrypt       ; mwcCarry = mwcSoph - 1 & mwcRandom = &hffffffff
OK:
  !fstp rndE                 ;restore rndE
  gsStoreSeq

[Gary Ramey]

I must confess that security had not crossed my mind with regard to Rnd2. Having said that if anyone asked me if it was OK to use in a secure environment it wouldn't take long for me to say no.

Okay folks, all our use of "crypto" this and that in the macro names, documentation, etc is going to lay a breadcrumb trail for the innocent to think RND2 might be a handy cryptography tool.

All of us have been questing for a truly perfectly random way to seed a MWC calculation. John came up with RND2(1) and David created RND2(6). Both are great, seemingly non-deterministic seeding options. John grasped that such a perfect seeding approach could be used before every RND2(whatever) that generates a new value. Along the way we all started using words in the macro names and documentation that are commonly used in cryptography. The latest documentation even refers to security aspects after seeding with RND2(6). Do we want to change our terms to avoid "crypto" and "security"?

I think we should completely drop RND2(7) so that there is no confusion for folks. RND2(7) can be created separately to live on its own in a much less bloated function.

[Gary Ramey]

If we could do something like use a different mwcSoph or whatever in lieu of an identical second call to gsRandomLong, that would be best. But even rotating bits or byte swapping as we come out of the second gsRandomLong call seems preferable to using the 32-bits exactly as generated.

In what sense Gary? Are you talking about the randomness or the security?

David, I'm really only concerned about randomness for RND2(). Every now and then I'm "thinking out loud" as I ponder our dilemma of building the 'eq' quad from two sequential uses of gsRandomLong. I've had some misconceptions clarified along the way, but I'm not seeing mathematically how it can randomly produce the "tails" near -1, 0, and +1. I'll keep on pondering...

[David Roberts]

I whole heartily agree with dropping Rnd(7) aka Rnd2Crypto. When I introduced crypto my intention was solely to provide an alternative to John's Rnd2(1) which was originally called TrueRandom and now called Rnd2Randomize. Rnd2Crypto should have no place in a function offered as a prng additional to RND. I have never regarded Rnd2 as a replacement for RND. My original Rnd2 was slower than RND, clearly not as convenient to a built-in function but its strength was its period and depth of precision. Speed is no longer an issue, RND is still more convenient but its period and/or depth of precision may give some programmers a reason to implement Rnd2.

If we did drop Rnd(7) then we are left with Rnd(6) aka Rnd2RandomizeCrypto and only one macro using the term crypto. This command should be understood to do a similar job to Rnd2Randomize which, in turn, should be understood to do a similar job to RND's Randomize. I don't think that we should drop the crypto term here; after all it is using Microsoft's CryptGenRandom.

I ponder our dilemma of building the 'eq' quad from two sequential uses of gsRandomLong

You know that I don't have a problem with that.

However, it may be a worthwhile exercise to determine an expected behaviour as a null hypothesis and then statistically examine the status of what we are experiencing. If our experience is unusual then we should be bound to consider correcting that, if possible, and a dual generator may be one avenue to look at.