/sci/ - Science & Math » Thread #11488758

23KiB, 374x327, estimate_pi.png

View Same Google iqdb SauceNAO

Estimating pi by approximating a quarter circle

Anonymous Sat 21 Mar 10:05:46 2020 No.11488758 View Reply Original Report

Quoted By: >>11488854 >>11488950 >>11489274 >>11489462

Is there something strange going on here? Because I think there is.
Running it with n = 10 gives around 3.13226, while n = 100 gives around 2.85846.
What am I missing? I thought this was supposed to get more accurate as n is increased. Does it have something to do with the nature of this series that I'm summing?

Anonymous

Anonymous Sat 21 Mar 2020 10:15:52 No.11488783 Report

Quoted By: >>11488826

rounding errors probably
define variables with larger bit usage
https://www.youtube.com/watch?v=pQs_wx8eoQ8

Anonymous

Anonymous Sat 21 Mar 2020 10:18:19 No.11488788 Report

Quoted By: >>11488826

No need to keep the variable prev_y

Anonymous

Anonymous Sat 21 Mar 2020 10:42:29 No.11488826 Report

Quoted By: >>11488830

>>11488783
Yeah, you were right anon. I thought javascript numbers could be arbitrarily long and stuff.
Not a programmer.
>>11488788
I guess, but it looks comfy to me :^)

Anonymous

Anonymous Sat 21 Mar 2020 10:44:30 No.11488830 Report

Quoted By:

>>11488826
js makes it all floats, you loose precision pretty quickly (59 bit iirc).
use a big int library instead

Anonymous

Anonymous Sat 21 Mar 2020 11:02:20 No.11488854 Report

Quoted By:

>>11488758
The way the algorithm is defined, it should be impossible for f(n) > f(k*n), where n and k are positive integers. The fact that you get this result proves there is some issue with numerical instability.
Because (d_x)^2 = inc^2 (and you know this without having to subtract anything), the only operation causing your instability should be your computation of (d_y)^2, as you are subtracting nearly equal values (y and prev_y).

Anonymous

Anonymous Sat 21 Mar 2020 11:55:32 No.11488950 Report

Quoted By: >>11488975

>>11488758
I copied your algorithm into Java and Python, and they both fuck up at exactly n = 35. Can someone give a detailed explanation as to why that is?

Anonymous

Anonymous Sat 21 Mar 2020 12:01:57 No.11488966 Report

Quoted By:

Additionally, your computation of y could be an issue when x gets close to 1.
The best thing you can do here is to try and find a formula that doesn't rely on subtraction. First, we want to compute equally spaced points on the circumference using some formula that doesn't rely on subtracting nearly equal numbers. We can recursively compute these points by taking a pair of neighboring circumference points, taking the average of those points, and then normalizing that average point using its euclidean distance. If we start with the points (1,0), (0,1), (-1,0) and (-1, -1), then the euclidean distance will always be sqrt(2)/2 or greater, so we don't have to worry about computing square roots of small numbers. Next, we will want to change our perspective on the formula. Instead of computing the straight line approximations between the circumference points (that involves subtracting nearly equal numbers), lets approximate the area of the regular polygon inscribed in the circle, with vertices defined by our points. Starting with the area of the diamond, which is 1, we see that the area of the next regular polygon, the octagon, is sqrt(2) times the area of the diamond. In fact, the next area of the 2^n+1 - gon will always be the area of the 2^n - gon times the reciprocal of the euclidean norm of the arithmetic mean of a neighboring pair of vertices on the 2^n - gon. This method of computing the area of the circle (which is pi*(1)^2) only takes square roots of numbers larger than sqrt(2)/2, it only needs addition, multiplication, and division, hence, it will fix your numerical stability issues.

Anonymous

Anonymous Sat 21 Mar 2020 12:04:56 No.11488975 Report

Quoted By: >>11489001

>>11488950
His algorithm subtracts nearly equal numbers as the increment gets smaller and smaller. Subtracting nearly equal numbers causes catastrophic cancellation, which is the only explanation for why the algorithm can return smaller approximations as n goes from 10 to 100.

Anonymous

Anonymous Sat 21 Mar 2020 12:24:06 No.11489001 Report

Quoted By: >>11489015 >>11489030 >>11489495

>>11488975
but why exactly 35? Does it have to do with the IEEE floating point standards?

Anonymous

Anonymous Sat 21 Mar 2020 12:31:51 No.11489015 Report

Quoted By:

>>11489001
Increasing the number of bits in the mantissas of your floating point numbers should only improve a finite number of your summands. Even if you switched from single precision to double precision, you would most likely still see those catastrophic cancellation problems at the same point.

Anonymous

Anonymous Sat 21 Mar 2020 12:38:59 No.11489030 Report

Quoted By:

>>11489001
Specifically, they should only improve summands where the mantissas look almost the same in single precision, but are quite different in double precision. No matter what size mantissa you are using, you can use the loss of significance formula to figure out how many sig figs you lose.

Anonymous

Anonymous Sat 21 Mar 2020 14:40:02 No.11489274 Report

Quoted By:

>>11488758
Nibba just use romberg

Anonymous

Anonymous Sat 21 Mar 2020 16:00:18 No.11489462 Report

Quoted By: >>11489546

>>11488758
Rounding error in your while condition. For certain values of N, prev_x + inc will be slightly greater than 1 on the last step and be skipped.

try integer math:

i = 0
while (i < n) {
i = i + 1
x = i/n

Anonymous

Anonymous Sat 21 Mar 2020 16:17:11 No.11489495 Report

Quoted By: >>11489546

>>11489001
python -c $'x=0\nfor i in range(35):x+=1.0/35.0\nprint("%.17f"%x)'

1.00000000000000022

Anonymous

Anonymous Sat 21 Mar 2020 16:42:32 No.11489546 Report

Quoted By:

>>11489462
>>11489495
This is correct
it seems wrong at first, because it would imply that, for n = 100, that the 100th term contributes 9% of the total. However, that really is the case, because the orthogonal projections are uniform length, not the chord lengths. The chord lengths get much longer as the slope gets steeper.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches