How do I find the factorial of a positive number?

Question

The challenge:

Write a program or a function that inputs a positive number and returns its factorial.

^{Note: This is a code-trolling question. Please do not take the question and/or answers seriously. More information here. Every code-trolling question is also a popularity-contest question, so the highest voted answer wins.}

Answer 1

This is a very simple numerical computing problem that we can solve with Stirling's approximation:

As you can see, that formula features a square root, which we will also need a way to approximate. We will choose the so-called "Babylonian method" for that because it is arguably the simplest one:

Note that computing the square root this way is a good example of recursion.

Putting it all together in a Python program gives us the following solution to your problem:

def sqrt(x, n): # not the same n as below
    return .5 * (sqrt(x, n - 1) + x / sqrt(x, n - 1)) if n > 0 else x

n = float(raw_input())
print (n / 2.718) ** n * sqrt(2 * 3.141 * n, 10)

With a simple modification the above program can output a neat table of factorials:

1! =    0.92215
2! =    1.91922
3! =    5.83747
4! =   23.51371
5! =  118.06923
6! =  710.45304
7! = 4983.54173
8! = 39931.74015
9! = 359838.58817

This method should be sufficiently accurate for most applications.

Answer 2

C#

Sorry, but I hate recursive function.

public string Factorial(uint n) {
    return n + "!";
}

Answer 3

Java

public int factorial ( int n ) {
switch(n){
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 6;
case 4: return 24;
case 5: return 120;
case 6: return 720;
case 7: return 5040;
case 8: return 40320;
case 9: return 362880;
case 10: return 3628800;
case 11: return 39916800;
case 12: return 479001600;
default : throw new IllegalArgumentException();
}
}

Answer 4

Python

Of course the best way how to solve any problem is to use regular expressions:

import re

# adapted from http://stackoverflow.com/q/15175142/1333025
def multiple_replace(dict, text):
  # Create a regular expression  from the dictionary keys
  regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))
  # Repeat while any replacements are made.
  count = -1
  while count != 0:
    # For each match, look-up corresponding value in dictionary.
    (text, count) = regex.subn(lambda mo: dict[mo.string[mo.start():mo.end()]], text)
  return text

fdict = {
    'A': '@',
    'B': 'AA',
    'C': 'BBB',
    'D': 'CCCC',
    'E': 'DDDDD',
    'F': 'EEEEEE',
    'G': 'FFFFFFF',
    'H': 'GGGGGGGG',
    'I': 'HHHHHHHHH',
    'J': 'IIIIIIIIII',
    'K': 'JJJJJJJJJJJ',
    'L': 'KKKKKKKKKKKK',
    'M': 'LLLLLLLLLLLLL',
    'N': 'MMMMMMMMMMMMMM',
    'O': 'NNNNNNNNNNNNNNN',
    'P': 'OOOOOOOOOOOOOOOO',
    'Q': 'PPPPPPPPPPPPPPPPP',
    'R': 'QQQQQQQQQQQQQQQQQQ',
    'S': 'RRRRRRRRRRRRRRRRRRR',
    'T': 'SSSSSSSSSSSSSSSSSSSS',
    'U': 'TTTTTTTTTTTTTTTTTTTTT',
    'V': 'UUUUUUUUUUUUUUUUUUUUUU',
    'W': 'VVVVVVVVVVVVVVVVVVVVVVV',
    'X': 'WWWWWWWWWWWWWWWWWWWWWWWW',
    'Y': 'XXXXXXXXXXXXXXXXXXXXXXXXX',
    'Z': 'YYYYYYYYYYYYYYYYYYYYYYYYYY'}

def fact(n):
    return len(multiple_replace(fdict, chr(64 + n)))

if __name__ == "__main__":
    print fact(7)

Answer 5

Haskell

Short code is efficient code, so try this.

fac = length . permutations . flip take [1..]

Why it's trolling:

I'd laugh at any coder who wrote this... The inefficiency is beautiful. Also probably incomprehensible to any Haskell programmer who actually can't write a factorial function.

Edit: I posted this a while ago now, but I thought I'd clarify for future people and people who can't read Haskell.

