views:

1702

answers:

20

How can I write a program to find the factorial of any number?

+23  A: 

This will work for the factorial (although a very small subset) of positive integers:

unsigned long factorial(unsigned long f)
{
    if ( f == 0 ) 
        return 1;
    return(f * factorial(f - 1));
}

printf("%i", factorial(5));

Due to the nature of your problem (and level that you have admitted), this solution is based more in the concept of solving this rather than a function that will be used in the next "Permutation Engine".

Kyle Rozendo
Holy. Did I just get the heck voted out of me, because of someone asking a question that may, or may not be homework? Shouldn't he be the one getting nailed? (Not downvoted though) :P
Kyle Rozendo
Wonder what's wrong with this one...it *is* the simplest correct answer (assuming positive integers); why the downvotes? (edit to clarify: I commented when question was at -2 and answer at -4)
Piskvor
Thanks Piskvor, I must actually mention its only for positive ints.
Kyle Rozendo
i think so to, how down votes this answer and why? if you downvote, i should add a comment (the reason for downvote isn't obviously)
Tyzak
i dint down vote it...since nt so familiar wyth the site i dint know wht it wwas downvoting nd hw it's done..sorry.bro..nd thnx fr he solution..
hopefulLLl
I don't think this is a good place to use recursion. Sure a compiler can probably optimise it away, but still I think iteration is more appropriate.
John
@John I think that the recursive solution is better as it is closer to the mathematical definition and as such is far more understandable.
Yacoby
"far more" is a big stretch. The two are very similar and it really depends which concept the developer knows better. Since most people are less comfortable with recursion, I wouldn't recommend it without an algorithmic advantage.
John
I agree with John. In principle, C is the wrong language for assuming that recursion is best. Even if your compiler does tail call optimisations, that doesn't mean the next guys does - and at least an iterative solution *will* exit with an (admittedly numerically overflowed) result, rather than causing a stack overflow. As for the mathematical definition, I'd argue that most peoples mathematical intuition of factorial is basically iterative anyway.
Steve314
Also, this function isn't tail recursive anyway, is it? Looks to me like the multiplication is done after the nested call exits. So the compiler *won't* optimise it even if it can optimise tail calls. Someone included a tail recursive version in another answer.
Steve314
@Steve I tweaked it so now it is.
Yacoby
A: 

Example in C (C was tagged so i guess that's what you want) using recursion

unsigned long factorial(unsigned long f)
{
        if (f) return(f * factorial(f - 1));
        return 1;
}

printf("%lu", factorial(5));
S.Hoekstra
A: 
unsigned int factorial(unsigned int a)
 {
   if (a == 1)
   return 1;
   else
    {
      a *= factorial(a-1);
      return a;
   }
 }
muruga
+1 for providing the iterative version.
Piskvor
In order to understand recursion, one must first understand recursion
Sergio
how do i vote up /down any answer??
hopefulLLl
nd thnx murugaperumal...fr the answer
hopefulLLl
Hmm. On my machine that doesn't find the factorial of any number, it only finds the factorials of numbers up to 12. YMMV ;-)
Steve Jessop
It’s rare that an accepted answer is such a bad code. Sorry, but even if we forget about the screwed-up indentation, this code is just not well written. Basically, it’s a lot of bloat that only answers the question coincidentally, and without pointing out the solution, and how and why it works.
Konrad Rudolph
This is pretty messy and limited to be picked as the best possible answer.
John
I upvoted. The code answers the question, but doesn't point out the caveats. So what? YAGNI. The OP may eventually ask another question like "why does this give me a negative number??" and someone will talk about overflow. If we never hear from the OP again, the solution works for his/her use case and was understandable enough that he/she picked it as the answer.
Jeff Meatball Yang
I upvoted because I suspect naive versions will more quickly get a stack overflow due to recursion than a `unsigned long` overflow.
Earlz
This must be a magical day. First time I am seeing an accepted answer with -6 votes.
Vivin Paliath
And now an accepted answer that no longer exists!
John
Yup.. A simple question like `factorial` fetching 10 upvotes and the answer for it getting -10 votes.
Guru
I smell a rat..
BlueRaja - Danny Pflughoeft
@Earlz: whut? Other way around, surely. On my machine, `unsigned long` can hold up to 12!. If it's 64 bits, it can hold up to 20!. This is not a challenge to the available stack on my machine, or on a typical 64 bit machine. Integer overflow will occur long before stack overflow.
Steve Jessop
-1, |-13| == 13 is not a good number in almost all cultures.delete it please.
Behrooz
@Steve: numeric overflow will return a bad result. stack overflow will crash. It's not safe to assume somebody will only ever call this with small N.
John
True. In C, you shouldn't really write functions that recurse O(N) deep (N the magnitude of an input) without some kind of limit on N, in documentation at the very least. But what does that have to do with what Earlz said, that I was responding to?
Steve Jessop
Kyle handles the 0! case, but with only a few integers that work in a 32 bit word, perhaps a lookup table is best. A test for n>12 or n>20 (for the 64 bit words) might be good too. Perhaps returning 0 as an error value.
philcolbourn
0! = 1. I am not sure what this code would return...
Andreas Rejbrand
+3  A: 

How can I write a programme to find the factorial of any number?

Nobody has answered the question, even using unsigned 64-bit values it will only work up to 20! and using signed 32-bit ints only up to 15!

Please define what you mean by "any number", because factorials break built-in types very quickly.

John
All right then, I've bothered.
Steve Jessop
The Haskell versions will work for any number, as long as you have memory and time...
Dan Andreatta
I think you mean 12! Why worry about signed?
philcolbourn
+4  A: 

a tail-recursive version:

long factorial(long n)
{
    return tr_fact(n, 1);
}
static long tr_fact(long n, long result)
{
    if(n==1)
        return result;
    else
        return tr_fact(n-1, n*result);
}
Odin
+1 for correct tail recursion, though (1) the compiler isn't guaranteed to optimise it, and (2) in this case I still think iterative is best anyway.
Steve314
But being tail recursive, isn't it easy to optimise it yourself by eliminating the tail-call?
philcolbourn
+5  A: 

For large n you may run into some issues and you may want to use Stirling's approximation:

Which is:

alt text

ast4
You really need to define large. Given that 21! is already outside the range of standard C data types, does large mean 20, 100, 1000, ...?
John
I think it depends on what your acceptable level of error vs. computational time is, for 10! it's a bit under 1%. The larger the number gets, the more accurate the approximation becomes.
ast4
+1  A: 

You use the following code to do it.

#include    <stdio.h>
#include    <stdlib.h>

int main()
{
   int x, number, fac;
   fac = 1;
   printf("Enter a number:\n");
   scanf("%d",&number);

   if(number<0)
   {
      printf("Factorial not defined for negative numbers.\n");
      exit(0);
   }

   for(x = 1; x <= number; x++)
   {
      if (number >= 0)
         fac = fac * x;
      else
         fac=1;
   }

   printf("%d! = %d\n", number, fac);
} 
+5  A: 

If your main objective is an interesting looking function:

int facorial(int a) {
   int b = 1, c, d, e;
   a--;
   for (c = a; c > 0; c--)
   for (d = b; d > 0; d--)
   for (e = c; e > 0; e--)
   b++;
   return b;
}

(Not recommended as an algorithm for real use.)

sth
+20  A: 

This calculates factorials of non-negative integers[*] up to ULONG_MAX, which will have so many digits that it's unlikely your machine can store a whole lot more, even if it has time to calculate them. Uses the GNU multiple precision library, which you need to link against.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

void factorial(mpz_t result, unsigned long input) {
    mpz_set_ui(result, 1);
    while (input > 1) {
        mpz_mul_ui(result, result, input--);
    }
}

int main() {
    mpz_t fact;
    unsigned long input = 0;
    char *buf;

    mpz_init(fact);
    scanf("%lu", &input);
    factorial(fact, input);

    buf = malloc(mpz_sizeinbase(fact, 10) + 1);
    assert(buf);
    mpz_get_str(buf, 10, fact);
    printf("%s\n", buf);

    free(buf);
    mpz_clear(fact);
}

Example output:

$ make factorial CFLAGS="-L/bin/ -lcyggmp-3 -pedantic" -B && ./factorial
cc -L/bin/ -lcyggmp-3 -pedantic    factorial.c   -o factorial
100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

[*] If you mean something else by "number" then you'll have to be more specific. I'm not aware of any other numbers for which the factorial is defined, despite valiant efforts by Pascal to extend the domain by use of the Gamma function.

Steve Jessop
Interesting to know the GNU lib exists, but I assume it's GPL and therefore off-limits to many/most of us? I don't suppose Boost has any big-number support?
John
It's LGPL, which should be OK for most proprietary software (and for that matter most freer-than-GPL software) provided you can stand the paperwork. The usual way is to link dynamically, since then the requirement that the end user can relink your code against a modified version of GMP is trivially satisfied. You can simultaneously distribute a GMP dll with source.
Steve Jessop
@John: Last I looked, Boost didn't have bignum support, which I consider an unfortunate omission. (Then again, Boost got an unordered_map implementation awful late, so there's always hope.)
David Thornley
My planned defense was to claim I meant that many results of `n!` for a natural integer `n` can be represented as a `double`.
Pascal Cuoq
@Pascal: Oh I see. When you said 'quite a few "numbers"', I thought you were referring to the fact that your function gives results for non-integers. Either way you're right, moving to double does give extra headroom.
Steve Jessop
+9  A: 

Thanks to Christoph, a C99 solution that works for quite a few "numbers":

#include <math.h>
#include <stdio.h>

double fact(double x)
{
  return tgamma(x+1.);
}

int main()
{
  printf("%f %f\n", fact(3.0), fact(5.0));
  return 0;
}

produces 6.000000 120.000000

Pascal Cuoq
The only real answer I've seen to the question as asked, since all the others are limited to nonnegative integers.
David Thornley
@David: factorial is not defined for negative integers. Big-Gamma is not factorial, it's the analytical continuation of factorial, and *even so* is infinite for negative integers and 0, so negative integers still don't have "a factorial". By the same argument, btw, the sum of 1 + 2 + 3 ... is -1/12 (that is, Riemann zeta(-1))
Steve Jessop
Another realisation in looking this up is that base-2 floating-point numbers are actually quite nice to represent results of factorial: since `n!`'s decomposition in prime factors accumulates 2's rather quickly, `n!` can be expected to remain representable as a `double` well above 2^53. I didn't compute how high it's possible to go. Wikipedia has a note about 170! but I am not sure they mean "representable exactly".
Pascal Cuoq
Change a couple of 10's to 2's in my code, then `| sed 's/0*$//' | wc -c`. 22! has 52 binary digits before the trailing zeros, 23! has 57 and therefore will lose precision in an IEEE double. I think.
Steve Jessop
@Pascal, thanks for that insight. So every 2nd iteration effectively gives you a 'spare' bit in the mantissa to use by incrementing the exponent. Nice.
philcolbourn
@philcolbourn It's more than that, the power of `2` in the decomposition of `!n` the partial sum of the sequence 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4...
Pascal Cuoq
@Pascal. I see, because 4 is 2x2, 8 is 2x2x2, 12 is 2x2x3 and 16 is 2x2x2x2 etc. These even numbers give you lots of extra 'spare' bits.
philcolbourn
+3  A: 

Here's a C program that uses OPENSSL's BIGNUM implementation, and therefore is not particularly useful for students. (Of course accepting a BIGNUM as the input parameter is crazy, but helpful for demonstrating interaction between BIGNUMs).

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <openssl/crypto.h>
#include <openssl/bn.h>

BIGNUM *factorial(const BIGNUM *num)
{
    BIGNUM *count = BN_new();
    BIGNUM *fact = NULL;
    BN_CTX *ctx = NULL;

    BN_one(count);
    if( BN_cmp(num, BN_value_one()) <= 0 )
    {
        return count;
    }

    ctx = BN_CTX_new();
    fact = BN_dup(num);
    BN_sub(count, fact, BN_value_one());
    while( BN_cmp(count, BN_value_one()) > 0 )
    {
        BN_mul(fact, count, fact, ctx);
        BN_sub(count, count, BN_value_one());
    }

    BN_CTX_free(ctx);
    BN_free(count);

    return fact;
}

This test program shows how to create a number for input and what to do with the return value:

int main(int argc, char *argv[])
{
    const char *test_cases[] =
    {
        "0", "1",
        "1", "1",
        "4", "24",
        "15", "1307674368000",
        "30", "265252859812191058636308480000000",
        "56", "710998587804863451854045647463724949736497978881168458687447040000000000000",
        NULL, NULL
    };
    int index = 0;
    BIGNUM *bn = NULL;
    BIGNUM *fact = NULL;
    char *result_str = NULL;

    for( index = 0; test_cases[index] != NULL; index += 2 )
    {
        BN_dec2bn(&bn, test_cases[index]);

        fact = factorial(bn);

        result_str = BN_bn2dec(fact);
        printf("%3s: %s\n", test_cases[index], result_str);
        assert(strcmp(result_str, test_cases[index + 1]) == 0);

        OPENSSL_free(result_str);
        BN_free(fact);
        BN_free(bn);
        bn = NULL;
    }

    return 0;
}

Compiled with gcc:

gcc factorial.c -o factorial -g -lcrypto
indiv
+1  A: 

For large numbers you probably can get away with an approximate solution, which tgamma gives you (n! = Gamma(n+1)) from math.h. If you want even larger numbers, they won't fit in a double, so you should use lgamma (natural log of the gamma function) instead.

If you're working somewhere without a full C99 math.h, you can easily do this type of thing yourself:

double logfactorial(int n) {
  double fac = 0.0;
  for ( ; n>1 ; n--) fac += log(fac);
  return fac;
}
Rex Kerr
+13  A: 

Why doing it in C when you can do it in Haskell:

Freshman Haskell programmer

fac n = if n == 0 
           then 1
           else n * fac (n-1)

Sophomore Haskell programmer, at MIT (studied Scheme as a freshman)

fac = (\(n) ->
        (if ((==) n 0)
            then 1
            else ((*) n (fac ((-) n 1)))))

Junior Haskell programmer (beginning Peano player)

fac  0    =  1
fac (n+1) = (n+1) * fac n

Another junior Haskell programmer (read that n+k patterns are “a disgusting part of Haskell” 1 and joined the “Ban n+k patterns”-movement [2])

fac 0 = 1
fac n = n * fac (n-1)

Senior Haskell programmer (voted for Nixon Buchanan Bush — “leans right”)

fac n = foldr (*) 1 [1..n]

Another senior Haskell programmer (voted for McGovern Biafra Nader — “leans left”)

fac n = foldl (*) 1 [1..n]

Yet another senior Haskell programmer (leaned so far right he came back left again!)

-- using foldr to simulate foldl

fac n = foldr (\x g n -> g (x*n)) id [1..n] 1

Memoizing Haskell programmer (takes Ginkgo Biloba daily)

facs = scanl (*) 1 [1..]

fac n = facs !! n

Pointless (ahem) “Points-free” Haskell programmer (studied at Oxford)

fac = foldr (*) 1 . enumFromTo 1

Iterative Haskell programmer (former Pascal programmer)

fac n = result (for init next done)
        where init = (0,1)
              next   (i,m) = (i+1, m * (i+1))
              done   (i,_) = i==n
              result (_,m) = m

for i n d = until d n i

Iterative one-liner Haskell programmer (former APL and C programmer)

fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))

