Announcement

**David Roberts** · 25 Oct 2008, 08:15 PM

> if we figure out where they go and their exact values.

The first idea was bad ie being determined at the head of NoParams in the 'If OneTime...'.

The second idea placed the determination at the head of the function with a once only calculation via Factors.

However, asking the same question on each entry is expensive so I looked at alternatives. First was a Global UDT. Rnd() took twice as long. I then looked at a Class where the determination was executed in a Constructor Method and the values placed in Instance variables. These were got via a Method's value. Rnd2() came in at 4500ms as opposed to less than 300ms. That's right - 4500ms. Bit of an eye opener. There are more and more reasons coming to me to use objects but speed is not one of them - so it seems. I then created a Macro and determined the Factors into Globals. This halved the improvement. So, asked at the head of the function is the fastest so far.

Their exact values? Don't understand you, there.

Come to think of it having two identical mwcRandoms should have been expected. Of course, we won't get two mwcRandoms and two mwcCarrys the same else the the mwc will will freeze up.

> The CASE 2 Rnd2mizeCrypto asm doesn't match the original PB code output.

What do you mean by output? I checked the output from CASE 2 and they were the same ie when rndE was overwritten by the default sequence values both sets of code read the values correctly. If you are comparing the final output may be your two sets of code differ from the end of CASE 2 to the surface.

**David Roberts** · 25 Oct 2008, 08:45 PM

Testing CASE 2

Code:

#Compile Exe
#Dim All  
  
Function PBMain
  Static mwcRandom, mwcCarry As Long, mwcSoph As Dword
  Static rndE As Ext
  Local qTime As Quad
  
  !lea ecx, rndE
  !mov Dword Ptr[ecx], &ha5b218da
  !mov Dword Ptr[ecx+4], &h3fe8700c  
  !mov  Word Ptr[ecx+8], 12345678 
  
  Tix qTime
  !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 mwcCarrySophFail  ; yes
  !cmp mwcCarry, 0            ; Is mwcCarry = 0
  !jne OK               ; no, Not interested In mwcRandom now
  !cmp mwcRandom, 0           ; Is mwcRandom = 0
  !je reSeedCrypt       ; we now have both mwcCarry & mwcRandom = 0
  !jmp OK               ; mwcCarry = 0 but mwcRandom Is Not
mwcCarrySophFail:
  !cmp mwcRandom, &hffffffff  ; does mwcRandom = &hffffffff
  !je reSeedCrypt       ; mwcCarry = mwcSoph - 1 & mwcRandom = &hffffffff
OK:
  
  Tix End qTime

  Print mwcRandom;mwcCarry;mwcSoph;qTime

reSeedCrypt:
  Tix qTime
  mwcRandom = Peek(Dword, VarPtr(rndE))
  mwcCarry  = Peek(Dword, VarPtr(rndE) + 4)
  mwcSoph   = Peek( Word, VarPtr(rndE) + 8)
  mwcSoph = Peek(Dword, CodePtr(multiplier) + (mwcSoph Mod 384) * 4) 'get soph prime
  If mwcCarry = 0 GoTo reSeedCrypt           'odds are less than 1 in 4.2 billion
  If mwcCarry = mwcSoph - 1 GoTo reSeedCrypt
  Tix End qTime
  
  Print mwcRandom;mwcCarry;mwcSoph;qTime
  
  Waitkey$
  
  Exit Function
  
multiplier: 'a bunch of Sophie Germain primes. Each makes its own unique sequence of ~2^63 LONG random values
!DD 4055108289, 4183291290, 4066422669, 4010830218, 4144557798, 4047225099, 4169878863, 4156378278
!DD 4068734223, 4013003148, 4128794349, 4044603045, 4147482834, 4050081738, 4169007204, 4084483623
!DD 4182936234, 4061167764, 4116557445, 4184835774, 4098609075, 4000058700, 4005596580, 4131991143
!DD 4026365904, 4082490609, 4170263943, 4064971044, 4192040679, 4069686423, 4112450355, 4116008373
!DD 4051352658, 4131639393, 4026209880, 4143019908, 4057560153, 4153038378, 4178347353, 4101943515
!DD 4163817693, 4126770675, 4122227184, 4150506573, 4124871525, 4097114355, 4171215009, 4094254353
!DD 4185190458, 4184112513, 4187782989, 4037092584, 4114448259, 4096721880, 4003880118, 4035500259
!DD 4080989598, 4090215738, 4104202098, 4144153608, 4027213065, 4112123319, 4029634383, 4188620745
!DD 4003957254, 4158202674, 4165028370, 4101889029, 4064867064, 4056294705, 4117302630, 4094813610
!DD 4089078504, 4072584339, 4075250574, 4144182519, 4020827805, 4077052605, 4012941570, 4114015830
!DD 4015303260, 4012049835, 4031934513, 4123667379, 4025171265, 4149021864, 4020494469, 4152989853
!DD 4141465314, 4050172164, 4130534940, 4124347128, 4155032220, 4123523313, 4038610005, 4066391700
!DD 4052359893, 4138494750, 4046848368, 4015233183, 4065337650, 4181156010, 4149686553, 4115669703
!DD 4080411408, 4029985884, 4072279314, 4136476293, 4102312674, 4148638644, 4020161274, 4056852945
!DD 4084467288, 4090139205, 4152479904, 4129623354, 4189154793, 4042650633, 4113056934, 4070634510
!DD 4172190345, 4012616748, 4092782529, 4042027470, 4034320863, 4017110193, 4128178095, 4005317820
!DD 4121565819, 4160465475, 4093432608, 4094047308, 4092039654, 4132108680, 4160799915, 4109110719
!DD 4190254803, 4063105479, 4123739478, 4086096945, 4113466908, 4169157873, 4036670034, 4035486873
!DD 4154194098, 4074334704, 4006945965, 4119880785, 4050935955, 4131729105, 4170646809, 4191996963
!DD 4055775498, 4029162399, 4118132214, 4116397584, 4121266560, 4102454433, 4146555864, 4103353149
!DD 4119974010, 4080379233, 4192378968, 4061071950, 4104928533, 4042978743, 4188739878, 4066717740
!DD 4017709695, 4027617453, 4110604308, 4107339654, 4076278878, 4077074274, 4097495403, 4179562659
!DD 4187765853, 4187454249, 4015793904, 4083863454, 4078492929, 4166495943, 4101303048, 4149525330
!DD 4095286830, 4078227909, 4189944624, 4010811645, 4032304584, 4151394078, 4044317298, 4136517915
!DD 4198354635, 4192501860, 4073134869, 4060180830, 4076815050, 4190613315, 4142749785, 4122567564
!DD 4071542523, 4024430004, 4122798648, 4041267495, 4006243575, 4092566124, 4141397349, 4175565558
!DD 4159829190, 4173505479, 4084339563, 4085131608, 4081507743, 4069428324, 4011038568, 4092438129
!DD 4005482298, 4020895359, 4127615184, 4162803795, 4038272028, 4123171464, 4199942199, 4067713245
!DD 4129181838, 4021766328, 4141102845, 4002607668, 4051580310, 4082443044, 4078962945, 4072199883
!DD 4180693749, 4040763375, 4025696004, 4066226853, 4013137770, 4084688994, 4081465923, 4185884010
!DD 4184193840, 4095653625, 4071642489, 4003011123, 4021708860, 4038391383, 4003548888, 4016275635
!DD 4051483344, 4052001093, 4131504594, 4129105653, 4187278653, 4058921709, 4167113355, 4106971188
!DD 4074045393, 4069825200, 4009724565, 4120937589, 4119577560, 4151390115, 4000637598, 4088788530
!DD 4014859458, 4003633353, 4192075623, 4009856424, 4048255155, 4100175633, 4129717695, 4012882215
!DD 4119226824, 4122492603, 4074693864, 4062187338, 4022104890, 4186039455, 4191285474, 4165800789
!DD 4047934929, 4045886208, 4028478450, 4098395724, 4095869853, 4004229753, 4110500373, 4188458055
!DD 4093944063, 4122368673, 4136075109, 4024434645, 4145270010, 4121262090, 4051650480, 4076720613
!DD 4057135713, 4053301650, 4074379569, 4103950185, 4146078999, 4029125490, 4036104003, 4122595203
!DD 4173008610, 4155931704, 4048316175, 4178853645, 4049069715, 4187855514, 4193714559, 4132340133
!DD 4001184978, 4087342068, 4038996009, 4032782589, 4103313705, 4057212699, 4094324010, 4117022988
!DD 4016133978, 4057176333, 4081210119, 4183410330, 4054406019, 4008415374, 4131217578, 4049176725
!DD 4033804230, 4154677353, 4194818769, 4057689999, 4065887250, 4083913149, 4160269749, 4148719650
!DD 4086572148, 4079152770, 4198797849, 4025836533, 4121774838, 4114818903, 4193265369, 4005720123
!DD 4172736744, 4113446385, 4153872675, 4022863908, 4169665353, 4080875223, 4148976378, 4158173325
!DD 4012107315, 4146530883, 4042645638, 4189878099, 4075365840, 4053276279, 4112504730, 4144260888
!DD 4102144035, 4181673825, 4171915968, 4123257354, 4032551355, 4054454535, 4132616253, 4057321905
!DD 4174490559, 4165419468, 4169862234, 4116771594, 4009920498, 4164231630, 4163597154, 4181713095
!DD 4000268439, 4077171264, 4045424718, 4116626304, 4052701140, 4140380880, 4027965249, 4102323183
  