The code here takes the list of the numbers 1 to n, creates the list of all permutations of that list, and returns the length of that list. On my machine it takes about 20 minutes for 13!. And then it ought to take four hours for 14! and then two and a half days for 15!. Except that at some point in there you run out of memory.

Edit 2: Actually you probably won't run out of memory due to this being Haskell (see the comment below). You might be able to force it to evaluate the list and hold it in memory somehow, but I don't know enough about optimizing (and unoptimizing) Haskell to know exactly how to do that.

Answer 6

C#

Since this is a math problem, it makes sense to use an application specifically designed to solve math problems to do this calculation...

Step 1:

Install MATLAB. A trial will work, I think, but this super-complicated problem is likely important enough to merit purchasing the full version of the application.

Step 2:

Include the MATLAB COM component in your application.

Step 3:

public string Factorial(uint n) {
    MLApp.MLApp matlab = new MLApp.MLApp();
    return matlab.Execute(String.Format("factorial({0})", n);
}

Answer 7

C#

Factorials are a higher level math operation that can be difficult to digest all in one go. The best solution in programming problems like this, is to break down one large task into smaller tasks.

Now, n! is defined as 1*2*...*n, so, in essence repeated multiplication, and multiplication is nothing but repeated addition. So, with that in mind, the following solves this problem:

long Factorial(int n)
{
    if(n==0)
    {
        return 1;
    }

    Stack<long> s = new Stack<long>();
    for(var i=1;i<=n;i++)
    {
        s.Push(i);
    }
    var items = new List<long>();
    var n2 = s.Pop();
    while(s.Count >0)
    {
        var n3 = s.Pop();
        items.AddRange(FactorialPart(n2,n3));
        n2 = items.Sum();
    }
    return items.Sum()/(n-1);
}

IEnumerable<long> FactorialPart(long n1, long n2)
{
    for(var i=0;i<n2;i++){
        yield return n1;
    }
}

Answer 8

#include <math.h>

int factorial(int n)
{
    const double g = 7;
    static const double p[] = { 0.99999999999980993, 676.5203681218851,
                                -1259.1392167224028, 771.32342877765313,
                                -176.61502916214059, 12.507343278686905,
                                -0.13857109526572012, 9.9843695780195716e-6,
                                1.5056327351493116e-7 };
    double z = n - 1 + 1;
    double x = p[0];
    int i;
    for ( i = 1; i < sizeof(p)/sizeof(p[0]); ++i )
        x += p[i] / (z + i);
    return sqrt(2 * M_PI) * pow(z + g + 0.5, z + 0.5)  * exp(-z -g -0.5) * x + 0.5;
}

Trolls:

• A 100% correct way of computing factorial that completely misses the point of either doing it iteratively or recursively.
• You have no idea why it works and could not generalize it to do anything else.
• More costly than just computing it with integer math.
• The most obvious "suboptimal" code (z = n - 1 + 1) is actually self-documenting if you know what's going on.
• For extra trolling I should compute p[] using a recursive calculation of the series coefficients!

(It's the Lanczos approximation of the gamma function)

Answer 9

We all know from college that the most efficient way to calculate a multiplication is through the use of logarithms. After all, why else would people use logarithm tables for hundreds of years?

So from the identity a*b=e^(log(a)+log(b)) we form the following Python code:

from math import log,exp

def fac_you(x):
    return round(exp(sum(map(log,range(1,x+1)))))

for i in range(1,99):
    print i,":",fac_you(i)

It creates a list of numbers from 1 to x, (the +1 is needed because Python sucks) calculates the logarithm of each, sums the numbers, raises the e to the power of the sum and finally rounds the value to the nearest integer (because Python sucks). Python has a built-in function for calculating factorials, but it only works for integers, so it can't produce big numbers (because Python sucks). This is why the function above is needed.

Btw, a general tip for students is that if something doesn't work as expected, it's probably because the language sucks.

Answer 10

Unfortunately, Javascript lacks a built-in way to compute the factorial. But, you can use its meaning in combinatorics to determine the value nevertheless:

The factorial of a number n is the number of permutations of an list of that size.

So, we can generate every list of n-digit number, check if it is a permutation, and if so, increment a counter:

window.factorial = function($nb_number) {
  $nb_trials = 1
  for($i = 0; $i < $nb_number; $i++) $nb_trials *= $nb_number
  $nb_successes = 0
  __trying__:
  for($nb_trial = 0; $nb_trial < $nb_trials; $nb_trial++){
    $a_trial_split = new Array
    $nb_tmp = $nb_trial
    for ($nb_digit = 0; $nb_digit < $nb_number; $nb_digit++){
      $a_trial_split[$nb_digit] = $nb_tmp - $nb_number * Math.floor($nb_tmp / $nb_number)
      $nb_tmp = Math.floor($nb_tmp / $nb_number)
    }
    for($i = 0; $i < $nb_number; $i++)
      for($j = 0; $j < $nb_number; $j++)
        if($i != $j)
          if($a_trial_split[$i] == $a_trial_split[$j])
            continue __trying__
    $nb_successes += 1
  }
  return $nb_successes
}

alert("input a number")
document.open()
document.write("<input type = text onblur = alert(factorial(parseInt(this.value))))>")
document.close()

---

---

Trolls:

• Types hungarian notation, snake_case and unneccessary sigils. How evil is that?
• Invented my own convention for jump labels, incompatible with the current use of this convention.
• Every possible variable is accidentally global.
• The solution is not O(n), not O(n!), but O(n^n). This alone would have sufficed to qualify here.
• Incrementing a number and then converting as base-n is a bad way to generate a list of sequences. Even if we did want duplicates. Mysteriously breaking for n > 13 is not the only reason.
• Of course we could have used number.toString(base), but that doesn't work for bases above 36. Yes, I know 36! is a lot, but still...
• Did I mention Javascript had the modulus operator? Or Math.pow? No? Oh well.
• Refusing to use ++ outside of for-loops makes it even more mysterious. Also, == is bad.
• Deeply nested braceless looping constructs. Also, nested conditionals instead of AND. Also, the outer condition could have been avoided by ending the inner loop at $i.
• The functions new Array, document.write (with friends) and alert (instead of a prompt or an input label) form a complete trifecta of function choice sins. Why is the input added dynamically after all?
• Inline event handlers. Oh, and deep piping is hell to debug.
• Unquoted attributes are fun, and the spaces around = make them even harder to read.
• Did I already mention I hate semicolons?

Answer 11

Ruby and WolframAlpha

This solution uses the WolframAlpha REST API to calculate the factorial, with RestClient to fetch the solution and Nokogiri to parse it. It doesn't reinvent any wheels and uses well tested and popular technologies to get the result in the most modern way possible.

require 'rest-client'
require 'nokogiri'

n = gets.chomp.to_i
response = Nokogiri::XML(RestClient.get("http://api.wolframalpha.com/v2/query?input=#{n}!&format=moutput&appid=YOUR_APP_KEY"))
puts response.xpath("//*/moutput/text()").text

Answer 12

Javascript

Javascript is a functional programming language, this means you have to use functions for everything because its faster.

function fac(n){
    var r = 1,
        a = Array.apply(null, Array(n)).map(Number.call, Number).map(function(n){r = r * (n + 1);});
    return r;
}

Answer 13

Using Bogo-Sort in Java

public class Factorial {
    public static void main(String[] args) {
        //take the factorial of the integers from 0 to 7:
        for(int i = 0; i < 8; i++) {
            System.out.println(i + ": " + accurate_factorial(i));
        }
    }
    
    //takes the average over many tries
    public static long accurate_factorial(int n) {
        double sum = 0;
        for(int i = 0; i < 10000; i++) {
            sum += factorial(n);
        }
        return Math.round(sum / 10000);
    }
    
    public static long factorial(int n) {
        //n! = number of ways to sort n
        //bogo-sort has O(n!) time, a good approximation for n!
        //for best results, average over several passes
        
        //create the list {1, 2, ..., n}
        int[] list = new int[n];
        for(int i = 0; i < n; i++)
            list[i] = i;
        
        //mess up list once before we begin
        randomize(list);
        
        long guesses = 1;
        
        while(!isSorted(list)) {
            randomize(list);
            guesses++;
        }
        
        return guesses;
    }
    
    public static void randomize(int[] list) {
        for(int i = 0; i < list.length; i++) {
            int j = (int) (Math.random() * list.length);
            
            //super-efficient way of swapping 2 elements without temp variables
            if(i != j) {
                list[i] ^= list[j];
                list[j] ^= list[i];
                list[i] ^= list[j];
            }
        }
    }
    
    public static boolean isSorted(int[] list) {
        for(int i = 1; i < list.length; i++) {
            if(list[i - 1] > list[i])
                return false;
        }
        return true;
    }
}

This actually works, just very slowly, and it isn't accurate for higher numbers.

Answer 14

PERL

Factorial can be a hard problem. A map/reduce like technique -- just like Google uses -- can split up the math by forking off a bunch of processes and collecting the results. This will make good use of all those cores or cpus in your system on a cold winter's night.

Save as f.perl and chmod 755 to make sure you can run it. You do have the Pathologically Eclectic Rubbish Lister installed, don't you?

#!/usr/bin/perl -w                                                              
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
    my($l, $h) = @_;
    return $l    if ($l==$h);
    return $l*$h if ($l==($h-1));
    # arghhh - multiplying more than 2 numbers at a time is too much work       
    # find the midpoint and split the work up :-)                               
    my $m = int(($h+$l)/2);
    my $pid = open(my $KID, "-|");
      if ($pid){ # parent                                                       
        my $X = &main::rangeProduct($l,$m);
        my $Y = <$KID>;
        chomp($Y);
        close($KID);
        die "kid failed" unless defined $Y;
        return $X*$Y;
      } else {
        # kid                                                                   
        print STDOUT &main::rangeProduct($m+1,$h)."\n";
        exit(0);
    }
}

Trolls:

• forks O(log2(N)) processes
• doesn't check how many CPUs or cores you have
• Hides lots of bigint/text conversions that occur in every process
• A for loop is often faster than this code

Answer 15

Python

Just an O(n!*n^2) algorithm to find the factorial. Base case handled. No overflows.

def divide(n,i):
    res=0
    while n>=i:
         res+=1
         n=n-i
    return res

def isdivisible(n,numbers):
    for i in numbers:
         if n%i!=0:
             return 0
         n=divide(n,i)
    return 1

def factorial(n):
    res = 1
    if n==0: return 1 #Handling the base case
    while not isdivisible(res,range(1,n+1)):
         res+=1
    return res

Answer 16

Well, there is an easy solution in Golfscript. You could use a Golfscript interpreter and run this code:

.!+,1\{)}%{*}/

