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. 59 5462
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
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)
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?
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.
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
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?
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))
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
About your code.
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
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
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
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
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
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?
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
return total
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
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
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)
"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))
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.
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 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)
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
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)
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.
>
>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 -
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
"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.
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
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.
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...
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
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.
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.
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!
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%%21"
% x):
m = r.search(line)
if m:
return int(m.group(1))
--
Roberto Bonvallet
"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):
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
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.
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
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?
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 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'>
"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
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
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
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 -
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)
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)
Dare I add fact(0)?
120
6
1
<__main__.fact_0 object at 0x011729F0>
Hmm..not sure what that means, but I bet I can't calculate
combinations.
What about fact(-1)?
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.
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))
In article <11**********************@e9g2000prf.googlegroups. com>,
"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 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
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
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
What about this no map, reduce, mutiplication or even addition
Its truly interative and You will need to interate till infinity if
you want correct answer ;)
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) ### This discussion thread is closed Replies have been disabled for this discussion. |