You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

2015 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(12) 
_{Nov}

_{Dec}
(1) 
2016 
_{Jan}

_{Feb}
(1) 
_{Mar}
(1) 
_{Apr}
(1) 
_{May}

_{Jun}
(1) 
_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 

1

2
(3) 
3
(13) 
4
(5) 
5
(5) 
6
(8) 
7
(12) 
8
(7) 
9
(3) 
10
(11) 
11
(2) 
12
(8) 
13
(19) 
14

15
(1) 
16
(1) 
17
(1) 
18
(9) 
19
(2) 
20
(1) 
21
(1) 
22
(4) 
23
(2) 
24
(6) 
25

26
(10) 
27
(12) 
28
(2) 
29
(5) 
30
(7) 
31





From: Adrian Stephens <adrians@is...>  20070730 21:04:10

Just for the record, I wouldn't make such an assumption either  just trying to make my reply match the OP's example. I suppose I should have written: 'If I were to make the assumption that rand() returned a 15 bit number, I would use something like...'. In practice I expect pretty much everyone uses their own RNG, and knows exactly how many bits they're getting. Adrian Original Message From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Tom Plunket Sent: Friday, July 27, 2007 4:47 PM To: Game Development Algorithms Subject: Re: [Algorithms] fast random floats > Assuming rand() returns a 15 bit number... That's a dangerous assumption. I don't remember what I was doing, but I was recently writing some code to generate random ints in a range, and found that the output of rand() in GCC was actually 31 or 32 bits. IOW, I'd put an assert in your code that RAND_MAX == ((1 << (assumed_number_of_bits + 1))  1 if you're going to be assuming. ;) ...but yeah, masking the output of rand onto the end of 0x3F800000 is a good way to generate random values between one and two IMO, whatever the number of bits that your rand supports. tom!  This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Jon Watte <hplus@mi...>  20070730 18:42:10

Strictly speaking, the union isn't safe, either. The only safe type is pointertochar. Anything accessed through pointertochar must be assumed to alias. Cheers, / h+ Gino van den Bergen wrote: > > Here’s my fast random float function from IEEE 754 singleprecision > floats. I borrowed the rand32() function from Numerical Recipes. The > frand32 function masks out the lower 23 bits of the random integer > value for the mantissa. The exponent of the float value is set to 127 > which is the biased exponent for 1.0f. The binary float representation > 0x3f800000UL  (rand32() & 0x007fffffUL) is a uniformly distributed > float between 1.0 and 2.0, so you have to subtract 1.0 to get a float > between 0.0 and 1.0. Note that you have to use a union rather than a > pointer in order to pun the integer value to a float, since pointers > break strict aliasing rules, and some compilers (gcc 4.0 and up) > exploit that. >   Revenge is the most pointless and damaging of human desires. 
From: Gino van den Bergen <gvandenbergen@pl...>  20070730 10:03:45

Here's my fast random float function from IEEE 754 singleprecision floats. I borrowed the rand32() function from Numerical Recipes. The frand32 function masks out the lower 23 bits of the random integer value for the mantissa. The exponent of the float value is set to 127 which is the biased exponent for 1.0f. The binary float representation 0x3f800000UL  (rand32() & 0x007fffffUL) is a uniformly distributed float between 1.0 and 2.0, so you have to subtract 1.0 to get a float between 0.0 and 1.0. Note that you have to use a union rather than a pointer in order to pun the integer value to a float, since pointers break strict aliasing rules, and some compilers (gcc 4.0 and up) exploit that.=20 =20 static uint32_t g_seed =3D 12345UL; =20 uint32_t seed32() { return g_seed; } =20 uint32_t rand32() { g_seed =3D 1664525UL * g_seed + 1013904223UL; return g_seed; } =20 void srand32(uint32_t seed) { g_seed =3D seed; } =20 float frand32() { union=20 {=20 uint32_t i;=20 float f;=20 } pun; =20 pun.i =3D 0x3f800000UL  (rand32() & 0x007fffffUL); return pun.f  1.0f; } =20 I would advise against returning a general random float value since the range of a float [2^126,2^126] is usually not very practical. Rather take a random float between 0.0 and 1.0 (you lose only 1 bit of precision due to the sign bit) and use a multiplication and/or an addition to transform the random value to the proper range. =20 Gino =20 =20 ________________________________ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Jeff Russell Sent: vrijdag 27 juli 2007 23:06 To: Game Development Algorithms Subject: [Algorithms] fast random floats =20 Anyone have a cool solution for some better, faster way to generate random floating point numbers? Say that a solution for quickly generating random bits exists already, such as rand(). Common solution is of course this:=20 result =3D float( rand() ) / float( RAND_MAX ) but that doesn't make full use of the range of a 32 bit float I would imagine. Seems to me that if your range were fixed (on say [0,1]) you could take your random bits and arrange them somehow directly into say the mantissa bits of the float. Not sure that this would=20 really be faster, but could get you better precision perhaps? Any thoughts? Jeff Russell 
From: <cschueler@re...>  20070730 09:46:45

Hi=20 It is possible to construct a pseudorandom number directly in the float = domain, using a 24bit modulo. I tread the float as an "integer" times 2^24. The modulo for the LCG is = then simpliy 1. I use a purely multiplicative generator (seed !=3D 0), and the = multiplicator a can be chosen from tables for LCG with modulo 2^24. =20 float floatrand() const { static float x =3D 1.f / 16777216.f; return x =3D fmod( 3513381.f * x, 1.f ); } =20 Christian =20 ________________________________ From: gdalgorithmslistbounces@... = [mailto:gdalgorithmslistbounces@...] On Behalf Of = Jeff Russell Sent: Friday, July 27, 2007 11:06 PM To: Game Development Algorithms Subject: [Algorithms] fast random floats =20 Anyone have a cool solution for some better, faster way to generate = random floating point numbers? Say that a solution for quickly generating random bits exists already, = such as rand(). Common solution is of course this:=20 result =3D float( rand() ) / float( RAND_MAX ) but that doesn't make full use of the range of a 32 bit float I would = imagine. Seems to me that if your range were fixed (on say [0,1]) you could take your random bits and arrange them somehow directly into = say the mantissa bits of the float. Not sure that this would=20 really be faster, but could get you better precision perhaps? Any = thoughts? Jeff Russell 
From: <Alex_Clarke@sc...>  20070730 08:46:50

Mm just noticed that link contains really old style C so it probably won't be usable without some effort , oh well :< Alex Clarke Sony Computer Entertainment Europe http://www.scee.com gdalgorithmslistbounces@... wrote on 30/07/2007 09:44:23: > > Donald Knuth developed a floating point PRNG based on subtraction. > It's commonly known as ran3 and was published in Numerical Recepies. > > It might be worth a look as with a bit of effort it's vectorzable > and really quite fast, the results seem pretty random to me although > I'm no expert. > > http://www.google.com/codesearch?hl=en&q=+donald+knuth+ran3+show: > TL8rpa0Q5bA:YxYahnTkhjI:jPL5VD0PVQI&sa=N&cd=5&ct=rc&cs_p=ftp://gaia. > cs.umass.edu/pub/hgschulz/ccitt/ccitt_tools.tar.Z&cs_f=MNRU.C#a0 > > Alex Clarke > Sony Computer Entertainment Europe > http://www.scee.com > ********************************************************************** > This email and any files transmitted with it are confidential and > intended solely for the use of the individual or entity to whom they > are addressed. If you have received this email in error please > notify postmaster@... > This footnote also confirms that this email message has been checked > for all known viruses. > Sony Computer Entertainment Europe Limited > Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom > Registered in England:3277793 > ********************************************************************** >  > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: <Alex_Clarke@sc...>  20070730 08:43:43

Donald Knuth developed a floating point PRNG based on subtraction. It's commonly known as ran3 and was published in Numerical Recepies. It might be worth a look as with a bit of effort it's vectorzable and really quite fast, the results seem pretty random to me although I'm no expert. http://www.google.com/codesearch?hl=en&q=+donald+knuth+ran3+show:TL8rpa0Q5bA:YxYahnTkhjI:jPL5VD0PVQI&sa=N&cd=5&ct=rc&cs_p=ftp://gaia.cs.umass.edu/pub/hgschulz/ccitt/ccitt_tools.tar.Z&cs_f=MNRU.C#a0 Alex Clarke Sony Computer Entertainment Europe http://www.scee.com ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England:3277793 ********************************************************************** 
From: Tom Plunket <gamedev@fa...>  20070730 06:41:09

Jon Watte wrote: > Right, but the OP wanted to get "higher precision" in the lower ranges. Ah, missed that part. > To get higher precision random numbers for the numbers that are closer=20 > to 0, while still maintaining the even distribution, your best bet is = to=20 > generate 32 or 64bit floating point numbers, cast to double and do = the=20 > divide. True, that's probably easiest all around, assuming your doubleprecision hardware exists. :) I've had a strong aversion to seeing dptofp() being called in my games, but that usually because doubleprecision was emulated. > And while division is pretty expensive on x86 platforms, it's not like=20 > EMMS or taking an interrupt or anything. 14 cycles is on the order of=20 > the cost of a L2 cache *HIT* in cost. =46air enough. Old habits. ;) tom! =20 
From: Jon Watte <hplus@mi...>  20070729 16:49:12

Stephan Rose wrote: > When a user places a new object, there are times when the user should > not be able to place the object closer than a certain distance to > another object. So basically, I need to find the closest object and see > if the distance is not too short. > The general term you want to google for is "Minkowski sum"  although doing what you want for an arbitrary convex polygon is somewhat intricate. In brief, you want to test the Minkowski sum where you add the placed object to the tested present object against the placed point; if you get intersection then that point is illegal. Minkowski sum of line and circle, or circle and circle, is trivial: the first turns into a fatter line with round endcaps; the second turns into a fatter circle. The other primitives are more challenging to different degrees. Cheers, / h+   Revenge is the most pointless and damaging of human desires. 
From: Anders Nilsson <jag@an...>  20070729 16:28:01

Well I was thinking along the line of setting the mantissa totally randomly, then chosing an exponent such that the probability of chosing that exponent is proportional to the "bin"size when using that exponent. This requires two random number, but that could be gotten from 23+7 bits (mantissa+negative exponents). Getting the exponent should be farily straightforward given that the binsize is monotone (growing) function of the exponent (it it should be possible to invert it and do the inversedistributionthingy). But the division (using multiplication) seems just as fast, even though the need to work in 64bit/doubles might scare someone ;) Anders Nilsson 2007/7/29, Tom Plunket <gamedev@...>: > > Anders Nilsson wrote: > > > > Right, that's why you want to use your understanding of the floating > > > point format to generate an even distribution. Generally speaking, > use > > > the full range available at a given exponent, then subtract out the > > > bias. > > > > Is this always what we want? > > I won't claim that any solution is always appropriate. :) > > > Doesn't floats span over more values between 01 than over 12 (due to > > denormalization and exponent with negative sign)? > > Yes, quite a considerable number of them (about a third of the discrete > values available in IEEE754, if I remember correctly). However, if you > want an even distribution this is the easiest way to get it. If you > just converted a random set of bits into floating point, you would not > end up with an even distribution. Instead, you'd have significant > clustering around zero. The number of discrete values between one and > two is the same as the number of discrete values between 0.5 and 1, > again for between 0.25 and 0.5, and even more between 0.125 and 0.25. In > many (most?) cases where folks are generating random numbers in games, > they want a distribution that is as likely to generate (for example) > 0.0005 as it is 0.9995, and the easiest way to get that is with the bias > and subtract. > > Another option is to get a higherprecision random value, e.g. get a 64 > bit random set of bits, figure out where the highest set bit is and then > whack the lower remaining bits into the mantissa and set the exponent > "properly". So now you've got an "even" distribution such that the > number of values in the "low half" that you get is comparable to the > number of values in the "high half," but you get additional precision in > the "low half" with more aliasing in the "high half." Whether or not > this is desirable, though, is up to the people who are going to use it. > (FWIW I can't think of a case where this would be desirable, but neither > can I think of one in which it would be undesirable; YMMV.) > > > It seems that generating random numbers in the range 12 and then > > subtracting 1.0 can only reach as many numbers as are available between > > 12. > > Actually, there are more than 2^30 discrete values between 0 and .5, and > only 2^23 between 0.5 and 1.0. > > > I guess it's not a big problem but if I'm right it might be worth > > pointing out... > > Yeah, it is correct, but how you want to deal with that may require > further analysis of the problem domain. :) > > > tom! > >  > >  > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Jon Watte <hplus@mi...>  20070729 11:52:41

