Scatter Plot

[KeepingRealBusy]

Michael,

I wanted a scatter plot so I grabbed yours from http://masm32.com/board/index.php?topic=408.msg2815#msg2815 and modified it. I have attached a zip of the tests. I wanted to do a scatter plot of 4 of the RNGs, CONG, KIP, MASM32, and my new one New. it turns out that CONG does not do so well, it leaves the screen with vertical bars and never completes. My RNG, NEW also had a bit of a slow execution, but eventually cleared the screen. I found that if I changed the display from 200x200 to 199x200, both improved dramatically. I also tried to change my NEW final rotation from 7 to 8 that it also sped up the 200x200 display. All of the displays seemed to go in spurts, quickly at first, and slowed down, then sped up again, at least this is what appeared visually.

To get around this, I developed an array version that created a 1024x1024 array (I could have done this dynamically, but it was easier to grab a big array and only partially fill and use it). The method filled the array with the x/y offsets of all of the pixels, then used the RNG to only select a random entry in the array (and also get the current last entry in the array), and save the x/y coordinates, and replace the selected entry with the last entry, and decrement the array size for the next go. This version seems to run rapidly for all 4 test cases and all of the RNGs appear to randomly access the entire array.

If you execute makeall it will rebuild all of the 4 test cases in each zip, there are only 2 asm modules in each zip then you can execute any of the 4 test cases. I would be interested in your analysis of why CONG seems to hang without clearing the screen (leaving the vertical bars). I believe this is under the condition of a 200x200 display. You may also take a stab at explaining why NEW also seems so slow for 200x200. All test cases seem to run OK at 199x200  All of the array test cases run quickly.

Dave.

[MichaelW]

Hi Dave,

CONG is a congruential generator with the widely used 69069 as multiplier: x(n)=69069x(n-1)+1234567. It has period 2^32. The leading half of its 32 bits seem to pass all tests, but bits in the last half are too regular.

By “leading half” he apparently meant the most significant half, so my fix was to rotate the value by 16 bits after the new seed was saved. It worked for my test app, but for general-purpose use CONG is probably a bad choice. Without the rotate, when generating numbers over a range much less than 16 bits, the output is decidedly non-random, for some ranges to the point that most of the values never occur.

The output for your NEW generator seems to be more or less non-random over all ranges, and for some ranges most of the values never occur. But running in my app it does produce some interesting patterns.

Code: [Select]

;==============================================================================
    include \masm32\include\masm32rt.inc
;==============================================================================
    .data
      hInstance dd    0
      hDlg      dd    0
      hdc       dd    0
      msg       MSG   <>
      rc        RECT  <>
      sz        db 30 dup(0)
      ctr       dd 0
    .code
;==============================================================================
;------------------------------------------------------------------------
; This is an assembly implementation of a generator by George Marsaglia.
;
; "CONG is a congruential generator with the widely used 69069 as
; multiplier: x(n)=69069x(n-1)+1234567. It has period 2^32.
; The leading half of its 32 bits seem to pass all tests, but bits
; in the last half are too regular."
;
;   http://www.ciphersbyritter.com/NEWS4/RANDC.HTM
;
;------------------------------------------------------------------------
OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
align 4
cong proc base:DWORD
    mov eax, cong_seed
    mov ecx, 69069
    mul ecx
    add eax, 1234567
    mov cong_seed, eax
    ;----------------------------------------------------------------
    ; It looks like "leading half" means the most significant half.
    ; This ROR appears to correct the problem, for this app, but
    ; unfortunately it also shortens the period.
    ;
    ; Without the ROR the worst distribution I could find, in the
    ; short time I spent on it, was at 184x368.
    ;----------------------------------------------------------------
    ROR EAX, 16
    xor edx, edx
    div DWORD PTR [esp+4]
    mov eax, edx
    ret 4
    .data
      align 4
      cong_seed dd 1234567
    .code
cong endp

align 4
new proc base:DWORD
    mov   eax,dSeed
    add   eax,dPrime
    mov   dSeed,eax
    ror   eax,7
    xor edx, edx
    div DWORD PTR [esp+4]
    mov eax, edx
    ret 4
    .data
      align 4
      dSeed DWORD 0
      dPrime DWORD 275604541
    .code
new endp
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef

;==============================================================================
DialogProc proc hwndDlg:DWORD, uMsg:DWORD, wParam:DWORD, lParam:DWORD
    SWITCH uMsg
        CASE WM_CTLCOLORDLG
            invoke GetStockObject, WHITE_BRUSH
            ret
        CASE WM_SIZE
            invoke InvalidateRgn, hwndDlg, NULL, TRUE
        CASE WM_COMMAND
            SWITCH wParam
                CASE IDCANCEL
                    invoke DestroyWindow, hwndDlg
            ENDSW
        CASE WM_CLOSE
            invoke DestroyWindow, hwndDlg
        CASE WM_DESTROY
            invoke PostQuitMessage, NULL
    ENDSW
    xor eax, eax
    ret
