How can I compute logarithm when comparison is undecidable?

Question

In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively:

newtype ArbReal = ArbReal {approximate :: Word -> Integer}
data ArbComplex = ArbReal :+ ArbReal

For the ArbReal type, the ArbReal constructor labels a function that, when fed an integer $n$, computes the encoded real number to $n$ decimal digits below the decimal point, rounded. For example, when ArbReal f = pi, f 0 = 3, f 1 = 31, f 2 = 314, and so on.

Note that there is no guarantee to the direction of rounding. Given ArbReal g = 0.5, g 0 can be either 0 or 1. This is inevitable, for if there were, an interval would be decidable.

ArbComplex encodes a complex number by specifying its real part and imaginary part.

I've successfully implemented addition, subtraction, multiplication, and division on both types. Division by 0 falls in an infinite loop, though.

I also implemented nth root function of real numbers, square root function of complex numbers (where branch cut doesn't exist, hence multivalued), and $\pi$.

Now it's time to implement natural logarithm (on complex numbers, without a branch cut). And that's where a problem emerged. I was implementing the algorithm (namely, AGM iteration) in this paper, but:

Finally, if $0< x <1$, we may use $\log(x) =−\log(1/x)$, where $\log(1/x)$ is computed as above.

This paragraph forces a comparison, which is undecidable. So it's impossible to implement the algorithm directly. Indeed, in my current version of implementation, $\log 1$ falls in an infinite loop.

Is there a tweak on the algorithm that makes the algorithm computable? Or must I implement a completely different algorithm?

Answer 1

Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range.

For example, you should be able to tell that $x$ definitely falls into at least one of the ranges $A = \left(0,\frac{3}{4}\right]$, $B = \left[\frac{1}{2},\frac{3}{2}\right]$, or $C = \left[\frac{5}{4},\infty\right)$ with little difficulty. Use AGM if it's in $C$, the transformation if it's in $A$, and if it's in $B$, use this transformation:

$$\log (x) = \log (2x) - \log 2$$

Answer 2

Logarithm is undefined for x<0 and -infinity when x=0, that’s something you have to handle somehow. For the test x < 1: whatever approximation you use for x >= 1 will most likely work for x > 0.9999. You don’t need to decide if x < 1, just if x is small enough. For x = 0.99995 either decision will work.