Research News, September 1997

Previous News Next News

Return to Research News Index

September 1997 Issue.

[9/09/97] The binary GCD algorithm. In the July issue, we had a pointer to a "beta test" version by Knuth of the analysis of the binary GCD algorithm. Knuth's document has disappeared, a good sign that the printing of the new edition of Volume 2 of The Art of Computer Programming is under way... The "beta test" notes should be part of Section 4.5.2 of the future edition. (Fortunately, we had snatched a version of it and offer it discreetly here till somebody complains.)



Recall that the binary gcd algorithm uses only subtraction (between odd numbers) and divisions by powers of two, that is binary shifts. By analogy with the usual gcd algorithm, we expect the average complexity to be of the asymptotic form

b N log N Richard Brent has published in 1976 (in Algorithms and Complexity: New Directions and Recent Results, J. F. Traub editor, pp. 321-355) an analysis that is based on operator methods and a continuous model believed to describe what goes on asymptotically. Roughly, one step of the algorithm is viewed as an operator that transforms probability measures on the real line. (This is like in the classical Euclidean algorithm.) Iterations of this algorithm correspond to powers of the operator and you look for the dominant eigenvector (giving an invariant measure) that corresponds to the eigenvalue 1. Keywords are thus: operators, functional spaces, spectrum, dominant eigenvalue, etc. Brent had worked out in 1976 a highly plausible model accounting for the behaviour of the binary gcd algorithm.

Here's a story that happened recently in the background, of the type that doesn't make it usually to serious books. :-) In his original paper Brent proposed several ways to approach the determination of the magic constant b. That week of July 14th, Knuth and Brent were working in parallel with two different methods to estimate theses constants. Now, something strange kept happening. The two methods would produce values in agreement for about 12 digits, but never more. It'd seem perhaps one of the two programs had to have a small mistake, or that some unexpectedly wild numerical instability was striking!! Independently, Brigitte Vallée and Philippe Flajolet motivated by an earlier writeup of Knuth's "beta test" made available on the web, had decided to send their observations by e-mail. All this within hours of the time when Knuth in California and Brent in Australia were starting to suspect that something was going wrong with the two methods.

Nobody seems to have full answers yet. What happens is that at least the functional space on which Brent's operator acts, as considered by Brent in 1976, is a bit too small, a fact noted by Vallée. Indeed, periodic fluctuations should be there. Very roughly, the binary gcd involves harmonic sums with frequencies that are powers of two. In many other contexts (like tries and radix exchange sort), this has long been recognized as leading to small fluctuations, and probably the best approach is via Mellin transforms. Such fluctuations are often small, easily passing unnoticed. Here, it can be proved for instance that already at the first stage of the binary gcd, these fluctuations are precisely of amplitude about 10^(-12). Thus the observations of Vallé'e and Flajolet were providing a somewhat plausible reason for the discrepancy observed between the two methods. Indeed, only one of the two was right, the other one off by a tiny tiny amount due to the "wobbles", and the correct value eventually agreed upon by Brent and Knuth b is

b = 0.70597 12461 01916 39152 93141 or just about.

Brigitte has an analysis conditioned upon a few highly plausible conjectures that agrees very well with numerical computations of Richard and Don while explaining otherwise unsuspected relations between various structure constants of the binary gcd algorithm. Many questions remain, and we hope that a complete analysis will be available in the near future. These problems are tricky, though! Perhaps Richard and Brigitte can tell us more about what goes on on the bulletin board.



[10/09/97] Wobbles. Talking of forgotten "wobbles", there's the absolutely wonderful book Ramanujan: Twelve lectures suggested by his life and work, by G. H. Hardy (Chelsea 1978). Years ago, Bob Sedgewick pointed out to me a counterexample by Hardy to a fallacious (but of course clever!) "proof" of the Prime Number Theorem that's relevant to our discussion. Hardy's counterexample deals with solutions of functional equations of the form

f(2x)-f(x)= a(x), with f the unknown function. Though one can come up easily with formal series solutions, the actual solutions normally involve periodic functions of log(x) and are thus nonanalytic at 0.

We have by now perhaps some 50 instances of this phenomenon in analytic combinatorics and analysis of algorithms. Mellin transforms are a great help, here. For quite general reasons, fluctuations associated with "smooth" functions a(x) are invariably of a very small amplitude. There is precisely a phenomenon of this sort in the binary Gcd algorithm. As a bit of self-advertisement cannot hurt, I'll point to the "Flagodu" paper (Flajolet, Gourdon, and Dumas, Theoretical Computer Science 114, pp 3-58).

[18/09/97] Why care about wobbles?. If you build a trie on random strings built from random bits say with probabilities p,q with p+q=1, something funny happens: the expected size of the trie grows like C . n precisely when the ratio logp/logq is irrational (this has been known since at least 1986). If the ratio is rational for instance when we have unbiased bits, then there is a tiny fluctuation in the "coefficient" of n. Since no statistical model can be accurate enough to decide such an irrationality property, perhaps the question is even meaningless from a practical standpoint. This may incite the more pragmatically inclined to think that this pursuit of wobbles is nothing but a somewhat vacuous game.

