472,119 Members | 935 Online

# Iteration for Factorials

I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.

Oct 22 '07 #1
59 5655
Py-Fun wrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
Show us your attempts, and we might suggest a fix. Because otherwise this
sounds suspiciously like homework.

Diez
Oct 22 '07 #2
On 22 Oct, 13:28, "Diez B. Roggisch" <de...@nospam.web.dewrote:
Py-Fun wrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.

Show us your attempts, and we might suggest a fix. Because otherwise this
sounds suspiciously like homework.

Diez
Here is my futile attempt. Be careful with this though, I just ran
something similar and it was never ending...

def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")

itforfact(n)

Oct 22 '07 #3
Py-Fun wrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
As opposed to what, a complicated one?
Oct 22 '07 #4
Py-Fun wrote:
def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")
You function should probably return something. After that, you can see
what happens with the result you get.
Oct 22 '07 #5
Py-Fun <lo*********@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:

def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a
Oct 22 '07 #6
On 22 Oct, 13:43, Marco Mariani <ma...@sferacarta.comwrote:
Py-Fun wrote:
def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")

You function should probably return something. After that, you can see
what happens with the result you get.
Marco, Thanks for the tip. This now works:

def itforfact(n):
while n<100:
print n
n = n+1
n = input("Please enter a number below 100")

itforfact(n)

Is it a "factorial" though?

Oct 22 '07 #7
On Oct 22, 2:43 pm, Marco Mariani <ma...@sferacarta.comwrote:
Py-Fun wrote:
def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")

You function should probably return something. After that, you can see
what happens with the result you get.
lambda n: n<=0 or reduce(lambda a,b: long(a)*long(b),xrange(1,n+1))
Oct 22 '07 #8
On 10/22/07, Py-Fun <lo*********@gmail.comwrote:
On 22 Oct, 13:28, "Diez B. Roggisch" <de...@nospam.web.dewrote:
Py-Fun wrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
Show us your attempts, and we might suggest a fix. Because otherwise this
sounds suspiciously like homework.

Diez

Here is my futile attempt. Be careful with this though, I just ran
something similar and it was never ending...

def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")

itforfact(n)
Let me give you a pseudo code (which though can be found in most of
the textbooks and some 'simple' googling). Try to understand the code
and then write an equivalent python function.

function iFactorial(n: integer): integer;
var i, temp: integer;
begin
temp = 1;
for i = 1 to n do
temp = temp * i
end
return temp

1. why doesn't it surprise you if the code that you posted goes in
infinite loop ?!
2. why do you use condition: n < 100
3. How do you think that your function will calculate the factorial ?
4. Instead of "input" use "raw_input", and then "cast" the input as integer .

Cheers,
amit.
--
--
Amit Khemka
Oct 22 '07 #9
On Oct 22, 5:43 pm, Marco Mariani <ma...@sferacarta.comwrote:
Py-Fun wrote:
def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")

You function should probably return something. After that, you can see
what happens with the result you get.

i am just suggesting u an idea
but i dont know it satisfies ur needs

x=10
def cal_range(10)
for i in range(10):
print 2**i
Oct 22 '07 #10
On Oct 22, 1:26 pm, Py-Fun <lorna.bu...@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
The following simple adder functions should give you an idea of how
recursion can be recast as iteration:

def acc(i):
'''i should be a positive integer'''
if i 0:
return i + acc(i - 1)
return 0

print "acc", acc(9)

def itt(i):
'''i should be a positive integer'''
out = 0

while i 0:
out += i
i = i - 1

return out

print "itt", itt(9)
...
Is it a "factorial" though?
Er, no. And neither is mine. You may want to google for the definition
of factorial! Here's a hint:

reduce(operator.mul, range(1, i + 1))

--
Anthony Roy
Oct 22 '07 #11
From the cookbook, this time.
It satisfies the requirements nicely ;)
http://aspn.activestate.com/ASPN/Coo.../Recipe/496691