Accumulating Haskell programmer (building up to a quick climax)

facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)

fac = facAcc 1

Continuation-passing Haskell programmer (raised RABBITS in early years, then moved to New Jersey)

facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)

fac = facCps id

Boy Scout Haskell programmer (likes tying knots; always “reverent,” he belongs to the Church of the Least Fixed-Point [8])

y f = f (y f)

fac = y (\f n -> if (n==0) then 1 else n * f (n-1))

Combinatory Haskell programmer (eschews variables, if not obfuscation; all this currying’s just a phase, though it seldom hinders)

s f g x = f x (g x)

k x y   = x

b f g x = f (g x)

c f g x = f x g

y f     = f (y f)

cond p f g x = if p x then f x else g x

fac  = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))

List-encoding Haskell programmer (prefers to count in unary)

arb = ()    -- "undefined" is also a good RHS, as is "arb" :)

listenc n = replicate n arb
listprj f = length . f . listenc

listprod xs ys = [ i (x,y) | x<-xs, y<-ys ]
                 where i _ = arb

facl []         = listenc  1
facl n@(_:pred) = listprod n (facl pred)

fac = listprj facl

Interpretive Haskell programmer (never “met a language” he didn't like)

-- a dynamically-typed term language

data Term = Occ Var
          | Use Prim
          | Lit Integer
          | App Term Term
          | Abs Var  Term
          | Rec Var  Term

type Var  = String
type Prim = String


-- a domain of values, including functions

data Value = Num  Integer
           | Bool Bool
           | Fun (Value -> Value)

instance Show Value where
  show (Num  n) = show n
  show (Bool b) = show b
  show (Fun  _) = ""

prjFun (Fun f) = f
prjFun  _      = error "bad function value"

prjNum (Num n) = n
prjNum  _      = error "bad numeric value"

prjBool (Bool b) = b
prjBool  _       = error "bad boolean value"

binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j)))))


