Como posso calcular o logaritmo quando a comparação é indecidível?

Question

Em Haskell, tenho os seguintes tipos de dados que codificam números reais arbitrários e números complexos arbitrários, respectivamente:

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

Para o ArbRealtipo, o ArbRealconstrutor rotula uma função que, quando alimentada com um inteiro$n$, calcula o número real codificado para $n$dígitos decimais abaixo da vírgula, arredondados. Por exemplo, quando ArbReal f = pi, f 0= 3, f 1= 31, f 2= 314 e assim por diante.

Observe que não há garantia da direção do arredondamento. Dado ArbReal g = 0.5, g 0pode ser 0 ou 1. Isso é inevitável, pois, se houvesse, um intervalo seria decidível.

ArbComplex codifica um número complexo especificando sua parte real e parte imaginária.

Implementei com sucesso adição, subtração, multiplicação e divisão em ambos os tipos. A divisão por 0 cai em um loop infinito, no entanto.

Eu também implementei a função de raiz enésima de números reais, função de raiz quadrada de números complexos (onde o corte de ramo não existe, portanto, multivalorado), e $\pi$.

Agora é hora de implementar o logaritmo natural (em números complexos, sem corte de galho). E foi aí que surgiu um problema. Eu estava implementando o algoritmo (ou seja, iteração AGM) neste artigo , mas:

Finalmente, se $0< x <1$, podemos usar $\log(x) =−\log(1/x)$, Onde $\log(1/x)$ é calculado como acima.

Este parágrafo força uma comparação, que é indecidível. Portanto, é impossível implementar o algoritmo diretamente. Na verdade, na minha versão atual de implementação,$\log 1$ cai em um loop infinito.

Existe um ajuste no algoritmo que o torna computável? Ou devo implementar um algoritmo completamente diferente?

Answer 1

Mesmo que as comparações absolutas possam não convergir, você deve ser capaz de restringir o argumento em pelo menos um dos vários intervalos parcialmente sobrepostos, de forma que você tenha uma técnica que funcione nesse intervalo.

Por exemplo, você deve ser capaz de dizer que $x$ definitivamente se enquadra em pelo menos um dos intervalos $A = \left(0,\frac{3}{4}\right]$, $B = \left[\frac{1}{2},\frac{3}{2}\right]$, ou $C = \left[\frac{5}{4},\infty\right)$com pouca dificuldade. Use AGM se estiver em$C$, a transformação se estiver em $A$, e se estiver em $B$, use esta transformação:

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

Answer 2

O logaritmo é indefinido para x <0 e -infinity quando x = 0, isso é algo que você tem que lidar de alguma forma. Para o teste x <1: qualquer aproximação que você usar para x> = 1 provavelmente funcionará para x> 0,9999. Você não precisa decidir se x <1, apenas se x é pequeno o suficiente. Para x = 0,99995, qualquer decisão funcionará.