def tail_recursion(g):
'''
Version of tail_recursion decorator using no stack-frame
inspection.
'''
loc_vars ={"in_loop":False,"cnt":0}

def result(*args, **kwd):
loc_vars["cnt"]+=1
if not loc_vars["in_loop"]:
loc_vars["in_loop"] = True
while 1:
tc = g(*args,**kwd)
try:
qual, args, kwd = tc
if qual == 'continue':
continue
except (TypeError, ValueError):
loc_vars["in_loop"] = False
return tc
else:
if loc_vars["cnt"]%2==0:
return ('continue',args, kwd)
else:
return g(*args,**kwd)
return result
@tail_recursion
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
res = factorial(n-1, n*acc)
return res

Oct 22 '07 #12
Marco Mariani wrote:
From the cookbook, this time.
It satisfies the requirements nicely ;)
http://aspn.activestate.com/ASPN/Coo.../Recipe/496691
[... snip the ultimate general-purpose answer to the OP's question ...

I really hope that's a wink up there, Marco. The poor guy
was just trying to get his homework done!

:>

TJG
Oct 22 '07 #13
Tim Golden wrote:
> From the cookbook, this time.
It satisfies the requirements nicely ;)

http://aspn.activestate.com/ASPN/Coo.../Recipe/496691

[... snip the ultimate general-purpose answer to the OP's question ...

I really hope that's a wink up there, Marco.
The wink is in the second line of my post... more for the "do the least
amount of work to meet the requirements" people that for the OP
The poor guy was just trying to get his homework done!
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?
Oct 22 '07 #14
On Oct 22, 8:26 am, Py-Fun <lorna.bu...@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
def fac_btt(num):
total = 1
if num 1:
for i in range(1, num+1):
total *= i

Oct 22 '07 #15
On Oct 22, 8:02 am, vimal <cool.vimalsm...@gmail.comwrote:
On Oct 22, 5:43 pm, Marco Mariani <ma...@sferacarta.comwrote:
Py-Fun wrote:
def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")
You function should probably return something. After that, you can see
what happens with the result you get.

i am just suggesting u an idea
but i dont know it satisfies ur needs

x=10
def cal_range(10)
for i in range(10):
print 2**i
Maybe a little math refresher would be good for those trying to post
suggestions.

"Factorial of N" means "the product of 1 x 2 x 3 x ... x N", and is
shown symbolically as "N!".

(Factorial is only defined for nonnegative numbers, and for reasons
that go beyond this little note, just know that 0! = 1.)

In Python, a fully expanded factorial for values >= 1 would be:

2! = 1 * 2
5! = 1 * 2 * 3 * 4 * 5
8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8

Here is an example routine showing iteration, that prints these
expressions:
def print_factorial(n):
print str(n)+"! =",
print "1",
t = 2
while t <= n:
print "*",t,
t += 1
print

Perhaps this example will give you some ideas on how to approach your
problem.
-- Paul

Oct 22 '07 #16
Marco Mariani wrote:
Tim Golden wrote:
>> From the cookbook, this time.
It satisfies the requirements nicely ;)

http://aspn.activestate.com/ASPN/Coo.../Recipe/496691
[... snip the ultimate general-purpose answer to the OP's question ...

I really hope that's a wink up there, Marco.

The wink is in the second line of my post...
I did see it :)
>The poor guy was just trying to get his homework done!

I don't see how my answer is in any way worse than those based on
lambda.
Nor do I. I was just joking with a colleague that the guy
just wanted a bit of help (which he did get, in fact from
several sources) and then out came the lambda and the
decorator. It's only a moment before the metaclass and
the Twisted solution come along. :)
(It's like watching a convention of lisp programmers --
ducks, runs for cover)

TJG
Oct 22 '07 #17
On Oct 22, 7:50 am, Duncan Booth <duncan.bo...@invalid.invalidwrote:
Py-Fun <lorna.bu...@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.

This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:

def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a
Not simple enough for my taste:
>>import gmpy
gmpy.fac(10)
mpz(3628800)

