Show full content
Approximating 
We can derive a good approximation using continue fractions, series, or some spigot algorithm. We can also use Monte Carlo methods, such as drawing uniformly distributed values inside a square, count those who falls in the circle, then use the ratio of inside points to outside points to evaluate
If we count the number of (discrete) points inside a circle, one by one, that would be an 
Using Bresenham’s midpoint circle algorithm, and symmetries, we can cover an 
We have to be a bit careful on the symmetries, as the algorithm works only on one eighth of the circle. If 
A quick implementation would look like this:
// c++20
#include
#include
#include
template T sqr(const T & x) { return x*x; }
int main()
{
int64_t r=1'000'000'000;
int64_t x=0;
int64_t y=r;
int64_t oy=0; // old y
int64_t d=5-4*r; // everything times 4 to avoid fractions
size_t s1=0;
size_t s2=0;
while (x<y)
{
s1+=y;
if (d<0)
d+=4*x+6;
else
{
d+=8*(x-y)+20;
y--;
}
x++;
if (oy!=y) // symmetry
s2+=x;
oy=y;
}
double pi_est=4.0*(s1+s2-r/2)/sqr(r);
std::cout
<< (s1+s2) << '/' << sqr(r) << std::endl
<< pi_est << std::endl
<< pi_est-std::numbers::pi << std::endl;
return 0;
}
The output is:
time a.out 785398163690333774/1000000000000000000 3.14159 -8.28458e-10 real 0m0.412s user 0m0.412s sys 0m0.000s
The interesting thing about this algorithm is that it is 
, if 
is the arity (or branching) of the tree. Intuitively, we know that if we increase 
keys, and for each, we must do comparisons for lower-than and equal (the right-most child will be searched without comparison, it will be the “else” of all the comparisons). We must first understand how these comparisons affect average search time.
is smaller than a key 
; one to test if they’re equal. If neither tests is true, we move on to the next key. If none of the tests are true, it is an “else” case and we go down the rightmost branch. That scheme does way more work than necessary and would ask for 
comparison per node (because there are 
,
(as we can treat 
as a constant, since we’re not optimizing for 
):
is the optimal solution.
,
the comparison cost, and 
, the cost of accessing the node. We can set 
. Now, luckily for us, this function is convex in 
,
.
and 
, one axes being 
.
ths. To express the result correctly in 
.
, everyone at a cost of 
products (
for 
, plus one for 
). When you sum over all 
products (and 
additions) for a polynomial of degree 
,
, but you can easily adapt the splitting for an arbitrary degree. The first step is to split the polynomial into binomials, each of which are evaluated in parallel. You then combine those into new binomials, also evaluated in parallel, and again, until you have only one term left, that is, the answer.
,
(and its logarithm) keep showing up in the analysis of algorithm. Unfortunately, it’s very often unwieldy, and we use approximations of 
) to simplify things. Let’s examine a few!
,
,
.
.
.
.
.
into the square root; so it’s a good numerical trade off. However, “Stirling More” and Mohanty & Rummens’ compare with a slight advantage to the later.
.
to 
) (in appropriate luminosity units), others, like Fein and Szuts[
to 
). Depending on the range, that’d yield
bits,
bits.
in the figure, only a certain range can be perceived (with lower range marked as 
). That range seems to be only 4, or 5 order of magnitude, so only
bits.
