Jump to content
  • Advertisement
Sign in to follow this  
discman1028

Rand # generator w/o int multiplies?

This topic is 3681 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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>();





Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by _fastcall
Quote:
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)?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Depending on how random you need the results you could try this:


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.0
x -= 1.0f;

Share this post


Link to post
Share on other sites
Quote:
Original post by Adam_42

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.


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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!