Easy huh :) Good luck!

Answer 17

Mathematica

factorial[n_] := Length[Permutations[Table[k, {k, 1, n}]]]

It doesn't seem work for numbers larger than 11, and factorial[11] froze up my computer.

Answer 18

Ruby

f=->(n) { return 1 if n.zero?; t=0; t+=1 until t/n == f[n-1]; t }

The slowest one-liner I can imagine. It takes 2 minutes on an i7 processor to calculate 6!.

Answer 19

The correct approach for these difficult math problems is a DSL. So I'll model this in terms of a simple language

data DSL b a = Var x (b -> a)
             | Mult DSL DSL (b -> a)
             | Plus DSL DSL (b -> a)
             | Const Integer (b -> a) 

To write our DSL nicely, it's helpful to view it as a free monad generated by the algebraic functor

F X = X + F (DSL b (F X)) -- Informally define + to be the disjoint sum of two sets

We could write this in Haskell as

Free b a = Pure a
         | Free (DSL b (Free b a))

I will leave it to the reader to derive the trivial implementation of

join   :: Free b (Free b a) -> Free b a
return :: a -> Free b a
liftF  :: DSL b a -> Free b a

Now we can descibe an operation to model a factorial in this DSL

factorial :: Integer -> Free Integer Integer
factorial 0 = liftF $ Const 1 id
factorial n = do
  fact' <- factorial (n - 1)
  liftF $ Mult fact' n id

