Statistics of Extended GCD Consider a coprime pair of integers $a, b.$ As we all know ("Bezout's theorem") there is a pair of integers $c, d$ such that $ac + bd=1.$ Consider the smallest (in the sense of Euclidean norm) such pair $c_0, d_0$, and consider the ratio $\frac{\|(c_0, d_0)\|}{\|(a, b)\|}.$ The question is: what is the statistics of this ratio as $(a, b)$ ranges over all visible pairs in, for example, the square $1\leq a \leq N, 1 \leq b \leq N?$
Experiment shows the following amazing histogram:
EDIT by popular demand: the histogram is for an experiment for $N=1000.$ The $x$ axis is the ratio, the $y$ axis is the number of points in the bin. The total number of points is $1000000/\zeta(2),$ so there are $100$ bins each with around $6000$ points.
But no immediate proof leaps to mind.
 A: Here's a more geometric formulation of your question:
On the torus $\mathbb R^2/\mathbb Z^2$, consider a long simple closed geodesic
$\overline {(0,0)(a,b)}$. It cuts the torus into a thin cylinder; the cylinder is joined
to itself by a twist by some angle to form the torus.  What is the distribution of the
angle of the twist?
From this perspective, perhaps your intuition tells you that the angles of twist should
tend toward the uniform distribution, as the homotopy classes of geodesics are chosen
uniformly with longer and longer lengths.
To get a rigorous argument, we can think about the problem from the opposite direction.
Begin by starting from a long thin annulus of area 1, and ask what are the ways to glue it together to form a torus? You can glue it by any angle; however, the torus you get is not usually isometric to the square torus; but it is isometric to $\mathbb E^2$ modulo
some lattice of area 1.
The space of lattices up to similarity in $\mathbb E^2$ together with a choice of positively oriented generators is the Teichmüller space for the torus, and can be identified with the hyperbolic plane, in the upper halfspace model:  make the first vector go from $0$ to $1$ along the $x$-axis, and the second vector will be a point $z$ in upper half space.
Change of generators acts by fractional linear transformations, and preserves the hyperbolic
metric; the quotient is the space of isometry classes of Euclidean tori of area 1, the
moduli space of the torus.
Twisting an annulus is a well-studied operation, the horocycle flow, on the moduli space.
The action preserves a probably familiar tiling of the hyperbolic plane by ideal triangles
whose vertices are at rational points on the bounding line, completed to make
$\mathbb {RP}^1$, and whose edges connect pairs of slopes corresponding to your equation.
The points in Teichmüller space that give square toruses are the midpoints of the edges.
(Actually, the edges are infinitely long, so they don't have an obvious definition of
midpoint, but the triangles have altitudes whose feet we can call the midpoints: these
are the square toruses).
In any case: if you look at all lattice vectors with length between say $N$ and $2N$,
and ask for the distribution of angles among these, this is equivalent to taking
all points representing square lattices in a band in Teichmüller space between
horocycles that appear in upper half space as a rectangle
bounded by  horizontal lines at height $1/N$ and $1/2N$ and vertical lines  $x = \pm 1/2$; the question is
the distribution of $x$-coordinates of points representing square toruses within that
band.  That this tends to the uniform distribution follows from
ergodicity of the horocycle flow, a well-known fact whose history probably predates the sources I'm familiar with, so I won't try to give the attribution.


*
 - 