Oct 22 '07 #18
"me********@aol.com" <me********@aol.comwrites:
On Oct 22, 7:50 am, Duncan Booth <duncan.bo...@invalid.invalidwrote:
>Py-Fun <lorna.bu...@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.

This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:

def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a

Not simple enough for my taste:
>>>import gmpy
gmpy.fac(10)
mpz(3628800)
I haven't followed all this thread, but has anyone yet done:

import operator
def fact(x):
return reduce(operator.mul, xrange(1,x))
Oct 22 '07 #19
On Oct 22, 1:35 pm, Paul Rudin <paul.nos...@rudin.co.ukwrote:
"mensana...@aol.com" <mensana...@aol.comwrites:
On Oct 22, 7:50 am, Duncan Booth <duncan.bo...@invalid.invalidwrote:
Py-Fun <lorna.bu...@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:
def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a
Not simple enough for my taste:
>>import gmpy
gmpy.fac(10)
mpz(3628800)

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.
>>import operator
def fact(x):
return reduce(operator.mul,xrange(1,x))
>>fact(3)
2
>>fact(2)
1
>>fact(1)
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
>>fact(0)
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.

Oct 22 '07 #20
On 22 oct, 20:35, Paul Rudin <paul.nos...@rudin.co.ukwrote:
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

Oct 22 '07 #21
to*****@gmail.com writes:
On 22 oct, 20:35, Paul Rudin <paul.nos...@rudin.co.ukwrote:
>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)
Or just:

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

Oct 22 '07 #22
On Oct 22, 3:38 pm, Paul Rudin <paul.nos...@rudin.co.ukwrote:
tokl...@gmail.com writes:
On 22 oct, 20:35, Paul Rudin <paul.nos...@rudin.co.ukwrote:
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)

Or just:

reduce(operator.mul, xrange(1, x), 1)
Nope, still doesn't work:
>>def fact(x):
return reduce(operator.mul,xrange(1,x+1),1)
>>fact(3)
6
>>fact(2)
2
>>fact(1)
1
>>fact(0)
1
>>fact(-1)
1
>>fact(-2)
1
>>fact(-3)
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):
>>def fact(x):
if x==0:
return 1
else:
return reduce(operator.mul,xrange(1,x+1))
>>fact(3)
6
>>fact(2)
2
>>fact(1)
1
>>fact(0)
1
>>fact(-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

Oct 22 '07 #23
On Oct 22, 4:39 pm, "mensana...@aol.com" <mensana...@aol.comwrote:
On Oct 22, 3:38 pm, Paul Rudin <paul.nos...@rudin.co.ukwrote:

tokl...@gmail.com writes:
On 22 oct, 20:35, Paul Rudin <paul.nos...@rudin.co.ukwrote:
>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)
Or just:
reduce(operator.mul, xrange(1, x), 1)

Nope, still doesn't work:
>def fact(x):

return reduce(operator.mul,xrange(1,x+1),1)
xrange(1,x) not xrange(1,x+1). The former only returns
correct factorials for x==0 and x==1.

Sorry for the confusion.
>
>fact(3)
6
>fact(2)
2
>fact(1)
1
>fact(0)
1
>fact(-1)
1
>fact(-2)
1
>fact(-3)

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):
>def fact(x):

if x==0:
return 1
else:
return reduce(operator.mul,xrange(1,x+1))
>fact(3)
6
>fact(2)
2
>fact(1)
1
>fact(0)
1
>fact(-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- Hide quoted text -

- Show quoted text -

Oct 22 '07 #24
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:
>>42 + fact(-1)
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

Oct 23 '07 #25
"Marco Mariani" <marc....arta.comwrote:

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.
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

Oct 23 '07 #26
On Oct 23, 8:53 am, "Hendrik van Rooyen" <m...@microcorp.co.zawrote:
"Marco Mariani" <marc....arta.comwrote:
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.
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.

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

Oct 23 '07 #27
Tim Chase wrote:
>>>fact = lambda i: i 1 and reduce(mul, xrange(1, i+1)) or not
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
Oct 23 '07 #28
On 22 oct, 23:39, "mensana...@aol.com" <mensana...@aol.comwrote:
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.

Oct 23 '07 #29
On Oct 23, 1:58 pm, tokl...@gmail.com wrote:
On 22 oct, 23:39, "mensana...@aol.com" <mensana...@aol.comwrote:
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.
indeed, especially considering that fact(x) is essentially just a
lambda statement as Marco Mariani said.

Oct 23 '07 #30
On Oct 22, 11:45 am, Ant <ant...@gmail.comwrote:
Er, no. And neither is mine. You may want to google for the definition
of factorial!

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

def fact(x):
r = re.compile(r"%d ! = (\d+)" % x)
% x):
m = r.search(line)
if m:
return int(m.group(1))