End Function

The asm and PB print the same values and the asm is twice as fast.

It is worth noting that if mwcRandom was a Dword with one piece of code and a long with the other then the resulting mwcRandoms printed may not be the same.

**John Gleason** · 26 Oct 2008, 10:43 AM

Originally posted by David Roberts View Post

> if we figure out where they go and their exact values.
Their exact values? Don't understand you, there.

That's because you have their exact values in there already--a fact I failed to notice--and I was trying to reenter them with like !fld and division. Because it doesn't make any sense to do that, you didn't understand it.

In time, maybe we'll be able to forget that I made that statement.

Come to think of it having two identical mwcRandoms should have been expected. Of course, we won't get two mwcRandoms and two mwcCarrys the same else the the mwc will will freeze up.

Can we get 0,0? How about &hffffffff,&hffffffff?

> The CASE 2 Rnd2mizeCrypto asm doesn't match the original PB code output.

What do you mean by output? I checked the output from CASE 2 and they were the same ie when rndE was overwritten by the default sequence values both sets of code read the values correctly. If you are comparing the final output may be your two sets of code differ from the end of CASE 2 to the surface.

I'm at a loss to explain it, but here is the test code:

Code:

'          CASE 2                ' Rnd2mizeCrypto
'            !fld tbyte rndE        ;save rndE for a moment
'          reSeedCrypt:
'            rndE = rnd2()
'            mwcRandom = PEEK(DWORD, VARPTR(rndE))
'            mwcCarry  = PEEK(DWORD, VARPTR(rndE) + 4)
'            mwcSoph   = PEEK( WORD, VARPTR(rndE) + 8)
'            mwcSoph = PEEK(DWORD, CODEPTR(multiplier) + (mwcSoph MOD 384) * 4) 'get soph prime
'            IF (mwcCarry = 0 AND mwcRandom = 0) OR ((mwcCarry = mwcSoph -1) AND mwcRandom = &hffffffff) GOTO reSeedCrypt
'            !fstp rndE             ;restore rndE
'            mStoreSeq
'            oneTime = 1
'-------------------------------------------------------------------------------------
          CASE 2                   ' Rnd2mizeCrypto
            !fld tbyte rndE        ;Save rndE For a moment
          reSeedCrypt:
            rndE = rnd2()
            !push esi                   ;not sure if we need esi push. Can change to scratch reg instead
            !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
            !pop esi
            !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       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       reSeedCrypt       ; mwcCarry = mwcSoph - 1 & mwcRandom = &hffffffff
          OK:
            !fstp rndE                 ;restore rndE
            mStoreSeq
            oneTime = 1

I moved oneTime = 1 to the bottom so the default sequence EXT's would seed rndE. I then printed the results from the little loop below, uncommenting one of the above 2 sections at a time. It seems like they should match.

Code:

#COMPILE EXE
#DIM ALL
#INCLUDE "win32api.inc"
#INCLUDE "rnd2TC3.inc"

FUNCTION PBMAIN () AS LONG
      LOCAL ii AS LONG
      DIM arr(&h0fffff) AS EXT
      rnd2goCrypto
      OPEN "c:\problemMatchAsm4.dat" FOR BINARY AS #1
      FOR ii = 0 TO &h0fffff
         rnd2(2)
         arr(ii) = rnd2()
      NEXT
        PUT #1,, arr()
      ? "k"
      rnd2stopCrypto
END FUNCTION

**David Roberts** · 26 Oct 2008, 01:44 PM

This will make you chuckle as well, John.

Code:

#Compile Exe
#Dim All

Function PBMain () As Long

  Static dummy, mwcSoph As Dword
  
  dummy = 43981 ' HABCD
  
  mwcSoph = &h08547ffff
  !lea eax, dummy
  !mov eax, [eax]
  !mov mwcSoph, ax
  Print Hex$(mwcSoph)
  
  mwcSoph = &h08547ffff
  !mov mwcSoph, 0 ' Reset mwcSoph
  !lea eax, dummy
  !mov eax, [eax]
  !mov mwcSoph, ax
   Print Hex$(mwcSoph)
 
  Waitkey$