-- environments mapping variables to values

type Env = [(Var, Value)]

getval x env =  case lookup x env of
                  Just v  -> v
                  Nothing -> error ("no value for " ++ x)


-- an environment-based evaluation function

eval env (Occ x) = getval x env
eval env (Use c) = getval c prims
eval env (Lit k) = Num k
eval env (App m n) = prjFun (eval env m) (eval env n)
eval env (Abs x m) = Fun  (\v -> eval ((x,v) : env) m)
eval env (Rec x m) = f where f = eval ((x,f) : env) m


-- a (fixed) "environment" of language primitives

times = binOp Num  (*)
minus = binOp Num  (-)
equal = binOp Bool (==)
cond  = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y)))

prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ]


-- a term representing factorial and a "wrapper" for evaluation

facTerm = Rec "f" (Abs "n" 
              (App (App (App (Use "if")
                   (App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1))
                   (App (App (Use "*")  (Occ "n"))
                        (App (Occ "f")  
                             (App (App (Use "-") (Occ "n")) (Lit 1))))))

fac n = prjNum (eval [] (App facTerm (Lit n)))

Static Haskell programmer (he does it with class, he’s got that fundep Jones! After Thomas Hallgren’s “Fun with Functional Dependencies” [7])

-- static Peano constructors and numerals

data Zero
data Succ n

type One   = Succ Zero
type Two   = Succ One
type Three = Succ Two
type Four  = Succ Three


-- dynamic representatives for static Peanos

zero  = undefined :: Zero
one   = undefined :: One
two   = undefined :: Two
three = undefined :: Three
four  = undefined :: Four


-- addition, a la Prolog

class Add a b c | a b -> c where
  add :: a -> b -> c

instance              Add  Zero    b  b
instance Add a b c => Add (Succ a) b (Succ c)


-- multiplication, a la Prolog

class Mul a b c | a b -> c where
  mul :: a -> b -> c

instance                           Mul  Zero    b Zero
instance (Mul a b c, Add b c d) => Mul (Succ a) b d


-- factorial, a la Prolog

class Fac a b | a -> b where
  fac :: a -> b

instance                                Fac  Zero    One
instance (Fac n k, Mul (Succ n) k m) => Fac (Succ n) m

-- try, for "instance" (sorry):
-- 
--     :t fac four

Beginning graduate Haskell programmer (graduate education tends to liberate one from petty concerns about, e.g., the efficiency of hardware-based integers)

-- the natural numbers, a la Peano

data Nat = Zero | Succ Nat


-- iteration and some applications

iter z s  Zero    = z
iter z s (Succ n) = s (iter z s n)

plus n = iter n     Succ
mult n = iter Zero (plus n)


-- primitive recursion

primrec z s  Zero    = z
primrec z s (Succ n) = s n (primrec z s n)


-- two versions of factorial

fac  = snd . iter (one, one) (\(a,b) -> (Succ a, mult a b))
fac' = primrec one (mult . Succ)


-- for convenience and testing (try e.g. "fac five")

int = iter 0 (1+)

instance Show Nat where
  show = show . int

(zero : one : two : three : four : five : _) = iterate Succ Zero


Origamist Haskell programmer
(always starts out with the “basic Bird fold”)

-- (curried, list) fold and an application

fold c n []     = n
fold c n (x:xs) = c x (fold c n xs)

prod = fold (*) 1


-- (curried, boolean-based, list) unfold and an application

unfold p f g x = 
  if p x 
     then [] 
     else f x : unfold p f g (g x)

downfrom = unfold (==0) id pred


-- hylomorphisms, as-is or "unfolded" (ouch! sorry ...)

refold  c n p f g   = fold c n . unfold p f g

refold' c n p f g x = 
  if p x 
     then n 
     else c (f x) (refold' c n p f g (g x))


-- several versions of factorial, all (extensionally) equivalent

fac   = prod . downfrom
fac'  = refold  (*) 1 (==0) id pred
fac'' = refold' (*) 1 (==0) id pred

Cartesianally-inclined Haskell programmer (prefers Greek food, avoids the spicy Indian stuff; inspired by Lex Augusteijn’s “Sorting Morphisms” [3])

-- (product-based, list) catamorphisms and an application

cata (n,c) []     = n
cata (n,c) (x:xs) = c (x, cata (n,c) xs)

mult = uncurry (*)
prod = cata (1, mult)


-- (co-product-based, list) anamorphisms and an application

ana f = either (const []) (cons . pair (id, ana f)) . f

cons = uncurry (:)

downfrom = ana uncount

uncount 0 = Left  ()
uncount n = Right (n, n-1)


-- two variations on list hylomorphisms

hylo  f  g    = cata g . ana f

hylo' f (n,c) = either (const n) (c . pair (id, hylo' f (c,n))) . f