Well, there are several answers to this. First, thanks to the collection of methods that we now know (Mellin transforms, techniques a la Delange, Poisson summation formula, etc), it is at present much easier to come up with a precise analysis than to fiddle endlessly with upper and lower bounds exhibiting a mysterious gap that can never be filled.

More importantly, when such periodicities are present, say in expectation estimates, they strongly influence even the order of growth of variances. A common situation, for instance for the size of a trie built on unbiased bits, is that the mean and the second moment are respectively of the form

C.x+x.P(log x), D.x^2+... Variances usually involve cancellations between the second moment and the square of the fisrt moment. In such a case, the order of growth of the variance can no longer be obtained if wobbles are neglected. Thus, these tiny wobbles eventually determine the fact that a variance is O(n^2) or just O(n). For this reason, some early analyses around 1980 of the "tree protocol" (an adaptation of the trie idea to communication theory due to Capetanakis-Tsybakov-Mikhailov) were wrong: the tree protocol was believed for some time to be much more unstable than it is really. In fact, it has a rather tame behaviour due to a low variance that arises precisely from such cancellations.

Cancellations, when they occur, are often related to highly nontrivial identities. For instance the functional equation of Dedekind's eta-function plays a role, as do celebrated identities of Ramanujan's regarding zeta(2N+1). Here are some instances where this phenomenon was encountered (in papers of Kirschenhofer, Prodinger, Schoissengeier, Szpankowski as well as in theses of Werner Schachinger and Friedrich Hubalek in Vienna): path length in tries, patricia tries, digital search trees; size of tries and b-tries; leaves in digital search tries [an old problem of DEK].

With things like modular transformations, Ramanujan identities, and such, the analysis of "wobbles" is thus in pretty good company! Here is a last example that arises in recent works of Clement, Flajolet, and Vallée. Build a trie on the continued fraction representations of n random real numbers; then the growth rate of the second order asymptotic term in the expected size of a continued fraction trie is directly related to the location of zeros of the zeta functions, hence the determination of its order of growth is strictly equivalent to the Riemann hypothesis!



[21/09/97] Optimal directed trees. I haven't had much time yet to report on the Random Structure and Algorithms conference that took place in Poznan in August 1997. Nice, as always! Here is a cute result due to Jennie Hansen in Edinburgh.

Consider n points with random weights placed independently on all directed edges connecting them (no geometry implied, just abstract graphs). Look at the optimal tree, that is the minimal cost directed tree that uses all n the nodes. What is its cost? This has a flavour similar to the minimum spanning tree problem, except that edges here are directed. Well, Hansen has very precise probabilistic characterizations of this optimal cost, including conditions for asymptotic normality.

Jennie's argument starts with the idea of taking all mimimum cost edges starting from each node. If you assemble these edges, you get a mapping, and loo and behold, under the independence assumption, that mapping is a random mapping. Now, we know quite a bit about random mapping. For instance, a random mapping of size n has with high probability a large component of size about 0.6n. If we open the cycles of this mapping, we thus get a partial forest with a few missing edges and at least a tree of a reasonable size; all this built only out of edges of minimal costs! Thus, we're in pretty good shape. Jennie's paper shows that you can patch this construction (with high probability) in an algorithmic way, adding only edges of relatively negligible cost. And we're home... Her paper is an interesting illustration of the interplay between probabilistic and algorithmic ideas. We don't analyse an algorithm here; rather, we design an algorithm to analyse a probabilistic problem!



[28/09/97] Local and central limit laws. When considering limiting probability distributions, probabilists usually think of central limit laws corresponding to convergence of distribution functions to the cumulative distribution function of a Gaussian variable (the error function, "erf"). This approach is consistent with the classical continuity theorem of probability theory after which such a convergence in distribution (also known as weak convergence) is equivalent to convergence of characteristic functions. However, asymptoticians tend to have a different picture in mind: if one represents the histograms of a collection of discrete distributions, usually these converge to the characteristic bell-shaped curve: in this case, we say that a local limit law holds. It is a fact of experience, though theory seems to be lagging behind, that a local limit law usually accompanies a central limit law in many if not most discrete problems.

In the August issue of Research News [RN-08/97], I have discussed the contraction metrics approach thanks to which Michael Cramer had derived a central limit law for Mergesort. I failed to mention a recent paper of Hsien-Kuei Hwang that appeared in Random Structures and Algorithms, vol 8, July 1996, pp 319--336. There, Hwang derives very precise estimates for the generating function of costs of the standard (recursive top-down) Mergesort. As a consequence, he gets both a central limit law and a local limit law.

Hsien-Kuei's local limit law is obtained by means of Cauchy coefficient integrals to which the saddle point method is applied. I was amazed to discover some time ago, that in essence, this approach, nowadays familiar to analytic combinatorialists (Danièle Gardy has several papers on this topic) has in fact some of its roots in Laplace's Théorie analytique des probabilities published in 1812! In the case of mergesort, though the intuition of what goes on is natural (a large number of recursive calls contribute independently to randomness and the generating functions involve products of a large number of somewhat similar-looking factors), the problem is not that easy due to the periodic fluctuations involved.

At any rate, we now know quite a bit about Mergesort, one of the simplest algorithm belonging to the divide-and-conquer paradigm: the mean and variance exhibit fractal fluctuations; the limiting distribution of the number of comparisons is Gaussian, and both a local law and a central law hold.