End Function

Gives

8547ABCD
ABCD

We need to reset mwcSoph before loading it with ax.
......
......
!mov ax, [esi+8] ; the last two Of the 10 collected
!mov mwcSoph, 0 ; <--- Insert
!mov mwcSoph, ax
......
......

Added: My code didn't find a problem because mwcSoph was zero by default before the code ran.

Added more: Actually a better way without involving mwcSoph is
......
......
!mov mwcCarry, eax
!Xor eax, eax
!mov ax, [esi+8] ; the last two Of the 10 collected
!mov ecx, 384 ; 384 possible sophie-germain multipliers
......
......

Told you my asm is suspect.

**David Roberts** · 27 Oct 2008, 12:01 PM

Can we get 0,0? How about &hffffffff,&hffffffff?

Going back to basics

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

Since x mod y = x - INT( x/y )*y then

newr = oldr*m + oldc - INT( (oldr*m + oldc )/2^32 )*2^32

The INT term can be written newc*2^32, so

newr = oldr*m + oldc - newc*2^32 ...... [1]

To see this working, the following code uses the default pairings, generates a new pairing and than calculates [1].

A different mwcCarry is then used to show that a new mwcRandom can be the same as an old mwcRandom as John found out with ".., because I tested it and ~1 in 4.3 billion dwords are identical to the previous dword."

I should point out that unless the three parameters are Dwords the maths and the code seem to be out of sync. The generator uses unsigned mul so it is best to keep the PB side of things as Dwords otherwise a very big headache follows.

Code:

#Compile Exe
#Dim All
 
Macro mRandomLong
   !mov eax, mwcSoph
   !mov ecx, mwcRandom
   !mul ecx
   !Add eax, mwcCarry
   !adc edx, 0
   !mov mwcRandom, eax
   !mov mwcCarry,  edx
End Macro
 
Function PBMain () As Long
 
  Static OldmwcRandom, mwcRandom, OldmwcCarry, mwcCarry, mwcSoph As Dword
 
  mwcSoph = 4221732234
  mwcRandom = &ha5b218da '2779912410
  mwcCarry  = &h3fe8700c '1072197644
  Print "Oldr";mwcRandom;"Oldc";mwcCarry;"MwcSoph";mwcSoph
 
  OldmwcRandom = mwcRandom
  OldmwcCarry = mwcCarry
 
  mRandomLong
  Print "Newr";mwcRandom;"Newc";mwcCarry
  Print "Newr from [1] in notes";OldmwcRandom*mwcSoph + OldmwcCarry - mwcCarry*2^32: Print  ' From [1] in notes
 
  Print: Print "Repeat using mwcCarry = &h54d37156": Print
  mwcRandom = &ha5b218da '2779912410
  mwcCarry  = &h54d37156 '1423143254
  Print "Oldr";mwcRandom;"Oldc";mwcCarry;"MwcSoph";mwcSoph
 
  OldmwcRandom = mwcRandom
  OldmwcCarry = mwcCarry
 
  mRandomLong
  Print "Newr";mwcRandom;"Newc";mwcCarry
  Print "Newr from [1] in notes";OldmwcRandom*mwcSoph + OldmwcCarry - mwcCarry*2^32: Print  ' From [1] in notes
 
  Print: Print "Continue": Print
  OldmwcRandom = mwcRandom
  OldmwcCarry = mwcCarry
  mRandomLong
 
  Print "Newc";mwcRandom;"Newc";mwcCarry
 
  Print: Print "Continue": Print
  mRandomLong
  Print "Newc";mwcRandom;"Newc";mwcCarry
 
  Print:Print "Done"
 
  Waitkey$
 
End Function

This is the output:

Code:

Oldr 2779912410 Oldc 1072197644 MwcSoph 4221732234
Newr 2428966800 Newc 2732511104
Newr from [1] in notes 2428966800
 
Repeat using mwcCarry = &h54d37156
Oldr 2779912410 Oldc 1423143254 MwcSoph 4221732234
Newr 2779912410 Newc 2732511104
Newr from [1] in notes 2779912410
 
Continue
 
Newc 4089280260 Newc 2732511104
 
Continue
 
Newc 2992507816 Newc 4019552443
 
Done

An Interesting side note here is that the new mwcCarry using a different mwcCarry is the same as the original mwcCarry. The new mwcCarry for the next pairings is a repeat again.

