Equações de Pell

Fevereiro 12, 2012

Equações diofantinas são equações polinomiais que só admitem soluções inteiras. Neste post, vou comentar sobre três casos particulares e me concentrar em um deles, conhecido como equações de Pell.

Triplas de Pitágoras

O caso mais conhecido de equações diofantinas é da forma:

x^2 + y^2 = z^2

As soluções inteiras para essa equação são conhecidas como triplas pitagóricas, por causa do teorema de Pitágoras, sobre a relação entre os comprimentos dos lados de um triângulo retângulo.

Para o caso mais geral, da forma x^n + y^n = z^n com n > 2, o famoso último teorema de Fermat diz que não existem soluções inteiras.

Indentidade de Bézout

Outro caso particular conhecido são as equações diofantinas lineares de duas variáveis, por exemplo, x e y, da forma

ax + by = c

Onde a, b, c são constantes inteiras. No caso em que c é o máximo divisor comum de a, b, temos a identidade de Bézout. É possível encontrar um par x, y inteiro usando o algoritmo de Euclides estendido.

Note entretanto que há infinitas soluções inteiras para essa equação, pois se x, y é uma solução, x' = x + b e y' = y - a é também uma solução.

Equação de Pell

Só recentemente ouvi falar sobre um outro caso particular, conhecido como equações de Pell, com a forma:

(1) x^2 - ny^2 = 1

Onde n é um inteiro positivo. Se n não possui raíz exata, então existem infinitas soluções inteiras x, y (Se n tiver raíz exata dá pra mostrar que a única solução é x = \pm 1 e y = 0). Vamos apresentar um algoritmo para encontrar as soluções para esse caso particular de n.

Frações continuadas

Um conceito usado no algoritmo é o de frações continuadas, que podem ser usadas para aproximar um número irracional através de frações. A fração continuada possui a seguinte forma:

Dado um número d, os coeficientes de sua fração continuada, a_0, a_1, \cdots, a_n são positivos e podem ser calculados através das recorrências, para i \ge 1:

r_i = \frac{1}{r_{i-1} - a_{i-1}}

a_i = \lfloor r_i \rfloor

e com a_0 = \lfloor d \rfloor.

Podemos representar uma fração continuada por seus coeficientes, ou seja, [a_0,a_1,a_2,\cdots]. Incrivelmente, no caso particular em que o número irracional é da forma \sqrt{n}, prova-se que os coeficientes da sua fração continuada são periódicos, ou seja \sqrt{n} = [a_0, \overline{a_1,a_2,\cdots,a_{r-1},a_{r}}] e a_{r} = 2a_0.

Como um exemplo, para n = 14 temos \sqrt{14} = [3,\overline{1,2,1,6}]

É possível calcular explicitamente o numerador p_i e o denominador q_i da fração continuada com i termos, através das recorrências:

\begin{array}{lcl}   p_0 & = & a_0\\  p_1 & = & a_1 a_0 + 1\\  p_n & = & a_n p_{n-1} + p_{n-2}   \end{array}

e

\begin{array}{lcl}   q_0 & = & 1\\  q_1 & = & a_1\\  q_n & = & a_n q_{n-1} + q_{n-2}   \end{array}

A fração p_i / q_i é chamada de n-ésimo convergente. Voltando ao exemplo para n = 14, temos:

\begin{array}{llcl}   i: & p_i / q_i  &  & \\  0:  & 3/1 & = & 3.0\\  1: & 4/1 & = & 4.0\\  2: & 11/3 & = & 3.66666666667\\   3: & 15/4 & = & 3.75\\  4: & 101/27 & = & 3.74074074074  \end{array}

Sendo que \sqrt{14} é aproximadamente 3.74165769645

Uma solução para a equação de Pell

Considere os coeficientes da fração continuada de \sqrt{n} e r o índice a partir do qual os coeficientes ficam periódicos.

Se r é par, seja x = p_{r-1} e y = q_{r-1}. Caso contrário, seja x = p_{2r-1} e y = q_{2r-1}. Surpreendentemente, existe um teorema que diz que x, y representam a menor solução inteira positiva para (1).

Algoritmo

Dadas essas propriedades, um algoritmo para encontrar uma solução para (1), consiste em iterar sobre os coeficientes p_i e q_i, até encontrar r tal que a_r = 2a_0. Segundo Lenstra [2], r \in O(\sqrt{n} \log n), ou seja, tem complexidade pseudo-polinomial. Assim, se d é o número de bits necessários para representar n, temos que r \in O(2^{d/2}d), ou seja, mesmo ignorando as complexidades das operações artiméticas no código, o nosso algoritmo é exponencial no número de bits.

