Precision issue in python
Shashwat Anand
anand.shashwat at gmail.com
Sat Feb 20 15:42:17 CET 2010
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)
a = str(10**frac_e * 10**(k - 1)).split('.')[0]
b = 1
for i in range(n, 0, -1):
b = (b * i) % 10**l
lb = len(str(b))
if lb < l:
b = str(b) + '0'* (l - lb)
print a, b
~l0nwlf
On Sat, Feb 20, 2010 at 6:14 PM, Mark Dickinson <dickinsm at gmail.com> wrote:
> 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
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100220/645dfa04/attachment.html>
More information about the Python-list
mailing list