flat assembler
Message board for the users of flat assembler.

Index > DOS > Random number generation

Goto page Previous  1, 2
Author
Thread Post new topic Reply to topic
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
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:

Image

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. Very Happy, i like the ease of asm to do very hard maths.

[edit]
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:

Image

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:
Image
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
Post 12 Dec 2010, 23:54
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
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
add rsi,rsi
adc rdi,rdi
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
Post 13 Dec 2010, 00:41
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
revolution
What is LHCA? Is it Linear Hybrid Cellular Automata?
Post 13 Dec 2010, 00:49
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
yeap
Post 13 Dec 2010, 00:50
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
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.
Post 13 Dec 2010, 01:01
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
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
Image
[edit]
in fact, the 0 value appears, it was just a bug in plotc.
Post 13 Dec 2010, 11:31
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
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)/¯ unlicense.org
Post 14 Dec 2010, 08:06
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< 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


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.