pair (f,g) (x,y) = (f x, g y)


-- several versions of factorial, all (extensionally) equivalent

fac   = prod . downfrom
fac'  = hylo  uncount (1, mult)
fac'' = hylo' uncount (1, mult)

Ph.D. Haskell programmer (ate so many bananas that his eyes bugged out, now he needs new lenses!)

-- explicit type recursion based on functors

newtype Mu f = Mu (f (Mu f))  deriving Show

in      x  = Mu x
out (Mu x) = x


-- cata- and ana-morphisms, now for *arbitrary* (regular) base functors

cata phi = phi . fmap (cata phi) . out
ana  psi = in  . fmap (ana  psi) . psi


-- base functor and data type for natural numbers,
-- using a curried elimination operator

data N b = Zero | Succ b  deriving Show

instance Functor N where
  fmap f = nelim Zero (Succ . f)

nelim z s  Zero    = z
nelim z s (Succ n) = s n

type Nat = Mu N


-- conversion to internal numbers, conveniences and applications

int = cata (nelim 0 (1+))

instance Show Nat where
  show = show . int

zero = in   Zero
suck = in . Succ       -- pardon my "French" (Prelude conflict)

plus n = cata (nelim n     suck   )
mult n = cata (nelim zero (plus n))


-- base functor and data type for lists

