You are viewing a single comment's thread. Return to all comments →
You only need to compute the square roots of prime numbers, because the square root of a composite number c is the product of the square roots of its prime factors.
E.g. for c=12: sqrt(12) = sqrt(2*2*3) = sqrt(2) * sqrt(2) * sqrt(3)
Actually you don't need a full factorization. Choose any two factors a and b where ab=c: sqrt(12) = sqrt(3) * sqrt(4) (or sqrt(2) * sqrt(12))
You need to be a bit careful, though: a factor can be a perfect square (such as 4), therefore memoize all (!) square roots, even the trivial ones of perfect squares. And even more, you have to increase your precision by a few digits because you'll introduce some rounding errors when multiplying. Adding 15 extra digits is more than enough.
After I added this trick to my code it became about 4x faster for N=100 and P=10000.