Now that we've modeled this, we just need to provide an actual interpretation function for our free monad.

denote :: Free Integer Integer -> Integer
denote (Pure a) = a
denote (Free (Const 0 rest)) = denote $ rest 0
...

And I'll leave the rest of the denotation to the reader.

To improve readability, it's sometimes helpful to present a concrete AST of the form

data AST = ConstE Integer
         | PlusE AST AST
         | MultE AST AST

and then right a trivial reflection

reify :: Free b Integer -> AST

and then it's straightforward to recursively evaluate the AST.

Answer 20

Python

Below is a Python version of the solution, which is not limited to the 32 bit (or 64 bit on a very recent system) limit for integer numbers in Python. To get around this limitation, we shall use a string as input and output for the factorial routine and internally split the string in it's digits to be able to perform the multiplication.

So here is the code: the getDigits function splits a string representing a number in to its digits, so "1234" becomes [ 4, 3, 2, 1 ] (the reverse order just makes the increase and multiply functions simpler). The increase function takes such a list and increases it by one. As the name suggests, the multiply function multiplies, e.g. multiply([2, 1], [3]) returns [ 6, 3 ] because 12 times 3 is 36. This works in the same way as you would multiply something with pen and paper.

Then finally, the factorial function uses these helper functions to calculate the actual factorial, for example factorial("9") gives "362880" as its output.

