Python for philosophers

[88888 Dihedral]

Chris Angelico於 2013年5月14日星期二UTC+8上午12時24分44秒寫道：
> On Tue, May 14, 2013 at 12:53 AM, rusi <rustompmody at 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.