#177538 - Toxic - Mon Aug 13, 2012 1:42 pm
Hi, I know this isn't the newbies section, but I haven't got an easy question. I'm new here and I've coded this GBA ROM image http://www.mediafire.com/download.php?q9fwafnqv1wf140
It's a graphical representation of a pseudorandom generator I invented. I was tinkering with xor and additions and came up with this code. I used mode 4 and page flipping with pointers to the vram to display the output.
b=b<<2;
b=((b+e)^((b+e)^((b+e)-((b+e)>>2))));
e+=b+1;
e and b are 32 bit unsigned integers.
b is the pseudo random number output.
It has 2 advantages.
*extremely fast
*rather random
If anyone could steer me in the right direction to working out this functions period, I'd be grateful. If you have an idea of how it actually works that'd be awesome!
Something I think it might do is that 'e' will exceed 2^32, but I haven't seen any glitches yet. What happens when you add a number to make the variable greater than 2^32 on the gamebayadvance?
Anyone is welcome to use this random generator in their game. But I'm interested in what you think about it.
#177539 - sverx - Mon Aug 13, 2012 2:01 pm
| Toxic wrote: |
| What happens when you add a number to make the variable greater than 2^32 on the gamebayadvance? |
Overflow, you'll loose the 33th bit (so, if unsigned, this will become 'truncated' to modulus 2^32)
_________________
libXM7|NDS programming tutorial (Italiano)|Waimanu DS / GBA|A DS Homebrewer's Diary
#177540 - Dwedit - Mon Aug 13, 2012 5:35 pm
I think the "standard" rand function is also pretty fast:
a *= 0x343FD;
a += 0x269EC3;
return (a >> 16) & 0x7FFF;
I'm just not sure if the "standard" rand function is any good.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#177541 - Toxic - Mon Aug 13, 2012 11:37 pm
Thanks for the info about overflow and the alternative... which I tested. lol
The alternative cannot possibly have a period greater than 0x7FFF because that's the value you are truncating, and the equation returns the same value for the same input number.
Dwedit shared this
| Quote: |
a *= 0x343FD;
a += 0x269EC3;
return (a >> 16) & 0x7FFF;
|
Here's what the one you specified looks like - ttp://www.mediafire.com/download.php?gpuxh5wah5q725h
It has a very short period, and I wouldn't use that for any seriously random content.
With my xor prg the value e is truncated at 2^32 and b+e is also trunctated at 2^32 which I think explains why it doesn't stop.
If you want to change its seed, you can change the starting value of b, or the starting value of e.
#177542 - Dwedit - Tue Aug 14, 2012 12:07 am
I think you might not have implemented that correctly. 'A' is the seed, it's the state of the random number generator. It's not necessarily the same as the returned variable. I don't see the value of 'a' (in register r4) getting stored anywhere after the constant is added, I just see it getting clobbered by the shift/truncate operation.
I don't think anything that you'd find in the standard library of many compilers would be THAT horrible.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#177543 - Toxic - Tue Aug 14, 2012 6:12 am
If there is a reason the period is so short, it might be the output to color code which takes the randomly generated number and uses i=x%256, then selects a color from the palette where:
while(i<256)
{
mypalette[i]=RGB15(i/8,i/8,i/8);
i++;
}
so every 8 values of the pallete are the same shade.
I'll fix it so that i=(x*256)/0x7FFF and that will display the entire randge of random numbers that the LCG generates. However, I don't expect it to be more random than my own generator which seems to randomise the lowest 8 bits very well.
Ok done. I would show it if it wasn't so similar only slower.. hmm. I'll show it if you ask to see it.
I used a seed of zero (started with a=0) but it doesn't make a big difference what I choose. Let me explain why:
Let's say the algorithm you gave me is a function where x is the input and y is the output, then for any given x you only have one possible output. We call this output y. Since we truncate at 0x7FFF there is no output value that can be higher. Likewise, if we procedurally re-compute 'a' then we get the same sequence of numbers. If we use a seed, and the pattern of numbers that result from that seed overlap a pattern of numbers from a different seed, the two patterns combine. That is to say, if a number exists in a pool of possible values as a result of a seed, then those numbers belong to that seed, and if the output y becomes a part of a pool, it will join that pool.
The >>16 is essentially "divide by 65536", and the &0x7FFF is essentially "%(2 pow 15)"
This is a variation of a Linear congruential generator. - http://en.wikipedia.org/wiki/Linear_congruential_generator
you essentially say the GBA standard library uses:
x=(b(ax+c))%m
where a=(1/16), b=214013, c=2531011 and m=65536
and you re-calculate the same equation over and over to get new(ish) numbers.
Wikipedia
| Quote: |
| The period of a general LCG is at most m, and for some choices of 'a' much less than that. |
If you read the page, it says that numerous offical windows compilers use the same equation but with different numbers.
Borland C/C++
x= (22695477*x+1)%(2pow32)
the seed is the starting value of x.
The standard library code is a mediator for us programmers. They must have whipped up a quick Pseudo random generator. They obviously thought about it because they used the AND operation instead of the modulus. They should have stuck with borlands method. It looks much nicer. Here is what borlands method looks like:
- http://www.mediafire.com/download.php?44ddi6u1wkxtu1l
it's very good.
i used the equation:
x=(22695477*x+1)&(0xFFFFFFFF) // which is nice and fast due to no modulus.
to scale the value down into 256 bits, i had to do some tricky math.
i=((x>>16)*256)>>16;
I think you'll find that borlands method has a period of 2pow32 which is alot of random.
I will make sure I don't use the standard library random function!
#177544 - Toxic - Tue Aug 14, 2012 6:33 am
I actually found a probelm with my own random generator. the values tend to be full of 1s. Where as borland is more 50% on/off. I think I'll use borlands. It's also even faster so it seems. :p
#177545 - Dwedit - Tue Aug 14, 2012 8:40 am
You had misinterpreted my first post. m is not 2^16, it's 2^32.
The code again:
seed *= a
seed += c
return (seed >> 16) & 0x7FFF
does not modify 'seed' anywhere in the third line, but the code you were using in your test program treated it as if it were doing 'seed = (seed >> 16) & 0x7FFF'.
The Wikipedia page you linked to (really cool stuff, I never knew these kind of formulas had names) says that:
| Quote: |
LCG will have a full period for all seed values if and only if:
* c and m are relatively prime (meaning GCD = 1)
* a - 1 is divisible by all prime factors of m,
* a - 1 is a multiple of 4 if m is a multiple of 4.
|
The formula I threw out was something I found in some lame decryption code, and turns out to be Visual C++'s RNG. It's listed on that page.
m = 2^32
a = 214013
c = 2531011
And these three numbers satisfy the conditions above to have a full 32 bit period.
Anyway, devkitarm (newlib) doesn't use Visual C++'s method in its standard library, it uses something else. Newlib uses "x = x * 0x5851F42D4C957F2D + 1", then returns the high 32 bits of the seed.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
Last edited by Dwedit on Tue Aug 14, 2012 9:42 am; edited 2 times in total
#177546 - Toxic - Tue Aug 14, 2012 9:36 am
awesome, thanks for clearing that up! :D
#177547 - sverx - Tue Aug 14, 2012 9:47 am
very interesting stuff :) Good to know Newlib has a proper generator :)
_________________
libXM7|NDS programming tutorial (Italiano)|Waimanu DS / GBA|A DS Homebrewer's Diary