report.txt

How to use

Este trabalho foi feito em python, usando somente bibliotecas padrões, e como o interpretador python está presente na maioria das distribuições linux, para executar o trabalho basta digitar "./main.py" ou "./main --verbose" em um emulador de console ou tty de sua preferência.


Justificativa da linguagem escolhida

Java é uma linguagem proprietária cujos interesses estão focados no mercado, visando o lucro em detrimento do conhecimento humano, e como ferramentas proprietárias não são adequadas para o meio acadêmico (Java é bastante inespressivo nesta área), foi dada preferência por uma linguagem livre.
A dúvida ficou entre Python e C++, mas logo foi possível observar a necessidade de se usar bigintegers e exponenciação modular, algo que não é difícil de se lidar com C++ mas com Python este problema torna-se trivial. Em python, conforme um número cresce ele pode tornar-se um biginteger internamente, sem o programador sequer ter que levar isto em consideração. Para a exponenciação modular, li alguns algoritmos, e o mais promissor apresentou um desempenho 1 ordem de grandeza inferior à função já existente "built-in" do Python, onde pow(x,y,m) é x elevado a y mod m.


Implementação e Dificuldades

A implementação do Teste de Primalidade de Fermat foi absolutamente "straightforward", basicamente bastou tranformar em código python a definição do algoritmo e então pensar num parâmetro adequado com relação ao número de iterações que o algoritmo deve utilizar (foi definido como 100 para os testes).
A única dúvida foi quanto à adaptação do algoritmo Xorshift, já que apesar dele internamente trabalhar com 4 registradores (128 bits), seu output é de 32 bits. A solução encontrada foi a de se encapsular este algoritmo numa classe, e então criar outra classe (xorshift100) que como atributo possui uma lista com 11 objetos do tipo xorshift, cada um inicializado com um seed diferente, 11 pois, em média, cada número retornado do xorshift possuia cerca de 8 a 10 digitos decimais. Feito isto, para gerar um número de 100 digitos, iterava-se nesta lista, concatenando os números retornados até este ter pelo menos 100 digitos decimais, então são descartados os digitos (LSB) além de 100.
O código do main.py consiste basicamente de contadores de estatística e output para o usuário, não há realmente uma lógica interessante nele.


Tempo gasto pelos algoritmos

O output do programa está bastante verboso, existe inclusive um arquivo chamado "output" nesta pasta, mostrando um exemplo do output gerado. O programa emite como output o tempo de execução de cada invocação do Teste de Primalidade de Fermat e do Xorshift100 (caso --verbose seja enviado como argumento na linha de comando), e então apresenta o tempo total da execução de todo o programa, o somatório dos tempos gastos pelo Teste de Primalidade de Fermat e do Xorshift100, e apresenta também a razão do tempo gasto no Xorshift100 em relação ao total, demonstrando que, em média, 25% do tempo é gasto com ele, portanto 75% do tempo foi despendido testando os números (usando-se um parâmetro de 100 tentativas). Também é mostrado o número de verificações de primalidade que retornaram falso, como uma forma de justificar o porquê desta parte estar consumindo a maior parte do tempo.