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.
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.
Muito bom!
ResponderExcluirEu 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.