DialogProc endp
;==============================================================================
start:
;==============================================================================
    invoke GetModuleHandle, NULL
    mov hInstance, eax
    Dialog "Test", \
           "FixedSys", 11, \
            WS_VISIBLE or WS_OVERLAPPEDWINDOW or \
            DS_CENTER, \
            0, \
            0,0,150,75, \
            1024
    CallModelessDialog hInstance, 0, DialogProc, NULL
    mov hDlg, eax
    invoke GetDC, hDlg
    mov hdc, eax
    invoke Sleep, 1000
  msgLoop:
    invoke PeekMessage, ADDR msg, NULL, 0, 0, PM_REMOVE
    .IF msg.message != WM_QUIT
        .IF eax != 0
            invoke IsDialogMessage, hDlg, ADDR msg
        .ELSE
            invoke GetClientRect, hDlg, ADDR rc
            inc ctr
            cmp ctr, 1000
            jb  @f
            invoke szappend, addr sz, chr$("  "), 0
            mov esi, eax
            invoke szappend, addr sz, str$(rc.right), esi
            mov esi, eax
            invoke szappend, addr sz, chr$(" x "), esi
            mov esi, eax
            invoke szappend, addr sz, str$(rc.bottom), esi
            invoke SetWindowText, hDlg, addr sz
            mov ctr, 0
          @@:
            ;invoke cong, rc.right
            invoke new, rc.right
            mov ebx, eax
            ;invoke cong, rc.bottom
            invoke new, rc.bottom
            mov esi, eax
            ;invoke cong, 1 SHL 24
            invoke new, 1 SHL 24
            mov edi, eax
            invoke SetPixel, hdc, ebx, esi, edi
        .ENDIF
        jmp msgLoop
    .ENDIF
    exit
;==============================================================================
end start


[KeepingRealBusy]

Michael,

Thank you for the answer. Did you look at the array implementation for scatter plot?

I had one question about randf_size that started all of this:

Code: [Select]


include \masm32\include\masm32rt.inc

randf PROTO

.code

randf_size PROC, min : REAL10, max : REAL10
FLD max
FLD min
FSUB
;FLD ST         ; <---<<<
invoke randf
FMUL
FLD min
FADD
RET
randf_size ENDP

You properly calculate the size of max-min, then get the random number, but then, instead of dividing the random number by the size and using the remainder, you multiply by the size, and finally add the base minimum value. Why multiply? This should produce huge numbers that are outsize of the display area. Does the bit set function truncate these numbers and plot only the least significant bits of the input?

Dave.

[FORTRANS]

By “leading half” he apparently meant the most significant half,

Hi Michael,

   We had a thread on the old forum that discussed
random number generators.  In one of my postings, I
commented on the quality of a Linear Congruential random
number Generator (LCG).  CONG is one of those.  I
discussed the nature of the low bits generated by a LCG
in Reply #53.  I uploaded a program to show the effects
on the low bits as well.  Only the high bits of a LCG should
be used.  And elsewhere in that thread a LCG was tested
with ENT, and performed well when using the high bits.

http://www.masmforum.com/board/index.php?topic=11679.msg123225#msg123225

Regards,

Steve N.

[MichaelW]

Dave,

The code in randf_size.asm and randf.asm was not my code and since I don’t have any memory of how it works I must not have analyzed it. I think the scatter plot test was a quick way to see if it actually worked before I bothered to analyze it, and from there I’m not sure what happened.

Looking back at it now, randf starts out by XORing a random 16-bit integer derived from nrandom with whatever junk is on the stack in the LOCAL num. Then after more manipulations that I can’t make sense of ATM, it apparently (as determined by test) returns a floating-point value somewhere between 0 and 1 on the FPU stack (like the BASIC RND function). Then randf_size multiplies this value by the specified range, and adds it to the minimum. This is the randf_size code with my modifications to display the value returned by randf on the console:

Code: [Select]

randf_size  PROC, min : REAL10, max : REAL10
  FLD max
  FLD min
  FSUB
  ;FLD ST         ; <---<<<
  invoke randf
  sub esp, 8
  fst QWORD PTR [esp]
  printf("%f\t", QWORD PTR [esp])
  add esp, 8
  FMUL
  FLD min
  FADD
  RET
randf_size  ENDP

Steve,

Thanks, I had forgotten that post and that very long thread, even though I have recently been referring to code from that thread, including my own :(

[KeepingRealBusy]

Michael,

The question still remains, why did you multiply the value returned from randomf instead of dividing by the size between max and min to have a sized return, and then add the min, or is this just an overlooked error because the resulting values just seemed to work for the scatter plot?

Dave.

[MichaelW]

The question still remains, why did you multiply the value returned from randomf instead of dividing by the size between max and min to have a sized return, and then add the min, or is this just an overlooked error because the resulting values just seemed to work for the scatter plot?

Sorry, I’m not following you. In the post that you provided a link to (first post in this thread) I was testing code from this post:

http://masm32.com/board/index.php?topic=408.msg2739#msg2739

Other than my commenting out what appeared to me to be an error in randf_size.asm, the only code I contributed was in test.asm.

And considering the [0,1) interval of the numbers returned by randf, a multiply is the only reasonable way I can see to expand the range.

[KeepingRealBusy]

Michael,

That was the answer I was looking for :t I forgot that the return was a float with that range. It all makes sense now.

Dave.