data L a b = Nil | Cons a b  deriving Show

instance Functor (L a) where
  fmap f = lelim Nil (\a b -> Cons a (f b))

lelim n c  Nil       = n
lelim n c (Cons a b) = c a b

type List a = Mu (L a)


-- conversion to internal lists, conveniences and applications

list = cata (lelim [] (:))

instance Show a => Show (List a) where
  show = show . list

prod = cata (lelim (suck zero) mult)

upto = ana (nelim Nil (diag (Cons . suck)) . out)

diag f x = f x x

fac = prod . upto


Post-doc Haskell programmer
(from Uustalu, Vene and Pardo’s “Recursion Schemes from Comonads” [4])

-- explicit type recursion with functors and catamorphisms

newtype Mu f = In (f (Mu f))

unIn (In x) = x

cata phi = phi . fmap (cata phi) . unIn


-- base functor and data type for natural numbers,
-- using locally-defined "eliminators"

data N c = Z | S c

instance Functor N where
  fmap g  Z    = Z
  fmap g (S x) = S (g x)

type Nat = Mu N

zero   = In  Z
suck n = In (S n)

add m = cata phi where
  phi  Z    = m
  phi (S f) = suck f

mult m = cata phi where
  phi  Z    = zero
  phi (S f) = add m f


-- explicit products and their functorial action

