Python for philosophers

[Chris Angelico]

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