flat assembler
Message board for the users of flat assembler.

Index > Projects and Ideas > RANDOM

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



Joined: 20 Feb 2006
Posts: 4225
Location: 2018
edfed
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: 275 Time(s)



Last edited by edfed on 17 Nov 2007, 12:49; edited 1 time in total
Post 16 Nov 2007, 12:48
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
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 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?
Post 16 Nov 2007, 20:38
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
I'm not really convinced but I am less skeptic now Smile 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 Laughing
Post 16 Nov 2007, 23:31
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4225
Location: 2018
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
Post 17 Nov 2007, 00:11
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
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. Laughing

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. Very Happy
Post 17 Nov 2007, 02:21
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
I understand that bitRAKE Smile

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 Razz

BTW, how do you calculate the period?
Post 17 Nov 2007, 04:11
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
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, ...
Post 17 Nov 2007, 06:07
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4225
Location: 2018
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!
Post 17 Nov 2007, 12:47
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
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 psuedo-random numbers. Very Happy

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    
Post 17 Nov 2007, 16:34
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
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 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!! Very Happy

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 Razz

Thanks for the enlightenment!!
Post 17 Nov 2007, 21:27
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
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 Razz
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. Confused

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

Very Happy

...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    
Laughing
Post 17 Nov 2007, 22:29
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


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

Quote:
...and the Mathematica code to get good primes:


Very simple, I was able to understand it all in less than a second Rolling Eyes
Post 17 Nov 2007, 23:28
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
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,...
Post 17 Nov 2007, 23:57
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4225
Location: 2018
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...
Post 17 Dec 2007, 05:52
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
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?
Post 17 Dec 2007, 20:59
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4225
Location: 2018
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...
Post 17 Dec 2007, 23:29
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
Random dines with truth and love. Although they order different entrés, all have the same dessert. Laughing
Post 18 Dec 2007, 10:45
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
Borsuc
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 Smile
Post 28 Dec 2007, 17:11
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4225
Location: 2018
edfed
7 memory reads,
to slow...
Post 28 Dec 2007, 17:15
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
Borsuc
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).
Post 28 Dec 2007, 17:24
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3, 4  Next

< 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-2019, Tomasz Grysztar.

Powered by rwasa.