So, when we have two consecutive mwcRandoms the mwcCarry for the second mwcRandom is repeated in the next pairings. Continueing further sees diffeent mwcRandoms and mwcCarrys.

I don't have time to pursue this aspect presently.

Anyway, going back to [1]. This can be rearranged as

oldc = newc*2^32 + newr - oldr*m

Suppose newr = oldr ...... [2]

then oldc = newc*2^32 - (m - 1)*newr

Since oldc >= 0 then newc >= (m - 1)*newr/2*32

Suppose newr = 2^32 - 1 (&hFFFFFFFF) and therefore oldr = 2^32 -1 from [2] ...... [3]

then newc >= (m - 1)*(2^32 - 1)/2^32

The right hand side when rounded up gives (m - 1)

so newc >= (m - 1)

The newc values produced by mwc are always less than m ie newc < m

Therefore m > (m - 1)

This is a contradiction.

We have made two suppositions

[2] is valid so [3] is false.

ie If newr = oldr then newr <> 2^32 - 1 if oldr = 2^32 - 1

We cannot then get succesive mwcRandoms equal to &hffffffff

Going back to [1]

ie newr = oldr*m + oldc - newc*2^32

Suppose newr = oldr = 0 ...... [4]

then 0 = oldc - newc*2^32

ie newc = oldc/2^32

Since oldc <= 2*32 - 1 then

newc <= (2*32 - 1)/2*32

which can only be satisfied with newc = 0

but we supposed newr = 0 from [4]

We cannot have newr = 0 and newc = 0

We cannot then get succesive mwcRandoms equal to 0

So, whilst RND is a [0,1] our implementation of mwc is (0,1)

A cup of tea is required, methinks.

**David Roberts** · 27 Oct 2008, 02:56 PM

OK I think this is what we have:

For each multiplier and a given mwcRandom there exists one and only one mwcCarry such that two successive mwcRandoms are the same.

Eamples:

mwcSoph = 4221483405
mwcRandom = 316289797 'Pulled out of the bag
mwcCarry = 2646047812

mwcSoph = 4151394078
mwcRandom = 85 'Pulled out of the bag
mwcCarry = 3613789023

The same code to find the mwcCarrys was given this

mwcSoph = 4151394078
mwcRandom = &Hffffffff

No mwcCarry was found to see the mwcRandom repeated.

**Gary Ramey** · 27 Oct 2008, 03:12 PM

David, I haven't studied your details, but your bolded conclusions are exactly what I have been talking about.

THOUGHTS ABOUT GENERATING THE LOW DWORD FOR EQ IN NOPARAMS

I'd like you to theorize with me about the possibility of modifying the second use of mRandomLong. (And I would love to remove "Long" from the name of that macro.) The first use of mRandom should be used to load our high dword of eq. The high dword is what controls the primary magnitude of our result, so it should be coupled to the primary mwc generator. The low dword is only repsonsible for precision in the positions past 1E-9 within our result.

((Note: eq is a signed quad, but I'm using dword terms since we're loading 4-bytes at a time without regard to sign or 2s-complement. The only way to load eq into the FPU is as a signed integer. That is fine since integers and floats in the FPU are signed.))

What would happen if we do not use mRandom a second time, BUT did something slightly different? What if we substituted another mwSoph (mwcSoph2) for calculating the low dword? I see no reason to worry about saving the mwcCarry and mwcRandom when calculating the low dword. Its calculation can be driven directly from the saved values associated with the high dword. It is not going to matter if we happen upon a mwcCarry and mwcRandom combination which will terminate a normally cycling mwc function. Our next use of the second generator will have the same mwcSoph2, but a new set of seeds. The second generator does necessarily need to be self sustaining.

Our mwcSoph2 would either need to be a fixed value that is not in the main set of 384 values, or derived as a repeatable offset from the primary mwcSoph so that the two mwcSophs are never the same. If a fixed value, then I'd go for a mwcSoph that is a little below our existing range of values.

A NOTE ABOUT [0,1) AND ABOUT (0,1)

Please note that our RND2() output approaches ZERO when the eq value is at both the low and high extremes (i.e., &h0000000000000000 and &hFFFFffffFFFFffff). We can get the zero output _ONLY_ when eq is all zeroes. We will get outputs of 0.##e-18 for eq's from &h00...0001 to &h00...0009, and outputs of -0.##e-18 for eq's in the range &hFF...FFE7 to &hFF...FFFF. The output from each of these eq inputs will be unique.