import copy

def getDigits(n):
    digits = []
    for c in n:
        digits.append(ord(c) - ord('0'))

    digits.reverse()
    return digits

def increase(d):
    d[0] += 1
    i = 0
    while d[i] >= 10:
        if i == len(d)-1:
            d.append(0)

        d[i] -= 10
        d[i+1] += 1
        i += 1

def multiply(a, b):
    subs = [ ]
    s0 = [ ]
    for bi in b:

        s = copy.copy(s0)
        carry = 0
        for ai in a:
            m = ai * bi + carry
            s.append(m%10)
            carry = m//10

        if carry != 0:
            s.append(carry)

        subs.append(s)
        s0.append(0)

    done = False
    res = [ ]
    termsum = 0
    pos = 0
    while not done:
        found = False
        for s in subs:
            if pos < len(s):
                found = True
                termsum += s[pos]

        if not found:
            if termsum != 0:
                res.append(termsum%10)
                termsum = termsum//10
            done = True
        else:
            res.append(termsum%10)
            termsum = termsum//10
            pos += 1

    while termsum != 0:
        res.append(termsum%10)
        termsum = termsum//10

    return res

def factorial(x):
    if x.strip() == "0" or x.strip() == "1":
        return "1"

    factorial = [ 1 ]
    done = False
    number = [ 1 ]
    stopNumber = getDigits(x)
    while not done:
        if number == stopNumber:
            done = True

        factorial = multiply(factorial, number)
        increase(number)

    factorial.reverse()

    result = ""
    for c in factorial:
        result += chr(c + ord('0'))

    return result

print factorial("9")

Notes

In python an integer doesn't have a limit, so if you'd like to do this manually you can just do

fac = 1
for i in range(2,n+1): 
    fac *= i

There's also the very convenient math.factorial(n) function.

This solution is obviously far more complex than it needs to be, but it does work and in fact it illustrates how you can calculate the factorial in case you are limited by 32 or 64 bits. So while nobody will believe this is the solution you've come up with for this simple (at least in Python) problem, you can actually learn something.

Answer 21

Python

The most reasonable solution is clearly to check through all numbers until you find the one which is the factorial of the given number.

print('Enter the number')
n=int(input())
x=1
while True:
    x+=1
    tempx=int(str(x))
    d=True
    for i in range(1, n+1):
        if tempx/i!=round(tempx/i):
            d=False
        else:
            tempx/=i
    if d:
        print(x)
        break

Answer 22

A most elegant recursive solution in C

Every one knows the most elegant solutions to factorials are recursive.

Factorial:

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

But multiplication can also be defined recursively as successive additions.

Multiplication:

n * 0 = 0
n * 1 = n
n * m = n + n * (m - 1)

And so can addition as successive incrementations.

Addition:

n + 0 = n
n + 1 = (n + 1)
n + m = (n + 1) + (m - 1)

In C, we can use ++x and --x to handle the primitives (x + 1) and (x - 1) respectively, so we have everything defined.

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

// For more elegance, use T for the type
typedef unsigned long T;

// For even more elegance, functions are small enough to fit on one line

