Chris Angelico於 2013年5月14日星期二UTC+8上午12時24分44秒寫道：
> On Tue, May 14, 2013 at 12:53 AM, rusi <rustompm...@gmail.com> wrote:
>
> > int fact(int n, int acc)
>
> > {
>
> > return !n? acc : fact(n-1,acc*n);
>
> > }
>
> > ---------------------------------
>
> > When I run these, the C happily keeps giving answers until a million
>
> >
>
> > However examined closely we find that though the C is giving answers
>
> > its giving junk after around 12
>
> > fact 17 is -288522240
>
> > And 35 onwards its 0 (!!)
>
>
>
> That'll depend on your integer size. If it's a 32-bit integer, you
>
> can't store numbers greater than 2**31-1 (if you declared it as
>
> 'unsigned int', you could go all the way to 2**32-1). I'm sure you
>
> could write this to use the GNU Multi-Precision library, but it'd be a
>
> lot more complicated. However, as far as I know, the Turing machine
>
> never promises that; its cells aren't meant to be infinite integers.
>
>
>
> The Python script is, of course, governed by sys.setrecursionlimit().
>
> But by adding a simple driver, we can test the real limit:
>
>
>
> import sys
>
>
>
> def fact(n,acc=1):
>
> return acc if not n else fact(n-1,n*acc)
>
>
>
> n=2
>
> while True:
>
> sys.setrecursionlimit(n+2)
>
> print("fact",n,"has",len(str(fact(n))),"digits")
>
> n*=2
>
>
>
> On my 64-bit system, running a recent trunk build of CPython 3.4, it
>
> can calculate 8192! but not 16384! (segfault). The limit seems to be
>
> 12772; after that, boom. Your crash-point will quite probably vary,
>
> and I'd say there'll be compile-time options that would change that.
>
>
>
> Of course, after playing with this in Python, I had to try out Pike.
>
> Using the exact same code you proposed for C, but with a different
>
> main() to save me the hassle of keying in numbers manually, I get
>
> this:
>
>
>
> fact 8192 has 28504 digits - 0.026 secs
>
> fact 16384 has 61937 digits - 0.097 secs
>
> fact 32768 has 133734 digits - 0.389 secs
>
> fact 65536 has 287194 digits - 1.628 secs
>
> fact 131072 has 613842 digits - 7.114 secs
>
> fact 262144 has 1306594 digits - 31.291 secs
>
> fact 524288 has 2771010 digits - 133.146 secs
>
>
>
> It's still going. One core consumed, happily working on 1048576!, and
>
> not actually using all that much memory. Hmm.... looks like the Pike
>
> optimizer has turned this non-recursive. Okay, let's tweak it so it's
>
> not tail-recursion-optimizable:
>
>
>
> return n?n*fact(n-1,1):1;
>
>
>
> Now it bombs at 65536, saying:
>
>
>
> Svalue stack overflow. (99624 of 100000 entries on stack, needed 256
>
> more entries)
>
>
>
> Hey, it's better than a segfault, which is what C would have done :)
>
> And it's a tweakable value, though I don't know what the consequences
>
> are of increasing it (presumably increased RAM usage for all Pike
>
> programs).
>
>
>
> Your final conclusion is of course correct; nothing we build can be
>
> truly infinite. But we can certainly give some very good
>
> approximations, if we're prepared to pay for them. The reality is,
>
> though, that we usually do not want to pay for approximations to
>
> infinity; why is IEEE 754 floating point so much more used than, say,
>
> arbitrary-precision rational? Most of the time, we'd rather have good
>
> performance and adequate accuracy than abysmal performance and perfect
>
> accuracy. But hey, if you want to render a Mandelbrot set and zoom in
>
> to infinity, the option IS there.
>
>
>
> ChrisA
Hey, ChisA, are you delibrately to write a recursive version
to demonstrate the stack depth problem in Python?
def fact(n):
ret=1
if n>1: # integer checking is not used but can be added
for x in xrange(n): ret*=x
#print ret # debugging only for long integers
return ret
In a 32 or 64 bit system, this non-recursive verssion
will be limited by the heap space not by the stack limit.
--
http://mail.python.org/mailman/listinfo/python-list