We have outputs approaching +1 an -1 when eq approaches &h8000...0000. Because of unavoidable rounding effects, we will actually get 0.99...999E+00 (i.e., all nines) for a range of values. On the "positive only" side, we will output all nines for eq ranging from &h07FFFffffFFFFfffB to &h07FFFFffffFFFFffff. One the "negative side" we will output all nines for eq ranging from &8000000000000000 to &h8000000000000005. So, there are actually 11 eq values which will produce all nines. All 11 of these inputs will be statistically extremely rare, even with two perfect mwc generators.

FYI, the "shape" of the output curve near 1 is in some ways not exactly linear due to the rounding effects in the FPU as we approach + and - unity (+/- 1). I don't presently know of any way to pursue all 18 possible digits with speed via multiplication and avoid this effect. Simple math shows us there are about 6 of those little "multiplier" slices with within that last "9" at the E-18 position. And, rounding effects bring in 5 more values.

**David Roberts** · 27 Oct 2008, 04:01 PM

Sounds good to me Gary.

Using a multiplier not in our set of 384 and less than those we could use

Code:

Macro m2RandomLong
  !mov eax, 4221474930
  !mov ecx, mwcRandom
  !mul ecx
  !Add eax, mwcCarry
'  !adc edx, 0
'  !mov mwcRandom, eax
'  !mov mwcCarry,  edx
End Macro

and in NoParams

Code:

mRandomLong               'sub to generate LONG rnd value
!lea ecx,   eq
!mov [ecx], eax           ; = Poke Long, eqPtr,     rndL
m2RandomLong               'sub to generate LONG rnd value
!lea ecx,     eq
!mov [ecx+4], eax         ; = Poke Long, eqPtr + 4, rndL

or should that be m2 followed by m - my grey matter always lets me down in this area.

Anyway, that was easy.

I've just done a demo run and all looks well.

Since m2 is shorter than m my latest best runs around 278ms has dropped a further 8% to 256ms. A bonus.

**David Roberts** · 27 Oct 2008, 04:22 PM

I was just about to embark on a mathematical analysis of using two generators when the 'phone rang and I must go out urgently.

In the immortal words of many of my reference books may I leave the proof of concept to the reader.

**John Gleason** · 27 Oct 2008, 05:59 PM

Gary said: We can get the zero output _ONLY_ when eq is all zeroes. We will get outputs of 0.##e-18 for eq's from &h00...0001 to &h00...0009, and outputs of -0.##e-18 for eq's in the range &hFF...FFE7 to &hFF...FFFF. The output from each of these eq inputs will be unique.

Here's a question: We can't get exactly zero, but do any of &h00...0001 to &h00...0009 or &hFF...FFE7 to &hFF...FFFF produce 0 or -0 rounded to 18 digits? The algo is designed only for 18-digit output accuracy. So it's possible we effectively get some zeros in there.

I too will consider the 2nd generator idea and try to figure out how it might pan out.

**Gary Ramey** · 27 Oct 2008, 06:33 PM

No, our algorithm only yields ZERO for a completely 0 eq. The rounding effect is only noticeable when the higher-order bits are already full of 'values' and we are incrementing that little 1E-19 multiplier in the few extra low-order bits that do not get displayed directly with the 18 "visible" decimal digits. Even near zero, we still have a full 18 digits of precision.

I have a utility program that is calculating exact output values using our actual code. Below are the results for outputs near +/- 1 and on both sides of 0.

Code:

      EQ (HEX)              RND2()               RND2() togScope
00000000 00000000  .000000000000000000e+01  0.00000000000000000e+00    
00000000 00000001  .108420217248550443e-18  1.08420217248550443e-19    
00000000 00000002  .216840434497100887e-18  2.16840434497100887e-19    
00000000 00000003  .325260651745651330e-18  3.25260651745651330e-19    
00000000 00000004  .433680868994201773e-18  4.33680868994201773e-19    
00000000 00000005  .542101086242752216e-18  5.42101086242752216e-19    
.....
7FFFFFFF FFFFFFFA  .999999999999999998e+0  9.99999999999999998e-1    
7FFFFFFF FFFFFFFB  .999999999999999999e+0  9.99999999999999999e-1    
7FFFFFFF FFFFFFFC  .999999999999999999e+0  9.99999999999999999e-1    
7FFFFFFF FFFFFFFD  .999999999999999999e+0  9.99999999999999999e-1    
7FFFFFFF FFFFFFFE  .999999999999999999e+0  9.99999999999999999e-1    
7FFFFFFF FFFFFFFF  .999999999999999999e+0  9.99999999999999999e-1    
80000000 00000000  .999999999999999999e+0  -9.99999999999999999e-1    
80000000 00000001  .999999999999999999e+0  -9.99999999999999999e-1    
80000000 00000002  .999999999999999999e+0  -9.99999999999999999e-1    
80000000 00000003  .999999999999999999e+0  -9.99999999999999999e-1    
80000000 00000004  .999999999999999999e+0  -9.99999999999999999e-1    
80000000 00000005  .999999999999999999e+0  -9.99999999999999999e-1    
.....
FFFFFFFF FFFFFFFA  .650521303491302660e-18  -6.50521303491302660e-19    
FFFFFFFF FFFFFFFB  .542101086242752216e-18  -5.42101086242752216e-19    
FFFFFFFF FFFFFFFC  .433680868994201773e-18  -4.33680868994201773e-19    
FFFFFFFF FFFFFFFD  .325260651745651330e-18  -3.25260651745651330e-19    
FFFFFFFF FFFFFFFE  .216840434497100887e-18  -2.16840434497100887e-19    
FFFFFFFF FFFFFFFF  .108420217248550443e-18  -1.08420217248550443e-19