Gerando mais soluções

Dada uma solução fundamental (x_1,y_1), Lenstra [2] afirma que se ordenarmos as soluções por magnitude, então a k-ésima solução (x_k, y_k) é tal que

(2) x_k + \sqrt{n}y_k = (x_1 + \sqrt{n}y_1)^k

Usando a ideia de [1], como ambos (x_1,y_1) e (x_k, y_k) são solução para (1), temos

x_k^2 - ny_k^2 = (x_1^2 - ny_1^2)^k = 1

Fatorando temos,

(x_k + \sqrt{n}y_k)(x_k - \sqrt{n}y_k) = (x_1 + \sqrt{n}y_1)^k(x_1 - \sqrt{n}y_1)^k

Por (2), concluímos que,

(3) x_k - \sqrt{n}y_k = (x_1 - \sqrt{n}y_1)^k

Resolvendo para (2) e (3), chegamos em:

\begin{array}{lcl}   x_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k + (x_1 - y_1\sqrt{n})^k}{2}\\  \\  y_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k - (x_1 - y_1\sqrt{n})^k}{2\sqrt{n}}  \end{array}

Implementação

Com base na teoria apresentada acima, é simples escrever um algoritmo. Adicionei uma implementação em python à minha biblioteca pessoal de teoria dos números, disponível no github.

Encontrei um post bastante interessante sobre equações de Pell e Haskell aqui [3]. Para praticar, resolvi implementar a minha versão antes de olhar o código do post. Apanhei bastante para lidar com o fato do Haskell não fazer conversão de tipos ponto flutuante e inteiro automaticamente. É preciso fazer isso explicitamente e por isso a função fromIntegral no código deste link.

Leitura complementar

[1] Wolfram – Pell Equation
[2] Solving the Pell Equation – H. W. Lenstra Jr.
[3] A Foray into Number Theory with Haskell

Anúncios

Python como alternativa a Bash Script

Fevereiro 18, 2011

Sempre que precisava automatizar alguma tarefa no linux, apelava para scripts bash. O problema é que escrevo scripts com pouca frequência e somada à sintaxe peculiar dos comandos bash, sempre preciso consultar referências e acabo perdendo bastante tempo.

Pra piorar, algumas tarefas como processamento de strings são complicadas de fazer em bash script e então normalmente usam-se ferramentas auxiliares como sed e awk. A sintaxe delas é bem concisa e elegante, mas acho difícil dominá-las usando-as tão pouco.

Foi por isso que decidi investir um tempo pesquisando modos de substituir bash script por python.

No meu ponto de vista, há um tradeoff entre usar bash script e python. O primeiro faz comunicação direta com o sistema operacional, sendo trivial executar programas, redirecionar entrada/saída ou manipular diretórios, mas é complicado para se fazer processamentos em geral. Já python é o oposto: é bem simples de se programar mas para comunicar com o sistema operacional é necessário usar API’s.

Módulo os

Algumas tarefas de manipulação de diretórios ficam relativamente simples usando o módulo os. Comandos como mkdir, chmod, chown têm suas versões homônimas nesse módulo. Outras comuns mas com nomes ligeiramente diferentes são

* ls — os.listdir(path) — retorna uma lista com os nomes dos arquivos no diretório apontado por path.

* pwd — os.getcwd() — retorna o nome do diretório corrente.

Além dessas, temos também algumas de manipulação de caminhos no módulo os.path. As que eu mais usei até agora,

* os.path.join — Sintaxe: os.path.join(path1[, path2[, …]])

Recebe um conjunto de strings e as concatena em ordem para formar um caminho. Exemplo:

print os.path.join('/home', 'joao/', 'musica')

Vai imprimir

/home/joao/musica

Nota: como está dito no manual, se alguma das strings representar um caminho absoluto, ele ignora todas as strings anteriores. No linux o caminho absoluto é iniciado por /. Por exemplo:

print os.path.join('/home', 'joao/', '/musica')

Vai imprimir

/musica

* os.path.exists — Sintaxe: os.path.exists(path)

Esse comando retorna True se o caminho path existe e False caso contrário.

Nota: esse comando não diferencia arquivos e diretórios. Assim, se existir o diretório foo/ mas você estiver procurando um arquivo chamado foo, o comando mencionado vai retornar True mesmo que o arquivo não exista. Para obter o comportamento esperado, deve-se usar o comando os.path.isfile (ou os.path.isdir na situação oposta).

Módulo subprocess

A criação de processos dentro de scripts python ficava no módulo os, mas está depreciada desde a versão 2.6. Essa tarefa agora está implementada no módulo subprocess.

