Exact Arithmetic using Continued Fractions

[KevB]

I've recently started development on a continued fraction based exact arithmetic computational package. This is work based on Bill Gosper's HACMEM algorithm and Peter Potts' Mobius transforms with significant modifications. These algorithms have some remarkable properties and can be made much more efficient. Some enhancements I've developed include the ability to detect patterns which define exact solutions when they exist and a method to automatically compose operations (reducing operation counts significantly).

While these algorithms have been around since the early 70's (HACMEM was written in 1972), they don't seem to be commonly implemented commercially. Are these algorithms used in proprietary software (e.g. Mathematica )? I've seen some simple implementations, but most fail to address some of the issues Bill identified (e.g. non-termination when computing the square of a root).

I intend to release a version of this system to the public domain at some point, but was curious about similar systems that might exist. I'm also interested in applying these algorithms with complex numbers (which should be reasonably straightforward), and wondered if anyone had done this.

 

[explain]

I've recently started development on a continued fraction based exact arithmetic computational package. This is work based on Bill Gosper's HACMEM algorithm and Peter Potts' Mobius transforms with significant modifications. These algorithms have some remarkable properties and can be made much more efficient. Some enhancements I've developed include the ability to detect patterns which define exact solutions when they exist and a method to automatically compose operations (reducing operation counts significantly).

While these algorithms have been around since the early 70's (HACMEM was written in 1972), they don't seem to be commonly implemented commercially. Are these algorithms used in proprietary software (e.g. Mathematica )? I've seen some simple implementations, but most fail to address some of the issues Bill identified (e.g. non-termination when computing the square of a root).

I intend to release a version of this system to the public domain at some point, but was curious about similar systems that might exist. I'm also interested in applying these algorithms with complex numbers (which should be reasonably straightforward), and wondered if anyone had done this.

I'm not sure you can guarantee termination in cases such as computing f(g(x)) where x is integer and f(g(x)) is also integer, but g(x) is transcendental...

There seems to be a conclusion in the literature that CF-based methods are slower than other methods for exact arithmetic.

If you have significant optimizations, this could change everything.

Did you describe your optimizations in any papers? This would be interesting to look at.

 

[KevB]

If you use standard simple continued fractions you see the termination problems that Bill Gosper also described in his write up. I use a hybrid between simple and nearest-integer continued fractions to address this problem. I still need to derive better algorithms for calculations of some transcendental functions (sin and cos) for infinite continued fractions.

While I've done some optimization to combine operations I'm sure this algorithm isn't as fast as conventional IEEE arithmetic. It's not really a fair comparison since IEEE has limited precision. What other exact arithmetic algorithms exist? You also have to consider that most processors have floating point operations in hardware. If the processors were designed with integer matrix operations instead it would be a better comparison.

I'm just starting to write this up. Since I'm only playing with this in my free time it won't be quick.

 

[explain]

Did you look at the work of Potts, Edalat, and others on LCF and Moebius-based methods? I wonder how your approach connects with those.

 

[KevB]

Thank you for your suggestions and comments.

I have looked at methods that use LLT and Mobius Transforms and incorporate many of those ideas into my system. I suppose you could say my system has two components, a computational engine (based on Gosper's algorithms), and a analytic system (based on LLTs). Gosper's algorithm is lazy, which allows one to accumulate the LLTs and combine them where possible through composition.

In some cases, such as computations of logarithms and exponentials, I use an interval method to determine the continued fraction coefficients, but most arithmetic operations don't require this additional overhead. I expect I'll need to use this interval approach for calculations of other transcendental functions (like sin and cos) as well.

The methods outlined by Gosper and the LLT and Mobius Transforms are obviously closely coupled. In my system I've tried to take advantage of each approaches strength. Gosper offers simple, lazy computation, while Mobius transforms provide flexible manipulation.

 

[explain]

There are already some implementations of Gosper's algorithms. For example here:
http://contfrac.sourceforge.net/

What are the problems with Gosper's algorithms that you are primarily trying to solve?

Also, which programming language are you using? Just curious.

 

[KevB]

The application is programmed in Python as a new data type, with all the standard operators overridden. Python has a number of features, like portablility, unlimitted length integer computations, generator functions, and complete object oriented paradigm that makes it attractive. While Python isn't as fast as a compiled language cPython typically is.

I've looked at Creal as well as several other implementations of Gosper's scheme and have exchanged e-mails with some of the developers. Most are not very robust and don't support additional math functions (like log(CF), CF^CF,sin(CF), cos(CF),...)