Tom Plunket wrote: > E.g., or'ing 0x3f800000 onto a 23bit random value gives you the full > range [1, 2), as evenly distributed as your random number generator > (after shifting lowerdepth generated values up as appropriate). > Subtracting 1 from that result gives you a nice and stillevenly > distributed value in the range of [0, 1). > Right, but the OP wanted to get "higher precision" in the lower ranges. Because your number only uses the 24 bits available in the range [1,2), your minimum quantum is determined by that range. To get higher precision random numbers for the numbers that are closer to 0, while still maintaining the even distribution, your best bet is to generate 32 or 64bit floating point numbers, cast to double and do the divide. Then cast to float. This throws away precision in the upper parts of the range, through truncation, but the minimum representable quantum is a lot higher (whatever that's useful for is another question). And while division is pretty expensive on x86 platforms, it's not like EMMS or taking an interrupt or anything. 14 cycles is on the order of the cost of a L2 cache *HIT* in cost. If you want to use a divide, you can pretty much use it these days. However, in this particular case, the dividend is known, and you can multiply by the reciprocal instead, if you really care. Cheers, / h+   Revenge is the most pointless and damaging of human desires. 
From: Tom Plunket <gamedev@fa...>  20070729 07:21:45

Anders Nilsson wrote: > > Right, that's why you want to use your understanding of the floating > > point format to generate an even distribution. Generally speaking, = use > > the full range available at a given exponent, then subtract out the > > bias. >=20 > Is this always what we want? I won't claim that any solution is always appropriate. :) > Doesn't floats span over more values between 01 than over 12 (due to=20 > denormalization and exponent with negative sign)? Yes, quite a considerable number of them (about a third of the discrete values available in IEEE754, if I remember correctly). However, if you want an even distribution this is the easiest way to get it. If you just converted a random set of bits into floating point, you would not end up with an even distribution. Instead, you'd have significant clustering around zero. The number of discrete values between one and two is the same as the number of discrete values between 0.5 and 1, again for between 0.25 and 0.5, and even more between 0.125 and 0.25. In many (most?) cases where folks are generating random numbers in games, they want a distribution that is as likely to generate (for example) 0.0005 as it is 0.9995, and the easiest way to get that is with the bias and subtract. Another option is to get a higherprecision random value, e.g. get a 64 bit random set of bits, figure out where the highest set bit is and then whack the lower remaining bits into the mantissa and set the exponent "properly". So now you've got an "even" distribution such that the number of values in the "low half" that you get is comparable to the number of values in the "high half," but you get additional precision in the "low half" with more aliasing in the "high half." Whether or not this is desirable, though, is up to the people who are going to use it. (FWIW I can't think of a case where this would be desirable, but neither can I think of one in which it would be undesirable; YMMV.) > It seems that generating random numbers in the range 12 and then > subtracting 1.0 can only reach as many numbers as are available between= =20 > 12. Actually, there are more than 2^30 discrete values between 0 and .5, and only 2^23 between 0.5 and 1.0. > I guess it's not a big problem but if I'm right it might be worth=20 > pointing out... Yeah, it is correct, but how you want to deal with that may require further analysis of the problem domain. :) tom! =20 
From: Anders Nilsson <jag@an...>  20070729 00:38:48

