flat assembler
Message board for the users of flat assembler.
Index
> Projects and Ideas > RANDOM Goto page Previous 1, 2, 3, 4 Next 
Author 

edfed
good in term of that
Last edited by edfed on 17 Nov 2007, 12:49; edited 1 time in total 

16 Nov 2007, 12:48 

bitRAKE
Using a prime number increases the dimensionality of the result. We know from fundamental theorem of arithmetic that composite numbers break down into primes. This has the effect of dividing the algorithmic number space used for psuedorandom numbers. If we are opperating on nbit numbers it is best to use an nbit prime. Otherwise it is like we are using two or more smaller algorithms and combining them.
That random number generator has a period of 16095. If we multiply by 127 then the period increases to 52241, but we would have to look at the distribution of numbers  maybe this sequence is not so good for this program? 

16 Nov 2007, 20:38 

edfed
random is a strange thing
to really understand an feel the random power, i will hibernate like an hermite coding and coding all the ideas i have, it's spring, nothing to do, no girl to love, lets go for my coding party of the spring!!! thema : make an os really fast and define tha constraints while fingers can move and eyes can see, i'll code 

17 Nov 2007, 00:11 

bitRAKE
We don't even need math to understand, but we do need to understand equality. Prime numbers do not allow equality  we can call them evil, selfish numbers.
For example, if you have six pieces of candy: you can share with either one friend or two friends  six is a good number  flexible, friendly number. But if you have seven pieces of candy: you cannot share equally unless you find six friends. To save candy until six other people present themselves is just evil. As you can imagine equality is not random  they are like opposites. Therefore, primes provide the least equal environment, and beer/soda is distributed in six packs. 

17 Nov 2007, 02:21 

LocoDelAssembly
I understand that bitRAKE
The part I'm not fully convinced of is how this relates to the fact that multiplying by a prime number is better than just an odd number. Seems that I had to pay more attention when I was at high school and of course elementary school as well BTW, how do you calculate the period? 

17 Nov 2007, 04:11 

bitRAKE
Code: xor ecx,ecx mov eax,123 .0: imul ax,byte 123 rol ax,byte 5 inc ecx cmp ax,123 jne .0 Quote: The part I'm not fully convinced of is how this relates to the fact that multiplying by a prime number is better than just an odd number. Don't think about the numbers  imagine the surface of a balloon with points on the surface. When we blow up the ballon the dots get further apart, but the orientation doesn't change  the dots are still in the same position. The second part to the puzzle is the fact we have a limited number of bits. We can expand the numbers (multiplication), but the space is limited. So, it folds over. Imagine a rubber band  stretch and fold, stretch and fold, ... Now the question becomes: Given a constant fold distance, what is the best constant amount to stretch? Let us look at some examples: A) What if we stretch and fold by the same amount? Say 8bit numbers, stretch by 2^8? 1*256/256 = 1, 2*256/256 = 2, ... doesn't change anything! Not at all random! B) Let us try some small odd number? 6bit numbers, stretch by 9? 0,9,18,27,36,45,54,63, 8,17,26,35,44,53,62, 7,16,25,34,43,52,61, 6,15,24,33,42,51,60, 5,14,23,32,41,50,59, 4,13,22,31,40,49,58, 3,12,21,30,39,48,57, 2,11,20,29,38,47,56, 1,10,19,28,37,46,55 these are the numbers 063, multiplied by 9 and wrapped around (folded) at 64. Notice how there are 9 groups? We can see many other patterns in these groups. Not very random. C) What would you say happens when we multiply by a prime and wrap around? How many groups are there? What patterns are readily apparent? We only have a limited range of numbers to work with and we want to remove as many patterns as possible  with a small number of operations. The ROL instruction kind of twists the result. Stretch, fold, twist, ... 

17 Nov 2007, 06:07 

edfed
with this algorythm, the zero value never appears.
probability to have the 0 value is 0 but a good radom have all numbers with same proba. so in fact it's not a good random generator sorry! 

17 Nov 2007, 12:47 

bitRAKE
It takes much work to insure a specific distribution of numbers. Additionally, it is arguable if randomness should have a specific distribution. Randomness includes millions of zeros in a row  it just isn't that probable. Thank goodness it just generates psuedorandom numbers.
We can use the zero value for something special because we know the random stream will not include it  obviously, there are other values excluded. Here is some code to generate a list of excluded numbers: Code: buffer rb 10000h / 8 ; clear buffer mov ecx,10000h / 32 xor eax,eax lea edi,[buffer] rep stosd mov eax,123 .y: imul ax,127 rol ax,5 bts dword [buffer],eax cmp eax,123 jne .y xor eax,eax xor ecx,ecx .z: bt dword [buffer],eax jc .1 push eax inc ecx .1: inc ax jne .z ; ECX is count of DWORDs on the stack ; each DWORD is not generated by PRNG 

17 Nov 2007, 16:34 

