domingo, 14 de dezembro de 2014

Depois de 20 anos enrolando, aproveitei o fim do domingo para finalmente implementar o algoritmo BBP, que acha o n-ésimo dígito hexadecimal de pi, sem precisar achar os n dígitos anteriores.

Achei bacana demais, as duas coisas que me impressionaram foram:

1. O algoritmo é O(n log n), bem melhor que aquela coisa cúbica que você precisaria se fosse calcular todos os dígitos que vieram antes.

2. O algoritmo não precisa de bignum! Dá para fazer todinho com inteiro e floating point.

Eu não vou postar o código porque usei ele num probleminha do spoj:

http://www.spoj.com/ranks/PIHEX2/

Fiquei em terceiro, agora preciso descobrir qual é o truque para ficar em primeiro. Aposto que ele usou montgomery multiplication, esse é outro que estou enrolando faz anos para implementar.

Um comentário:

  1. Muito bom!

    Eu usei montgomery multiplication em outro challenge do SPOJ, o PRIC. Na época fiquei em primeiro lugar, mas depois fiquei tão para trás que não apareço mais nem na primeira página do ranking, hahah.

    ResponderExcluir