> Right, that's why you want to use your understanding of the floating > point format to generate an even distribution. Generally speaking, use > the full range available at a given exponent, then subtract out the > bias. Is this always what we want? Doesn't floats span over more values between 01 than over 12 (due to denormalization and exponent with negative sign)? It seems that generating random numbers in the range 12 and then subtracting 1.0 can only reach as many numbers as are available between 12. I guess it's not a big problem but if I'm right it might be worth pointing out... Anders Nilsson 
From: Tom Plunket <gamedev@fa...>  20070728 20:47:02

Jon Watte wrote: > The problem with floating point numbers is that the decimal point=20 > floats. If you want to use "more precision" then most simple approaches= =20 > will have a skewed distribution, where a number in the range [0.25x <=20 > 0.5x) will have the same probability as [0.5x < 1.0x). And, given that=20 > floats go pretty far down in size, you'll be skewed towards the low end= =20 > of the range very quickly. Right, that's why you want to use your understanding of the floating point format to generate an even distribution. Generally speaking, use the full range available at a given exponent, then subtract out the bias. E.g., or'ing 0x3f800000 onto a 23bit random value gives you the full range [1, 2), as evenly distributed as your random number generator (after shifting lowerdepth generated values up as appropriate). Subtracting 1 from that result gives you a nice and stillevenly distributed value in the range of [0, 1). ...and it doesn't require any divides (although FP subtracts are still quite costly as I understand it). ...although you don't get the intto float conversion hit, either. (0x3f800000 is the typical representation for 1.0f on the hardware we use in games: 0 sign, biased exponent of 127, and zero in the "mantissa".) It seems that the author's requirements suggest that he won't want to set the exponent (or sign) field(s) directly. It's a bummer that computers tend to these halfopen intervals, because the best you could do if you wanted [1,1] is [1,1) using a starting exponent of 128 (0x3f9...), thereby giving you a value [2,4) and subtracting 3 yields the desired range. tom! =20 
From: Jon Watte <hplus@mi...>  20070728 18:50:40

The problem with floating point numbers is that the decimal point floats. If you want to use "more precision" then most simple approaches will have a skewed distribution, where a number in the range [0.25x < 0.5x) will have the same probability as [0.5x < 1.0x). And, given that floats go pretty far down in size, you'll be skewed towards the low end of the range very quickly. If the divide really is a problem, then multiply by the inverse. If you're getting 32bit integers, and multiply by 1/RAND_MAX then a float can't actually represent the full precision of the result anyway. Btw: I second the recommendation of using the MT implementation; it's pretty good! However, the doubleprecision implementation is, if I recall correctly, just the division of the integer numbers. Cheers, / h+ Jeff Russell wrote: > Anyone have a cool solution for some better, faster way to generate > random floating point numbers? > Say that a solution for quickly generating random bits exists already, > such as rand(). Common solution is of course this: > > result = float( rand() ) / float( RAND_MAX ) > > but that doesn't make full use of the range of a 32 bit float I would > imagine. Seems to me that if your range were fixed (on say [0,1]) > you could take your random bits and arrange them somehow directly into > say the mantissa bits of the float. Not sure that this would > really be faster, but could get you better precision perhaps? Any > thoughts?   Revenge is the most pointless and damaging of human desires. 
From: Tom Plunket <gamedev@fa...>  20070727 23:46:31

> Assuming rand() returns a 15 bit number... That's a dangerous assumption. I don't remember what I was doing, but I was recently writing some code to generate random ints in a range, and found that the output of rand() in GCC was actually 31 or 32 bits. IOW, I'd put an assert in your code that RAND_MAX == ((1 << (assumed_number_of_bits + 1))  1 if you're going to be assuming. ;) ...but yeah, masking the output of rand onto the end of 0x3F800000 is a good way to generate random values between one and two IMO, whatever the number of bits that your rand supports. tom! 
From: Adrian Stephens <adrians@is...>  20070727 21:30:14

Assuming rand() returns a 15 bit number, then I use something like: int i = (rand()<<8)  0x3f800000; return (float&)i  1.0f; You need a 23 bit random integer (e.g. call rand() twice) to get full precision. Adrian Stephens _____ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Jeff Russell Sent: Friday, July 27, 2007 2:06 PM To: Game Development Algorithms Subject: [Algorithms] fast random floats Anyone have a cool solution for some better, faster way to generate random floating point numbers? Say that a solution for quickly generating random bits exists already, such as rand(). Common solution is of course this: result = float( rand() ) / float( RAND_MAX ) but that doesn't make full use of the range of a 32 bit float I would imagine. Seems to me that if your range were fixed (on say [0,1]) you could take your random bits and arrange them somehow directly into say the mantissa bits of the float. Not sure that this would really be faster, but could get you better precision perhaps? Any thoughts? Jeff Russell 
From: Emmanuel Deloget <logout@fr...>  20070727 21:28:48