--
Roberto Bonvallet

Oct 23 '07 #31
"Dennis Lee Bieber" <wl*****@ix.netcom.comwrote:
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):

do-something
.
.
.
store,9 param1
store,9 param2
do-stuff
addimmediate,2 2 ;number of args to
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
Oct 23 '07 #32
On 2007-10-23, Hendrik van Rooyen <ma**@microcorp.co.zawrote:
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.
Oct 23 '07 #33
Roberto Bonvallet wrote:
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%%21" % x):
m = r.search(line)
if m:
return int(m.group(1))

You solution reminds me the web-based WTF calculator.

http://worsethanfailure.com/Articles...-Web-Calc.aspx
Oct 23 '07 #34
On Oct 23, 6:58 am, tokl...@gmail.com wrote:
On 22 oct, 23:39, "mensana...@aol.com" <mensana...@aol.comwrote:
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?
The fact that it returns 1 for negative x?

And didn't you see my followup message? About how the
example, as posted, doesn't even produce correct answers
for legal values of x?
if not allowing negative numbers is so
important for you,
Mathematical consistency is only important to _me_?
add a if statement and raise a ValueError exception.
Not necessary when done correctly. Didn't you see my example?
Oct 23 '07 #35
On Oct 23, 5:55 am, Marco Mariani <ma...@sferacarta.comwrote:
Tim Chase wrote:
>>fact = lambda i: i 1 and reduce(mul, xrange(1, i+1)) or not
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
Needs work.

IDLE 1.2
>>def fact(n):
try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return 1
>>fact(3)
6
>>fact(2)
2
>>fact(1)
1
>>fact(0)
1
>>fact(-1)
1
>>fact(-2)
1

Oct 23 '07 #36
me********@aol.com wrote:
Needs work.
Uh... ok.. this one gives an exception ;-)
def fact(n):
try:
return eval('*'.join(str(x) for x in range(1,n+1)))
except:
return n>=0 or ValueError

print fact(-1)
<type 'exceptions.ValueError'>
Oct 23 '07 #37
"Jon Ribbens" <jon+use...quivocal.co.ukwrote:

On 2007-10-23, Hendrik van Rooyen <ma**@microcorp.co.zawrote:
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.
Yes, worse luck. The market has chosen...

- Hendrik

Oct 24 '07 #38
Py-Fun <lo*********@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
Here is the math geek answer ;-)

import math

def factorial(i):
n = i + 1
return math.exp(-n)*(n**(n-0.5))*math.sqrt(2*math.pi)*(1. + 1./12/n + 1./288/n**2 - 139./51840/n**3)

Works for non integer factorials also...

See here for background

http://mathworld.wolfram.com/StirlingsSeries.html

--
Nick Craig-Wood <ni**@craig-wood.com-- http://www.craig-wood.com/nick
Oct 24 '07 #39
In article <sl*****************@irishsea.home.craig-wood.com>,
Nick Craig-Wood <ni**@craig-wood.comwrote:
Py-Fun <lo*********@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.

Here is the math geek answer ;-)

import math

def factorial(i):
n = i + 1
return math.exp(-n)*(n**(n-0.5))*math.sqrt(2*math.pi)*(1. + 1./12/n +
1./288/n**2 - 139./51840/n**3)

