Fast and small Multiplicative Random number generator

Index > Main > Fast and small Multiplicative Random number generator

Goto page 1, 2, 3 Next

Author

Thread

hopcode

Joined: 04 Mar 2008
Posts: 563
Location: Germany

hopcode 19 Dec 2011, 16:07

Hi everybody,
some days ago i started thinking upon a
fast and simple random number generator of few
lines of codes, wondering about the use of
MUL and RDTSC. after some "deviations" from the theory Smile

i stumbled upon this following idea of mine:

Code:

.randomB:
   rdtsc
   mov rcx,866AA7'3F0B'7F'0B'03h
   movd mm0,eax
   movq mm1,rcx
   pshufw mm0,mm0,00'10'01'00b
   pmaddwd mm1,mm0
   pshufb mm1,mm0
   pmullw mm1,mm0
   movq rax,mm0
   movq rcx,mm1
   mul rdx
   sub rax,rcx
   ret

then using ENT to test some of its features
here what i have found:

Code:

ent result.bin
Entropy = 7.841899 bits per byte.

Optimum compression would reduce the size
of this 130800 byte file by 1 percent.

Chi square distribution for 130800 samples is 29972.95, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 129.7706 (127.5 = random).
Monte Carlo value for Pi is 3.139266055 (error 0.07 percent).
Serial correlation coefficient is -0.001012
(totally uncorrelated =0.0).

could you please help me to read those values about it ?

ent link is at
http://www.fourmilab.ch/random/

and the following 2 screenshots using gnuplot
total distribution of 65536 items ANDED to 65535
http://sites.google.com/site/x64lab/randomB_ganz.gif?attredirects=0
and a detail of it
http://sites.google.com/site/x64lab/randomB_detail.gif?attredirects=0
i have drawn some blu lines to denote visible
constant "holes" inside it.

Hints, general guidelines about the subject,
improvements, your opinion on the results well appreciated

Thanx in advance,
Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑

19 Dec 2011, 16:07

AsmGuru62

Joined: 28 Jan 2004
Posts: 1619
Location: Toronto, Canada

AsmGuru62 19 Dec 2011, 16:32

Best tests you can run on your generator are DIEHARD tests.

19 Dec 2011, 16:32

cod3b453

Joined: 25 Aug 2004
Posts: 618

cod3b453 19 Dec 2011, 20:53

In general, random numbers should follow:

- Each bit changes with probability 0.5 on each iteration [Strict Avalanche Criterion]
- Each bit changes independently of the others [Bit Independence Criterion]

which translates to:

- Have uniform distribution; 1/N occurences of all N numbers, hence an average of N/2
- Only repeat each value every N times on average

The stream that is produced should then have no pattern (in general) and therefore cannot be compressed because the stream is the simplest form, which can also be measured as entropy (uncertainty), and there is no overall correlation between values.

I'm not familiar with Chi square. Monte Carlo is when you use a random source as the input to a function; in this case it looks like a Pi approximation calculation.

----

I'm wondering if, when you say "anded", you mean "Rand = RandA AND RandB" ? If so, might want to try XOR instead, since it preserves bit distribution instead of skewing to 0.

The "p..." instructions might also have room for improvement (not really looked at this).

HTH

19 Dec 2011, 20:53

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 19 Dec 2011, 21:00

Everybody should note that this is actually a pseudo random number generator. There are thousands of variations of these. And there is probably very little sense in trying to invent your own unless you have some extremely specific requirement not met by existing algorithms. Some of my favourites are the Titanic Twister and the Mersenne Twister series. Both of these types would be faster than the example above and have proven to pass the various tests.

19 Dec 2011, 21:00

AsmGuru62

Joined: 28 Jan 2004
Posts: 1619
Location: Toronto, Canada

AsmGuru62 20 Dec 2011, 04:25

btw, here is a problem: a generator returns 32-bit numbers, like Mersenne. And the number from 0 to 9 is needed. Usually, in this case the MOD operation used, like VALUE = RAND MOD 10. This solution is not correct, however. The correct one is like this:

1. Turn the unsigned 32-bit integer into value in range [0.0 ... 1.0]
2. Multiple that value by 10
3. Truncate the result to integer again

OR

1. Divide FFFFFFFFh by 10
2. Divide the generated value by a value from step #1

That second method may lose precision in some cases.

20 Dec 2011, 04:25

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 20 Dec 2011, 04:35

AsmGuru62 wrote:

btw, here is a problem: a generator returns 32-bit numbers, like Mersenne. And the number from 0 to 9 is needed. Usually, in this case the MOD operation used, like VALUE = RAND MOD 10. This solution is not correct, however. The correct one is like this:

1. Turn the unsigned 32-bit integer into value in range [0.0 ... 1.0]

Do you mean convert to a float?

AsmGuru62 wrote:

2. Multiple that value by 10
3. Truncate the result to integer again

OR

1. Divide FFFFFFFFh by 10
2. Divide the generated value by a value from step #1

That second method may lose precision in some cases.