data Prod e c = Pair c e

outl (Pair x y) = x
outr (Pair x y) = y

fork f g x = Pair (f x) (g x)

instance Functor (Prod e) where
  fmap g = fork (g . outl) outr


-- comonads, the categorical "opposite" of monads

class Functor n => Comonad n where
  extr :: n a -> a
  dupl :: n a -> n (n a)

instance Comonad (Prod e) where
  extr = outl
  dupl = fork id outr


-- generalized catamorphisms, zygomorphisms and paramorphisms

gcata :: (Functor f, Comonad n) =>
           (forall a. f (n a) -> n (f a))
             -> (f (n c) -> c) -> Mu f -> c

gcata dist phi = extr . cata (fmap phi . dist . fmap dupl)

zygo chi = gcata (fork (fmap outl) (chi . fmap outr))

para :: Functor f => (f (Prod (Mu f) c) -> c) -> Mu f -> c
para = zygo In


-- factorial, the *hard* way!

fac = para phi where
  phi  Z             = suck zero
  phi (S (Pair f n)) = mult f (suck n)


-- for convenience and testing

int = cata phi where
  phi  Z    = 0
  phi (S f) = 1 + f

instance Show (Mu N) where
  show = show . int

Tenured professor (teaching Haskell to freshmen)

fac n = product [1..n]
fortran
+1 - awesome. I don't even care whether or not it's correct. I don't know Haskell, and I'm glad for the opportunity to see it. Loved the progression in time for telling the story.
duffymo
-1. Interesting as it may be, this is totally off-topic and clutters the thread. Everyone, voting is not a popularity contest!
John
Zero effort, unless you're the original author of this blog post... which I doubt.
Derrick Turk
@Derrick 1. I'm not claiming the authorship of the post, I give credit to him by linking the original source. - 2. I had to format the code snippets (and there are a lot), so the effort, although small is strictly greater than zero.
fortran
@John the question is vague enough to make almost any answer in topic... and this one is even funny! :-p
fortran
Vague? It asks how to calculate a factorial in C. The post is funny, but should be in some other thread about code humor or something.
John
@John the title says "how to find a factorial?" the answer could be as well "looking for the ! sign", and the body says "How can I write a program to find the factorial of any number?" and the answer for that could be for example "using a text editor" or "You cannot calculate the factorial of *any number*, as it's defined only for natural numbers". So yes, it's vague.
fortran
I don't think so. I you are being deliberately pedantic, unless you are actually unable to understand what the question was asking like every other person who answered.
John
Am I? Let me check... `echo $CFLAGS` `-pedantic -Wall`, oh, that might be the reason, but anyway, the question is still either vague (does he need bigints, is a floating point approximation good enough, will the factorial be used in other operations so it won't be needed to be calculated entirely [as in for example a combinational number], how far has he gone before getting stuck, etc.) or lame (as it seems to be the case given the answer that was accepted, and in that case I think a hilarious answer is better than a lame answer).
fortran
Voting to close would be better so the question goes away or he asks it better. In a year when someone gets this as a Google result for factorials, they won't find it too useful I fear :)
John
At least they'll have a good time! :-D Not everything needs to be boring and work ;-)
fortran
I can't wait to start learning Haskell. I might go away and do it right now!
Callum Rogers
A: 

I don't think I'd use this in most cases, but one well-known practice which is becoming less widely used is to have a look-up table. If we're only working with built-in types, the memory hit is tiny.

Just another approach, to make the poster aware of a different technique. Many recursive solutions also can be memoized whereby a lookup table is filled in when the algorithm runs, drastically reducing the cost on future calls (kind of like the principle behind .NET JIT compilation I guess).

John
A: 

We have to start from 1 to the limit specfied say n.Start from 1*2*3...*n.

In c, i am writing it as a function.

main()
{
 int n;
 scanf("%d",&n);
 printf("%ld",fact(n));
}

long int fact(int n)
{
 long int facto=1;
 int i; 
for(i=1;i<=n;i++)
 {
  facto=facto*i;
 }
 return facto;
}
Raj
A: 

Simplest and efficent is to sum up logarhitms. If you use Log10 you get power and exponent.

Pseudocode

r=0
for i form 1 to n
    r=r+log(i)/log(10)

print "result is:", 10^(r-floor(r)) ,"*10^" , floor(r)

You might need to add the code so the integer part does not increase to much and thus decrease accuracy, but result suld be ok for even very large factorials.

ralu
Log operations are more expensive than simple multiplication.
EvilTeach
This code is not ment for speed but for simplicity.I was just able to calculate 1000000! whitout bignum library in 2sec using python and default float precision. Result was 8.2639294179038796*10^5565708 (correct res is 8.263931688331240*10^5565708 ) and whit improvement can be increased.
ralu
A: 

I have to make my CS professors proud and say that this is a perfect Dynamic Programming problem :)

