News:

MASM32 SDK Description, downloads and other helpful links
MASM32.com New Forum Link
masmforum WebSite

Random Generator

Started by Neil, June 17, 2009, 12:44:13 PM

Previous topic - Next topic

jj2007

Quote from: Antariy on November 02, 2010, 01:47:33 AM
Quote from: jj2007 on November 02, 2010, 01:38:54 AM
by choosing e.g. Ciao

You can use the Пока и Хайр, too  :bg


Almost everything goes, of course. But caution with exotic values such as 0 or -1. And the bswap is needed, too - try removing that, and the randomness parameters drop dramatically.

Antariy

Quote from: jj2007 on November 02, 2010, 02:04:53 AM
Almost everything goes, of course. But caution with exotic values such as 0 or -1. And the bswap is needed, too - try removing that, and the randomness parameters drop dramatically.

Jochen, read the ~3 my previous posts, please. In them *I said: BSWAP IS THE KEY OF THE ALGO* !!! Probably you miss that posts.

I suggested to remove bswap and see results too, see previous posts  :wink



Alex

MichaelW

The 12346 multiplier is no good:

Entropy = 7.951915 bits per byte.

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

Chi square distribution for 10000000 samples is 661132.45, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.3905 (127.5 = random).
Monte Carlo value for Pi is 3.145268458 (error 0.12 percent).
Serial correlation coefficient is -0.001283 (totally uncorrelated = 0.0).
eschew obfuscation

FORTRANS

Quote from: Antariy on November 01, 2010, 10:06:11 PM
Hi, Steve!

Do you have the Diehard compiled with good Fortran compiler?

Hi Alex,

   No.  But I will look into it.

Quote
I have downloaded sources for C some days ago (when Michael made the test), but tried to build the program yesterday only.

I have builded it with different versions of MSVC (6 and 10), with PellesC, but program seems to work badly. Floating point results output says about errors or NaNs. Sources is ported not cleanly, too - compilers have many "asks" to code.
So, I'll ask you for the EXE which is compiled with Fortran compiler, as I understand - it is the original language on which is written that test.

   Okay.

Regards,

Steve N

FORTRANS

Hi,

   Here is a executable created with Microsoft FORTRAN.

Regards,

Steve N

http://www.stat.fsu.edu/pub/diehard/cdrom/dos/diehard.exe

Antariy

Quote from: MichaelW on November 02, 2010, 04:10:28 AM
The 12346 multiplier is no good:

It seems, that my supposition is right - about fact that if generator does not generate repeated value nearly to the end of the period - it is not good. Generator should generate the same value after all possible variants (i.e. - period length) is generated for targer datatype - I guess. For very long period with fixed datatype, needed to increase size of that type - maybe use QWORDs. Or use byte-range to generate bytes, with eventually seed of Initial. And construct needed datatype with that bytes.



Alex

Antariy

Quote from: FORTRANS on November 02, 2010, 06:26:49 PM
   Here is a executable created with Microsoft FORTRAN.

Thank you! I have downloaded it now, too.



Alex

Antariy

The Axrand code is not big. Moreover, it have only 2 places which is needed to be frequently changed for testing - that is the constants. So, if we initially write

imul edx,12345678h
add edx,12345678h

then compile this - constants would be have 4 bytes in the binary code.

We can use the piece, which contain full code of Axrand in this way:
1. Create different thread.
2. New thread copy the code of Axrand to its own space allocated (with executable attribs - for DEP).
3. New thread replace the constants at a fixed offset from the start of the Axrand binary code. New constants will be generated at runtime at main procedure - each new thread can get it's starting number for using in 2 constants from its parameter.
4. New thread works to find the best period.
5. After founding repeated thing, thread put the value of its maximal period into array, its member - the starting number which it is have at start, for example.

Testing on multicore/CPUs machines would help a lot.


To be honest - I have satisfyed with my current (i.e. - second posted at this thread) proc - it have good results in tests, and it have period which is very close to the maximal possible - the DWORD's range.  :bg



Alex

MichaelW

I tried a number of multipliers, and while some of them worked well for the ENT tests, they all produced shorter periods than the current Axrand coding. So I decided to try the multiplier and increment values from George Marsaglia's congruential generator CONG, which has a period of 2^32:

x(n)=69069x(n-1)+1234567

This worked well for the ENT tests, but had a shorter period than the current Axrand coding. After I eliminated the BSWAP instruction, then in addition to the P3 cycles dropping to 8, I got a period of 4,294,967,297 (which I see now is off by one because my code goes one count past the end of the period). Unfortunately, without the BSWAP the generated sequence does poorly on the Chi square test:

Entropy = 7.999992 bits per byte.

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

Chi square distribution for 10000000 samples is 107.67, and randomly
would exceed this value 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.4951 (127.5 = random).
Monte Carlo value for Pi is 3.140778056 (error 0.03 percent).
Serial correlation coefficient is 0.000210 (totally uncorrelated = 0.0).


eschew obfuscation

Antariy

Quote from: MichaelW on November 03, 2010, 02:04:08 AM
I tried a number of multipliers ...

Hard matter to full-testing. At least needed multithreaded test, or that requires too long time, probably.


Alex

Antariy

Quote from: MichaelW on November 03, 2010, 02:04:08 AM
... 1234567

Maybe that is too big constant - it does not make small step?



Alex

Antariy

Michael, if change ADD EDX,17 to ADD EDX,12347, I get these results, all other things is the same:

Entropy = 7.999818 bits per byte.

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

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

Arithmetic mean value of data bytes is 127.4555 (127.5 = random).
Monte Carlo value for Pi is 3.152196609 (error 0.34 percent).
Serial correlation coefficient is 0.000846 (totally uncorrelated = 0.0).



What you think?



Alex

MichaelW

The period is much shorter: 667,579,016

The reason I used the values from CONG was that those values satisfy the requirements for an LCG to have a maximum period. But because of the BSWAP, Axrand is not exactly an LCG.

eschew obfuscation

Antariy

Quote from: MichaelW on November 03, 2010, 03:07:40 AM
The period is much shorter: 667,579,016
The reason I used the values from CONG was that those values satisfy the requirements for an LCG to have a maximum period. But because of the BSWAP, Axrand is not exactly an LCG.

Is worth to make test, which is "designed" at reply #97 ?
Somebody with multicore CPU desire to run heavy test?  :green2



Alex

jj2007

Quote from: Antariy on November 03, 2010, 10:57:19 PM
Is worth to make test, which is "designed" at reply #97 ?
Somebody with multicore CPU desire to run heavy test?  :green2

Yes, but choose the fastest algo, and start with my favourite values :wink:
mov esi, -127
mov edi, -128
mov ebx, -1
call AxRand

Axrand proc ; STDCALL dwRange:DWORD
mov eax, Initial ; get the seed
imul eax, esi  ; -127 ; randomise
add eax, edi  ; -128
bswap eax ; we do need the high order bits
mov Initial, eax ; save for next round
mul ebx   ; -1 aka dword ptr [esp+4] ; multiply Initial with range
; mov eax, edx ; return random number (could also be returned in edx)
ret ; 4
Axrand endp