O principal componente desse módulo é a classe Popen, que recebe vários parâmetros. O primeiro deles é uma lista contendo o nome do programa a ser executado e os argumentos. Depois tem diversos outros, mas os que achei mais importantes são stdin, stderr, stdout.

Exemplo 1 — Executando um processo com argumentos

Imagine um programa chamado ./print que imprime o primeiro e o segundo parâmetro que ele receber. Em C++ pode ser algo como:

#include <iostream>
int main (int argc, char **argv){
    std::cout << argv[1] << " -- " << argv[2] << "\n"; 
}

No bash, se quisermos enviar um argumento para o programa ./print que contenha espaço, devemos pô-lo entre aspas. Por exemplo,

./print "ola mundo" "tudo bem?"

Vai imprimir: ola mundo -- tudo bem?

A vantagem de se usar uma lista de strings é que podemos especificar qual é argumento é qual. Podemos fazer assim:

import subprocess
p = subprocess.Popen(['./print', 'ola mundo',
                      'tudo bem?'])
p.wait()

Exemplo 2 — Processando stdout

No exemplo anterior, a string será impressa na saída padrão (stdout), mas o código python não terá acesso a ela. Se quisermos processar a string impressa por ./print, podemos redirecionar a saída usando pipes, como no bash.

Para fazer isso, usa-se a variável especial subprocess.PIPE. Por exemplo:

import subprocess
import sys
p = subprocess.Popen(['./print', 'oi', 'mundo'],
                     stdout=subprocess.PIPE)
saida = p.communicate()
sys.stdout.write(saida[0].upper())

Nesse caso, o método communicate() serve para fazer a comunicação com o processo. Ele retorna uma lista de dois elementos [stdout, stderr] e também pode receber como argumento a string que será redirecionada para o stdin do processo. No exemplo, só estamos redirecionando o stdout para o objeto, então saida[1] = None, enquanto que saida[0] contém a linha impressa por ./print. Estamos convertendo tudo para caixa alta, então o programa acima imprime:

OI -- MUNDO

Exemplo 3 — Usando stdin e stderr

Para completar, um exemplo onde usamos o stdin e o stdout. Seja ./read um programa que lê um inteiro da entrada padrão e imprima na saída de erro esse número multiplicado por 2, como o código C++ a seguir:

#include <iostream>
int main(){
    int n;
    std::cin >> n;
    std::cerr << 2*n << '\n';
}

Queremos executar esse programa, enviar um número na entrada padrão dele e ler da saída de erro. Podemos fazer isso com o seguinte código:

import subprocess
import sys
p = subprocess.Popen(['./read'],
                     stdin=subprocess.PIPE,
                     stderr=subprocess.PIPE)
sys.stdout.write(p.communicate('2')[1])

Nesse caso redirecionamos o stdin e o stderr. Conforme eu havia dito, o método communicate recebe como parâmetro os dados que serão enviados para a entrada padrão do processo. Além disso, o conteúdo da saída de erro é o segundo elemento da lista retornada.

Exemplo 4 — Redirecionamento para arquivo

Em bash script é comum redirecionarmos saída para arquivos com o operador ‘>’. Para fazer isso usando subprocess, temos que abrir o arquivo explicitamente com open e passar o objeto retornado como parâmetro para o stdout do Popen. Exemplo:

import subprocess
f = open('tmp.txt', 'w')
subprocess.call(['ls'], stdout=f)
f.close()

É comum redirecionarmos o stderr para o /dev/null para que ele não seja impresso no terminal. Se quisermos fazer isso com subprocess, basta abrir o arquivo '/dev/null' e passar o objeto para stderr.

Funções auxiliares

Adicionalmente há algumas funções para simplificar a tarefa dependendo das suas necessidades.

subprocess.call — executa um comando, espera o processo terminar e devolve o código retornado pelo processo. Seria adequado para o Exemplo 1.

subprocess.check_output — Executa um comando e retorna uma string com o conteúdo da saída padrão — só está disponível a partir da versão 2.7. Seria adequado para o Exemplo 2.

Nota: Em geral, eu adiciono permissão de execução para meus scripts bash, por exemplo script.sh, e o executo como ./script.sh. Porém, usando subprocess, tem que executá-lo usando o /bin/bash:

p = subprocess.Popen(['/bin/bash', 'script.sh'])

Conclusão

Com esses módulos mencionados, tenho conseguido me virar usando python como script. Agora só uso bash scripting mesmo quando preciso executar uma lista de comandos sem ter que fazer processamento algum.

Referências

[1] 15.1 – Miscellaneous operating system interfaces
[2] 17.1 – Subprocess management
[3] Stackoverflow — How do I check if a file exists using Python?