Kyle
Is it? Dynamic programming is supposed to make the solution quicker by saving the answers to sub-problems and re-using those values. This is just straight recursion, there are no DP optimizations. Fibonacci on the other hand, you'd have a point.
John
Yeah, I think you're right. I think I got Fibonacci and factorial confused. Guess I won't make them proud after all.
Kyle
+1  A: 
#Newbie programmer
def factorial(x):
    if x == 0:
        return 1
    else:
        return x * factorial(x - 1)
print factorial(6)


#First year programmer, studied Pascal
def factorial(x):
    result = 1
    i = 2
    while i <= x:
        result = result * i
        i = i + 1
    return result
print factorial(6)


#First year programmer, studied C
def fact(x): #{
    result = i = 1;
    while (i <= x): #{
        result *= i;
        i += 1;
    #}
    return result;
#}
print(fact(6))


#First year programmer, SICP
@tailcall
def fact(x, acc=1):
    if (x > 1): return (fact((x - 1), (acc * x)))
    else:       return acc
print(fact(6))


#First year programmer, Python
def Factorial(x):
    res = 1
    for i in xrange(2, x + 1):
        res *= i
    return res
print Factorial(6)


#Lazy Python programmer
def fact(x):
    return x > 1 and x * fact(x - 1) or 1
print fact(6)


#Lazier Python programmer
f = lambda x: x and x * f(x - 1) or 1
print f(6)


#Python expert programmer
import operator as op
import functional as f
fact = lambda x: f.foldl(op.mul, 1, xrange(2, x + 1))
print fact(6)


#Python hacker
import sys
@tailcall
def fact(x, acc=1):
    if x: return fact(x.__sub__(1), acc.__mul__(x))
    return acc
sys.stdout.write(str(fact(6)) + '\n')


