Message board for the users of flat assembler.
> DOS > Random number generation
Goto page Previous 1, 2
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:
.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.
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 13 Dec 2010, 00:41
...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.
; 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
Last edited by bitRAKE on 13 Dec 2010, 00:50; edited 1 time in total
|13 Dec 2010, 00:41||
revolution 13 Dec 2010, 00:49
What is LHCA? Is it Linear Hybrid Cellular Automata?
|13 Dec 2010, 00:49||
bitRAKE 13 Dec 2010, 00:50
|13 Dec 2010, 00:50||
bitRAKE 13 Dec 2010, 01:01
LFSR's are very simple in terms of number of instructions required. Not very random, though.
; 64-bit maximal length LFSR test byte[rnd],00011011b setpe al shr al,1 rcr qword [rnd],1
|13 Dec 2010, 01:01||
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 14 Dec 2010, 08:06
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.
They cannot take zero as input, nor generate zero as output. Otherwise each covers the complete bit range.
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||
|Goto page Previous 1, 2
< Last Thread | Next Thread >
Copyright © 1999-2023, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.