Feature suggestion -- return if true

[Chris Angelico]

Just to be pedantic, by any reasonable definition, 0! == one, not zero.

One reference:  http://en.wikipedia.org/wiki/Factorial
3rd sentence.

Hm! I never thought to check the definition... I just coded it up
quickly, and didn't even consider the possibility of a zero return
until the cache's loophole was challenged. Guess with a more correct
definition of factorial, it's even safer in the cache.

Question: How many factorial functions are implemented because a
program needs to know what n! is, and how many are implemented to
demonstrate recursion (or to demonstrate the difference between
iteration and recursion)?

ChrisA

 

[Aahz]

My idiom for fetching from a cache looks like this:

def get_from_cache(x):
y = cache.get(x)
if not y:
y = compute_from(x)
cache[x] = y
return y

I prefer not to create and destroy objects needlessly.

def get_from_cache(x):
if not x in cache:
cache[x] = compute_from(x)
return cache[x]

Aside from Steven's entirely appropriate pointed question, I find this
more readable:

if x not in cache:

Without testing, I'm not sure, but I believe it's more efficient, too
(creates fewer bytecodes).
--
Aahz ([email protected]) <*> http://www.pythoncraft.com/

"At Resolver we've found it useful to short-circuit any doubt and just
refer to comments in code as 'lies'. "
--Michael Foord paraphrases Christian Muirhead on python-dev, 2009-03-22

 

[Gregory Ewing]

Question: How many factorial functions are implemented because a
program needs to know what n! is, and how many are implemented to
demonstrate recursion (or to demonstrate the difference between
iteration and recursion)?

A related question is how often factorial functions are even
*used* in real code.

I can think of two uses for factorials off the top of my
head:

* Coefficients of polynomials resulting from Taylor expansions.
In that case you probably have a loop that's calculating the
numerators and denominators iteratively, and the factorial
is folded into that. Or you're looking up the coefficients in
a table and not calculating factorials at all.

* Combinations and permutations -- again, the factorials are
probably folded into a loop that calculates the result in a
more direct and efficient way.

 

[Jussi Piitulainen]

(I can't get to the parent directly, so I follow up indirectly.)

Factorials become an interesting demonstration of recursion when done
well. There's a paper by Richard J. Fateman, citing Peter Luschny:

<http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf>
<http://www.luschny.de/math/factorial/FastFactorialFunctions.htm>

Fateman's "major conclusion is that you should probably not use the
'naive' factorial programs for much of anything". I take this to
include their use as examples of recursion, unless the purpose is to
make the idea of recursion look bad.

 

[Chris Angelico]

Factorials become an interesting demonstration of recursion when done
well. There's a paper by Richard J. Fateman, citing Peter Luschny:

<http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf>
<http://www.luschny.de/math/factorial/FastFactorialFunctions.htm>

Fateman's "major conclusion is that you should probably not use the
'naive' factorial programs for much of anything". I take this to
include their use as examples of recursion, unless the purpose is to
make the idea of recursion look bad.

"
And here is an algorithm which nobody needs, for the Simple-Minded only:
long factorial(long n) { return n <= 1 ? 1 : n * factorial(n-1); } Do
not use it if n > 12.
"

I suppose the n > 12 issue is based on the assumption that
sizeof(long)==4. That's not an algorithmic question, that's a return
type issue... not to mention a rather naive assumption. 64-bit
integers let you go to n == 20 (iirc), and if you go bignum, even that
simple algorithm will be fine for up to n == 500 or so without stack
issues.

But sometimes you need a simple and well-known algorithm to
demonstrate a language feature with. Maybe we should switch to
Fibonacci instead... Anyone for caramel sauce?

http://www.dangermouse.net/esoteric/chef_fib.html

(As a side point, I have become somewhat noted around the house for
always saying "Fibonacci" whenever caramel sauce is mentioned...)

Chris Angelico

 

[Thomas Rachel]

Am 13.04.2011 01:06, schrieb Ethan Furman:

--> def func():
--> var1 = something()
--> var2 = something_else('this')
--> return? var1.hobgle(var2)
--> var3 = last_resort(var1)
--> return var3.wiglat(var2)

This makes me think of a decorator which can mimic the wantend behaviour:

def getfirst(f):
from functools import wraps
@wraps(f)
def func(*a, **k):
for i in f(*a, **k):
if i: return i
return func

# [BTW: a kind of "return decorator" would be nice here ;-)]

@getfirst
def func():
var1 = something()
var2 = something_else('this')
yield var1.hobgle(var2)
var3 = last_resort(var1)
yield var3.wiglat(var2)
yield "Even that did not work."

This has the advantage of being flexible about which condition to
evaluate: maybe the func does return tuples of which only the 2nd part
is relevant concerning the check. Then just do


def getfirst(f):
from functools import wraps
@wraps(f)
def func(*a, **k):
for i in f(*a, **k):
if i[1]: return i
return func

@getfirst
def func():
var1 = something()
var2 = something_else('this')
yield "first try", var1.hobgle(var2)
var3 = last_resort(var1)
yield "second try", var3.wiglat(var2)
yield "default value", "Even that did not work."


Disclaimer: Untested, but you should get the idea.

Thomas