Scanning for π

In a previous episode, we looked at how we could use random sampling to get a good estimate of , and found that we couldn’t, really, unless using zillions of samples. The imprecision of the estimated had nothing to do with the “machine precision”, the precision at which the machine represents numbers. The method essentially counted (using size_t, a 64-bits unsigned integer—at least on my box) the number of (random) points inside the circle versus the total number of points drawn.

Can we increase the precision of the estimate by using a better method? Maybe something like numerical integration?

Amicable Numbers (part I)

I know of no practical use for Amicable numbers, but they’re rather fun. And rare. But let’s start with a definition. Let be a natural number (a positive integer), and let

with and , be the sum of the divisors of . We’re in fact interested in the sum of the proper divisors of , that is,

Now we’re ready to define amicable numbers!

Amicable numbers: Two numbers, are amicable, if, and only if, and .

Given , we can find and test if . But to do that efficiently, we need to compute (or ) very rapidly. The first expression above requires , but we can do much better. Let’s see how.

Computing Binomials (Part I)

We often start thinking about something, make some progress, and eventually realize it’s not going anywhere, or, anyway, the results aren’t very phrasmotic—certainly not what you hoped for. Well, this week’s post is one of those experiments.

So I was wondering, how can I compute the binomial coefficient, , and minimize the size of the integers involved?

Of Drunkards

In a city with orthogonal streets and regular city block, a party-goer leaves a bar and walks back home. His home is North East from the bar, blocks up, and blocks east. At each intersection, he decide to go either north or east randomly—but whatever’s left of his sobriety keeps from backtracking: he always moves closer to home. How many ways can the drunkard get get back home?