3
$\begingroup$

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?

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.