flat assembler
Message board for the users of flat assembler.

 Index > DOS > Random number generation Goto page Previous  1, 2
Author
edfed

Joined: 20 Feb 2006
Posts: 4324
Location: Now
edfed 12 Dec 2010, 23:54
i just coded something to see the probabilities in real time about random numbers.

it uses a 256 bytes history to show the rate of each value.

then, it can be used to see if a generator is more or less random, and guess what, i saw that my randoim generator is not really random.
the curve is always the same at the end. it gives that:

the code of the probabilities monitor:
Code:
```.scope: dd f.plotc,0,0,256,64,Red,.history,0,0,1,4

.history:
times 256 db %-1
.occurences:
dd 0
.value:
rd 256
.probabilities:
Asm @f
@@:
push eax ebx ecx edx
mov ebx,[.occurences]
shl ebx,2
je .div0
mov ecx,256
@@:
mov eax,[.value+ecx*4-4]
mov edx,eax
shr edx,18
shl eax,14
idiv ebx
mov [.history+ecx*1-1],al
loop @b
.div0:
pop edx ecx ebx eax
ret
```

don't care about f.plotc and other fool design, it is just intended to display the content of a table in a scope like you can sse with the red curve in the blue frame.

now, the goal is to have a random curve. then, i will do a second random analysis on the first monitor. then, it will show me what values are really more frequent.

like a second order derivation. , i like the ease of asm to do very hard maths.

Aha!
after a little modification, it appears that my generator is a little random on low byte only.

in fact, i used the 4 bytes of a unique Dword number, and it gave me the curve above.
but now, if i use the low byte of 4 different random numbers, it gives the curve below:

i will run it this night and see if the curve is a straith line or not.
if yes, the géné have great chances to be a good random algo.

i do that way because it is funnier than a fast test on millions nubers generated in one second, it does like a fun screen saver.

it gives that on large tests:

always the same pattern, no matter the seed, no matter when the history reset occurs.

Last edited by edfed on 13 Dec 2010, 00:42; edited 1 time in total
12 Dec 2010, 23:54
bitRAKE

Joined: 21 Jul 2003
Posts: 3884
Location: vpcmipstrm
bitRAKE 13 Dec 2010, 00:41
Code:
```; 32-bit maximal length LHCA
mov edx,4001h ; bits 0,14
lea ecx,[eax+eax]
and edx,eax
shr eax,1
xor eax,ecx
xor eax,edx

; 64-bit maximal length LHCA
mov edx,10100b ; bits 2,4
lea rcx,[rax+rax]
and edx,eax
shr rax,1
xor rax,rcx
xor rax,rdx

; 128-bit maximal length LHCA
mov ebx,\$10000001 ; bits 0,28
mov rsi,rax
mov rdi,rdx
and ebx,eax
shr rdx,1
rcr rax,1
xor rax,rsi
xor rdx,rdi
xor rax,rbx    ```
...just some alternatives to LFSR or LCG type algorithms. They cannot take zero as input, nor generate zero as output. Otherwise each covers the complete bit range.

Last edited by bitRAKE on 13 Dec 2010, 00:50; edited 1 time in total
13 Dec 2010, 00:41
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 19869
revolution 13 Dec 2010, 00:49
What is LHCA? Is it Linear Hybrid Cellular Automata?
13 Dec 2010, 00:49
bitRAKE

Joined: 21 Jul 2003
Posts: 3884
Location: vpcmipstrm
bitRAKE 13 Dec 2010, 00:50
yeap
13 Dec 2010, 00:50
bitRAKE

Joined: 21 Jul 2003
Posts: 3884
Location: vpcmipstrm
bitRAKE 13 Dec 2010, 01:01
Code:
```; 64-bit maximal length LFSR
test byte[rnd],00011011b
setpe al
shr al,1
rcr qword [rnd],1    ```
LFSR's are very simple in terms of number of instructions required. Not very random, though.
13 Dec 2010, 01:01
edfed

Joined: 20 Feb 2006
Posts: 4324
Location: Now
edfed 13 Dec 2010, 11:31
effectivelly, the curve given by the monitor shows that 0 never appears, and that it is more like INC or DEC instruction, but at least, the distribution is straight

in fact, the 0 value appears, it was just a bug in plotc.
13 Dec 2010, 11:31
bitRAKE

Joined: 21 Jul 2003
Posts: 3884
Location: vpcmipstrm
bitRAKE 14 Dec 2010, 08:06
bitRAKE wrote:
They cannot take zero as input, nor generate zero as output. Otherwise each covers the complete bit range.
I should have said that a zero input (seed) to a Linear Hybrid Cellular Automata (LHCA) will produce a zero output. LHCA's can be constructed for any desired bit width, and usually has a higher period than other generators with the same state space. SFMT, period 2^216091-1, state bytes 33,232. With the same state space a LHCA would have a period of 2^265856-1.

MWC1038, period 2^33242-1, state bytes 4,152.
CMWC4096, period 2^131086-1, state bytes 16,384.

The great thing about SFMT is the test harness - there are so many bad implementations of random number generators on the web. It is easy to produce erroneous code without knowing the mathematics behind their creation (the position I'm usually in).

On the contrary LHCA's are incredibly simple to understand. [A][B][C]

* MWC1038, CMWC4096, and SFMT referenced above are PRNG suggestions of George Marsaglia

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup
14 Dec 2010, 08:06
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2

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