Have you checked your value of RAND_MAX? There is no guarantee that the number is 32 bits anyway. Another solution would be to use the ubliquitous mersenne twister (http://www.math.sci.hiroshimau.ac.jp/~mmat/MT/emt.html; they have a SIMD version that generates double precision pseudorandom numbers). Cheers!  .Emmanuel Deloget .Website: http://www.emmanueldeloget.com .Software Architect @ Amesys .News Team Manager @ GameDev.Net Selon Joshua Barczak <Josh.Barczak@...>: > I suspect that it would be faster, since divides are much more expensive > than a few AND and ORs. > > ________________________________ > > From: gdalgorithmslistbounces@... > [mailto:gdalgorithmslistbounces@...] On Behalf Of > Jeff Russell > Sent: Friday, July 27, 2007 5:06 PM > To: Game Development Algorithms > Subject: [Algorithms] fast random floats > > > Anyone have a cool solution for some better, faster way to generate > random floating point numbers? > Say that a solution for quickly generating random bits exists already, > such as rand(). Common solution is of course this: > > result = float( rand() ) / float( RAND_MAX ) > > but that doesn't make full use of the range of a 32 bit float I would > imagine. Seems to me that if your range were fixed (on say [0,1]) > you could take your random bits and arrange them somehow directly into > say the mantissa bits of the float. Not sure that this would > really be faster, but could get you better precision perhaps? Any > thoughts? > > Jeff Russell > > 
From: Joshua Barczak <Josh.Barczak@am...>  20070727 21:14:43

I suspect that it would be faster, since divides are much more expensive than a few AND and ORs. =20 ________________________________ From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Jeff Russell Sent: Friday, July 27, 2007 5:06 PM To: Game Development Algorithms Subject: [Algorithms] fast random floats Anyone have a cool solution for some better, faster way to generate random floating point numbers? Say that a solution for quickly generating random bits exists already, such as rand(). Common solution is of course this:=20 result =3D float( rand() ) / float( RAND_MAX ) but that doesn't make full use of the range of a 32 bit float I would imagine. Seems to me that if your range were fixed (on say [0,1]) you could take your random bits and arrange them somehow directly into say the mantissa bits of the float. Not sure that this would=20 really be faster, but could get you better precision perhaps? Any thoughts? Jeff Russell 
From: Jeff Russell <jeffdr@gm...>  20070727 21:05:37

Anyone have a cool solution for some better, faster way to generate random floating point numbers? Say that a solution for quickly generating random bits exists already, such as rand(). Common solution is of course this: result = float( rand() ) / float( RAND_MAX ) but that doesn't make full use of the range of a 32 bit float I would imagine. Seems to me that if your range were fixed (on say [0,1]) you could take your random bits and arrange them somehow directly into say the mantissa bits of the float. Not sure that this would really be faster, but could get you better precision perhaps? Any thoughts? Jeff Russell 
From: Stefan Sandberg <keffo.sandberg@gm...>  20070727 12:03:00

I had a clever idea, if you wanna take it to extremes, (but in my mind it's actually quite a cute solution)... If all of the objects are based on simple geometry, like sphere, thickline/cylinder etc etc, you can treat them all as one function, as an iso surface. That way you can figure out how far away a certain point in space is from the closest surface.. In 2d it would be very simple and very fast, but might be a bit flakey :) Stephan Rose wrote: > On Thu, 20070726 at 19:12 0700, John Ketchpaw wrote: > >> More generically, if you really do intend to have 100k objects, you need some kind of spatial data structure to narrow the search down. >> > > It's kind of amazing how currently am living very well without any kind > of spatial data structure even on lower send systems. > > But I may need to implement a quad tree at a later point in time though, > you're right about that. The only thing I don't like about them is that > that none of the geometry is static and can be moved by the user at any > point in time so I always have the work of not just translating the > object but also updating the quad tree as well. Not something I can't > deal with, but I'm just being lazy and trying to keep the code as simple > as possible. Can't have a bug in code that does not exist. =) > > I've thought of maybe using a loose quad tree but I'm not sure how well > that would do with objects that can without a problem go across the > entire area? A line going from one side completely to the other side is > not unusual. > > Thanks, > > Stephan > > >> Original Message >> From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Aick in der Au >> Sent: Thursday, July 26, 2007 3:49 PM >> To: gdalgorithmslist@... >> Subject: Re: [Algorithms] Finding Minimum Distance >> >> Maybe you can rasterize your objects in a low resolution bitmap and than run >> some dilation filters to attach some extra pixels to your shape. Do this a >> few passes until your objects are fat enough in the bitmap. >> >> Testing then against new objects is easy and your objects can as complex as >> you like. >> >> Cheers, >> Aick >> >> _________________________________________________________________ >> Express yourself instantly with MSN Messenger! Download today it's FREE! >> http://messenger.msn.clickurl.com/go/onm00200471ave/direct/01/ >> >> >>  >> This SF.net email is sponsored by: Splunk Inc. >> Still grepping through log files to find problems? Stop. >> Now Search log events and configuration files using AJAX and a browser. >> Download your FREE copy of Splunk now >> http://get.splunk.com/ >> _______________________________________________ >> GDAlgorithmslist mailing list >> GDAlgorithmslist@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >> >> >>  >> This SF.net email is sponsored by: Splunk Inc. >> Still grepping through log files to find problems? Stop. >> Now Search log events and configuration files using AJAX and a browser. >> Download your FREE copy of Splunk now >> http://get.splunk.com/ >> _______________________________________________ >> GDAlgorithmslist mailing list >> GDAlgorithmslist@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >> >> > > >  > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > > 
From: <Paul_Firth@sc...>  20070727 11:49:41

gdalgorithmslistbounces@... wrote on 27/07/2007 12:28:47: > I've thought of maybe using a loose quad tree but I'm not sure how well > that would do with objects that can without a problem go across the > entire area? A line going from one side completely to the other side is > not unusual. Have a look at the "hash grid" stuff by brian mirtch  i think its described in his thesis but i might be wrong. Very good for large numbers of dynamic objects... Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** 
From: Stephan Rose <kermos@so...>  20070727 11:28:47

On Thu, 20070726 at 19:12 0700, John Ketchpaw wrote: > More generically, if you really do intend to have 100k objects, you need some kind of spatial data structure to narrow the search down. It's kind of amazing how currently am living very well without any kind of spatial data structure even on lower send systems. But I may need to implement a quad tree at a later point in time though, you're right about that. The only thing I don't like about them is that that none of the geometry is static and can be moved by the user at any point in time so I always have the work of not just translating the object but also updating the quad tree as well. Not something I can't deal with, but I'm just being lazy and trying to keep the code as simple as possible. Can't have a bug in code that does not exist. =) I've thought of maybe using a loose quad tree but I'm not sure how well that would do with objects that can without a problem go across the entire area? A line going from one side completely to the other side is not unusual. Thanks, Stephan > > Original Message > From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Aick in der Au > Sent: Thursday, July 26, 2007 3:49 PM > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Finding Minimum Distance > > Maybe you can rasterize your objects in a low resolution bitmap and than run > some dilation filters to attach some extra pixels to your shape. Do this a > few passes until your objects are fat enough in the bitmap. > > Testing then against new objects is easy and your objects can as complex as > you like. > > Cheers, > Aick > > _________________________________________________________________ > Express yourself instantly with MSN Messenger! Download today it's FREE! > http://messenger.msn.clickurl.com/go/onm00200471ave/direct/01/ > > >  > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > > >  > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Stephan Rose <kermos@so...>  20070727 11:23:58

On Thu, 20070726 at 22:48 +0000, Aick in der Au wrote: > Maybe you can rasterize your objects in a low resolution bitmap and than run > some dilation filters to attach some extra pixels to your shape. Do this a > few passes until your objects are fat enough in the bitmap. > > Testing then against new objects is easy and your objects can as complex as > you like. That thought actually has crossed my mind, and it would be sufficient enough for giving coarse realtime feedback as a visual aid to the user, but it'd be too inaccurate for tests I need to run on the data later to ensure proper spacing. I need better than 1,000th of an inch accuracy. =) Thanks, Stephan 
From: Stephan Rose <kermos@so...>  20070727 11:21:16

On Thu, 20070726 at 10:42 0700, Matthew J. Brown wrote: > Just a quick note about: > "Now I can't just generate a bounding circle or rectangle around the > geometry and test their centers. While that would ensure that I never > get too close, it would be far too inaccurate, especially in the case of > a line. The actual geometry shape matters." > > In my experience, the use of bounding circles and rectangles isn't to > actually solve the problem itself, but is an optimization... i.e. you only > test against objects whose bounding circle or rectangle overlap your object > of interest. This is very useful if you want to very quickly cull out a > large number of objects I your given plane. In this sense, it will still be > very useful for your problem, as you only need to test against a smaller set > of objects. > > Just thought I'd give you a headsup on what I read as a misconception on > the use of bounding areas. For some of the objects bounding circles would actually work, but yea, in general you are right. =) I was just throwing it out there as a thing that I've considered and know won't work. I have a tendency to overdefine things when I write ;) Thanks though, appreciated. Stephan > Matt > > Original Message > From: gdalgorithmslistbounces@... > [mailto:gdalgorithmslistbounces@...] On Behalf Of > Stephan Rose > Sent: Thursday, July 26, 2007 5:55 AM > To: Game Development Algorithms > Subject: [Algorithms] Finding Minimum Distance > > Hey Everyone, > > I have the following problem I am currently trying to find a solution > for. I already have some ideas on how to solve it but I thought I'd see > if there maybe aren't some better ways I have not thought of yet. > > Here's the scenario: > > I have a whole bunch of 2 dimensional objects which all lie on the same > plane in 3D space. There are multiple such planes, all parallel to each > other, each plane with its own set of objects, but generally I am only > concerned with the objects on a single plane at a given time. The > different planes are basically used to generate different layers for the > objects. > > The objects most commonly are either lines (with round endcaps), > circles, arcs, or rectangles but can also nonself intersecting polygons > (no holes). > > When a user places a new object, there are times when the user should > not be able to place the object closer than a certain distance to > another object. So basically, I need to find the closest object and see > if the distance is not too short. > > Now I can't just generate a bounding circle or rectangle around the > geometry and test their centers. While that would ensure that I never > get too close, it would be far too inaccurate, especially in the case of > a line. The actual geometry shape matters. > > So I need a more sophisticated method that really gives me the minimum > distance between the actual geometry of two objects. > > Currently I have two different ideas floating around my head: > > Method 1: > Create a function to calculate the minimum distance of each triangle in > Object A against each triangle of Object B. Kind of brute force but it > should work. One nice thing is that with this method I can just use the > existing geometry and don't need to create additional data. > > Method 2: > For each object, create a line based outline around the object and test > outlines against outlines and find their minimum distance. That should > run faster and quicker than testing triangles against triangles, but > would mean additional memory overhead to store the outline. Plus it's > yet another set of data that I need to perform transformations everytime > the object is moved, rotated, etc while making sure that the outline > always matches the generated geometry. > > Neither method really makes me that particularly happy. Method 1 is > probably the safest in terms of accuracy and stability as I don't need > to carry a second dataset around. But it's kind of brute force as I > ultimately test triangle line segments that I don't need to. > > Method 2 is more efficient but is also more overhead to implement and > more vulnerable to bugs that could cause the outline and triangle data > to not match and eats more memory which can matter 100k objects later. > =) > > I suppose I could maybe do a compromise between the two methods and add > a dataset to each object, similar to an index list, which contains > indices to the outer edge line segments. Since my geometry never changes > in triangle count or order once created, the list would only have to be > created once and then never need to be modified again even if my > geometry is transformed. > > Anyone have any additional thoughts or suggestions? =) > > Thanks, > > Stephan > > > >  > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > > >  > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Stephan Rose <kermos@so...>  20070727 11:18:38

On Thu, 20070726 at 14:04 +0100, Paul_Firth@... wrote: > gdalgorithmslistbounces@... wrote on 26/07/2007 > 13:55:03: > > > Anyone have any additional thoughts or suggestions? =) > > Have a look at my website: > > http://www.pfirth.co.uk/collision.html#Penetration > > There are some interactive applets there (and some maths) which hopefully > will give you some pointers... :) Great reading, thanks very much for that! Stephan 