Iteration for Factorials

[Steven Bethard]

# Not legal Python code.
def fact3(n, acc = 1):
TOP:
if n > 0
n = n - 1
acc = acc * n
goto TOP
else:
return acc

Yes, to write this in legal Python code, you have to write::

from goto import goto, label # http://entrian.com/goto/

def fact3(n, acc = 1):
label .TOP
if n > 0
n = n - 1
acc = acc * n
goto .TOP
else:
return acc

;-)

STeVe

 

[mensanator]

I haven't followed all this thread, but has anyone yet done:

import operator
def fact(x):
return reduce(operator.mul, xrange(1,x))

I hope not.
return reduce(operator.mul,xrange(1,x))

Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
fact(1)
File "<pyshell#7>", line 2, in fact
return reduce(operator.mul,xrange(1,x))
TypeError: reduce() of empty sequence with no initial value

Traceback (most recent call last):
File "<pyshell#11>", line 1, in <module>
fact(0)
File "<pyshell#7>", line 2, in fact
return reduce(operator.mul,xrange(1,x))
TypeError: reduce() of empty sequence with no initial value

I think you need to make it a bit more complicated.

 

[tokland]

import operator
def fact(x):
return reduce(operator.mul, xrange(1,x))

Maybe:

import operator
def fact(x):
return reduce(operator.mul, xrange(2, x+1), 1)

fact(0)
1
fact(4)
24

 

[Tim Chase]

def fact(x):

if x == 0 or x == 1:
return 1
else:
return reduce(operator.mul, xrange(1,x+1))

If obscurity is the name of the game,


My eyes hurt after reading that...as the order of operations is
left to Python to discern (a few judiciously placed parens might
improve things...though that may be like polishing coprolite)

I haven't yet seen an implementation in C (using the python/C
interface) or anybody handing off a python AST/opcode-list to an
appropriate function

-tkc

 

[Paul Rudin]

Maybe:

import operator
def fact(x):
return reduce(operator.mul, xrange(2, x+1), 1)

Or just:

reduce(operator.mul, xrange(1, x), 1)

 

[mensanator]

Or just:

reduce(operator.mul, xrange(1, x), 1)

Nope, still doesn't work:
return reduce(operator.mul,xrange(1,x+1),1)
1

fact() should raise an exception if x is negative.

My variant of your original (same as Tim Chase's except the
test for x==1 is not necessary):
if x==0:
return 1
else:
return reduce(operator.mul,xrange(1,x+1))

Traceback (most recent call last):
File "<pyshell#40>", line 1, in <module>
fact(-1)
File "<pyshell#35>", line 5, in fact
return reduce(operator.mul,xrange(1,x+1))
TypeError: reduce() of empty sequence with no initial value

 

[mensanator]

If obscurity is the name of the game,


My eyes hurt after reading that...as the order of operations is
left to Python to discern (a few judiciously placed parens might
improve things...though that may be like polishing coprolite)

Indeed. Particularly since it doesn't work:

-2! = -2
-1! = -1
0! = 0
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880

0! is defined to be 1. You'll have a hard time calculating
combinations if 0! returns 0. Also, fact() should raise an
exception when x is negative.

It not only has to work correctly, it has to fail correctly also.

 

[mensanator]

Nope, still doesn't work:


return reduce(operator.mul,xrange(1,x+1),1)

Excuse me, I mistyped your proposed solution. You had
xrange(1,x) not xrange(1,x+1). The former only returns
correct factorials for x==0 and x==1.

Sorry for the confusion.

 

[Tim Chase]

If obscurity is the name of the game,

Indeed. Particularly since it doesn't work:

Huh? Works on the Python (2.4) I have, both the Win32 python at
work and Linux Python at home:
....
-2! = None
-1! = None
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880

It could even be more obscure by making it
i and 1 or None

Stunts like this would get a person fired around here if they
were found in production code

-tkc

 

[mensanator]

Huh? Works on the Python (2.4) I have, both the Win32 python at
work and Linux Python at home:

Sorry about that, Google line wrapped the fact definition
and it worked anyway in Idle (but not as written).

Still, why do you want None instead of raisng an exception
(as is the case in other factorial implementations)?

 

[Tim Chase]

Still, why do you want None instead of raisng an exception

(as is the case in other factorial implementations)?

A null value is as good/bad as raising an exception in my book.
Since you can't do math on a None object, any attempt to do so
will raise an exception:

I generally prefer my functions to return semi-sensible results
(in this case, None makes sense to me, as there isn't really a
definition of "negative-one factorial"). It also fits in my head
alongside my SQL where NULL values/expressions can be returned
and evaluated without the whole query falling over.

I suppose if you really wanted to throw an exception using this
lambda craziness, you could wrap the whole result in "0 +
([body])" which, if the body returned Null, would push up
exception daisies (with slightly misleading exception information).

-tkc

 

[Hendrik van Rooyen]

I don't see how my answer is in any way worse than those based on
lambda. Maybe I'm just envious because when I was his age I couldn't
google for answers. He should at least be able to do that, shouldn't he?
But wait. That would mean understanding what a factorial is. That would
require a second search, or a textbook, or an understanding of
arithmetics before programming with or without recursion. Should we
blame the teachers?

Yes. And burn their cars to get their attention!