// Addition
T A(T n, T m) { return (m > 0)? A(++n, --m) : n; }

// Multiplication
T M(T n, T m) { return (m > 1)? A(n, M(n, --m)): (m? n: 0); }

// Factorial
T F(T n) { T m = n; return (m > 1)? M(n, F(--m)): 1; }

int main(int argc, char **argv)
{
    if (argc != 2)
        return 1;

    printf("%lu\n", F(atol(argv[1])));

    return 0;
}

Let's try it out:

$ ./factorial 0
1
$ ./factorial 1
1
$ ./factorial 2
2
$ ./factorial 3
6
$ ./factorial 4
24
$ ./factorial 5
120
$ ./factorial 6
720
$ ./factorial 7
5040
$ ./factorial 8
40320

Perfect, although 8! took a long time for some reason. Oh well, the most elegant solutions aren't always the fastest. Let's continue:

$ ./factorial 9

Hmm, I'll let you know when it gets back...

Answer 23

Python

As @Matt_Sieker's answer indicated, factorials can be broken up into addition- why, breaking up tasks is the essence of programming. But, we can break that down into addition by 1!

def complicatedfactorial(n):
    def addby1(num):
        return num + 1
    def addnumbers(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addby1(cp2)
            b -= 1
    def multiply(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addnumbers(cp2,cp2)
    if n == 0:
        return 1
    else:
        return multiply(complicatedfactorial(n-1),n)

I think this code guarantees an SO Error, because

1. Recursion- warms it up

2. Each layer generates calls to multiply

3. which generates calls to addnumbers

4. which generates calls to addby1!

Too much functions,right?

Answer 24

Just go to Google and type in your factorial:

5!

http://lmgtfy.com/?q=5!

Answer 25

TI-Basic 84

:yumtcInputdrtb@gmail And:cReturnbunchojunk@Yahoo A!op:sEnd:theemailaddressIS Crazy ANSWER LOL

It really works :)

Answer 26

Javascript

Obviously the job of a programmer is to do as little work as possible, and to use as many libraries as possible. Therefore, we want to import jQuery and math.js. Now, the task is simple as this:

$.alert=function(message){
    alert(message);
}$.factorial=function(number){
    alert(math.eval(number+"!"));
    return math.eval(number+"!");
}
$.factorial(10);

Answer 27

Python

With just a slight modification of the standard recursive factorial implementation, it becomes intolerably slow for n > 10.

def factorial(n):
    if n in (0, 1):
        return 1
    else:
        result = 0
        for i in range(n):
            result += factorial(n - 1)
        return result

Answer 28

Bash

#! /bin/bash

function fact {
    if [[ ${1} -le 1 ]]; then
        return 1
    fi;

    fact $((${1} - 1))
    START=$(date +%s)
    for i in $(seq 1 $?); do sleep ${1}; done
    END=$(date +%s)
    RESULT=$(($END - $START))
    return $RESULT
}

fact ${1}
echo $?

Answer 29

Let's try to do it by the Monte Carlo Method. We all know that the probability of two random n-permutations being equal is exactly 1/n!. Therefore we can just check how many tests are needed (let's call this number b) until we get c hits. Then, n! ~ b/c.

Sage, should work in Python, too

def RandomPermutation(n) :           
    t = range(0,n)                   
    for i in xrange(n-1,0,-1):       
        x = t[i]                     
        r = randint(0,i)             
        t[i] = t[r]                  
        t[r] = x                     
    return t                         

def MonteCarloFactorial(n,c) :   
    a = 0                            
    b = 0                            
    t = RandomPermutation(n)         
    while a < c :                
        t2 = list(t)                 
        t = RandomPermutation(n)     
        if t == t2 :                 
            a += 1                   
        b += 1                       
    return round(b/c)            

MonteCarloFactorial(5,1000)
# returns an estimate of 5!

Answer 30

bash

Factorials are easily determined with well known command line tools from bash.

read -p "Enter number: " $n
seq 1 $n | xargs echo | tr ' ' '*' | bc

As @Aaron Davies mentioned in the comments, this looks much tidier and we all want a nice and tidy program, don't we?

read -p "Enter number: " $n
seq 1 $n | paste -sd\* | bc