A: I did a little experiment. Fix $a=29$, let $b=1,2,\dots,28$. So, you get 28 data points. Well, these points are already extremely regularly distributed. Taking just the first half, $1\le b\le14$, and rearranging the ratios in increasing order, they are (to three decimals) $$.034,.069,.103,.138,.172,.207,.242,.275,.310,.345,.379,.414,.448,.483$$ To three decimals, and modulo round-off errors, these are the numbers $1/29,2/29,\dots,14/29$, which is to say they are about as regularly distributed as possible. The ratios for $15\le b\le28$ are essentially the same numbers - in fact, the ratio for $(a,b)$ seems to be pretty nearly the ratio for $(b-a,b)$. 
If what's happening for 29 happens in general, I think it would explain the original histogram. 
EDIT: So I think I see what's going on. We're looking at the numbers $$\sqrt{c^2+d^2\over a^2+b^2}$$ But $b$ is very close to $-ac/d$ (since $ac+bd=1$), so these numbers are very close to $$\sqrt{c^2+d^2\over a^2+(ac/d)^2}$$ which simplifies to $|d|/a$. For fixed $a$, as $b$ runs through the units modulo $a$, so does $d$, since $bd\equiv1\pmod a$. So our ratios are as uniformly distributed as the fractions $|d|/a$, which is very. 
A: Roughly:
Suppose you have a fraction $a/b$ and you expand it as a simple continued fraction
$1/c_1+1/c_2\cdots+1/c_{n-1}+1/c_n$.  Now truncate the last convergent and collapse
$1/c_1+1/c_2\cdots+1/c_{n-1}$ to get, say, $a'/b'$.  Now consider the simple continued
fraction expansion of $b'/b$.  As I recall, this will (usually? perhaps I need a hypothesis to avoid degenerate cases?) equal the reverse of the continued fraction of $a/b$.  
For complicated fractions the beginning and end of a continued fraction should be almost uncorrelated.  Also for a random fraction the convergents have a known distribution (Gauss-Kuzmin) and reversing the continued fraction doesn't change the distribution of the convergents, so you get the uniform distribution back.   
A: Here is an attempt to give a somewhat finer grained view of the distribution. The set of ratios $\sqrt{\frac{s^2+t^2}{a^2+b^2}} \subset(0,\frac{1}{2})$ are essentially  the values in the first half of the Farey sequence $\lbrace \frac{p}{q} | \gcd(p,q)=1,\ 2p \le q<N\  \rbrace$. This has already been pointed out but I'll give a simple (if less nuanced) justification. Then I'll mention how that sequence is and is not smoothly distributed.
Instead of looking at all the relatively prime pairs $(a,b)$ with $1 \le a,b\le N$ I'll just consider those with $a<b$ since order is irrelevant for the question asked and $(a,b)=(1,1)$ is an extreme outlier. There are non-negative integers $s,t$ with $|as-bt|=1$ and just one such pair with $\sqrt{\frac{s^2+t^2}{a^2+b^2}}<\frac{1}{2}$. This ratio turns out to be very close to $\frac{t}{s}$. Then $(0,0),(t,s),(a,b)$ and $(t+a,s+b)$ are corners of a long thin parallelogram with area 1 and (thus) no integer points on its boundary or interior. Because the sides are very nearly parallel, the ratio $\sqrt{\frac{s^2+t^2}{a^2+b^2}}$ of their lengths is quite close to $\frac{t}{a}$ and even closer to $\frac{s}{b}$ (in fact they are convergents to the continued fraction for that irrational number). So that set of ratios is quite close to the lower half of the set of fractions 

LATER 
For fixed $b$ the discrepency between $\sqrt{\frac{s^2+t^2}{a^2+b^2}}$ and $\frac{s}{b}$ is almost exactly $\frac{1}{b(2b^2+1)}$ for $\frac{1}{b}$ and increases to $\frac{2}{b(4b-1)}$ for $\frac{b-1}{b}$  

Let $\mathcal{H}_N=\lbrace \frac {p}{q} |\frac{p}{q}\le \frac{1}{2} ,\gcd(p,q)=1,q \le N \rbrace$ The letter $\mathcal{H}$ is because this is half a Farey sequence. It is known that $P(N)=|\mathcal{H}_N|=\frac{3N^2}{2\pi^2}+O(N\log N)$. How evenly spaced are these? There are  $P \approxeq \frac{0.15}{N^2}$ points in an interval of width $1/2$ so perfectly even spacing would put the kth point at $\frac{k}{2P}\approx\frac{3.3k}{N^2}$. However a fraction $\frac{p}{q}$ with $q$ small will be about $\frac{1}{qN}$ from the next nearest points. Hence  the largest point other than $\frac{1}{2}$ is $\frac{1}{2}-\frac{1}{N}$ (replace N by N-1 in the even case) and the smallest point is $\frac{1}{N}$ which seems far from $\frac{3.3}{N^2}$  These empty zones force other points closer together, the first few points are only separated by about $\frac{1}{N^2}$. I can't resist an attempt to put in a picture of Ford Circles. A disk of radius $\frac{1}{q^2}$ is centered at $(\frac{p}{q},\frac{1}{q^2}).$ Disks are either disjoint or tangent. One can see the enforced distance around fractions with small denominators. On the other hand, each disk is put into the largest gap present (albeit not exactly at the center). This is a subtle topic. I'll just mention that a conjecture about the distance (in the $\ell_1$ or $\ell_2$ norm) between the sorted vector of Farey fractions and the evenly spaced vector $[0,1/2P,1/4P,\cdots$ is equivalent to the Riemann Hypothesis.
alt text http://www.freeimagehosting.net/uploads/2e24bdc608.png
With the appropriate bin size and placement things might come out fairly even. The chart by the OP uses 100 bins for roughly 608,382 points. As I said, the results should be essentially the same as for $\mathcal{H}_N$. The very first bin is smashed against the y axis but it is below average by 213 and the next two bins are over by about 148 and 30 respectively. It is easier to see that the bin containing $\frac{1}{3}$ ($ 0.330<1/3<0.335$) is deficient from the average by about 95 points (by my calculations) the bin before it is about average but the one after is up by about 68 points. The last bin is under by 33 and the one before it over by 24. My other answer discussed an example made with rounding rather than truncation and a number of bins ($2520=8 \cdot 9 \cdot 5 \cdot 7$) that put simple fractions in the center of a bin. This allowed more choppy behavior.
