Scanning for π

August 27, 2013

In a previous episode, we looked at how we could use random sampling to get a good estimate of \pi, 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.

pi-pie

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

Read the rest of this entry »


Amicable Numbers (part I)

August 20, 2013

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

\displaystyle \sigma(n)=\sum_{d|n}d

with d \in \mathbb{N} and 1\leqslant{d}\leqslant{n}, be the sum of the divisors of n. We’re in fact interested in the sum of the proper divisors of n, that is,

s(n)=\sigma(n)-n

Now we’re ready to define amicable numbers!

Amicable numbers: Two numbers, n, m \in \mathbb{N} are amicable, if, and only if, s(n)=m and s(m)=n.

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

Read the rest of this entry »


Computing Binomials (Part I)

August 13, 2013

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.

trombone-small

So I was wondering, how can I compute the binomial coefficient, \binom{n}{k}, and minimize the size of the integers involved?

Read the rest of this entry »


Of Drunkards

August 6, 2013

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, N blocks up, and E 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?

city

Read the rest of this entry »