#154250 - Programix - Sun Apr 13, 2008 4:45 pm
Hi!
I'm using palib and very much of random numbers but palib's random number generator is too slow for me, and I also tried to uLib's rand function but it's too slow too :(. Have you any ideas for a very fast rand number generator?
Thanks in advance :)
PS : Sorry for my english if it's bad
_________________
My blog
#154253 - bean_xp - Sun Apr 13, 2008 5:50 pm
You should check out the Mersenne Twister algorithm. That should probably be suitable for what you need.
#154254 - melw - Sun Apr 13, 2008 6:02 pm
Super mega fast? If you don't mind spending some memory and pseudo-random is enough, how about something simple like:
| Code: |
#define NUM_RAND 4096 // change to fit your needs
u16 randArray[NUM_RAND];
u16 randPtr=0;
void precalcRand(int seed)
{
srand(seed);
for(int i=0;i<NUM_RAND;i++)
{
randArray[i] = rand()&65535;
}
}
u16 ownRand()
{
return randArray[(++randPtr)%NUM_RAND];
} |
Something like reading microphone values might be a clever native way of reading random values on DS.
#154258 - PlagueSpark - Sun Apr 13, 2008 7:16 pm
| melw wrote: |
Super mega fast? If you don't mind spending some memory and pseudo-random is enough, how about something simple like:
| Code: | #define NUM_RAND 4096 // change to fit your needs
u16 randArray[NUM_RAND];
u16 randPtr=0;
void precalcRand(int seed)
{
srand(seed);
for(int i=0;i<NUM_RAND;i++)
{
randArray[i] = rand()&65535;
}
}
u16 ownRand()
{
return randArray[(++randPtr)%NUM_RAND];
} |
Something like reading microphone values might be a clever native way of reading random values on DS. |
It is better to have pregenerated array by desorting one after randArray[i]=i;
and % function is very slow too. If NUM_RAND is ^2 then it can be exchanged with &
The 1024 pregenerated random numbers is enogh to the map generation ;)
Microphone does not gives enogh value, the motion sensor could be more valid
#154266 - kusma - Sun Apr 13, 2008 9:57 pm
| PlagueSpark wrote: |
and % function is very slow too. If NUM_RAND is ^2 then it can be exchanged with &
|
Luckily, your compiler already does this when you have optimizations turned on, so there's no point in doing it in the source code.
#154273 - PlagueSpark - Sun Apr 13, 2008 11:37 pm
| kusma wrote: |
Luckily, your compiler already does this when you have optimizations turned on, so there's no point in doing it in the source code. |
If compiler is so wise? Why then he cannot cook homebrew all by himself?
Anyway, I prefer code to be optimized before ever compiling :) good habit I believe
#154321 - Miked0801 - Mon Apr 14, 2008 7:11 pm
No, not really a good habit. Premature optimization is the root of all evil. I'm not calling for code pessimisation, but your code should show what you are doing. If you are modding a value, use mod. If you are 'and'ing a value, use and. If you are dividing, use divide - shifting use shift. Even the lameass compilers we use can figure out these simple optimizations. And if you make your code cleaner to read, then you've saved yourself, and everyone else who reads your code, some time as well.
And every now and then, your compiler will surprise you and optimize something in a way you didn't think of.
One last thing - the 80/20 rule. 80% of a program's time is in 20% of the code. Actually, it's closer to the 99.9%, 0.1% rule with most code. If you hand optimize something that isn't taking up more than 1% of the CPU, you are wasting your time.
#154326 - elhobbs - Mon Apr 14, 2008 9:23 pm
| Miked0801 wrote: |
| Premature optimization is the root of all evil. |
Am I the only one who is sick of hearing this phrase repeated incessantly? Isn't the topic for a "super mega fast random number generator"? As such wouldn't it be appropriate for people to make suggestions on how to make something faster? It would also be appropriate to say that the compiler may already apply that optimization itself. However it is a suggested method that could be tested to see if it results in better performance.
In any case it sounds like Programix has already determined that the existing random number generator that is being used is too slow. Hence the need to optimize it.
#154328 - tepples - Mon Apr 14, 2008 9:50 pm
| elhobbs wrote: |
| Am I the only one who is sick of hearing this phrase repeated incessantly? |
No, but some people could be more forthcoming that they have profiler results in hand.
When I was coding TOD, my profiler told me that the fuzz-out effect, which adds a random offset to each scanline that changes every frame, was taking much more CPU time than I was expecting. I narrowed it down to rand() being slow. So I changed it to just use a pre-shuffled const array of 256 8-bit numbers, using rand() only to find the initial index into the array. I chose the well-known Sbox 256 because there wasn't an Xbox 360.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#154332 - Miked0801 - Mon Apr 14, 2008 10:29 pm
Listen. When coding, I get the most personal satisfaction by making a piece of code go as fast as possible. I love optimizing code. I adore assembler. I love tinkering with compression algorithms and scanline goofiness in order to shave every last 1/2 cycle out of a pice of code. I personally understand the desire to hand-tuning everything I write to be lightning quick.
But, as I've matured in my profession, I've also learned that hand-tuning said codes without profile or results is a waste of valuable time. Even worse, said codes then become much more difficult for others to read and comprehend, leading to unintended side effects/errors that only I can easily fix as I was the original code author.
My comment was directed towards PlagueSpark's comment about the habit of optimizing code before compiling. Perhaps he was refering to using the correct algorithm before coding, but I read it as hand optimizing as you go - which very often is counter productive.
I have no shame in bringing out the phrase as often as needed. Many newer developers need to hear and really comprehend its meaning. Code readability should trump code efficiency 99% of the time - and in that 1% where speed really is needed, you had better comment the hell out of your code because you personally will be supporting it for years.
#154351 - kusma - Tue Apr 15, 2008 2:16 am
| PlagueSpark wrote: |
| If compiler is so wise? |
If you're not aware of this basic fact, are you really the right person to give anyone optimization-tips? Yeah, I did get your point, but it's not a good point. Let's allow computers help us with what they are good at; spotting patterns.
| Quote: |
Anyway, I prefer code to be optimized before ever compiling :) good habit I believe |
I think we live in different worlds, man. I make a living of making code run fast - I'm glad to take every short-cut I can to improve productivity. And even above that, I enjoy keeping the meaning of the code intact whenever possible. To most programmers, modulo means something different and is simpler to decipher than bitwise and.
#154352 - kusma - Tue Apr 15, 2008 2:21 am
| Miked0801 wrote: |
| But, as I've matured in my profession, I've also learned that hand-tuning said codes without profile or results is a waste of valuable time. Even worse, said codes then become much more difficult for others to read and comprehend, leading to unintended side effects/errors that only I can easily fix as I was the original code author. |
Amen. Hands down, amen.
#154386 - elhobbs - Tue Apr 15, 2008 3:41 pm
I just find it annoying that people feel the need to quote Knuth/Hoare every time that they see the word optimize. Most of the people who pull this expression out are just saying it to sound smart - I am not saying this is the case here - this is just the millionth time I have seen this expression and I could no longer control myself. I apoligize, as this was an appropriate response to someone saying that they perform these type of optimizations as they write all of their code.
#154444 - Darkflame - Wed Apr 16, 2008 12:51 pm
I'm probably below the skill level of most here, but it seems to me both are necessary.
For 99% of use, trusting the compiler lets you concentrate on higher-scale optimisations which you might miss when micro-managing.
However, we also need people aware of how to optimise manually, else who will make the compilers better? If some coders want to understand a bit more behind the scenes, they might one day help improve what is done automatically for the rest of us.
_________________
Darkflames Reviews --
Make your own at;
Rateoholic:Reviews for anything, by anyone.
#154446 - Sunray - Wed Apr 16, 2008 1:31 pm
Premature optimizations may be evil. But using div on a platform without hardware support and relying on the compiler to optimize it is just stupidity.
#154447 - kusma - Wed Apr 16, 2008 2:09 pm
| Sunray wrote: |
| But using div on a platform without hardware support and relying on the compiler to optimize it is just stupidity. |
No, it's not - assuming that every single division will be problematic without proof is. Modern compilers rewrite pretty much all integer divides and modulos to long multiplies (or ands where appropriate), and even if they didn't it's only those divisions/modulos that are done frequently that will give you any notable performance enhancement from optimizing.
#154458 - tepples - Wed Apr 16, 2008 7:12 pm
| kusma wrote: |
| No, it's not - assuming that every single division will be problematic without proof is. Modern compilers rewrite pretty much all integer divides and modulos to long multiplies (or ands where appropriate) |
Is that in ARM mode or Thumb mode?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#154459 - Miked0801 - Wed Apr 16, 2008 7:19 pm
Lol - is Metrowerks a modern compiler? ;)
#154504 - kusma - Thu Apr 17, 2008 1:24 am
| tepples wrote: |
| Is that in ARM mode or Thumb mode? |
ARM and Thumb2. Thumb is not targeted at arithmetic-heavy code in the first place.
| Miked0801 wrote: |
| Lol - is Metrowerks a modern compiler? ;) |
No, lol right back at you. Metroweks isn't anymore at all - Freescale took over the IDE-business together with the semiconductor business from Motorola (the Metrowerks mother-company) back in 2005, and Metrowerks never made any compilers worth mentioning anyway. Are you sure you're not confusing compilers with IDEs? They seem to ship GCC with their IDEs these days...
#154505 - Miked0801 - Thu Apr 17, 2008 1:30 am
Freescale is the one we're stuck with - you are correct.
#154542 - PlagueSpark - Thu Apr 17, 2008 8:47 pm
Random-number generation nearly grew to compiler's holywar in this topic :)
rnd() seems to haunt us from inside ... slowly rotting our minds
We must bring order to this chaos ... by using pregenerated random number table :P
#154543 - Kyoufu Kawa - Thu Apr 17, 2008 8:53 pm
| Code: |
void srand(unsigned int seed)
{
rndseed = seed;
}
unsigned int rand()
{
rndseed = (rndseed * 0x41C64E6D) + 0x6073;
return rndseed;
} |
| Quote: |
| Fast enough for the old man. |
#154546 - Miked0801 - Thu Apr 17, 2008 9:33 pm
I actually liked the one we used for GB/GBC - took a table of 256 entries - each with 1 unique 8-bit value and randomly shuffled them. Then seed into the table, draw and increment the index. We debated checking the index past 256 and reshuffling instead of just anding to table size, but it was good enough as is. Pretty dang fast.
#155331 - a128 - Mon Apr 28, 2008 11:55 am
Great.
and if you use
| Code: |
int minutes = IPC->time.rtc.minutes;
int seconds = IPC->time.rtc.seconds;
srand(seconds*minutes);
|
then using the first rand() gives different values each time your applications starts
#155336 - tepples - Mon Apr 28, 2008 1:25 pm
Unless you start it in the first minute of each hour. People might memorize the RNG results for the first minute and use that as a "cheat code". I'd recommend this:
| Code: |
| srand(seconds + 60 * minutes + 3600 * hours); |
And I'd also recommend using libnds functions instead of accessing the IPC struct directly, especially given how libnds developers like to change the IPC struct around in each version.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#155341 - a128 - Mon Apr 28, 2008 3:05 pm
| tepples wrote: |
And I'd also recommend using libnds functions instead of accessing the IPC struct directly, especially given how libnds developers like to change the IPC struct around in each version. |
I missed the "cheat code" feature.
Which libnds functions do you mean?
#155349 - Miked0801 - Mon Apr 28, 2008 6:41 pm
The most common way to seed a random is to wait for some user input then set it off of some very highly volatile value - such as a cpu tics since program started or vcount register or whatever. The user input wait is the most random part.
#155385 - tepples - Tue Apr 29, 2008 12:25 am
| a128 wrote: |
| tepples wrote: | | And I'd also recommend using libnds functions instead of accessing the IPC struct directly, especially given how libnds developers like to change the IPC struct around in each version. |
I missed the "cheat code" feature. |
Several arcade versions of Tetris produced by Sega would always give the same tetromino sequence for the first play after the machine was power-cycled. Players would memorize this pattern and optimize piece placements for it.
| Quote: |
| Which libnds functions do you mean? |
For example, instead of reading touch coordinates directly from IPC, call touchReadXY().
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.