Precision issue in python

[Mark Dickinson]

On Sat, Feb 20, 2010 at 2:42 PM, Shashwat Anand
<anand.shashwat at gmail.com> wrote:
> A quick solution I came out with, no stirling numbers and had tried to avoid
> large integer multiplication as much as possible.
>
> import math
>
> for i in range(int(raw_input())):
>     n, k, l = [int(i) for i in raw_input().split()]
>     e = sum(math.log10(i) for i in range(1, n+1))
>     frac_e = e - math.floor(e)

This isn't going to give you enough accuracy when n gets large (and
the original problem seems to allow n to be as large as 10**8), for
the reasons I described earlier---that is, Python floats only give you
around 16 decimal digits of precision;  your 'e' value will already
have used up some of those 16 digits before the point, leaving you
fewer than 16 digits of precision after the point, so the absolute
error in frac_e will likely be larger than 1e-15.  That's not good
enough for getting the first 15 digits of 10**frac_e accurately.  For
large n, you'll also be accumulating significant error in the sum.

>     a = str(10**frac_e * 10**(k - 1)).split('.')[0]

The str(...).split('.') here doesn't do a good job of extracting the
integer part when its argument is >= 1e12, since Python produces a
result in scientific notation.  I think you're going to get strange
results when k >= 13.

--
Mark