#EXPERT PROGRAMMER
import c_math
fact = c_math.fact
print fact(6)


#ENGLISH EXPERT PROGRAMMER
import c_maths
fact = c_maths.fact
print fact(6)


#Web designer
def factorial(x):
    #-------------------------------------------------
    #--- Code snippet from The Math Vault          ---
    #--- Calculate factorial (C) Arthur Smith 1999 ---
    #-------------------------------------------------
    result = str(1)
    i = 1 #Thanks Adam
    while i <= x:
        #result = result * i  #It's faster to use *=
        #result = str(result * result + i)
           #result = int(result *= i) #??????
        result str(int(result) * i)
        #result = int(str(result) * i)
        i = i + 1
    return result
print factorial(6)


#Unix programmer
import os
def fact(x):
    os.system('factorial ' + str(x))
fact(6)


#Windows programmer
NULL = None
def CalculateAndPrintFactorialEx(dwNumber,
                                 hOutputDevice,
                                 lpLparam,
                                 lpWparam,
                                 lpsscSecurity,
                                 *dwReserved):
    if lpsscSecurity != NULL:
        return NULL #Not implemented
    dwResult = dwCounter = 1
    while dwCounter <= dwNumber:
        dwResult *= dwCounter
        dwCounter += 1
    hOutputDevice.write(str(dwResult))
    hOutputDevice.write('\n')
    return 1
import sys
CalculateAndPrintFactorialEx(6, sys.stdout, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL)


#Enterprise programmer
def new(cls, *args, **kwargs):
    return cls(*args, **kwargs)

class Number(object):
    pass

class IntegralNumber(int, Number):
    def toInt(self):
        return new (int, self)

class InternalBase(object):
    def __init__(self, base):
        self.base = base.toInt()

    def getBase(self):
        return new (IntegralNumber, self.base)

class MathematicsSystem(object):
    def __init__(self, ibase):
        Abstract

    @classmethod
    def getInstance(cls, ibase):
        try:
            cls.__instance
        except AttributeError:
            cls.__instance = new (cls, ibase)
        return cls.__instance

class StandardMathematicsSystem(MathematicsSystem):
    def __init__(self, ibase):
        if ibase.getBase() != new (IntegralNumber, 2):
            raise NotImplementedError
        self.base = ibase.getBase()

    def calculateFactorial(self, target):
        result = new (IntegralNumber, 1)
        i = new (IntegralNumber, 2)
        while i <= target:
            result = result * i
            i = i + new (IntegralNumber, 1)
        return result

print StandardMathematicsSystem.getInstance(new (InternalBase, new (IntegralNumber, 2))).calculateFactorial(new (IntegralNumber, 6))

source http://gist.github.com/25049

Anantha Kumaran
The first one was at least funny. It got old real fast.
John
Just the first one was funny? I enjoyed them. Thanks Anantha.
philcolbourn
+1  A: 
int factorial(int n){
    return n <= 1 ? 1 : n * factorial(n-1);
}
Orr Matarasso
is factorial defined for numbers less than zero? Otherwise nice - perhaps a test to ensure the result is in the range of int (or unsigned)?
philcolbourn
A: 

In C99 (or Java) I would write the factorial function iteratively like this:

int factorial(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }
    return result;
}
  • C is not a functional language and you can't rely on tail-call optimization. So don't use recursion in C (or Java) unless you need to.

  • Just because factorial is often used as the first example for recursion it doesn't mean you need recursion to compute it.

  • This will overflow silently if n is too big, as is the custom in C (and Java).

  • If the numbers int can represent are too small for the factorials you want to compute then choose another number type. long long if it needs be just a little bit bigger, float or double if n isn't too big and you don't mind some imprecision, or big integers if you want the exact values of really big factorials.

starblue
As demonstrated by Odin, recursion can mean iteration if the tail-call can be eliminated. The code is then very easy to read, verify and understand what is going on - and space efficient O(1) and time efficient O(n) at the same time.With yours, you need to run a few test cases to check that all the boundary cases work.If you are worried about speed, then a lookup table is even faster than your version: space O(n), Time O(1).
philcolbourn
"This will overflow silently if n is too big". Signed integer overflow is actually undefined behaviour in C. You can fix this by using unsigned arithmetic, or by noting that in real life, compilers you meet do indeed perform signed overflow mod 2^N, or by avoiding overflow. I'm not sure it's fair to say that it's "the custom" in C to allow silent overflow - some functions and applications will ignore it (and some of those will crash eventually due to treating a result as correct when it is not), other functions and applications will carefully avoid it.
Steve Jessop