Rand # generator w/o int multiplies?
Author
Anybody know of a random float # generation scheme that doesn't use any integer multiplies of any kind? (and preferably doesn't use 64-bit int's either, but that's not as important.)
Single-precision IEEE-754 float math (including multiplies), as well as integer adds, subtracts, and shifts are fair game.
EDIT: I need an algorithm, not an implementation... my instruction set is limited beyond standard C.
[Edited by - discman1028 on May 7, 2008 10:27:08 PM]
I don't think I quite understand, but this is what I came up with:
#include <cstdlib> template<class float_type>inline float_type random() { return static_cast<float_type>( std::rand() ) / static_cast<float_type>( RAND_MAX );}double x = random<double>();float y = random<float>();
Author
Hmm, might be able to do this, and use float multiplies for the int multiplies, as long as I make sure it wraps after overflow...
Author
Quote:Original post by _fastcall
I don't think I quite understand, but this is what I came up with:
*** Source Snippet Removed ***
A little more low-level... my restrictions pertain to what's inside of rand(). ;) I need an algorithm, not an implementation... my instruction set is limited beyond standard C.
Author
Quote:Original post by discman1028
Hmm, might be able to do this, and use float multiplies for the int multiplies, as long as I make sure it wraps after overflow...
...except the float multiplies don't match the int multiplies due to precision loss... only 23 bits for the "int" mantissa. Maybe the distribution would still be random enough for me... who knows?
But I still have to figure out how to deal with "int" overflow for the float multiply. I can check the float for an INF hex value, and branch based on that, but I couldn't know what to reset the float to, to continue getting random numbers.
Quote:Original post by discman1028
Hmm, might be able to do this,
That code runs 30x faster than my version :)
EDIT:
10,000,000 trials:
4x faster debug mode
30x faster release mode
Author
Quote:Original post by _fastcallQuote:Original post by discman1028
Hmm, might be able to do this,
That code runs 4x faster than my version :)
Glad I could help. ;)
From searches, it seems that the integer multiply (or possibly more specifically, the integer overflow behavior) is absolutely essentially to random number generation...? Has no one on earth ever done it without integer multiplies (in the absence of huge tables)?
Standard linear congruent random number generators multiply by a fixed constant, so you can replace the multiplication by shifts and adds (this still relies on normal integer overflow though). Another simple generator without multiplication would be an LFSR.
What are your limitations exactly? If you're trying to generate random numbers solely with the use floating point arithmetic (say from within a shader or whatever) and without any bit hacks then I don't know of any useful methods without table lookups.
What are your limitations exactly? If you're trying to generate random numbers solely with the use floating point arithmetic (say from within a shader or whatever) and without any bit hacks then I don't know of any useful methods without table lookups.
Depending on how random you need the results you could try this:
The results appear reasonably random to me, but you'd need to do some tests to be sure it's random enough for your needs.
There's also the following trick to convert int to float quickly, which you may find useful. It's from www.agner.org/optimize
static float seed = 0.5f;void srandom(float f){ if (seed <= 0.0f || seed >= 1.0f) return; // Invalid seed seed = f;}float random(void){ seed = 3.8f * seed * (1.0f - seed); return seed;}The results appear reasonably random to me, but you'd need to do some tests to be sure it's random enough for your needs.
There's also the following trick to convert int to float quickly, which you may find useful. It's from www.agner.org/optimize
int n = random_number();float x;*(int*)&x = (n & 0x7FFFFF) | 0x3F800000; // Now 1.0 <= x < 2.0x -= 1.0f;
Author
Quote:Original post by Adam_42float random(void){ seed = 3.8f * seed * (1.0f - seed); return seed;}
The results appear reasonably random to me, but you'd need to do some tests to be sure it's random enough for your needs.
Cool will give it a shot. Will give LFSR a shot too.
Quote:Original post by implicit
What are your limitations exactly? If you're trying to generate random numbers solely with the use floating point arithmetic (say from within a shader or whatever) and without any bit hacks then I don't know of any useful methods without table lookups.
Do you have a table-based method? Depending on the size of the table, that could do. No, it's not for a shader, but it is for a SIMD unit with very little SIMD integer support.
[Edited by - discman1028 on May 8, 2008 1:04:08 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
