[Tutor] fac

[Magnus Lycka]

At 12:01 2003-01-10 +0100, Gregor Lingl wrote:
>Hi people,
>isn't this funny, to see the factorial function coming to
>the tutor-list in two completely different flavours and
>in two comletely different contexts within one minute?
>Does still anyone doubt, that it is a *very* important
>function?

It probably has something to do with 42. Maybe it required
1405006117752879898543142606244511569936384000000000
operations for Deep Thought to come up with its answer?

Factorial rarely comes up in contexts like this because
the result it calculates is useful, but rather because
it's simple to demonstrate recursion with it. I much
prefer Fibonacci numbers, but implementing Fibonacci with
recursion is even more stupid than implementing Factorial
that way.

Function calls have a cost, as the recent discussion should
have revealed. The limited amount of stack space is used,
and it takes time and memory to put context on the stack.

So, if you need factorials in real life (who does?) it's
much better to do:

def fac(n):
     prod = 1
     for i in range(1, n+1):
         prod *= i
     return prod

or if you are of the other inclination...

def fac(n):
     import operator
     return reduce(operator.mul, range(1,n+1))

Fibonacci numbers are much nicer, because the ratio of two
adjacent fibonacci numbers get closer and closer to the Golden
Ratio the higher they get. The Golden Ratio is something really
important. You can ask any ancient Egyptian, landscape
photographer or plastic surgeon about that.

But while recursive factorials are only linearly wasteful,
the function below is much worse. Think about it.

 >>> def fib(n):
...     if n <= 1: return 1
...     else: return fib(n-2) + fib(n-1)

Let's use it anyway, to show it's beauty.

 >>> old = 1
 >>> from __future__ import division
 >>> for i in range(1,17):
...     f = fib(i)
...     print f, f / old, old / f
...     old = f
...
1 1.0 1.0
2 2.0 0.5
3 1.5 0.666666666667
5 1.66666666667 0.6
8 1.6 0.625
13 1.625 0.615384615385
21 1.61538461538 0.619047619048
34 1.61904761905 0.617647058824
55 1.61764705882 0.618181818182
89 1.61818181818 0.61797752809
144 1.61797752809 0.618055555556
233 1.61805555556 0.618025751073
377 1.61802575107 0.618037135279
610 1.61803713528 0.618032786885
987 1.61803278689 0.618034447822
1597 1.61803444782 0.6180338134


-- 
Magnus Lycka, Thinkware AB
Alvans vag 99, SE-907 50 UMEA, SWEDEN
phone: int+46 70 582 80 65, fax: int+46 70 612 80 65
http://www.thinkware.se/  mailto:magnus@thinkware.se