But neither method will improve on the spread of generated values over what rand mod 10 gives. There will always be a small bias towards a subset of the digits. A method that completely avoids this problem is:
1. Get rand
2. If rand > 4294967289 goto step 1
3. value = rand mod 10
Then all 10 possible digit values will have even spread without bias (of course assuming the input 32-bit number is perfectly random).

20 Dec 2011, 04:35

smiddy

Joined: 31 Oct 2004
Posts: 557

smiddy 20 Dec 2011, 04:51

I have heard of a method to get a random number from the voltage off the power line. I can't recall the details, but it had something to do with using it as a reference, since the timing for sensing voltage levels are not discrete but highly random, especially if you can pickup the noise on the line too. That seems reasonable, but requires some work.

20 Dec 2011, 04:51

hopcode

Joined: 04 Mar 2008
Posts: 563
Location: Germany

hopcode 20 Dec 2011, 06:11

Hi people,
thanks all for answering.

smiddy wrote:

...you can pickup the noise on the line too. That seems reasonable..

and cool, even if too much system dependent. other
hardware possibility ex.: network card/fan etc ?

cod3b453 wrote:

...when you say "anded" Rand = RandA AND RandB ? If so, might want to try XOR instead...

exactly
the return value, 8 byte, ANDed to 0FFFFh. i didnt test with XOR, yet because
even if i "deviated" from the theories, it has a little theory embedded in it though. and You propably know it's difficoult to have good results in this branch of programming only by observing results from "Galileian" experimentations not supported by at least a little theory.

AsmGuru62 wrote:

DIEHARD tests.

done, they are surprisingly positive . follows one of the the very few but important negative tests that doesent require an explanation, because the reason is in the design of the algo.

Code:

 Chi-square with 5^5-5^4=2500 d.of f. for sample size: 256000
                      chisquare  equiv normal  p value
  Results for COUNT-THE-1's in specified bytes:
           bits  1 to  8  2712.06      2.999      .998645
           bits  2 to  9  2525.89       .366      .642844
           bits  3 to 10  2701.12      2.844      .997774
           bits  4 to 11  4739.64     31.673     1.000000
           bits  5 to 12 18639.68    228.250     1.000000
           bits  6 to 13 87082.48   1196.177     1.000000
           bits  7 to 14506249.30   7124.091     1.000000
           bits  8 to 15*********  42758.170     1.000000
           bits  9 to 16********* 213986.600     1.000000
           bits 10 to 17********* 137730.000     1.000000
           bits 11 to 18********* 170499.900     1.000000
           bits 12 to 19*********  80776.410     1.000000
           bits 13 to 20*********  16785.790     1.000000
           bits 14 to 21224561.30   3140.421     1.000000
           bits 15 to 22 51165.06    688.228     1.000000
           bits 16 to 23 11874.50    132.575     1.000000
           bits 17 to 24  2598.76      1.397      .918749
           bits 18 to 25  2745.13      3.467      .999736
           bits 19 to 26  2876.84      5.329     1.000000
           bits 20 to 27  4787.94     32.356     1.000000
           bits 21 to 28 19647.96    242.509     1.000000
           bits 22 to 29 92230.13   1268.976     1.000000
           bits 23 to 30540332.70   7606.103     1.000000
           bits 24 to 31*********  43608.360     1.000000
           bits 25 to 32********* 218090.700     1.000000

btw. nobody thought to rewrite that test-suite in assembly ? (i wwould suggest cutting some overbloating and speeding the whole suite)
but it is worth a new project imho, because almost 1 coders to 1 need it.

revolution wrote:

...Some of my favourites are the Titanic Twister and the Mersenne Twister series. Both of these types would be faster than the example above...

faster... i doubt it would be. good yes, because very simple. note that it initializes a 624 sushi-words vector. when using the algo seldom implies a cache page reload. using it extensively need obviously an optimizazion.

Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑

20 Dec 2011, 06:11

hopcode

Joined: 04 Mar 2008
Posts: 563
Location: Germany

hopcode 20 Dec 2011, 06:20

btw, by surprisingly positive i meant good and encouraging
results.

_________________
⠓⠕⠏⠉⠕⠙⠑

20 Dec 2011, 06:20

hopcode

Joined: 04 Mar 2008
Posts: 563
Location: Germany

hopcode 20 Dec 2011, 14:13

hi,
some little improvement for a 4 byte-ANDed-result algo

Code:

.randomB:
   rdtsc
       rol dx,4
    rol ax,3
    mov rcx,866AA7'3F0B'7F'0B'03h
   movd mm0,eax
        movq mm1,rcx
        pshufw mm0,mm0,01'00'01'00b
      pmaddwd mm1,mm0
     pshufb mm1,mm0
      movq rax,mm0
        movq rcx,mm1
        mul rdx
     ret 0

with following unstable results yet on the x2.
they are yet around 30% and 70%
Entropy = 7.999309 bits per byte.
Optimum compression would reduce the size
of this 262144 byte file by 0 percent.

Chi square distribution for 262144 samples is 250.54, and randomly
would exceed this value 56.72 percent of the times.

