Random Generator

[Antariy]

Yes, but choose the fastest algo, and start with my favourite values :wink:

Well, anybody can choose its own algo  :bg, which period have your algo?
Reply #97 is the skeleton :P



Alex

[jj2007]

Yes, but choose the fastest algo, and start with my favourite values :wink:

Well, anybody can choose its own algo  :bg, which period have your algo?
Reply #97 is the skeleton :P

1898349916 for imul eax, -127 and add eax, -128

[Antariy]

Yes, but choose the fastest algo, and start with my favourite values :wink:

Well, anybody can choose its own algo  :bg, which period have your algo?
Reply #97 is the skeleton :P

1898349916 for imul eax, -127 and add eax, -128

Algorithm, which is initially posted at second my post at this thread, have period which is close to full DWORDs range: 4,138,934,403 (posted by Michael at reply #78).



Alex

[jj2007]

The -127/-124 pair has both a long period and excellent randomness:

; with imul -127, add eax, n:   ; period, chi square 0123/dword
   ; -128   1898349916
   ; -127   2766784829
   ; -126   786943256
   ; -125   1492884433
   ; -124   4158707804, 5*50
   ; -123   3720667977, 75, 75, 50, 75, 50
   ; -122   3008980430, 75, 50, 97.5, 75, 50
   ; -121   3461554912, 50, 75, 75, 50, 50
   ; -119   115388264, 50, 75, 50, 50, 50
   ; -118   1121767446
   ; -117   4071617755, 25, 25, 90, 25, 5
; with imul -128, add eax, n:   ; period, chi square 0123/dword
   ; -128   0 aka 2^32, chi square horrible
   ; -127   0 aka 2^32, chi square horrible
; with imul -123, add eax, n:   ; period, chi square 0123/dword
   ; -128   662055917
   ; -127   368088112
   ; -123   693250349

Code Select Expand

start:
push -1
call Axrand3
mov ebx, eax
xor esi, esi
.Repeat
push -1
call Axrand3
inc esi
.Until Zero? || eax==ebx ; 2147483648
print chr$(13, 10, "The period: ")
inkey ustr$(esi), 7, 13, 10
exit

[Antariy]

-117 is better than other - other is too long (bigger than DWORD range).



Alex

[Antariy]

P.S. But it is still less than DWORD can holds. So, this is interesting thing - find values which will generate period close to DWORD range, but not bigger and not lot smaller.

[jj2007]

Yes indeed, Alex. Besides, the period also depends on the range, in ways that are not obvious:

   ; -127   2766784829, 50, 90, 50, 50, 50, periods 100/1000 etc: 5, 1584, 5216, 5216, 339035, ..
   ; -124   4158707804, 5*50, periods 100/1000 etc: 153, 2861, 10095, 111553, 956647, 956647, 956647, 279161941

However, these periods are not important when the range is -1, e.g. when you want to return a float as shown below.

Code Select Expand

RndSeed MACRO SeedName:=<MbSeed>
  ifndef SeedName
LOCAL SeedName:QWORD
  endif
  rdtsc
  mov dword ptr SeedName, eax
  and dword ptr SeedName+4, 0
  ifdif <SeedName>, <MbSeed>
MbSeed equ SeedName
  endif
ENDM

Rnd MACRO dest
  mov eax, dword ptr MbSeed ; Initial
  imul eax, -127 ; randomise
  add eax, -124
  bswap eax ; we need the high order bits
  mov dword ptr MbSeed, eax ; save for next round
  ffree st(7)
  if type(MbSeed) ne QWORD
% .err <MbSeed must be a qword>
  endif
  fild MbSeed
  fmul RndMul
  fstp dest
ENDM


[Antariy]

However, these periods are not important when the range is -1, e.g. when you want to return a float as shown below.

No, it is important at point how fastly would appear the same value, after some number of generations. Anyway, your constants gives the good results, too.



Alex

[Antariy]

Jochen, still do you want to have ENT as DLL? Just I have no look to it, yet. This is allowed - build it as unindepended executable (i.e. - DLL)?



Alex

[jj2007]

GregL quoted a pretty liberal license, so I guess it is allowed to turn it into a dll. It would speed up testing dramatically - imagine how many millions of cycles you need just to open a console window :lol

The terse mode would be enough. My preferred syntax would be invoke ENT, ptrCommandLine, ptrSourceBuffer, bytes, ptrResults, i.e. no need to write to a file.

Greg:
This software is in the public domain. Permission to use, copy, modify, and distribute this software and its documentation for any purpose and without fee is hereby granted, without any conditions or restrictions.

[Antariy]

imagine how many millions of cycles you need just to open a console window :lol

Okay, okay...  :bg



Alex

[FORTRANS]

Hi,

   While browsing Marsaglia's Diehard notes, I see that he likes
what he calls "Multiply With Carry" random number generators.
Using his MAKEWHAT.EXE as a reference, I coded up an MWC
generator.  Seems good overall, except for the name.  Since
"carry" has a specific meaning for assembly programmers.

   ENT results show all bytes are good.  See Reply#33 to
compare to the LCG results.

Full ENT.EXE results for RandMWC first file.

Entropy = 7.999839 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 222.84, and randomly
would exceed this value 90.00 percent of the times.

Arithmetic mean value of data bytes is 127.5642 (127.5 = random).
Monte Carlo value for Pi is 3.130236521 (error 0.36 percent).
Serial correlation coefficient is 0.001554 (totally uncorrelated = 0.0).

   Condensed
Run#, Chi square  percent
   1    222.84,    90.00
   2    240.36,    50.00
   3    247.61,    50.00
   4    320.84,     0.50
   5    273.72,    25.00
   6    253.78,    50.00
   7    258.05,    50.00
   8    250.85,    50.00
   9    249.83,    50.00
  10    255.38,    50.00
  11    239.91,    50.00
  12    216.47,    95.00


   And using my dice throw simulation to compare MWC and LCG.

RANLCG max events.

Roll of Dice Simulation, Chi-Squared Test
Number of bins =  11, Constraint =   1, Number of events =100000
Observed evnt 2746. 5502. 8375.11029.13836.16580.13814.11160. 8462. 5661. 2835.
Expected evnt 2778. 5556. 8333.11111.13889.16667.13889.11111. 8333. 5556. 2778.
  DF, CHSQ, PROB    10.00    8.13   61.59

  1, CHSQ, PROB     8.13   61.59%
  2, CHSQ, PROB    12.18   27.30%
  3, CHSQ, PROB     7.47   68.03%
  4, CHSQ, PROB     4.31   93.23%
  5, CHSQ, PROB     9.13   52.02%
  6, CHSQ, PROB     5.11   88.34%

RandMWC max events.

Roll of Dice Simulation, Chi-Squared Test
  1, CHSQ, PROB    10.02   43.91%
  2, CHSQ, PROB    11.62   31.14%
  3, CHSQ, PROB     6.25   79.40%
  4, CHSQ, PROB     6.27   79.25%
  5, CHSQ, PROB     5.77   83.44%
  6, CHSQ, PROB    10.02   43.92%


   My implementation.

Code Select Expand


;RandMWC:        ; Multiply with carry "Random" number Generator from Marsaglia

Rand32  DD      31415926        ; a la K
        DD      1013904223      ; As per NR RandC
RandA   DD      1517746329      ; See RandMWC

; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
; 3 November 2010, try Marsaglia's "Multiply With Carry".
; His notation:
;   RandN+1 = A*RandN + Carry Mod B, M = A * B - 1 = Prime Safe.
; for my understanding:
;   RandN+1 = RandA*RandN + High DWordN
;   Fold would be better than carry?

;(In general, for any choice of `a`, let m=a*2^32-1. If both m
;and (m-1)/2 are prime then the period will be (m-1)/2).

RandMWC:
        MOV     EAX,[Rand32]
        MUL     [RandA]
        ADD     EAX,[Rand32+4]
        ADC     EDX,0
        MOV     [Rand32],EAX
        MOV     [Rand32+4],EDX

        RET


   Thoughts?

Regards,

Steve N.

[MichaelW]

It looks like it should be fairly fast.

[Antariy]

It looks like it should be fairly fast.

Yes, about ~8 cycles on your CPU, I guess.

Steve, if add a range specifier - that is will be best algo, probably.



Alex

[FORTRANS]

Hi Alex,

   Do you mean you want it to output a limited set of integers?
I would warm up the generator and use the current random
number, then fall through to refresh the random number.
Something like:

Code Select Expand


; - - - - - -
; Limit random number to 0 <= returned < LIMIT.
; Enter wwith LIMIT in ECX.
; Return result in in ECX.
LimitRand:
        MOV     EAX,[Rand32]
        MUL      ECX
        MOV     ECX,EDX
; - - - - - -
RandMWC:
        MOV     EAX,[Rand32]
        MUL     [RandA]
        ADD     EAX,[Rand32+4]
        ADC     EDX,0
        MOV     [Rand32],EAX
        MOV     [Rand32+4],EDX

        RET


   Does that make sense to you?

Regards,

Steve N.