How on Factorial

[Geobird]

I am a beginner in Python and would ask for a help.


I was searching for smaller version of code to calculate
factorial . Found this one
def fact(x):
return x > 1 and x * fact(x - 1) or 1

But I don't really get how ( ....x > 1 and x * fact(x - 1)....)
works .

 

[Ulrich Eckhardt]

I am a beginner in Python and would ask for a help.


I was searching for smaller version of code to calculate
factorial . Found this one
def fact(x):
return x > 1 and x * fact(x - 1) or 1

I'd say this is about as small as it gets.

But I don't really get how ( ....x > 1 and x * fact(x - 1)....)
works .

In that case, I'd suggest not trying to make things smaller, but more easy
to read:

def fact(x):
if x > 1:
return x * fact(x - 1)
else:
return 1

This is equivalent to the above code and I hope it illustrates how that code
works.

Uli

 

[Chris Rebert]

 I  am a beginner in Python and would ask for a help.


I  was searching for  smaller  version  of  code  to calculate
factorial . Found  this one
def fact(x):
       return x > 1 and x * fact(x - 1) or 1

 But I don't  really get how (  ....x > 1 and x * fact(x - 1)....)
works .

It exploits short-circuit evaluation
(http://en.wikipedia.org/wiki/Short-circuit_evaluation ). This is
stunt coding / code golf; no one should actually write factorial like
that.

For pedagogical purposes, the code is equivalent to:
def fact(x):
# begin AND
result = x > 1
if result: # x was > 1
result = x * fact(x - 1) # Recursive Case
# end AND
# begin OR
if not result:
result = 1 # Base Case; x was <= 1, so result was False and we
didn't recurse.
# If we did recurse, then result = x!, and
# since x! is always nonzero,
# and Python considers nonzero numbers to be boolean true,
# then we won't even enter this `if`.
# end OR
return result

Note that `and` has higher precedence than `or` in Python.

Also, as of Python 2.6.6 (and possibly earlier), there's a built-in
factorial function in the `math` std lib module, so there's no need to
write one:
Python 2.6.6 (r266:84292, Oct 12 2010, 14:31:05)
[GCC 4.2.1 (Apple Inc. build 5664)] on darwin
Type "help", "copyright", "credits" or "license" for more information.120

Cheers,
Chris

 

[Arnaud Delobelle]

It exploits short-circuit evaluation
(http://en.wikipedia.org/wiki/Short-circuit_evaluation ). This is
stunt coding / code golf; no one should actually write factorial like
that.

True. It's far too verbose. I'd go for something like:

f=lambda n:n<=0 or n*f(~-n)

I've saved a few precious keystrokes and used the very handy ~- idiom!

 

[Geobird]

@ Ulrich : Tx
@ Rebert : Appreciate your interpretation.
It made me think about ternary operation . Say
Are all ternary operations prone to ...( in your words )

 

[Jussi Piitulainen]

@ Ulrich : Tx
@ Rebert : Appreciate your interpretation.
It made me think about ternary operation . Say

Are all ternary operations prone to ...( in your words )

The purpose of a conditional expression is to select one branch of
computation and avoid another. Other ternary operations might well
use the values of all three arguments.

(I agree that no one should write factorial like that, except as
a joke. I have nothing against (x if (a > b) else y). The trick
with and and or was used before Python had an actual conditional
expression.)

 

[Dave Angel]

Huh, I've never seen that one before. Seems to work on both positive and
negative numbers. Is there a caveat to this?

Cheers,
Xav

The ~- trick only works on two's complement numbers. I've worked on
machines in the past that used one's complement, and this wouldn't work
there.

DaveA

 

[Dave Angel]

I imagine this wouldn't work on floating point numbers either.

Cheers,
Xav

From the help:

"The unary ~ (invert) operator yields the bitwise inversion of its plain
or long integer argument. The bitwise inversion of x is defined as
-(x+1). It only applies to integral numbers"

Inverting the bits of a floating point number wouldn't make much sense,
so fortunately it gives an error.

DaveA

 

[karmaguedon]

True.  It's far too verbose.  I'd go for something like:

    f=lambda n:n<=0 or n*f(~-n)

I've saved a few precious keystrokes and used the very handy ~- idiom!

I didn't know the idiom, nice tip.
thanks

 

[Stefan Behnel]

karmaguedon, 28.10.2010 18:46:

I didn't know the idiom, nice tip.

Not really. Given that many people won't know it, most readers will have a
hard time deciphering the above code, so it's best not to do this.

Stefan

 

[Arnaud Delobelle]

karmaguedon, 28.10.2010 18:46:

Not really. Given that many people won't know it, most readers will
have a hard time deciphering the above code, so it's best not to do
this.

Stefan

My reply was obviously tongue in cheek, triggered by Chris Rebert's
"code golf" remark. using ~-n instead of n-1 if obfuscatory and doesn't
even save keystrokes! (Although it could in other situations, e.g
2*(n-1) can be written 2*~-n, saving two brackets.)

 

[Stefan Behnel]

Arnaud Delobelle, 28.10.2010 20:38:

using ~-n instead of n-1 if obfuscatory and doesn't
even save keystrokes! (Although it could in other situations, e.g
2*(n-1) can be written 2*~-n, saving two brackets.)

Sure, good call. And look, it's only slightly slower than the obvious code:

$ python3 -m timeit -s "n=30" "2*~-n"
10000000 loops, best of 3: 0.0979 usec per loop

$ python3 -m timeit -s "n=30" "2*(n-1)"
10000000 loops, best of 3: 0.0841 usec per loop

Stefan

 

[Steven D'Aprano]

Inverting the bits of a floating point number wouldn't make much sense,
so fortunately it gives an error.

.... bits = pack("d", x)
.... return unpack("q", bits)[0]
........ bits = pack("q", i)
.... return unpack("d", bits)[0]
....nan



Makes perfect sense to me

 

[Wolfram Hinderer]

True.  It's far too verbose.  I'd go for something like:

    f=lambda n:n<=0 or n*f(~-n)

I've saved a few precious keystrokes and used the very handy ~- idiom!

You can replace "n<=0" with "n<1". Then you can leave out the space
before "or" ("0or" wouldn't work with newer python versions).

f=lambda n:n<1or n*f(~-n)

Much better, isn't it? ;-)

 

[Lawrence D'Oliveiro]

I'd say this is about as small as it gets.

fact = lambda x : x > 1 and x * fact(x - 1) or 1

 

[Lawrence D'Oliveiro]

(I agree that no one should write factorial like that, except as
a joke. I have nothing against (x if (a > b) else y). The trick
with and and or was used before Python had an actual conditional
expression.)

You know what, I think I actually prefer the trick to Python’s backwards-if
syntax...

 

[Steven D'Aprano]

You know what, I think I actually prefer the trick to Python’s
backwards-if syntax...

What backwards-if syntax? I tried writing it backwards:

true_clause fi condition esle false_clause

and got a syntax error, so I tried writing it backwards another way:

false_clause else condition if true_clause

and still got a syntax error, so I can only conclude that you're using
some hacked version of Python with non-standard syntax, if you're
serious, else you're unaware that Python's ternary if operator follows
English syntax.

 

[Vito 'ZeD' De Tullio]

You know what, I think I actually prefer the trick to Python’s
backwards-if syntax...

fact = lambda x: x*fact(x-1) if x>1 else 1

naa, it's not too bad...