Alternatively, fact x = if x == 0 then 1 else x * fact(x-1);main=readLn >>= print.fact
Name:
Anonymous2009-06-15 16:28
Can your C do this? f@(_:fs) = 0 : 1 : zipWith (+) f fs
Name:
Anonymous2009-06-15 16:36
from IntroductoryExercises import Fibonacci;
main = fib;
Name:
Anonymous2009-06-15 17:32
: fact 1+ 1 tuck +do i * loop ;
Name:
Anonymous2009-06-15 17:58
#include <stdio.h>
#include <stdlib.h>
#define grunnurr(m) fprintf(stderr,"grunnur: %s\n",#m)
#define grun(c) exit(c)
#define nnnur(s) atoi(s)+1
#define NUR main
#define nn =
#define n *
#define nnur 1
#define GRUNNUR return 0;
#define grunn while
#define GRU(f,d) printf(f,d)
#define nnn "%d\n"
#define grunnur NNUR[nnur]
#define _(a,b) b=a
#define ur
typedef char gruun;
typedef int GRUN;
GRUN NUR(GRUN NURR,gruun n n NNUR){GRUN nur,grun nn nnur;grunn(nnur&&!grunnur){grunnurr(GRUNNuR);grun(nur);}grun nn nnnur(grunnur);_(grun,nur);grun nn nnur;grunn(--nur)grun nn ur grun n nur;_(grun,nur);GRU(nnn,nur);GRUNNUR;}
Name:
Anonymous2009-06-15 19:04
slow factorial is slow...
try this one: primes = 2 : 3 : 5 : 7 : [k + r | k <- [0, 30..], r <- [11, 13, 17, 19, 23, 29, 31, 37], primeTest (k + r)]
where primeTest n = all ((0 /=) . mod n) . takeWhile ((n >=) . join (*)) $ drop 3 primes
bitCount 0 = 0
bitCount n = bitCount (shiftR n 1) + n .&. 1
swing n | n < 33 = genericIndex smallOddSwing n
| True = product pList
where smallOddSwing = [1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 300540195, 300540195]
pListA q p prime = let x = div q prime in case x of
0 -> case p of
1 -> []
_ -> [p]
_ -> pListA x (p * prime ^ (mod x 2)) prime
pListB = (filter ((1==) . flip (.&.) 1 . div n) . takeWhile (<= div n 3) $ dropWhile ((<= n) . join (*)) primes)
pListC = takeWhile (<= n) $ dropWhile (<= shiftR n 1) primes
pList = (concatMap (pListA n 1) . takeWhile ((n >=) . join (*)) $ tail primes) ++ pListB ++ pListC
recFactorial n | n < 2 = 1
| True = join (*) (recFactorial $ div n 2) * swing n
factorial :: Int -> Integer
factorial n | n < 20 = product [2..fromIntegral n]
| True = shiftL (recFactorial $ fromIntegral n) (n - bitCount n)
or this one: product([], 1).
product([H|T], X) :- product(T, Y), X is H * Y.
factorial(N, R) :- numlist(2, N, Ns), product(Ns, R).
fact: mov rax, rdi
dec rdi
.loop: mul rdi
dec rdi
jnz .loop
ret
Name:
Anonymous2009-06-17 8:49
>>20
lol @ inefficient algorithm
see >>7,10 for better ones.
especially the prime-swing one in >>7. implement that (with a better prime sieve) in assembly and unless you do something incredibly stupid it should be faster than GMP's factorial function.
Name:
Anonymous2009-06-17 9:34
>>21 >>7's algorithm uses my method for n < 20, and for n > 20 mine doesn't work anyway, so I don't see how you can call it inefficient.
Name:
Anonymous2009-06-17 9:37
>>22
(define factorial (λ(n) 120))
It works for n=5 super efficiently. The edge case where n is not 5 may not behave correctly.
>>28
No actually, your factorial not only doesn't output the correct answer on an unspecified number of legitimate inputs, but in fact, doesn't halt at all on a subset of said inputs. I suggest you rethink some dubious design decisions.
Name:
Anonymous2009-06-18 8:42
>>29
droves of diverse dubious design decisions are distributed throughout this thread.
public final long factorial(final int n)
Java makes me lol.
Also, why are you implicitly typecasting int to long in that multiplication?
Name:
Anonymous2009-06-18 19:32
Also, why are you implicitly typecasting int to long in that multiplication?
you keep using that word... i do not think it means what you think it means. http://www.merriam-webster.com/dictionary/typecast
Name:
Anonymous2009-06-19 1:48
def fact(x): return (1 if x==0 else x * fact(x-1))
Name:
Anonymous2009-06-19 2:16
from math import sqrt
from itertools import takewhile, dropwhile
def eratosthenes():
D = {}
q = 2
while 1:
if q not in D:
yield q
D[q*q] = [q]
else:
for p in D[q]:
D.setdefault(p+q,[]).append(p)
del D[q]
q += 1
def bitcount(n):
r = 0;
while n > 0:
r += n & 1
n >>=1
return r
def take(n, g):
for i in range(n): yield g.next()
def swing(n):
primes = list(takewhile(lambda x: x <= n, eratosthenes()))
smalloddswing = [1,1,1,3,3,15,5,35,35,315,63,693,231,3003,429,6435,6435,109395,12155,230945,46189,969969,88179,2028117,676039,16900975,1300075,35102025,5014575,145422675,9694845,300540195,300540195]
if n < 33: return smalloddswing[n]
primelist = []
rootn = long(sqrt(n))
primesa = takewhile(lambda x: x <= rootn, dropwhile(lambda x: x < 3, primes))
primesb = takewhile(lambda x: x <= n // 3, dropwhile(lambda x: x <= rootn, primes))
for prime in primesa:
q = n // prime
p = 1
while q > 0:
if q & 1 == 1: p *= prime
q //= prime
if p > 1: primelist.append(p)
return reduce(lambda x, y: x * y, list(takewhile(lambda x: x <= n, dropwhile(lambda x: x <= n // 2, primes))) + primelist + filter(lambda x: n // x & 1 == 1, primesb), 1)
def recfactorial(n):
if n < 2: return 1
return recfactorial(n // 2) ** 2 * swing(n)
def factorial(n):
if n < 20: return reduce(lambda x, y: x * y, range(2,n + 1), 1)
return recfactorial(n) << (n - bitcount(n))
After fixing that: 7.hs:2:67: Not in scope: `join'
7.hs:5:23: Not in scope: `shiftR'
7.hs:5:39: Not in scope: `.&.'
7.hs:7:19: Not in scope: `genericIndex'
7.hs:17:41: Not in scope: `.&.'
7.hs:17:105: Not in scope: `join'
7.hs:18:52: Not in scope: `shiftR'
7.hs:19:64: Not in scope: `join'
7.hs:22:25: Not in scope: `join'
7.hs:26:23: Not in scope: `shiftL'
After importing Control.Monad, Data.List and Data.Bits: 7.hs:26:25:
No instance for (Monad ((->) Integer))
arising from a use of `join' at 7.hs:26:25-57
Possible fix:
add an instance declaration for (Monad ((->) Integer))
In the first argument of `(*)', namely
`join (*) (recFactorial $ div n 2)'
In the expression: join (*) (recFactorial $ div n 2) * swing n
In the definition of `recFactorial':
recFactorial n | n < 2 = 1
| True = join (*) (recFactorial $ div n 2) * swing n
Name:
tehmeh2009-06-19 18:13
>>50
def fact(x): return (1 if x==0 else x * fact(x-1))