Precision issue in python
Mark Dickinson
dickinsm at gmail.com
Sat Feb 20 13:44:12 CET 2010
On Feb 20, 11:17 am, mukesh tiwari <mukeshtiwari.ii... at gmail.com>
wrote:
> Hello everyone. I think it is related to the precision with double
> arithmetic so i posted here.I am trying with this problem (https://www.spoj.pl/problems/CALCULAT) and the problem say that "Note : for
> all test cases whose N>=100, its K<=15." I know precision of doubles
> in c is 16 digits. Could some one please help me with this precision
> issue.I used stirling (http://en.wikipedia.org/wiki/
> Stirling's_approximation) to calculate the first k digits of N.
> Thank you.
If I understand you correctly, you're trying to compute the first k
digits in the decimal expansion of N!, with bounds of k <= 15 and 100
<= N < 10**8. Is that right?
Python's floats simply don't give you enough precision for this:
you'd need to find the fractional part of log10(N!) with >= 15 digits
of precision. But the integral part needs ~ log10(log10(N!)) digits,
so you end up needing to compute log10(N!) with at least 15 +
log10(log10(N!)) ~ 15 + log10(N) + log10(log10(N)) digits (plus a few
extra digits for safety); so that's at least 25 digits needed for N
close to 10**8.
The decimal module would get you the results you need (are you allowed
imports?). Or you could roll your own log implementation based on
integer arithmetic.
--
Mark
More information about the Python-list
mailing list