Arithmetic mean value of data bytes is 127.7175 (127.5 = random).
Monte Carlo value for Pi is 3.140306706 (error 0.04 percent).
Serial correlation coefficient is -0.000857 (totally uncorrelated = 0.0).

cut away the pmullw, because too much aggressive
the pshufb is aggressive too, but i dont know how to resolve it at the moment.

i know it's quite mpossible to have a good rng without using a seed+state.
but that is the challenge, or ?

Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑

20 Dec 2011, 14:13

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 20 Dec 2011, 14:25

hopcode wrote:

i know it's quite mpossible to have a good rng without using a seed+state.

You don't ever need any state if you are seeding upon every call. You are using RDTSC as your seed on every call.

20 Dec 2011, 14:25

hopcode

Joined: 04 Mar 2008
Posts: 563
Location: Germany

hopcode 20 Dec 2011, 14:35

revolution wrote:

hopcode wrote:
i know it's quite mpossible to have a good rng without using a seed+state.
You don't ever need any state if you are seeding upon every call. You are using RDTSC as your seed on every call.

no, i mean working on the seed+state. because when generating number serially you could percieve the seed re-appearing when not being elaborated. in this case being the seed the timestamp.

_________________
⠓⠕⠏⠉⠕⠙⠑

20 Dec 2011, 14:35

hopcode

Joined: 04 Mar 2008
Posts: 563
Location: Germany

hopcode 20 Dec 2011, 14:52

but i am not satisfied yet with the algo, because i want a 2-byte-ANDed
result. the pmaddwd plays its role ok, and i like it.
i was thinking about creating a 2-stage-non-serialized-RDTSC for a delta-T,
then jmp to label accordingly, where the a fixed k will be loaded to be integrated in some way in the final result.

_________________
⠓⠕⠏⠉⠕⠙⠑

20 Dec 2011, 14:52

AsmGuru62

Joined: 28 Jan 2004
Posts: 1619
Location: Toronto, Canada

AsmGuru62 20 Dec 2011, 15:15

@revolution:
I tried MOD - it's very bad.
I tried it on the STAR TREK game I ported - the maps were really bad looking - not random at all! When I used FPU - all looked awesomely random.

Say, you want a number 5 out of 10.
In the range of 0-FFFFFFFF there will be a lot of instances of 5 with using MOD and there must be only one instance of 5.

20 Dec 2011, 15:15

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 20 Dec 2011, 15:24

AsmGuru62 wrote:

@revolution:
I tried MOD - it's very bad.
I tried it on the STAR TREK game I ported - the maps were really bad looking - not random at all! When I used FPU - all looked awesomely random.

Say, you want a number 5 out of 10.
In the range of 0-FFFFFFFF there will be a lot of instances of 5 with using MOD and there must be only one instance of 5.

What PRNG are you using?

20 Dec 2011, 15:24

AsmGuru62

Joined: 28 Jan 2004
Posts: 1619
Location: Toronto, Canada

AsmGuru62 20 Dec 2011, 17:06

Mersenne.

20 Dec 2011, 17:06

mindcooler

Joined: 01 Dec 2009
Posts: 423
Location: Västerås, Sweden

mindcooler 20 Dec 2011, 17:09

What is a good simple floating-point RNG? Can you get one with normal distribution?

20 Dec 2011, 17:09

AsmGuru62

Joined: 28 Jan 2004
Posts: 1619
Location: Toronto, Canada

AsmGuru62 20 Dec 2011, 21:37

Here is a simple MT -- just coded it today.
Did not test it, however tested this:

1. Generate 32-bit value
2. ECX = -1
3. Loop until same number is received

ECX is ended, but I did not receive that number.
Cool!

Also, this code can do float point numbers, but probably not normal distribution.

Description:		Download
Filename:	MT19937.Asm
Filesize:	5.63 KB
Downloaded:	907 Time(s)

20 Dec 2011, 21:37

hopcode

Joined: 04 Mar 2008
Posts: 563
Location: Germany

hopcode 21 Dec 2011, 04:00

AsmGuru62 wrote:

Also, this code can do float point numbers, but probably not normal distribution.

what do you mean by "normal distribution" ?
i presume normal distribution of returned values in the range.

in this case, the x2 (chi square) from ENT is not meaningful, because you can
find for example the number 5 now and later 160. they have both a bad x2, but a good unique distribution. in my last snippet i posted, x2 is around 50% but if you see the value filled in a graph, you will find the distribution not so good as in my first snippet.

Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑

21 Dec 2011, 04:00

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 21 Dec 2011, 05:14

AsmGuru62 wrote:

Mersenne.

My tests here don't show any problem. But no matter, if you still need to eliminate the bias then you can change the last step:

1. Get rand
2. If rand > 4,294,967,289 goto step 1
3. value = truncate (rand / 429,496,729)

hopcode wrote:

what do you mean by "normal distribution" ?
i presume normal distribution of returned values in the range.

Usually when we need to generate a different distribution, like Normal, Poisson, Binomial etc., is it easiest to generate the Uniform distribution (like all the generators here) and do post processing to alter the output to suit the desired target distribution.

21 Dec 2011, 05:14

Goto page 1, 2, 3 Next

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum