Transcript wk04.5
Bonus Puzzle #1
Random Doubles [0,5]
Instructor: Scott Kristjanson
CMPT 125/125
SFU Burnaby, Fall 2013
Bonus Puzzle #1
2
Write an expression to calculate double random numbers from
[0, 5.000000000] inclusive
Note: Generating the range: [0, 5.0) is easy:
generator.nextFloat()*5
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 2
Honourable Mentions
3
Some good tries by:
Amritpaul Gill
Gavin Haynes
Adam Tuck
A working solution by Raymond Zeng
• But slow convergence, not guaranteed to ever complete
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 3
And the Winner is….
4
Serena Read:
• Simple elegant well commented solution
• Returns entire range with [0,5] inclusive
• Fast convergence, but still may never terminate
public static float ranNum()
{
Random ran = new Random();
int a;
float f, r;
do{
a = ran.nextInt(6);
f = ran.nextFloat();
r = (float)a - f;
}
while(r<0);
}
return r;
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 4
Scott’s solution
5
Can we improve on Serena’s and Raymond’s solution?
• Want guaranteed convergence
• Want to eliminate loops
• Want to cover the whole range uniformly
(this last bullet is much trickier than you think!)
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 5
BUT DO WE WANT TO SOLVE THIS?
6
What is the practical difference between [0,5) and [0,5] ?
• Remember when you compare floats, we useTolerances
• That means 4.999999 equals 5.000000 within a tolerance
• How many real numbers are in between 4.999999 and 5.000000?
∞
• How many java floating point numbers are in this gap?
ONE : 4.9999995
That is because floats only have 32 bits to represent the number
There is limited precision, and thus limited resolution.
Do we WANT to put all this effort into something whose probability of
occurring approaches zero in the limit?
It took over 2 million tries for Serena’s algorithm to return 5.000000
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 6
Representing Real numbers in Java [2]
7
• Java uses the IEEE 754 standard:
This uses 1-plus form of the binary normalized fraction (rounded).
• The fraction part is called the mantissa.
• 1-plus normalized scientific notation base two is then:
N = ± (1.b1b2b3b4 ...)2 x 2+E
float
double
For a great overview of this standard, see [2] at:
http://people.uncw.edu/tompkinsj/133/Numbers/Reals.htm
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 7
Ok, so you really want to solve this…
8
Only missing a single finite range with [0,5)
If we know the size of this gap,
• We can add it in with 50/50 probability to close the gap uniformly
generator.nextFloat()*5 +
((generator.nextInt() >= 0) ? epsilon : 0);
What’s epsilon?
It is based on the resolution (# bits in real number) plus the
exponent (smaller magnitude numbers have finer resolution).
epsilon = (.5)23 = 0.00000000000000000000001B
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 8
But this assumes nextFloat works as expected…
9
Yes, nextFloat works, but is does not cover the entire [0,1)
space uniformly.
nextFloat produces a random number based on 224 possible
floats within this range (see [3] for details).
However there are really 230 possible floats in the range [0,1)
using the IEEE 754 standard (see [2] for details).
That’s only about 1.6% of all possible floats that get returned.
If you really want to get them all, you will need to add in a 6 bit
random number to the end of what nextFloat returns.
Instead of using a constant Epsilon as in previous slide, it
needs to become a 6-bit random variable.
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
References:
10
1.
J. Lewis, P. DePasquale, and J. Chase., Java Foundations: Introduction to
Program Design & Data Structures. Addison-Wesley, Boston, Massachusetts,
3rd edition, 2014, ISBN 978-0-13-337046-1
2.
Tompkins, J.A. , Java Primitive Data Types - Reals - IEEE754
http://people.uncw.edu/tompkinsj/133/Numbers/Reals.htm
Oracle Reference Pages on the Random Class
3.
http://docs.oracle.com/javase/7/docs/api/java/util/Random.html#nextFloat%28%29
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk04.1 Slide 10