Random-Number Generator: Function that generates uniformly-distributed random numbers.
Remember — RNG functions implemented as computer programs aren’t truly random, only pseudo random. All computers are deterministic (same input always gives the same output).
This is the lead-up to Monte Carlo algorithms; which are algorithms which use probability to solve complex problems.
Aside — Chaotic Functions: Tiny changes in the input generate unpredictable changes in the output.
- Chaotic functions can be deterministic, so don’t mix it up!
UNIX uses this pseudo RNG function:
x_0 = \text{seed} \\ y = x_{n+1} = (Ax_n + B) \mod 2^{31}
You usually want to pick an A and B that are coprime (they don’t share any common factors), because TODO.
Note — Random.org is a good source for true random numbers.
Problem: Compute the integral.
(Used for integrating explicit functions)
Explanation: The integral is the area under the curve. Geometrically, this is \text{Area} = \text{Width} \times \text{Avg. Height}
We previously approximated the integral using [\frac{(f(a) + f(b))(b-a)]}{2}
The whole point of f(a) + f(b) is to poorly estimate the height.
Instead, we can sample the function’s height at n random uniform points, which changes the approximation to:
\frac{(\sum_i^n f(x_i)}{n} (b-a)
It is SUPER important that you select these points from a uniform distribution. Otherwise, you are introducing bias.
Every time you use a biased selection method, there is an input to fool it.
We increase accuracy by increasing the number of points, rather than increasing the number of trapezoids, which is less work.
Q:
f(x) = x^2 + 3x + 1, \quad a=1, \quad b=2
A:
Here are the random numbers we’ll use:
1.39345
1.59651
1.96963
1.91880
1.79424
1.95752
1.83763
1.57461
1.63042
1.07487Note — We just generated these numbers with Random.org, by adding one to the floating points it gave us, to get it in range.
TODO MISSING SOLUTION STEPS HERE
\int_1^2 f(x) dx = 8.75132501248 ???
Aside — For reference, the actual value is 7.8\overline{3}.
You’ll find out this is worse than Richardson’s for this simple problem. But, multi-variable functions benefit greatly.
=== Professor now began talking about 3D area under a shape? ===
If you do this like the trapezoid problem, you’ll be doing a crapton more work computing tons of little prisms.
If you do this with Monte Carlo, the work stays the same.
Example: Multi-Variable Integration
Q:
f(x,y) = 3x^2 + 5y + 1
Integrate over 0 \le x \le 2, 1 \le y \le 2
A:
We can see this is a half pipe diving to the right.
\int_1^2 \int_0^2 (3x^2 + 5y + 1) dx dy = \int_1^2 (x^3 + 5xy + x) |_0^2 dy \\ = \int_1^2 10y + 10 dy \\ = (5y^2 + 10y)|_1^2 \\ = 25
The only special thing we did was solve x and treat y as a constant
A: Now we’ll do it again but with Monte Carlo Integration
We’ll generate twenty random numbers (ten numbers for x, and ten numbers for y).
Remember — To get numbers in range, we’ll have to use multiplication/division/addition/subtraction.
x_1 = 1.74254 \\ x_2 = 1.1909 \\ x_3 = 0.73206 \\ x_4 = 0.74202 \\ x_5 = 0.77804 \\ x_6 = 1.9432 \\ x_7 = 1.15826 \\ x_8 = 1.93952 \\ x_9 = 1.6486 \\ x_{10} = 1.85054 \\
y_1 = 1.24556 \\ y_2 = 1.48978 \\ y_3 = 1.615108 \\ y_4 = 1.23733 \\ y_5 = 1.6437 \\ y_6 = 1.26651 \\ y_7 = 1.8392 \\ y_8 = 1.81442 \\ y_9 = \\ y_{10} = \\ TODO finish copying random numbers
??? = 16.33713695
??? = 12.6834 TODO
??? = 10. TODO
??? = 8.838 TODO
??? = 11.0345 TODO
??? =
??? = 14.200 TODO
??? = 19.135263434912 TODO
??? = 18.22574588
??? = 20.5268948748
–
NOw let’s compute
\frac{\sum_i f(x_i, y_i)}{n} = \frac{150.3261015198}{10} = 15.03261015198
Therefore, the volume that we are looking for is the above number times 2 times 1. (TODO why? something to do with the area of the base of the shape formed by the limits?)
30.06522
“Four lines of code, basically, but very effective”
(Used for implicit volumes/shapes)
Explanation: You can’t do “area under the X” for a closed surface like a sphere, though we’re basically doing the same thing but in 3D (and the same reasoning applies to higher-dimensions).
Steps
V_s \approx \frac{k}{n} V_{\text{box}}
Q:
x^2 + y^2 + (z-1)^2 = 1
A:
This is a sphere centered at (0,0,1) with a radius of 1.
The bounding box will be 2x2x2.
We need to generate n random points in this box. Mathematically, this means generating points (x_i,y_i,z_i) where 1 \le i \le n, that follow these contraints:
\text{In Bounding-Box?} \begin{cases} -1 \le x_i \le 1 \\ -1 \le y_i \le 1 \\ 0 \le z_i \le 2 \\ \end{cases}\\~\\ \small \textit{(just a formal way of saying, "the points must be in the box")}
To check if a point is inside the sphere, we must check if is this is true:
\text{In Sphere?: } x_i^2 + y_i^2 + (z_i-1)^2 \le 1 \\~\\ \small \textit{(just a formal way of testing if a point is inside the sphere")}
TODO Align notation. V_box is my thing, V_c is what we actually did in class.
We’ll do twenty points.
TODO I’ll do this myself later dawg, I do not want to copy these damn points down.
To get the points in range, multiply by 2 and subtract 1.
In class we got like \frac{11}{20}(8)=4.4 ^ this result from class (to be overwritten by my work) is pretty lucky, because the range could’ve been ??? to ???.
The true volume is 4.18879
Suppose the intersection of this conical shape cutting into the sphere.
\begin{aligned} x^2 + y^2 + (z-1)^2 &= 1 \\ \sqrt{x^2 + y^2} &= z^2 \end{aligned}
We want to find the area of the shape formed by the intersection.
TODO draw this stumpy icecream cone looking thing
Q: Find the volume
A:
The box will be the same size as before, so the constraints for the random points are the same.
The differnce is the constraints to check if points fall in the ice cream cone will be
x^2 + y^2 + (z-1)^2 \le 1 \\ \sqrt{x^2 + y^2} - z^2 \le 0
Note we moves the z^2 term left in the bottom function for niceness ??? TODO
Aside — The real volume is just V_c + \frac{V_s}{2}.
V_c = \frac{1}{3}\pi r^2 h = \frac{1}{3} \pi \\ V_s = \frac{4}{3}\pi r^3 = \frac{2}{3} \pi \\~\\ V_{ic} = \pi
Here are the twenty random points we’ll use:
Modify the following table of random numbers to be in the respective 3 ranges:
[-1,1] [-1,1] [0,2]
0.95526 0.97036 0.09884
0.63532 0.87558 0.54776
0.72402 0.82532 0.88717
0.30007 0.24039 0.40403
0.64942 0.98282 0.99464
0.49327 0.33884 0.45765
0.03533 0.27944 0.43261
0.52069 0.40464 0.67015
0.45893 0.02859 0.66381
0.80286 0.49054 0.08719
0.69975 0.05308 0.29838
0.34732 0.54225 0.24882
0.42259 0.63095 0.40953
0.11053 0.41241 0.77606
0.29834 0.56380 0.30713
0.04171 0.76315 0.78369
0.14949 0.54690 0.79315
0.82239 0.86686 0.12750
0.51108 0.58095 0.04933
0.20729 0.58790 0.02552In-Range:
0.91052 0.94072 0.19768
0.27064 0.75116 1.09552
0.44804 0.65064 1.77434
-0.39986 -0.51922 0.80806
0.29884 0.96564 1.98928
-0.01346 -0.32232 0.91530
-0.92934 -0.44112 0.86522
0.04138 -0.19072 1.34030
-0.08214 -0.94282 1.32762
0.60572 -0.01892 0.17438
0.39950 -0.89384 0.59676
-0.30536 0.08450 0.49764
-0.15482 0.26190 0.81906
-0.77894 -0.17518 1.55212
-0.40332 0.12760 0.61426
-0.91658 0.52630 1.56738
-0.70102 0.09380 1.58630
0.64478 0.73372 0.25500
0.02216 0.16190 0.09866
-0.58542 0.17580 0.05104x^2 + y^2 + (z-1)^2 \le 1 \\ \sqrt{x^2 + y^2} - z^2 \le 0
f(x,y,z) := x^2 + y^2 + (z-1)^2
g(x,y,z) := sqrt(x^2 + y^2) - z^2
h(x,y,z) := if(f(x,y,z) <= 1, [ if(g(x,y,z) <= 0, [ true ], [false]) ], [false])
h( 0.91052 , 0.94072 , 0.19768 ) = 0
h( 0.27064 , 0.75116 , 1.09552 ) = 1
h( 0.44804 , 0.65064 , 1.77434 ) = 0
h(-0.39986 ,-0.51922 , 0.80806 ) = 0
h( 0.29884 , 0.96564 , 1.98928 ) = 0
h(-0.01346 ,-0.32232 , 0.91530 ) = 1
h(-0.92934 ,-0.44112 , 0.86522 ) = 0
h( 0.04138 ,-0.19072 , 1.34030 ) = 1
h(-0.08214 ,-0.94282 , 1.32762 ) = 0
h( 0.60572 ,-0.01892 , 0.17438 ) = 0
h( 0.39950 ,-0.89384 , 0.59676 ) = 0
h(-0.30536 , 0.08450 , 0.49764 ) = 0
h(-0.15482 , 0.26190 , 0.81906 ) = 1
h(-0.77894 ,-0.17518 , 1.55212 ) = 1
h(-0.40332 , 0.12760 , 0.61426 ) = 0
h(-0.91658 , 0.52630 , 1.56738 ) = 0
h(-0.70102 , 0.09380 , 1.58630 ) = 1
h( 0.64478 , 0.73372 , 0.25500 ) = 0
h( 0.02216 , 0.16190 , 0.09866 ) = 0
h(-0.58542 , 0.17580 , 0.05104 ) = 0TODO I screwed up somewhere, k is supposed to be 9 dawg. ughughughughuhgu
Thus,
\begin{aligned} V_s &\sim \frac{k}{n} V_c \\ &\approx \frac{6}{20} (8) \\ &\approx \frac{6}{20} (8) \\ &\approx 2.4 \end{aligned}
Ugh what the hell did i do wrong.