Works for non integer factorials also...

See here for background

http://mathworld.wolfram.com/StirlingsSeries.html

Well, that's Sterling's formula. You do have to worry about
convergence/accuracy.

How about (for intergers - simple-minded version):

def factorial(i):
fact=1.0
for n in xrange(i):
fact=n*fact
return fact

There might even be an array method that can be adapted to get the
product. Is there a product method? (analogous to a sum method)

Then you could use,

arr=arange(i)+1
fact=arr.product() # or something like that

--
-- Lou Pecora
Oct 24 '07 #40
On Oct 24, 4:05 pm, Lou Pecora <pec...@anvil.nrl.navy.milwrote:
In article <slrnfhvalj.67s.n...@irishsea.home.craig-wood.com>,
Nick Craig-Wood <n...@craig-wood.comwrote:

Py-Fun <lorna.bu...@gmail.comwrote:
I'm stuck trying to write a function that generates a factorial of a
number using iteration and not recursion. Any simple ideas would be
appreciated.
Here is the math geek answer ;-)
import math
def factorial(i):
n = i + 1
return math.exp(-n)*(n**(n-0.5))*math.sqrt(2*math.pi)*(1. + 1./12/n +
1./288/n**2 - 139./51840/n**3)
Works for non integer factorials also...
See here for background
http://mathworld.wolfram.com/StirlingsSeries.html

Well, that's Sterling's formula. You do have to worry about
convergence/accuracy.

How about (for intergers - simple-minded version):

def factorial(i):
fact=1.0
for n in xrange(i):
fact=n*fact
return fact
Simple minded indeed.
>>factorial(3)
0.0
>
There might even be an array method that can be adapted to get the
product. Is there a product method? (analogous to a sum method)

Then you could use,

arr=arange(i)+1
fact=arr.product() # or something like that

--
-- Lou Pecora- Hide quoted text -

- Show quoted text -

Oct 24 '07 #41
Tim Golden napisa (a):
It's only a moment before the metaclass and
the Twisted solution come along. :)
I couldn't resist. It's not as elegant as I hoped, but hey, at least
it memoizes the intermediate classes :-)
class fact_0(object):
value = 1

class fact_meta(object):
def __new__(cls, name, bases, attrs):
n = attrs['n']
class_name = 'fact_%i' % n
try:
return globals()[class_name]
except KeyError:
new_class = type(class_name, bases, {})
new_class.value = n * fact(n - 1).value
new_class.__str__ = lambda self: str(self.value)
globals()[class_name] = new_class
return new_class

class fact(object):
def __new__(self, n_):
class spanish_inquisition(object):
__metaclass__ = fact_meta
n = n_
return spanish_inquisition()

print fact(5)
print fact(3)
print fact(1)

Oct 24 '07 #42
On Oct 24, 5:19 pm, marek.ro...@wp.pl wrote:
Tim Golden napisa (a):
It's only a moment before the metaclass and
the Twisted solution come along. :)

I couldn't resist. It's not as elegant as I hoped, but hey, at least
it memoizes the intermediate classes :-)

class fact_0(object):
value = 1

class fact_meta(object):
def __new__(cls, name, bases, attrs):
n = attrs['n']
class_name = 'fact_%i' % n
try:
return globals()[class_name]
except KeyError:
new_class = type(class_name, bases, {})
new_class.value = n * fact(n - 1).value
new_class.__str__ = lambda self: str(self.value)
globals()[class_name] = new_class
return new_class

class fact(object):
def __new__(self, n_):
class spanish_inquisition(object):
__metaclass__ = fact_meta
n = n_
return spanish_inquisition()

print fact(5)
print fact(3)
print fact(1)

120
6
1
<__main__.fact_0 object at 0x011729F0>

Hmm..not sure what that means, but I bet I can't calculate
combinations.

120
6
1
<__main__.fact_0 object at 0x011729F0>

