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

Joined: 20 Feb 2006
Posts: 4325
Location: Now
edfed 16 Nov 2007, 12:48
good in term of that

 Description: this file comme from www.256b.com it's not a code of mine i'm not a good coder enough to code that ;-)- Download Filename: hell.zip Filesize: 1.84 KB Downloaded: 710 Time(s)

Last edited by edfed on 17 Nov 2007, 12:49; edited 1 time in total
16 Nov 2007, 12:48
bitRAKE

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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
LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 16 Nov 2007, 23:31
I'm not really convinced but I am less skeptic now Thanks for the link

PS: I think that I did a maths exercise to proof by induction the claim that a number can only be prime or a product of primes, but never realized that this is the basis for understanding why primes are better for random functions (and applicable to hashing I suppose where I was even more skeptic). Disadvantages of being genetically hard coded to never understand maths as a normal human do
16 Nov 2007, 23:31
edfed

Joined: 20 Feb 2006
Posts: 4325
Location: Now
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

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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

Joined: 06 May 2005
Posts: 4624
Location: Argentina
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

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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    ```
We know once we get the same value the routine begins with it will just repeat. ECX is used to count each itteration until AX is again 123. "imul ax,byte 127" will demonstrate the greater period - that is the largest unsigned byte prime. The ROL instruction will sometimes change the sign of AX. This is important because IMUL is signed instruction.
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.
Let us look at multiply differently: when we multiply the numbers just get spread out - nothing special - just moves them further apart. For example, {1,2,3,4,5} multiplied by three becomes {3,6,9,12,15}. The relationship between the numbers is the same, but they are further apart.

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

Joined: 20 Feb 2006
Posts: 4325
Location: Now
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

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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

Joined: 06 May 2005
Posts: 4624
Location: Argentina
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

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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
One of my problems is that I will brute force a solution without a second thought. It slows my learning, but I feel that I understand a problem more thoroughly - although this might be an illusion to maintain my lazy approach.

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    ```
Here are some other values that work equally well:4001876867, 4009357153, 4010304653, 4011032239, 4030079069, 4071389801, 4088285039, 4107079841, 4108880141, 4136016263, 4163058421, 4164590659, 4188914677, 4196532023, 4247828653, 4265277593

...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

Joined: 06 May 2005
Posts: 4624
Location: Argentina
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

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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

Joined: 20 Feb 2006
Posts: 4325
Location: Now
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

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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

Joined: 20 Feb 2006
Posts: 4325
Location: Now
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

Joined: 21 Jul 2003
Posts: 3947
Location: vpcmipstrm
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

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania
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    ```
Of course this is only an example, you need not necessarily make this a function (you can 'inline' it).

doesn't need multiplications
28 Dec 2007, 17:11
edfed

Joined: 20 Feb 2006
Posts: 4325
Location: Now
edfed 28 Dec 2007, 17:15
to slow...
28 Dec 2007, 17:15
Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania
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
 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, 3, 4  Next

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