Introdução à Programação OCaml
A sequência de inteiros de Perrin

O problema que segue foi proposto na edição 2017 como item inicial da avaliação da componente prática da aprendizagem da programação OCaml

Problema

A sequência de Perrin é uma sequência de inteiros naturais que tem uma história interessante. Sugerida em 1876, foi explicitamente definida por François Olivier Raoul Perrin em 1899.

Tem várias aplicações, em particular em teoria dos grafos. Mas recentemente tem sido usada para descobrir coordenadas de taxis em redes urbanas de forma confidencial ¹.

A sequência define-se de forma simples como

Input

A entrada deste exercício consiste numa linha onde consta o inteiro n para qual se pretende obter P_n.

Output

Uma simples linha com o inteiro P_n.

Constraints

 
Este limite é arbitrário mas já obriga saber tratar de grandes números. Comece por usar o tipo int para garantir uma boa implementação e teste com valores pequenos. Garantida esta parte, use a seguir o tipo de dado num ou big_int fornecidos no módulo num (em particular num ou big_int).

Sample Input

44

Sample Output

236282

Apresentamos diferentes soluções possíveis nos ficheiros seguintes:

• O ficheiro perrin_trivial.ml (html). Apelidada de naive no benchmark, esta solução implementa de forma fiel e directa a definição da sequência de Perrin.
• O ficheiro perrin_hash.ml(html). Esta solução (hash) opta por memoizar a função recursiva natural, com base numa tabela de hash
• O ficheiro perrin_vect.ml(html). Esta solução (vect) é semelhante a anterior, mas socorre-se de um vector para realizar a memoização
• O ficheiro perrin_rect.ml(html). Esta solução (terminal) codifica a versão naive de forma recursiva terminal. Para esse efeito foi necessário introduzir três acumuladores. Uma solução simples com uma preocupação minima sobre a optimização é espantosamente eficiente, como se verá já em seguida.
• O ficheiro perrin_mat.ml(html). Esta solução (matrix) implementa o método do cálculo do n-ésimo elemento da sequência de Perrin pela exponenciação (rápida) de uma matrix três por três. Como esperado, é a melhor solução (em termos computacionais) aqui apresentada. Tem um desempenho logarítmico!

 
Procedeu-se a avaliação do tempo de execução das diferentes soluções aqui apresentadas. Todos os tempos são em medidos em segundos. As execuções foram single-threaded. o parâmetro n varia de 10 até 2.10⁷, valor a partir do qual nenhuma solução apresenta um tempo razoável de cálculo.

O computador que serviu de base à execução dos testes de performance tem a seguinte especificação técnica:

1

see MrRobot

This document was translated from L^AT_EX by H^EV^EA.