Traceback (most recent call last):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 31, in <module>
print fact(-1)
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, in __new__
new_class.value = n * fact(n - 1).value
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 21, in __new__
class spanish_inquisition(object):
File "C:/Program Files/PyGTK/Python/user/yet_another_factorial.py",
line 13, i

Wow! An infinite loop in the Traceback. Not quite the exception
I was looking for.

Oct 24 '07 #43
Lou Pecora <pe****@anvil.nrl.navy.milwrites:
There might even be an array method that can be adapted to get the
product. Is there a product method? (analogous to a sum method)
The "reduce" function which is being removed from python in 3.0.

import operator
def factorial(n):
return reduce(operator.mul, xrange(1,n+1))
Oct 25 '07 #44
ma*********@wp.pl writes:
It's only a moment before the metaclass and
the Twisted solution come along. :)

I couldn't resist. It's not as elegant as I hoped, but hey, at least
it memoizes the intermediate classes :-)
It gets even weirder in Haskell.

http://www.willamette.edu/~fruehr/ha...evolution.html
Oct 25 '07 #45
"me********@aol.com" <me********@aol.comwrote:
def factorial(i):
fact=1.0
for n in xrange(i):
fact=n*fact
return fact

Simple minded indeed.
>factorial(3)
0.0
Whoops, should have xrange(i)+1 there. Or, better, xrange(2,n+1). Save a
multiplication. Just trying to show the OP the scheme for iteration
here.

--
-- Lou Pecora
Oct 25 '07 #46
ma*********@wp.pl wrote:
class fact_0(object):
value = 1
[...
def __new__(self, n_):
class spanish_inquisition(object):
__metaclass__ = fact_meta
n = n_
return spanish_inquisition()

You wrote lots of boilerplate to hide the fact you're cheating, didn't you?

The OP explicitly asked for an iterative procedure.

btw... writing a test unit to check the tested code is not calling
itself.. could be interesting

Oct 26 '07 #47
On Oct 25, 2:36 am, Paul Rubin <http://phr...@NOSPAM.invalidwrote:
Lou Pecora <pec...@anvil.nrl.navy.milwrites:
There might even be an array method that can be adapted to get the
product. Is there a product method? (analogous to a sum method)

The "reduce" function which is being removed from python in 3.0.

import operator
def factorial(n):
return reduce(operator.mul, xrange(1,n+1))
Since reduce is being removed, and Guido is known not to like its use
anyway, I propose the following code for Py2.5 and later:

import math
def fact(n):
return math.exp(sum((math.log(i) for i in range(1,n+1)))) if n
>= 0 else None
If you don't like the rounding errors you could try:

def fact(n):
d = {"p":1L}
def f(i): d["p"] *= i
map(f, range(1,n+1))
return d["p"]

It is left as an exercise to the reader as to why this code will not
work on Py3K

Nicko
Oct 26 '07 #48
Nicko wrote:
If you don't like the rounding errors you could try:

def fact(n):
d = {"p":1L}
def f(i): d["p"] *= i
map(f, range(1,n+1))
return d["p"]

It is left as an exercise to the reader as to why this code will not
work on Py3K
Serves you right for abusing map(). ;-)

STeVe
Oct 27 '07 #49
Its truly interative and You will need to interate till infinity if

def factorial(N):
"""
Increase I ...and go on increasing...
"""
import random

myNumer = range(N)
count = 0
I = 10000 #10**(N+1)
for i in range(I):
bucket = range(N)
number = []
for i in range(N):
k = bucket[ random.randrange(0,len(bucket))]
bucket.remove(k)
number.append(k)

if number == myNumer:
count+=1

return int(I*1.0/count+.5)

Oct 30 '07 #50

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 1 post views Thread by revhemphill | last post: by 3 posts views Thread by isladogs | last post: by reply views Thread by beacampos | last post: by reply views Thread by isladogs | last post: by 1 post views Thread by beacampos | last post: by reply views Thread by pddon | last post: by reply views Thread by antdb | last post: by reply views Thread by antdb | last post: by 3 posts views Thread by Bright1Light | last post: by 7 posts views Thread by bounthong | last post: by