**Gary Ramey** · 27 Oct 2008, 06:59 PM

You guys have probably long ago rejected using just one 32-bit mwc generated in the noParams section. But, for personal edification I took a look at what our output would look like under such a scenario. Here are some representative calculations:

Code:

Divisor = (2^32 +1) = 4294967297
................
         1 / Divisor = 0.232 830 643 599 659 520   29459655278022e-9
                   or  0.000 000 000 232 830 643   599 659 520   29459655278022e+0
         2 / Divisor = 0.465 661 287 199 319 040   58919310556045e-9
                   or  0.000 000 000 465 661 287   199 319 040   58919310556045e+0
         3 / Divisor = 0.698 491 930 798 978 560   88378965834067e-9
                   or  0.000 000 000 698 491 930   798 978 560   88378965834067e+0
................
&h07fffffff/ Divisor = 0.499 999 999 650 754 034   60051071955811
&h080000000/ Divisor = 0.499 999 999 883 584 678   2001702398527
&h080000001/ Divisor = 0.500 000 000 116 415 321   7998297601473
&h080000002/ Divisor = 0.500 000 000 349 245 965   39948928044189
................
(2^31 -3 ) / Divisor = 0.999 999 999 068 677 425   60136191882161
(2^32 -2 ) / Divisor = 0.999 999 999 301 508 069   20102143911621
(2^32 -1 ) / Divisor = 0.999 999 999 534 338 712   80068095941081
    (2^32) / Divisor = 0.999 999 999 767 169 356   4003404797054
................

Something like this is probably why PB keeps just the higher-order digits even though RND is providing an EXT type result. That extra housekeeping is probably one factor which slows RND down just a bit below what we have been able to achieve.

**David Roberts** · 28 Oct 2008, 04:33 AM

> Our mwcSoph2 would either need to be a fixed value that is not in the main set of 384 values

Post #228 does that.

> Its calculation can be driven directly from the saved values associated with the high dword

Post #228 does that.

> I'd go for a mwcSoph that is a little below our existing range of values. ...... [1]

Post #228 does that.

> It is not going to matter if we happen upon a mwcCarry and mwcRandom combination which will terminate a normally cycling mwc function.

The primary generator will never issue a mwcRandom of zero and a mwcCarry of zero. However, it could generate a mwcRandom = &Hffffffff and a mwcCarry equal to the secondary's multiplier minus 1. In this case the second generator would return &Hffffffff in mwcRandom ie its output will be its input.

The logic of [1] evades me. If the secondary's multiplier was chosen to be greater than any of the 384 available to the primary generator then since the primary generator issues all mwcCarrys less than its multiplier the second generator would never be compromised.

**Gary Ramey** · 28 Oct 2008, 07:31 AM

Okay, we can go to a higher mwcSoph for the second generator.

> Its calculation can be driven directly from the saved values associated with the high dword. Post #228 does that.

Actually, I believe that post #228 is still loading mRandom in the LOW dword and m2Random in the HIGH dword of eq. The x86 processor is little-endian. The high dword is (ecx+4). We need to CHANGE the sequence to (ecx+4) then (ecx).

I don't have time now, but we need to save the 32-bit outputs of m2Random in a way to independently test the randomness of what we getting out that half of our generator. To do this, we can rem out the loading of eq's high dword and just load m2Random to the low dword. (In other words, isolate m2Random as a simple 32-bit, unsigned generator.) Then we should scale our 'divisor' based on (2^32 +1). We're not worried about burning speed for testing, so we can just do a straight fpu divide instead of setting up an equivalent 'multiplier'. The output after fpu division will be scaled to [0, 1).

