 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / November 2007random real number between 0 (inclusive) and 1 (inclusive)
Hi.. I've been searching at the Internet, and in this newsgroup about this issue, but have not been able to find what I'm searching... What I need is to generate a lot of random real numbers between 0 and 1, both inclusive (normally it's possible to generate the number between 0(inclusive) and 1 (exclusive!!!) ) Can anyone tell me how this is done? /Peter On Sun, 04 Nov 2007 19:35:39 -0000, "(-Peter-)" <garfieldpbj@gmail.com> wrote, quoted or indirectly quoted someone who said : >What I need is to generate a lot of random real numbers between 0 and >1, both inclusive (normally it's possible to generate the number >between 0(inclusive) and 1 (exclusive!!!) ) Multiply the number by 1+ulp where ulp in the smallest increment in a double in the vicinity of 1.0 see http://mindprod.com/jgloss/ulp.html In practice it makes so different since the odds of generating a double bang on 1 is extremely remote.  SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com On 4 Nov., 21:28, Roedy Green <see_webs...@mindprod.com.invalid> wrote: > In practice it makes so different since the odds of generating a > double bang on 1 is extremely remote. > -- What if I need 2 billion of random numbers?? Would it statistically happen when? /Peter (-Peter-) schrieb: > On 4 Nov., 21:28, Roedy Green <see_webs...@mindprod.com.invalid> > wrote: [quoted text clipped - 8 lines] > > /Peter nope it would not happen ... not with just a billion of tries! > (-Peter-) schrieb: > [quoted text clipped - 12 lines] > > nope it would not happen ... not with just a billion of tries! Okay.. But I do still prefer Arne's method - isn't it the best? /peter (-Peter-) schrieb: >> (-Peter-) schrieb: >> [quoted text clipped - 13 lines] > > /peter I would make my decision based on what is most important to me... if you need 2 billion bumbers.. performance might be a significant issue.. so I would probably choose what ever is fastest... if performance is not an issue.. I would take what ever looks most readable in the code.. best is relative... On Sun, 04 Nov 2007 20:31:00 -0000, "(-Peter-)" <garfieldpbj@gmail.com> wrote, quoted or indirectly quoted someone who said : >What if I need 2 billion of random numbers?? > >Would it statistically happen when? roughly speaking one in 2^64 = 9,223,372,036,854,775,808 It is actually somewhat smaller than that since nextDouble produces 0..1 not the whole range. perhaps 2^7 = 128 times smaller. In any case quite a bit longer than you will likely generate numbers. SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com > On 4 Nov., 21:28, Roedy Green <see_webs...@mindprod.com.invalid> > wrote: [quoted text clipped - 6 lines] > > Would it statistically happen when? There are 2^53 values returned by nextDouble, the normalized doubles in [0,1). 2e9/2^53 is about 2.22e-7, a probability less than one in 4 million. Patricia > On 4 Nov., 21:28, Roedy Green <see_webs...@mindprod.com.invalid> > wrote: [quoted text clipped - 6 lines] > > Would it statistically happen when? You should be able to work this out in your head. Two billion ~= 2**31. The number of distinct doubles returned by nextDouble() = 2**53. Two billion samples thus represents 2**(31-53) = 2**(-22) of the possible range, about one four-millionth. In other words: If you generate two billion numbers apiece from two random sources A and B, one with output in [0,1) and the other in [0,1], there is only one chance in four million that you'd be able to tell which is which. To put it yet another way: The population of Costa Rica is approximately four million, but you happen to know that one of these "people" is actually a space alien. You have a special detector that can test whether someone is a space alien or an authentic homo sapiens, but you can use it only once: The detector's theta ray generator shorts out and fuses to a useless mass on its first and only discharge. Here's your plane ticket to Costa Rica; your mission is to bring back the ET. What do you think of your chances? SignatureEric Sosman esosman@ieee-dot-org.invalid > > On 4 Nov., 21:28, Roedy Green <see_webs...@mindprod.com.invalid> > > wrote: [quoted text clipped - 31 lines] > Eric Sosman > esos...@ieee-dot-org.invalid thank you for the comments, and the funny example... /peter > To put it yet another way: The population of Costa Rica > is approximately four million, but you happen to know that [quoted text clipped - 5 lines] > Here's your plane ticket to Costa Rica; your mission is > to bring back the ET. What do you think of your chances? Chances? Who cares about chances? I volunteer to do the experiment. Send the ticket - free holiday in Costa Rica Send the detector - will catch a fortune when sold on eBay Hunter Gratzner wrote On 11/05/07 15:18,: >> To put it yet another way: The population of Costa Rica >>is approximately four million, but you happen to know that [quoted text clipped - 10 lines] > Send the ticket - free holiday in Costa Rica > Send the detector - will catch a fortune when sold on eBay Your ticket and the detector are in the mail, along with the latest batch of purple pills and the, er, latex novelty items you ordered. Glad, as always, to provide service to my long-time customers! ;-) SignatureEric.Sosman@sun.com > To put it yet another way: The population of Costa Rica > is approximately four million, but you happen to know that [quoted text clipped - 3 lines] > once: The detector's theta ray generator shorts out and > fuses to a useless mass on its first and only discharge. Why not simply look for the bent pinky finger? SignatureLew > Your ticket and the detector are in the mail, along > with the latest batch of purple pills and the, er, latex > novelty items you ordered. Glad, as always, to provide > service to my long-time customers! Thanks for throwing in some free vitamin pills and a rubber duck. I'l make sure the rubber duck doesn't get lost on the beaches of Costa Rica. > On Sun, 04 Nov 2007 19:35:39 -0000, "(-Peter-)" > <garfieldpbj@gmail.com> wrote, quoted or indirectly quoted someone who [quoted text clipped - 11 lines] > In practice it makes so different since the odds of generating a > double bang on 1 is extremely remote. I think that would introduce a non-uniformity. [I'm using "^" to mean exponentiation, not xor.] The problem is that there are 2^53 normalized doubles in the range [0,1), and 2^53 nextDouble results. If you somehow map them to the (2^53)+1 normalized doubles in [0,1], one of the doubles has to be impossible, creating a bias. How about first obtaining a long in the range [0,2^53]. That could be done by combining the results of a couple of nextInt calls. Then divide by (double)(1L << 53). Patricia >> On Sun, 04 Nov 2007 19:35:39 -0000, "(-Peter-)" >> <garfieldpbj@gmail.com> wrote, quoted or indirectly quoted someone who [quoted text clipped - 16 lines] > done by combining the results of a couple of nextInt calls. Then divide > by (double)(1L << 53). Instead of obtaining randomly ("rolling") a long that way, see if you roll 2^53; anytime you miss bit 1 you can stop. If you actually hit 2^53, you have a 1, otherwise roll in [0,1). I think that is simpler and you can more easily adapt that to other random number generators which work with half-open intervals. On the other hand, the OP only needed 2 billion numbers. That's approx. 2^31. It'll take a few times generating before noticing that "1" is missing. Michael [...] > How about first obtaining a long in the range [0,2^53]. That could be > done by combining the results of a couple of nextInt calls. Then divide > by (double)(1L << 53). Or, instead of using nextInt() calls, the following should work as well: Random r = new Random() { public double nextDouble() { return (((long)(next(26)) << 27) + next(27) + next(1)) / (double)(1L << 53); } }; piotr > [...] > [quoted text clipped - 10 lines] > } > }; If you are going to do that you have to extend Random, because next is protected. Patricia Sorry if this is a double post, network problems... >> [...] >> [quoted text clipped - 15 lines] > > Patricia He did extend Random. Although, my argument would be that he shouldn't override nextDouble, but create a new method, as the new method has different semantics than the original nextDouble. SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> > Sorry if this is a double post, network problems... > [quoted text clipped - 21 lines] > but create a new method, as the new method has different semantics than > the original nextDouble. Yup, I realized that, and canceled my message just after I sent it, but cancel does not always catch up :-( I agree that the new method should be given a different name, because of the different semantics. Patricia >> Sorry if this is a double post, network problems... >> [quoted text clipped - 29 lines] > I agree that the new method should be given a different name, because of > the different semantics. Yes, you are both right. In fact, I have had a different name of that method in my initial approach, but have changed that for simplicity just while editing my post. Of course, the general purpose solution should not change nextDouble() semantics. But the problem here is, that the general purpose implementation must extend the concrete Random implementation (which can not be anonymous class). The best approach I can think of to achieve that might look as follows: public class RandomExtend extends java.util.Random { public interface BitsProvider { int nextBits(int numBits); void setSeed(long seed); } protected BitsProvider bitsProvider; private class DefaultBitsProvider implements BitsProvider { public final int nextBits(int numBits) { return RandomExtend.this.defaultNext(numBits); } public final void setSeed(long seed) { RandomExtend.this.defaultSetSeed(seed); } } public RandomExtend() { super(); this.bitsProvider = new DefaultBitsProvider(); } public RandomExtend(long seed) { super(seed); this.bitsProvider = new DefaultBitsProvider(); } public RandomExtend(BitsProvider bitsProvider) { super(0L); this.bitsProvider = bitsProvider; } @Override protected final int next(int numBits) { return bitsProvider.nextBits(numBits); } @Override public void setSeed(long seed) { bitsProvider.setSeed(seed); } final int defaultNext(int bits) { return super.next(bits); } final void defaultSetSeed(long seed) { super.setSeed(seed); } public double nextDoubleWith1() { return (((long)(next(26)) << 27) + next(27) + next(1)) / (double)(1L << 53); } } Note that the above implementation allows for any concrete Random support through the use of BitsProvider interface (any Random implementation, including SecureRandom, even when not extendable may be supported with that). However, as you can see, there is much more coding necessary than in the approach with broken semantics of nextDouble() in anonymous class. So, is that all extra coding really worth the effort? I think, that "yes" is not always the only right answer... piotr > [...] > But the problem here is, that the general purpose implementation must > extend the concrete Random implementation (which can not be anonymous > class). The best approach I can think of to achieve that might look as > follows: [...] Encapsulation might be a better choice than extension, and would certainly be less troublesome to code. public class FunnyRandom { private final Random rand = new Random(); public double nextInclusiveDouble() { // flawed implementation: double r = rand.nextDouble(); return rand.nextBoolean() ? r : 1.0 - r; } } If you wanted, you could add a constructor that supplies a pre-existing Random instead of generating a new one, and/or an access method to return a reference to the internal Random, and assorted other decorations. But it doesn't seem to me that there's any compelling reason that a generator of a special distribution should also "be a" Random. (As discussed elsethread, the value of implementing this particular special distribution is questionable. Also, even though I proposed the algorithm shown here, I have since realized that it is incorrect. As I wrote when I suggested it, "trust, but verify.") SignatureEric Sosman esosman@ieee-dot-org.invalid >> [...] >> But the problem here is, that the general purpose implementation must [quoted text clipped - 4 lines] > Encapsulation might be a better choice than extension, > and would certainly be less troublesome to code. Yup, that's often a better choice. > public class FunnyRandom { > private final Random rand = new Random(); [quoted text clipped - 11 lines] > that there's any compelling reason that a generator of a > special distribution should also "be a" Random. There is no real need to do so. The reason for me was to combine default implementation of Random with encapsulated "accessor" (BitsProvider) of the protected next() of Random. BTW, maybe better would be calling it RandomDelegate instead of RandomExtend... When we don't want delegation model (a bit tricky BTW, there are only two methods delegated), we just don't need setSeed() in proposed BitsProvider interface. However, "something" should still extend concrete Random implementation in order to access its next(), otherwise it must be simulated, e.g. using nextInt(), as proposed earlier by Patricia. So, as long as an implementation does not needs the next() access (as in your example) there is no need for Random extension. > (As discussed elsethread, the value of implementing this > particular special distribution is questionable. Also, even > though I proposed the algorithm shown here, I have since > realized that it is incorrect. As I wrote when I suggested it, > "trust, but verify.") Well, there is no need for that in the _final_ problem of the OP, no question on that. Proposed here is the solution of the _original_ problem, i.e. with no mention of taking just "two billion" distribution (that's the goal added later by the OP). The proposed solution is just to generate random sequence of doubles containing 1 with the same (approximately) probability as for the other doubles. Do you think it's incorrect for that? piotr Piotr Kobzda wrote On 11/05/07 11:55,: >> public class FunnyRandom { >> private final Random rand = new Random(); [quoted text clipped - 19 lines] > (approximately) probability as for the other doubles. Do you think it's > incorrect for that? Yes. The nextDouble() call produces 0.0 and 0.125 and 0.675 and ... with equal probability (to the limits of the underlying PRNG); call it probability P. My modification produces 0.0 with probability P/2 and 1.0 with probability P/2, while 0.375 and so on still have probability P: the returned values are not equiprobable. (In effect, I've "smeared" the original probability of 0.0 across the two values 0.0 and 1.0.) The easiest way I can think of to meet the original requirement is to use a rejection technique, as in double nextInclusiveDouble() { long number; do { number = ( ((long)rand.next(27) << 27) + rand.next(27); } while (number > 1L << 53); return number / (double)(1L << 53); } The loop executes at least once, more than once about 1/2 the time, more than twice 1/4 of the time, ... for an average of two executions per method call. That's not an especially wonderful ratio for rejection, but I can't think of an alternative that wouldn't risk introducing a bias somewhere. SignatureEric.Sosman@sun.com > Piotr Kobzda wrote On 11/05/07 11:55,: >> [...] The proposed solution is just [quoted text clipped - 10 lines] > "smeared" the original probability of 0.0 across the two > values 0.0 and 1.0.) OK, now I see your point, thanks for explanation. The same incorrectness I think applies to my previous proposition. > The easiest way I can think of to meet the original > requirement is to use a rejection technique, as in [quoted text clipped - 14 lines] > think of an alternative that wouldn't risk introducing > a bias somewhere. Nice. So, what do you think about the following: private double lastr = rand.nextDouble(); public double nextInclusiveDouble() { double r = lastr + rand.nextDouble(); if (r > 1d) r -= 1d; return lastr = r; } The probability of each double in range [0, 1] seams to equal. Is it correct? piotr Piotr Kobzda wrote On 11/05/07 14:28,: > [...] > So, what do you think about the following: [quoted text clipped - 9 lines] > The probability of each double in range [0, 1] seams to equal. Is it > correct? I don't know. `lastr' is essentially the fractional part of the sum of N uniformly-distributed values. The sum itself will converge toward a normal distribution as N increases, so the question is about the distribution of X mod 1 when X is normally distributed. It's possible that the distribution of X mod 1 is uniform, but it's not "obvious." Not to me, anyhow. SignatureEric.Sosman@sun.com > Piotr Kobzda wrote On 11/05/07 14:28,: >> [...] [quoted text clipped - 12 lines] > > I don't know. [...] ... but I've been thinking about it, and I've found the answer. Three answers, in fact: Yes, No, and Maybe. YES: The first number returned is the sum of two uniformly distributed values, possibly minus one. Call the two uniform values X and Y, and think of them as coordinates in the unit square. The returned value is x+y for any point in the lower left triangle or x+y-1 in the upper right triangle. This value will be less than some chosen r, 0<=r<=1, if (x,y) is in a small triangle at the origin (where x+y<r) or in a band just above the diagonal (where 1<x=y<1+r). The area of the small triangle is 0.5*r^2, and the area of the band is 0.5-0.5*(1-r)^2. Add those, and the total area in which the returned value is <r comes to r, which is precisely the definition of a uniformly distributed variable. So lastr is uniform after the first use, and will remain uniform for all subsequent uses: the lastr from one use becomes the X of the next one, with nextDouble contributing a new Y, and the same argument applies all over again. NO: The above assumes sums and differences are computed with perfect accuracy, but in fact a double has finite precision: 53 bits for Java (one implicit, for normalized values). To keep the illustration easy, imagine that double had only five bits of precision. Express X and Y as binary fractions .xxxxx and .yyyyy, where the x's and y's are jumbles of 1's and 0's. If the sum z=x+y is less than 1, it looks like .zzzzz and all is well. But if it's 1 or greater, it's 1.zzzz: one bit has been rounded off. Now subtract 1 from this, and you get .zzzz0 -- that is, after a subtraction step, the lowest-order fraction bit is necessarily zero. If x+y<1 the low-order bit is about equally likely to be zero or one, but the other half of the time it is always zero; all in all, the low-order bit is zero 75% of the time and one only 25% of the time. (A comment in the source of nextDouble says that early versions of that method had a related bug.) MAYBE: A double has 53 bits of precision when stored, but some JVM's use higher precision in intermediate computations if strictfp is not specified. On such JVM's, the sum of x+y might be 1.zzzz (rounded) or 1.zzzzz (exact, in a high-precision CPU register), and in the latter case subtracting 1 will not introduce a low-order 0. So you're at the mercy of the particular JVM and of exactly how the JIT decides to compile the byte code. "Go not to c.l.j.p. for advice, for they will say both Yes and No -- and sometimes Maybe." SignatureEric Sosman esosman@ieee-dot-org.invalid ... > NO: The above assumes sums and differences are computed with > perfect accuracy, but in fact a double has finite precision: 53 [quoted text clipped - 11 lines] > only 25% of the time. (A comment in the source of nextDouble > says that early versions of that method had a related bug.) ... This problem, and the general difficulties of double rounding, could be avoided by the rewriting of the problem I have previously suggested. Think of it as the problem of getting a long in the closed range 0 through 2**53, converting it to double, and dividing it by 2**53. The nextDouble result multiplied by 2**53 is a integer in the range 0 through 2**53 - 1, exactly convertible to long. private static final long MULTIPLIER = 1L<<53; private long lastr = (long)(rand.nextDouble()*MULTIPLIER); public double nextInclusiveDouble() { long r = lastr + rand.nextDouble() * MULTIPLIER; if (r > MULTIPLIER) r -= MULTIPLIER; lastr = r; return r/(double)MULTIPLIER; } If I've done this right, it is just like the previous version, except the addition, comparison, and subtraction are done in long, which can deal exactly with 54 bit numbers. Patricia > ... >> NO: The above assumes sums and differences are computed with [quoted text clipped - 28 lines] > public double nextInclusiveDouble() { > long r = lastr + rand.nextDouble() * MULTIPLIER; That should be: long r = lastr + (long)(rand.nextDouble() * MULTIPLIER); > if (r > MULTIPLIER) r -= MULTIPLIER; > lastr = r; [quoted text clipped - 6 lines] > > Patricia [...] >> private static final long MULTIPLIER = 1L<<53; >> [quoted text clipped - 8 lines] > >> if (r > MULTIPLIER) r -= MULTIPLIER; And that should be: if (r > MULTIPLIER) r -= MULTIPLIER + 1; Without that 1 more, zero is possible only once, just when a nextDouble() initializing 'lastr' is zero, and is never possible again later (the same mistake was in my initial double-based approach). >> lastr = r; >> return r/(double)MULTIPLIER; >> } This approach eliminates the Eric's "MAYBE" answer. However, does it really eliminate his "NO"? I'm not so sure about that... piotr Piotr Kobzda wrote On 11/06/07 10:45,: > [...] > [quoted text clipped - 25 lines] > This approach eliminates the Eric's "MAYBE" answer. However, does it > really eliminate his "NO"? I'm not so sure about that... Looks like it does. It certainly gets rid of the rounding problem. There's still a tiny bias because the amount added each time is just a bit too small: it's chosen from [0,2**53-1] instead of from [0,2**53] as it should be. The mean of the generated distribution will be just a touch less than 0.5, not 0.5 spot-on. Small values are just a hair more probable than large values. (I think. But I'm sometimes rong ...) The error is too small to pay heed to, but it's really the same error the O.P. was trying to eliminate, just sort of "spread out" instead of concentrated on the single value unity. SignatureEric.Sosman@sun.com > Piotr Kobzda wrote On 11/06/07 10:45,: [...] >> This approach eliminates the Eric's "MAYBE" answer. However, does it >> really eliminate his "NO"? I'm not so sure about that... > > Looks like it does. It certainly gets rid of the > rounding problem. I still have some doubts, I don't like "rand.nextDouble()*MILTIPLIER" part -- I've a feeling it somehow favors small doubles, but I may be wrong, so never mind... Anyway, how about reimplementing it as follows: private static final long maxr = 1L << 53; private long lastr = nextr(); private long nextr() { return ((long)next(26) << 27) + next(27) + next(1); } public double nextInclusiveDouble() { long r = lastr + nextr(); if (r > maxr) r -= maxr + 1; lastr = r; return r / (double)maxr; } ? piotr > Anyway, how about reimplementing it as follows: [...] Or, like that: private static final long maxr = 1L << 53; private long lastr; public double nextInclusiveDouble() { final int b1 = next(27), b2 = next(27); long r = lastr + ((long)b1 << 26) + (b2 >>> 1) + (b2 & 1); if (r > maxr) r -= maxr + 1; lastr = r; return r / (double)maxr; } ? Now, because we have a whole "bits domain" possible with each drawing, initial value of 'lastr' is not important, it now just serves the role of "error shifter". In addition, that variant is modified to "eat" one value less from the generator's sequence (pair of 27 bits is enough). piotr >> Piotr Kobzda wrote On 11/06/07 10:45,: > [quoted text clipped - 9 lines] > part -- I've a feeling it somehow favors small doubles, but I may be > wrong, so never mind... Take a look at the nextDouble code. It works by collecting a total of 53 bits from next(26) and next(27), concatenating them to form a double in the range 0 through MULTIPLIER-1, and then double precision dividing the result by MULTIPLIER. The multiplication just recovers the uniformly distributed [0,MULTIPLIER) long. Patricia [...] >> I still have some doubts, I don't like "rand.nextDouble()*MILTIPLIER" >> part -- I've a feeling it somehow favors small doubles, but I may be [quoted text clipped - 5 lines] > result by MULTIPLIER. The multiplication just recovers the uniformly > distributed [0,MULTIPLIER) long. OK, you right -- my mistake in analyzing... However, there is no need for that (long) -> (double) -> (long) conversion, which is 1:1 in this case. And that's what my recent implementation is avoiding. There is just one slight difference more (making it almost the same as was your initial suggestion), additional bit from the generator's sequence is used to make the result duly ranged for each nextInclusiveDouble() call. I'm just not sure, if it is really correct now? Simply, not sure if a "jumping" from last result is enough to prevent us from non-uniform distribution of the resulting sequence. Do you think it's still correct? piotr > [...] > [quoted text clipped - 11 lines] > for that (long) -> (double) -> (long) conversion, which is 1:1 in this > case. The intent of the conversion was to do the arithmetic in long, rather than double. The issue is floating point rounding. Adding two longs in the range [0,2**53-1] is an exact operation, because the result has no more than 54 significant bits. In double, it can cause rounding, because double only supports 53 significant bits. After the subtraction, the result is guaranteed to be exactly representable in double. I have not yet analyzed your latest solution from the point of view of floating point rounding. Did you take it into account in designing the solution? Patricia > [...] However, there is no need >> for that (long) -> (double) -> (long) conversion, which is 1:1 in this >> case. > > The intent of the conversion was to do the arithmetic in long, rather > than double. Yes, I know that. Note that the first conversion in a chain mentioned by me, i.e. (long) -> (double), is the one performed by nextDouble(), second one is a "recovering" it back in implementation. > I have not yet analyzed your latest solution from the point of view of > floating point rounding. Did you take it into account in designing the > solution? Yes, I did. For that aspect it do not differs from yours implementation. It's just more efficient approach (because of lack of unnecessary conversion). The only significant difference is in generating a longs within a whole range, i.e. [0, 2^53], not [0, 2^53 - 1]. piotr > [...] > Anyway, how about reimplementing it as follows: [quoted text clipped - 6 lines] > return ((long)next(26) << 27) + next(27) + next(1); > } This returns 42 twice as often as it returns 0 or maxr. The mean of the distribution is correct, but the variance is a wee bit too small: there is too much "central tendency." Is there any point in pursuing this further? We've known since the beginning that there's no practical need for a [0,1] as opposed to [0,1) distribution, and even if someone wants to use it for "impractical" reasons a correct solution has already been posted. The rest is just intellectual niggling about how many angels can dance on the least-significant bit, and has ceased to have much to do with Java programming. If the question still interests you as a theoretical study -- there's no harm and much good in pursuing such interests -- perhaps it would be better explored in comp.programming, say, or maybe sci.math. SignatureEric Sosman esosman@ieee-dot-org.invalid >> [...] >> Anyway, how about reimplementing it as follows: [quoted text clipped - 10 lines] > The mean of the distribution is correct, but the variance is > a wee bit too small: there is too much "central tendency." That's the property of nextr(). But the "central tendency" is propagated later into other values through shifting it from lastr. So, where is no "center". > Is there any point in pursuing this further? On, if you are satisfied with the results achieved. And maybe it's my fault, but I'm not. > We've known > since the beginning that there's no practical need for a [0,1] > as opposed to [0,1) distribution, and even if someone wants to > use it for "impractical" reasons a correct solution has already > been posted. Correct solutions posted already are less efficient than the latest one. > The rest is just intellectual niggling about how > many angels can dance on the least-significant bit, and has > ceased to have much to do with Java programming. True. But a lot of interesting problems covered by Java are not strictly Java related, aren't they? > If the question > still interests you as a theoretical study -- there's no harm > and much good in pursuing such interests -- perhaps it would be > better explored in comp.programming, say, or maybe sci.math. Maybe, but 1) I'm to lazy to start a new discussion (yes, I know, it's a shame); 2) I know that here are also the people who knows some aspects of the domains shared by the newsgroups mentioned by you (evidence is even in this thread!). Of course, if a luck of the satisfactory answers will cause me waking up at the middle of the night with a sweat on my brow, I'll consider to continue it somewhere else. Thanks! piotr > Of course, if a luck of the satisfactory answers will cause me waking up ^ "lack" of course. piotr >> [...] >> We've known [quoted text clipped - 4 lines] > > Correct solutions posted already are less efficient than the latest one. As far as I can tell, the more efficient "solutions" have all been incorrect. But as I've mentioned (and shown!) elsethread, I am sometimes rong. SignatureEric Sosman esosman@ieee-dot-org.invalid > So, what do you think about the following: > [quoted text clipped - 8 lines] > The probability of each double in range [0, 1] seams to equal. Is it > correct? Consider what happens if nextInclusiveDouble() ever returns 0. Then the next value cannot be 1. Similarly, if it ever returns 1, the next value cannot be 0. A correct solution would not discriminate against the sequences 0,1 and 1,0. > Consider what happens if nextInclusiveDouble() ever returns 0. Then the > next value cannot be 1. Similarly, if it ever returns 1, the next value > cannot be 0. A correct solution would not discriminate against the > sequences 0,1 and 1,0. Yes. The trivial solution may be calling it twice. However, the recent versions posted by me are free of that "inconvenience". The problem is, that they are not proven yet... :) piotr > Piotr Kobzda wrote On 11/05/07 11:55,: >> [...] The proposed solution is just [quoted text clipped - 10 lines] > "smeared" the original probability of 0.0 across the two > values 0.0 and 1.0.) OK, now I see your point, thanks for explanation. The same incorrectness I think applies to my previous proposition. > The easiest way I can think of to meet the original > requirement is to use a rejection technique, as in [quoted text clipped - 14 lines] > think of an alternative that wouldn't risk introducing > a bias somewhere. Nice. So, what do you think about the following: private double lastr = rand.nextDouble(); public double nextInclusiveDouble() { double r = lastr + rand.nextDouble(); if (r > 1d) r -= 1d; return lastr = r; } The probability of each double in range [0, 1] seems to be equal. Is it correct? piotr > So, what do you think about the following: > [quoted text clipped - 3 lines] > double r = lastr + rand.nextDouble(); > if (r > 1d) r -= 1d; Woops, zero is impossible that way. Math.nextUp(1d) should be used instead of 1d here. > return lastr = r; > } piotr > So, what do you think about the following: > [quoted text clipped - 3 lines] > double r = lastr + rand.nextDouble(); > if (r > 1d) r -= 1d; Woops, zero is impossible that way. Math.nextUp(1d) should be used instead of second 1d here. > return lastr = r; > } piotr >> So, what do you think about the following: >> [quoted text clipped - 9 lines] >> return lastr = r; >> } There is a more general solution approach that splits the problem into two parts: 1. Construct a long equivalent of nextInt(int), using the same implementation approach. 2. use nextLong((1L<<53)+1)/(double)(1L<<53) Patricia > There is a more general solution approach that splits the problem into > two parts: > > 1. Construct a long equivalent of nextInt(int), using the same > implementation approach. There is a long used in implementation for computations, so equivalent nextLong(long) will need 126 bits (or two longs) to do the similar -- not so straightforward reimplementation... > 2. use nextLong((1L<<53)+1)/(double)(1L<<53) I think that the Eric's approach (a "rejection technique") is "almost" equivalent to the above steps. It just omits the optimization, i.e. the special treatment of the power of 2 cases. piotr >> There is a more general solution approach that splits the problem into >> two parts: [quoted text clipped - 5 lines] > nextLong(long) will need 126 bits (or two longs) to do the similar -- > not so straightforward reimplementation... But that's the problem of the optimization only. Fortunately, do not applies to the heart of the algorithm implemented there. The following should work as expected: public long nextLong(long n) { //... long bits, val; do { bits = next(63); val = bits % n; } while (bits - val + (n-1) < 0); return val; } piotr [...] >>> 1. Construct a long equivalent of nextInt(int), using the same >>> implementation approach. [quoted text clipped - 5 lines] > But that's the problem of the optimization only. Fortunately, do not > applies to the heart of the algorithm implemented there. Tried that, and it seems that even special treatment of the power of 2 cases is not very complicated in implementation (64 bits is enough): public long nextlong(long n) { if (n <= 0) throw new IllegalArgumentException("n must be positive"); if ((n & -n) == n) // i.e., n is a power of 2 return (((((long) next(32)) << 32) >>> 1) | next(31)) >> (63 - Long.numberOfTrailingZeros(n)); long bits, val; do { bits = ((((long) next(32)) << 32) >>> 1) | next(31); val = bits % n; } while (bits - val + (n - 1) < 0); return val; } piotr > There is a more general solution approach that splits the problem into > two parts: [quoted text clipped - 3 lines] > > 2. use nextLong((1L<<53)+1)/(double)(1L<<53) How about, if the random is less than or equal to 1/2, use it; otherwise generate another and subtract half of that from 1.0? The only risk I can think of will be the possibility of giving 0.5 too much probability, depending on the rounding mode. > On Sun, 04 Nov 2007 19:35:39 -0000, "(-Peter-)" > <garfieldpbj@gmail.com> wrote, quoted or indirectly quoted someone who [quoted text clipped - 6 lines] > Multiply the number by 1+ulp where ulp in the smallest increment in a > double in the vicinity of 1.0 Are you sure that will work? I have a suspicion that the rounding of the products will at best relocate the absent value, gaining the ability to generate 1.0 at the cost of becoming unable to generate 0.mumble. The effect might be worse than that, suppressing many 0.mumble values while "piling on" nearby values and making them more likely. A safer approach (I think -- trust, but verify) might be to generate [0,1) values and "reflect" half of them at random: double r = rand.nextDouble(); if (rand.nextBoolean()) r = 1.0 - r; > see http://mindprod.com/jgloss/ulp.html > > In practice it makes so different since the odds of generating a > double bang on 1 is extremely remote. Agreed. One chance in 9007199254740992 if I haven't botched the arithmetic. You'd need to generate a number every nanosecond for three solid months to accumulate that many; probably six or twelve months before the lack of an exact 1.0 would be statistically noticeable. SignatureEric Sosman esosman@ieee-dot-org.invalid In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r @4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <see_website@mindprod.c om.invalid> posted: >On Sun, 04 Nov 2007 19:35:39 -0000, "(-Peter-)" ><garfieldpbj@gmail.com> wrote, quoted or indirectly quoted someone who [quoted text clipped - 6 lines] >Multiply the number by 1+ulp where ulp in the smallest increment in a >double in the vicinity of 1.0 By stretching [0, 1) to cover [0, 1] there is necessarily a hole created, perhaps at 0.5 . By creating random R in [0, 1) and doing if (R==0.5) { R = 1 } ; (apologies; I'm slowly learning to read Java; writing it properly may follow) one also gets a hole. Now replace 0.5 by a random in [0, 1) independently generated and renewed each time it is hit (so not correlated with the main Random), and ISTM that all values in [0, 1] should be obtained with virtually equal probability. Signature(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME. <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links; <URL:http://www.merlyn.demon.co.uk/clpb-faq.txt> RAH Prins : c.l.p.b mFAQ; <URL:ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ. > In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r > @4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <see_website@mindprod.c [quoted text clipped - 21 lines] > and ISTM that all values in [0, 1] should be obtained with virtually > equal probability. The Java code would be something like: double nextInclusiveDouble(){ double r = nextDouble(); return r == nextDouble() ? 1 : r; } If we were using a true random number generator, this would be close to perfect. Let N be 2**53, the number of different nextDouble results, and assume they are uniformly distributed and the results of consecutive calls are independent. The two nextDouble calls have N*N possible results. Of those, N give result 1. N-1 of the pairs result in e.g. 0. N numbers are each chosen with probability (N-1)/(N*N), and 1.0 is chosen with probability N/(N*N)=1/N. This is indeed close enough that I don't think the difference would be measurable over the probable lifetime of Java. Does anyone know whether nextDouble produces pairs of consecutive equal numbers with the correct probability, remembering that it is based on a pseudo-random number generator? Patricia Patricia Shanahan schrieb: >> In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r >> @4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <see_website@mindprod.c [quoted text clipped - 47 lines] > > Patricia really nice solution I like it .. though I doubt even just using nextDouble() could be measured over the usual lifetime 2 ** 53 doubles and you will need at least log n more experiments if I am not wrong until you can really measure something is wrong (chernov was it?) .. so its about 2**60 which results if 1 Billion numbers can be generated per second in 36 years of computing power. using anything else but simple nextDouble() seems to be overkill. [...] > Does anyone know whether nextDouble produces pairs of consecutive equal > numbers with the correct probability, remembering that it is based on a > pseudo-random number generator? To produce that, the default generator (a linear congruential generator) implemented in java.util.Random must generate a sequence of two consecutive equal pairs of 26, and 27 bits (both higher) of 48 bits of four consecutive seeds. Where each seed is generated using the following formula: seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1) As you can see, that's not easy to guess (at least to me) if that ever happens. And unfortunately, my machine would require about two years to check a whole period (2^48 at most) of the generator defined like that. There are of course other pseudo-random number generators which makes your question even harder to be answered... So, I don't know the answer. But I like the idea. piotr >> In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r >> @4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <see_website@mindprod.c [quoted text clipped - 25 lines] > return r == nextDouble() ? 1 : r; >} That's not the code for what I suggested. Whether it will do well enough must depend on the details behind nextDouble. I suggested an independent generator to maintain the Hole. Pseudo?-JavaSCRIPT : var Hole = SomeOtherRandomFunction() function nextInclusiveDouble() { var T if ((T=Math.random())==Hole) { T = 1 ; Hole = SomeOtherRandomFunction() } return T } Since SomeOtherRandomFunction is called only when Math.random() hits Hole, it can be slow : something from Knuth implemented in Java[script]. >If we were using a true random number generator, this would be close to >perfect. Let N be 2**53, the number of different nextDouble results, and >assume they are uniformly distributed and the results of consecutive >calls are independent. If the works behind nextDouble were to have 53 bits (I suspect they have more) consecutive calls would never give the same value. >The two nextDouble calls have N*N possible results. They have whichever is the less of N**2 and 2**(GeneratorBits), ISTM. > Of those, N give >result 1. N-1 of the pairs result in e.g. 0. N numbers are each chosen [quoted text clipped - 7 lines] >numbers with the correct probability, remembering that it is based on a >pseudo-random number generator? Is nextDouble based on *A* specific PRNG, or is it based on whichever PRNG the system author happened to like? In the latter case, your question may have multiple answers. Signature(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME. Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links; Astro stuff via astron-1.htm, gravity0.htm ; quotings.htm, pascal.htm, etc. No Encoding. Quotes before replies. Snip well. Write clearly. Don't Mail News. >>> In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r >>> @4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <see_website@mindprod.c [quoted text clipped - 39 lines] > Since SomeOtherRandomFunction is called only when Math.random() hits > Hole, it can be slow : something from Knuth implemented in Java[script]. Java has two built-in random number generators, java.util.Random and a subclass, java.security.SecureRandom. SecureRandom is the class to use if you want a different, possibly better, but slower generator. >> Does anyone know whether nextDouble produces pairs of consecutive equal >> numbers with the correct probability, remembering that it is based on a [quoted text clipped - 3 lines] > PRNG the system author happened to like? In the latter case, your > question may have multiple answers. Random's nextDouble is specified to be based on this method: synchronized protected int next(int bits) { seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); return (int)(seed >>> (48 - bits)); } seed is a long. Each call to nextDouble uses a next(26) and a next(27). You can see a lot of this information in the Random API documentation at http://java.sun.com/j2se/1.5.0/docs/api/java/util/Random.html Patricia Patricia Shanahan wrote On 11/06/07 20:38,: > [...] >>Is nextDouble based on *A* specific PRNG, or is it based on whichever [quoted text clipped - 14 lines] > You can see a lot of this information in the Random API documentation at > http://java.sun.com/j2se/1.5.0/docs/api/java/util/Random.html Note that java.util.Random is not final, and neither is its next() method. This is (presumably) deliberate: by extending Random and reimplementing next(), one can get Random's nextDouble() et al. to use a different PRNG. (java.util.SecureRandom does exactly this, although it also overrides and/or adds some other methods, too.) SignatureEric.Sosman@sun.com >Random's nextDouble is specified to be based on this method: > [quoted text clipped - 10 lines] >at >http://java.sun.com/j2se/1.5.0/docs/api/java/util/Random.html Interesting. With a 48-bit seed, there can only be 2^(48-53) of all possible normal Doubles in [0, 1} returned by that Random; not-perfect. That suggests another not-perfect implementation for the OP. Random should return all values in [0, 0.5] with equal probability, and some others too. So, expressed in Javascript (which I can write <g>?) : while ((R = Math.random()*2) > 1.0) {} or do (R = Math.random()*2) ; while (R>1.0) Disadvantages : LSB of R mantissa is always zero Takes average of two loops If Math.random were perfect, could take infinite loops, improbably Advantages : Short By inspection, will clearly generate R in [0, 1]. Signature(c) John Stockton, Surrey, UK. *@merlyn.demon.co.uk / ??.Stockton@physics.org Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links. Correct <= 4-line sig. separator as above, a line precisely "-- " (SoRFC1036) Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036) > I've been searching at the Internet, and in this newsgroup about this > issue, but have not been able to find what I'm searching... > > What I need is to generate a lot of random real numbers between 0 and > 1, both inclusive (normally it's possible to generate the number > between 0(inclusive) and 1 (exclusive!!!) ) private static Random rng = new Random(); ... double r = rng.nextInt(1000000001)/1000000000.0; or something similar. Arne On 4 Nov., 21:35, Arne Vajh?j <a...@vajhoej.dk> wrote: > > I've been searching at the Internet, and in this newsgroup about this > > issue, but have not been able to find what I'm searching... [quoted text clipped - 10 lines] > > Arne Hi.. And thanks.. Have you got an idea of how big the numbers should be chosen (what is the maximum, and would it take longer time to generate?) /peter >>> I've been searching at the Internet, and in this newsgroup about this >>> issue, but have not been able to find what I'm searching... [quoted text clipped - 8 lines] > Have you got an idea of how big the numbers should be chosen (what is > the maximum, and would it take longer time to generate?) With int you can go up to 2 billion. With long you can go up to a very big number. It should be very fast. Note that if you need the low bits of the double to be uniform distributed you need to use at least 2^53 and therefore long. Arne > Hi.. > [quoted text clipped - 8 lines] > > /Peter Are you really sure about the requirements? If we forget limitations of computational technology the chance to get 1 is infinitesimal. As such for any practical purposes you should be able to exclude 1 and be perfectly happy with results. Even if we take into account the fact that you don't get fine grained results the chance to get 1 is still very close to 0 for any practical purposes. Best Regards, Leonard Milcin SignatureIt is wrong always, everywhere, and for anyone, to believe anything upon insufficient evidence. -- William Kingdon Clifford Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.