# How can I compute logarithm when comparison is undecidable?

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?

• To everyone reading this question: It turns out this is a wrong way of implementing the reals. Nov 23 '20 at 7:48

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$$