**David Roberts** · 28 Oct 2008, 07:49 AM

> We need to CHANGE the sequence to (ecx+4) then (ecx).

Could do, or just remove the '2' in the latter 'call' and insert it into the former 'call'.

I'm not so sure about testing the secondary generator that way because it will not get used that way. What not just test a sufficiency large numbers of EAXs generated.

**Gary Ramey** · 28 Oct 2008, 08:29 AM

We should use mRandom first, not m2Random. Let's keep m2Random associated with the current calculation, not with the prior cycle's saved values. So, we need to switch the location of "+4".

You're right about just saving eax. How could I forgot about Diehard actually expecting 32-bit values?

**John Gleason** · 28 Oct 2008, 09:04 AM

Dave said: I don't have time now, but we need to save the 32-bit outputs of m2Random in a way to independently test the randomness of what we getting out that half of our generator.

I tested the data as quads just as they are produced (without the "ranging divide" to get between .999... and .000...) and unfortunately it fails diehard overall and in half a dozen indiv. tests. I did ok in ENT tho.

Gary posted:
00000000 00000001 .108420217248550443e-18 1.08420217248550443e-19
00000000 00000002 .216840434497100887e-18 2.16840434497100887e-19
00000000 00000003 .325260651745651330e-18 3.25260651745651330e-19
00000000 00000004 .433680868994201773e-18 4.33680868994201773e-19
FFFFFFFF FFFFFFFC .433680868994201773e-18 -4.33680868994201773e-19
FFFFFFFF FFFFFFFD .325260651745651330e-18 -3.25260651745651330e-19
FFFFFFFF FFFFFFFE .216840434497100887e-18 -2.16840434497100887e-19
FFFFFFFF FFFFFFFF .108420217248550443e-18 -1.08420217248550443e-19

Within the PowerBasic 18-digit range, the above are equal to zero as the below code shows. So we will get up to 8 (or 16) zero outputs from the mwc generator creating the eq quad from sequential values.

Code:

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG
    LOCAL x AS EXT
    x = VAL(".108420217248550443e-18")
    ? FORMAT$(x, ".000000000000000000")
    ? USING$(".##################", x)
    ? STR$(ROUND(x, 18))

END FUNCTION

**David Roberts** · 28 Oct 2008, 09:42 AM

> Let's keep m2Random associated with the current calculation, not with the prior cycle's saved values.

Point taken.

**Gary Ramey** · 28 Oct 2008, 01:37 PM

Within the PowerBasic 18-digit range, the above are equal to zero as the below code shows.

Okay, I see what you are thinking. But I don't think that is technically correct. What you are doing is 'denormalizing' the extended floating point value, and forcefully rounding the result. For our particular "near-zero" rndE's, there really are 17-18 digits of real precision available beyond the cut-off point. If we want to force our output to only have the appearance of having a value when it is between -0.1e-17 to +0.1e-17, then we need to add some more code. Actually, if that is what we are really trying to do, we need to go back to something closer to the noparams section in the original RND2 source code posting. We can optimaize that code, provided it passes Diehard and other tests. One optimization is to use a bit from the discarded top 4 bits as our sign bit, instead of rolling through mRandom again.

Regarding extended FP "precision". The PB9 help documentation states:

They have a range of approximately +/- 3.4*10^-4932 to 1.2*10^4932, and offer 18 digits of precision. All 18 digits can be "displayed" using the extended STR$ format (eg, STR$(var##,18)).

I'm accustomed to thinking about our full range of possible exponents. You didn't get "all zeros" until you added ROUND, which is not a PB limitation. I didn't understand that we were trying to round the results. The only way to avoid the unwanted rounding effects near 0 and +/-1 is to reduce the range of eq so that our scaling divisor (or multiplier) is exactly 1 to a power of 10. And, now I understand the general strategy of that original RND2 noparams code.

**John Gleason** · 28 Oct 2008, 02:26 PM

Gary, my original thought for the EXT random was all values from -.999... to .999... with 18 digits of precision from the decimal point. I should have added from the decimal point originally just to avoid confusion re. what 18 digits we were dealing with.
The possible output you can print near 0 would therefore be:

Code:

-.000000000000000001
0
 .000000000000000001

I think you're right about the original code being theoretically better, but there's no way I can see to make it near as fast as the current code. Also statistically, I doubt there will ever be a way to distinguish between them because the differences are so minute.

Announcement

Rnd2 disscussion

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment