Index
> Projects and Ideas > RANDOMGoto page Previous 1, 2, 3, 4 Next |
| Author |
|
|
edfed 16 Nov 2007, 12:48
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 16 Nov 2007, 20:38
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 psuedo-random numbers. If we are opperating on n-bit numbers it is best to use an n-bit 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 17 Nov 2007, 00:11
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 17 Nov 2007, 02:21
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 17 Nov 2007, 04:11
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 17 Nov 2007, 06:07
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 8-bit 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? 6-bit 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 0-63, 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 17 Nov 2007, 12:47
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 17 Nov 2007, 16:34
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 psuedo-random 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 17 Nov 2007, 21:27
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 non-prime 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 17 Nov 2007, 22:29
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 64-bit 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 17 Nov 2007, 23:28
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 17 Nov 2007, 23:57
I'd use "ROL EAX,13" after any 32-bit LCG because of the least-bit 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 17 Dec 2007, 05:52
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 17 Dec 2007, 20:59
I feel the same way. There are things beyond our understanding (non-computable). 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 17 Dec 2007, 23:29
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 18 Dec 2007, 10:45
Random dines with truth and love. Although they order different entrés, all have the same dessert.
|
|||
|
18 Dec 2007, 10:45 |
|
|
Borsuc 28 Dec 2007, 17:11
xorshift
Here some asm code (by UCM in another thread): Code: ;xorshift a,b,c,d ;generate random 32-bit 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 28 Dec 2007, 17:15
7 memory reads,
to slow... |
|||
|
28 Dec 2007, 17:15 |
|
|
Borsuc 28 Dec 2007, 17:24
but it has a long period (128-bits 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:
|