Finding the bits of in logspace

Chee Yap is one of the top experts in various aspects of computational geometry. He has worked on problems as diverse as upper and lower bounds for comparison problems, to algorithms in geometric complexity, to methods to control rounding errors in geometric computations. One of his specialties is in the area of numerical computation from a complexity viewpoint. He was a Ph.D. student of mine many years ago, so I may be biased in the following discussion.

Today I want to talk about a recent paper of Chee on a question I raised earlier here. He has solved the problem and I am quite happy to see that these discussions have helped raise some open problems that are getting solved.

The LEDA project was started by Kurt Mehlhorn years ago to implement geometric algorithms and data structures. It has grown into a major software system that is used by many in research, in education, and in companies.

Kurt told me he almost immediately ran into a serious problem with their first implementation project, which was to implement an algorithm for finding the convex hull in two dimensions. This algorithm takes any set of points in the plane and finds their bounding convex hull in time . The algorithm is due to Ron Graham and is really a type of sorting algorithm. Kurt’s group tested the algorithm on some examples. It worked, and they moved on to more complex algorithms.

Shortly after someone used their algorithm as a subroutine in a more complex computation—let’s call it C. They quickly noticed that C did not always work; sometimes it gave the right answer, but sometimes it did not.

What was going on? Kurt’s group looked into the problem and discovered an issue with their implementation of the convex hull: sometimes the “convex hull” returned was not convex. This is of course impossible—the hull by definition is convex. This meant that their implementation was incorrect. They quickly discovered the problem: certain examples caused the implementation of the algorithm to round incorrectly. Graham’s algorithm was fine, but it assumed infinite precision. They redesigned the implementation and fixed the bug. Now C worked fine.

Kurt said that this accuracy problem became a major issue for the whole LEDA project. They have to be sure that their implementations work given they only have finite precision. They use a variety of tricks: sometimes they use high precision, sometimes they check the answers, sometime they change the algorithms.

Let’s now turn to the problem Chee worked on, which is related to the difficulty that Kurt faced in LEDA.

The BBP Algorithm

In 1995, David Bailey, Peter Borwein, and Simon Plouffe discovered a beautiful algorithm–now called BBP–that computes the bit of the number without first computing any of the previous bits. From the viewpoint of complexity theory they showed that the problem of computing the bit of is in . The latter is “Steve’s Class” named after Steve Cook and consists of problems computable in polynomial time and poly-logspace.

The BBP result was quite unexpected—see my previous discussion on their great algorithm.

The BBP Algorithm Is Not An Algorithm

Their algorithm is wonderful. Or is it? The following remarkable quote is from Wikipedia:

“There is a vanishingly small possibility that a particular computation will be akin to failing to add a small number (e.g. ) to the number and that the error will propagate to the most significant digit, but being near this situation is obvious in the final value produced.”

Excuse me, this is nonsense. The statement “vanishingly small possibility” is a statement of probability theory. There is nothing random here at all. I agree that it seems that the problem may never arise in practice, but that is different. The last point of the quote is correct. But that means that the BBP is not really an algorithm.

For a theorist an algorithm must have two basic properties: it must always compute the correct answer and it must have a provable running time. I am leaving aside randomized algorithms, which have the above properties but with only probabilistic assurances. If your method works on “most” inputs or runs “fast” in practice, then it may be extremely useful, but it is not an algorithm is the strict sense. Thus the BBP algorithm is not an algorithm in our sense.

Yap’s Theorem

Chee has improved the BBP result in two fundamental ways. He shows that can be computed in not just but in logspace. Further he shows that his algorithm really works—not that it just works in practice. Note, Chee’s algorithm is different from BBP’s algorithm, and it remains open if BBP’s exact algorithm works as claimed.

What is neat is Chee uses the notion of irrationality measure to prove his algorithm works, which is an idea I suggested in the original discussion.

This is an inequality that bounds how closely the number can be approximated by rational numbers with small denominators. The rational numbers are dense, so given any irrational number there is a rational number so that

is as small as desired. However, not all irrational numbers are created equal when it comes to how small this approximation can be. If

for all and , this means to get a close approximation to one must have a large .

The standard definition is that has irrationality measure provided

has only a finite number of solutions and . We would prefer to have the above hold for all . But we usually cannot prove this for all, so we settle in the definition for almost all—that is for all large enough.

Theorem: Any number with a positive irrationality measure and a BPP series has an algorithm that computes its bit in polynomial time and space .

See Yap’s paper for the details.

Open Problems

What numbers can be computed in logspace? Can Chee’s theorem be generalized? His paper solves an open problem from this blog and I hope there will be many more in the future.