LocoDelAssembly
B)
Code: 0 13 26 39 52 1 14 27 40 53 2 15 28 41 54 3 16 29 42 55 4 17 30 43 56 5 18 31 44 57 6 19 32 45 58 7 20 33 46 59 8 21 34 47 60 9 22 35 48 61 10 23 36 49 62 11 24 37 50 63 12 25 38 51 That is the pattern for 13, a prime number. It also follows the A[*,i+1] = A[*,i]+1 and IMO even more perceptible because it starts at 0 and ends at 12. However I see your point, there are some nonprime numbers that makes the period much shorter, for example 8: Code: 0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56 The pattern is bigger compared with 13 (more columns), but every row is an exact copy of the previous!! However, all this happens because the number is multiple of the modulus. I do see now why using a big prime number for the modulus helps!! About the period calculation, I knew that method, I thought you was calculating it with a math method that does not require run the algorithm several times Thanks for the enlightenment!! 

17 Nov 2007, 21:27 

bitRAKE
LocoDelAssembly wrote: About the period calculation, I knew that method, I thought you was calculating it with a math method that does not require run the algorithm several times C'est la vie. [If we look at the pattern generated by the ROL instruction and the IMUL then the coverage can be determined. I bet looking at some data will help find an equation which would be useful for 64bit numbers  not going to brute force that, lol. Take a look here, though: http://en.wikipedia.org/wiki/Linear_congruential_generator ] There are many suitable LCG's: Code: mov ebx,4214669749 mov eax,ebx xor ecx,ecx .z: mul ebx inc ecx test eax,eax lea eax,[eax+ebx] jne .z ...and the Mathematica code to get good primes: Code: LCGTestQ[a_, c_, m_] := GCD[c, m] == 1 && ! Xor[Mod[a  1, 4] == 0 && Mod[m, 4] == 0] && And[IntegerQ[(a  1)/First /@ FactorInteger[m]]]; s = {}; Do[ i = RandomPrime[{2^31, 2^32}]; While[ LCGTestQ[i, i, 2^32], i = RandomPrime[{2^31, 2^32}]; ]; AppendTo[s, i]; , {j, 10}] Sort[s] // TableForm 

17 Nov 2007, 22:29 

LocoDelAssembly
In the first half of this year I saw that link, yesterday I revisited it but with less success though. I'm almost sure that on the wikipedia or surfing with wikipedia as a starting point I reached a resource that showed how you can calculate the seed after knowing only a few of the sequence (and a way to calculate the period if I remember right). Stupid I was that time however, because I not bookmarked that and I can't reach such nice formulas again
Quote: ...and the Mathematica code to get good primes: Very simple, I was able to understand it all in less than a second 

17 Nov 2007, 23:28 

bitRAKE
I'd use "ROL EAX,13" after any 32bit LCG because of the leastbit problem. Getting a random bit is a very common thing for me, and LCG's just go 0,1,0,1,0,1,...


17 Nov 2007, 23:57 

edfed
little random story:
Rain falls on the ground, the drops circles and generate a based noise rocking my ears. This sound is random, and no computer required to do so The rustling of the wind in the leaves, slowly fallin in a kaotic rhythm, it is also random. And yet, causes of these phenomena are well known, physics laws explain rain, wind and sound. who can foreseeing the exact location is going to fall a rain drop? Knowing that needs all the parameters, but it is necessary to redo it for every drop random doesn't exist, all things have a reason to be, nothing without causes. random is then impossible. what is random, is only something we cannot link easy to an other... 

17 Dec 2007, 05:52 

bitRAKE
I feel the same way. There are things beyond our understanding (noncomputable). If fact I would argue that everything we do is towards reducing complexity to create understanding  even encryption is a model for communication that falls far short of the 'encryption' nature is capable of! It makes we wonder if nature tries to communicate with us?


17 Dec 2007, 20:59 

edfed
wonder if hazardous exists, like fatal accident; one man in one context giving one result.
if i was there two minutes before or after, things like that. WHAT IS RANDOM ? is it real ? does random exists in the nature ? by this, random is a function of a lot of variable. so a good random generator can be a mix of many, many physical concept, like sound propagation and reflexion with air density function of temperature, temperature function of day and geographic location... reflexion factor function of the atoms and molecules, random is a big unresolved equation... erf... in computer i think we only accept something like random when it seems to be as random as possible, but there is always an algorythm behind. and this algoryhtm can be randomized too... 

17 Dec 2007, 23:29 

bitRAKE
Random dines with truth and love. Although they order different entrĂ©s, all have the same dessert.


18 Dec 2007, 10:45 

Borsuc
xorshift
Here some asm code (by UCM in another thread): Code: ;xorshift a,b,c,d ;generate random 32bit number based on seeds a,b,c and d ;returns new seeds a,b,c,d in eax,ebx,ecx,edx respectively ;edx is usable as random result ;proc xorshift,.a,.b,.c,.d xorshift: .a equ esp+4 .b equ esp+8 .c equ esp+12 .d equ esp+16 mov eax,[esp+4] shl eax,15 xor eax,[esp+4] mov edx,[esp+16] shr edx,21 xor edx,[esp+16] mov ebx,eax shr eax,4 mov ecx,[esp+16] xor eax,ebx mov ebx,[esp+12] xor edx,eax mov eax,[esp+8] ret 16 doesn't need multiplications 

28 Dec 2007, 17:11 

edfed
7 memory reads,
to slow... 

28 Dec 2007, 17:15 

Borsuc
but it has a long period (128bits used for seed).
you can use a faster, smaller period too, just one memory read (and that is the parameter! you may not need it if you're 'inlining' the function). 

28 Dec 2007, 17:24 

Goto page Previous 1, 2, 3, 4 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.