Asking someone to write a factorial algorithm before he knows WTF a
factorial "is", is either insane, or the ultimate demonstration of deliberate
lack of cooperation and coordination between departments.
I feel kind of strongly about this ever since, as a student, the physics people
expected me to use mathematics that I had not been taught yet...

;-)

I shall try to refrain from commenting on the concept of introducing
recursion into a first course in CS - I am too much tainted by my ability
to mentally "see" the stack growth in a small processor to be qualified
to comment.

- Hendrik

 

[cokofreedom]

Yes. And burn their cars to get their attention!

Asking someone to write a factorial algorithm before he knows WTF a
factorial "is", is either insane, or the ultimate demonstration of deliberate
lack of cooperation and coordination between departments.
I feel kind of strongly about this ever since, as a student, the physics people
expected me to use mathematics that I had not been taught yet...

;-)

I shall try to refrain from commenting on the concept of introducing
recursion into a first course in CS - I am too much tainted by my ability
to mentally "see" the stack growth in a small processor to be qualified
to comment.

- Hendrik

Completely agree with this point of view. After being on the receiving
end of such problems when first introduced to Haskell and told to look
at a database written in it and work my way through it (without having
started the course on databases, locks, or any of that jargon) you
find yourself almost helpless at times.

Hard to google for something you don't know about.

Recursive calling is a fun, and yet painful, thing...

 

[Dennis Lee Bieber]

Asking someone to write a factorial algorithm before he knows WTF a
factorial "is", is either insane, or the ultimate demonstration of deliberate
lack of cooperation and coordination between departments.
I feel kind of strongly about this ever since, as a student, the physics people
expected me to use mathematics that I had not been taught yet...

My condolences -- while I'd not encountered that particular problem
I did hate one aspect of a college course (was it probability?)...
Mainly because the HP-25 calculator did NOT have a built-in factorial,
and the 49-step program memory was volatile -- I had to code in the
factorial code before class, and hope the battery lasted the session.

I shall try to refrain from commenting on the concept of introducing
recursion into a first course in CS - I am too much tainted by my ability
to mentally "see" the stack growth in a small processor to be qualified
to comment.

Heh... the one saving grace of taking a CS major in a period where
the primary languages taught were FORTRAN (IV), COBOL (74), and
something close to K&K BASIC. Heck, even the assembler class followed
the FORTRAN parameter handling scheme (argument addresses copied to
static locals and used via one level of indirection) -- It would take me
some time, today, to figure out how to even create a "stack" (even the
return address was passed via a reserved register and saved locally):

call,2 sub-address
data arg1-address
data arg2-address
do-something
.
.
.
sub-address: store,2 my-return
load,9 *my-return,1 ;indexed access
store,9 param1
load,9 *my-return,2
store,9 param2
do-stuff
load,2 my-return
addimmediate,2 2 ;number of args to
adjust return
return,2

(format:
label command,register argument
*argument ;indirection
argument,x ;indexed )
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Marco Mariani]

i and 1 or None

Stunts like this would get a person fired around here if they
were found in production code

eheh, indeed.


def fact(n):
try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return 1

 

[tokland]

Nope, still doesn't work:

def fact(x):
return reduce(operator.mul,xrange(1,x+1),1)

fact() should raise an exception if x is negative.

So, where is the problem? if not allowing negative numbers is so
important for you, add a if statement and raise a ValueError exception.

 

[cokofreedom]

So, where is the problem? if not allowing negative numbers is so
important for you, add a if statement and raise a ValueError exception.

indeed, especially considering that fact(x) is essentially just a
lambda statement as Marco Mariani said.

 

[Roberto Bonvallet]

Er, no. And neither is mine. You may want to google for the definition
of factorial!

Don't google for the definition... google for the answer!

import urllib
import re
urllib.URLopener.version = "Mozilla/4.0"

def fact(x):
r = re.compile(r"%d ! = (\d+)" % x)
for line in urllib.urlopen("http://www.google.cl/search?q=%d%!"
% x):
m = r.search(line)
if m:
return int(m.group(1))

 

[Hendrik van Rooyen]

Heh... the one saving grace of taking a CS major in a period where
the primary languages taught were FORTRAN (IV), COBOL (74), and
something close to K&K BASIC. Heck, even the assembler class followed
the FORTRAN parameter handling scheme (argument addresses copied to
static locals and used via one level of indirection) -- It would take me
some time, today, to figure out how to even create a "stack" (even the
return address was passed via a reserved register and saved locally):

call,2 sub-address
data arg1-address
data arg2-address
do-something
.
.
.
sub-address: store,2 my-return
load,9 *my-return,1 ;indexed access
store,9 param1
load,9 *my-return,2
store,9 param2
do-stuff
load,2 my-return
addimmediate,2 2 ;number of args to
adjust return
return,2

(format:
label command,register argument
*argument ;indirection
argument,x ;indexed )
--

Yuk. Reminds me of one of the Hitachi processors that
has a single depth hardware "link register" that tells a
subroutine where it was called from.

I was thinking of a stack that grows when you call or push,
and shrinks when you return or pop.

When there are only 128 or so bytes, and an address is two bytes,
recursive calling soon runs into trouble. Especially so if you also
use the stack to pass params...

- Hendrik

 

[Jon Ribbens]

Yuk. Reminds me of one of the Hitachi processors that
has a single depth hardware "link register" that tells a
subroutine where it was called from.

That's how ARM processors work, and they're everywhere these days.