views:

11911

answers:

126

I want to see all the different ways you can come up with, for a factorial subroutine, or program. The hope is that anyone can come here and see if they might want to learn a new language.

Ideas:

  • Procedural
  • Functional
  • Object Oriented
  • One liners
  • Obfuscated
  • Oddball
  • Bad Code
  • Polyglot

Basically I want to see an example, of different ways of writing an algorithm, and what they would look like in different languages.

Please limit it to one example per entry. I will allow you to have more than one example per answer, if you are trying to highlight a specific style, language, or just a well thought out idea that lends itself to being in one post.

The only real requirement is it must find the factorial of a given argument, in all languages represented.

Be Creative!

Recommended Guideline:

# Language Name: Optional Style type

   - Optional bullet points

    Code Goes Here

Other informational text goes here

I will ocasionally go along and edit any answer that does not have decent formatting.

+2  A: 

Perl 6: Functional

multi factorial ( Int $n where { $n <= 0 } ){
  return 1;
}
multi factorial ( Int $n ){
   return $n * factorial( $n-1 );
}

This will also work:

multi factorial(0) { 1 }
multi factorial(Int $n) { $n * factorial($n - 1) }

Check Jonathan Worthington's journal on use.perl.org, for more information about the last example.

Brad Gilbert
http://www.rakudo.org/2008/12/rakudo-day-fixes-and-features.html
Brad Gilbert
+2  A: 

Perl 6:Procedural

sub factorial ( int $n ){

  my $result = 1;

  loop ( ; $n > 0; $n-- ){

    $result *= $n;

  }

  return $result;
}
Brad Gilbert
+1  A: 

C:

Edit: Actually C++ I guess, because of the variable declaration in the for loop.

 int factorial(int x) {
      int product = 1;

      for (int i = x; i > 0; i--) {
           product *= i;
      }

      return product;
 }
yjerem
C99 is fine with that.
aib
+2  A: 

Javascript:

factorial = function( n )
{
   return n > 0 ? n * factorial( n - 1 ) : 1;
}

I'm not sure what a Factorial is but that does what the other programs do in javascript.

Annan
This is what factorial is: http://en.wikipedia.org/wiki/Factorial
trinithis
+11  A: 

Haskell:

ones = 1 : ones
integers   = head ones     : zipWith (+) integers   (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
olliej
I think you are missing a parentheses, but the ( after the 3: is unnecessary.
Jared Updike
Your factorial is [1, 2, 3, 6, 18, 108, ...] instead of true factorial [1, 2, 6, 24, 120, 720, ...].
J.F. Sebastian
I have removed wrong and trivial definitions.
Alexander Prokofyev
`factorials = 1 : (scanl1 (*) . scanl1 (+) . repeat $ 1)`
trinithis
+7  A: 

Scheme

Here is a simple recursive definition:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

In Scheme tail-recursive functions use constant stack space. Here is a version of factorial that is tail-recursive:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))
Kyle Cronin
+1  A: 

C++

factorial(int n)
{
    for(int i=1, f = 1; i<=n; i++)
        f *= i;
    return f;
}
Niyaz
+5  A: 

C/C++: Procedural

unsigned long factorial(int n)
{
    unsigned long factorial = 1;
    int i;

    for (i = 2; i <= n; i++)
     factorial *= i;

    return factorial;
}

PHP: Procedural

function factorial($n)
{
    for ($factorial = 1, $i = 2; $i <= $n; $i++)
     $factorial *= $i;

    return $factorial;
}

@Niyaz: You didn't specify return type for the function

Imran
You really need to make sure n and $n are not negative!
jmucchiello
+108  A: 

lolcode:

sorry I couldn't resist xD

HAI
CAN HAS STDIO?
I HAS A VAR
I HAS A INT
I HAS A CHEEZBURGER
I HAS A FACTORIALNUM
IM IN YR LOOP
    UP VAR!!1
    TIEMZD INT!![CHEEZBURGER]
    UP FACTORIALNUM!!1
    IZ VAR BIGGER THAN FACTORIALNUM? GTFO
IM OUTTA YR LOOP
U SEEZ INT
KTHXBYE
Ed
LOL. Totally unexpected, loved it.
Alex
Love it. LOLCODE FTW!!
Nathan W
I accepted the answer because it was the highest voted answer. If someone posts a polyglot answer, I will accept it in a heartbeat.
Brad Gilbert
There's some problems here, like the fact that the loop will never gtfo. I pastebinned a better one http://pastebin.com/f7b2dd022
Chris Charabaruk
+7  A: 

D Templates: Functional

template factorial(int n : 1)
{
  const factorial = 1;
}

template factorial(int n)
{
  const factorial =
     n * factorial!(n-1);
}

or

template factorial(int n)
{
  static if(n == 1)
    const factorial = 1;
  else 
    const factorial =
       n * factorial!(n-1);
}

Used like this:

factorial!(5)
Brad Gilbert
In the second example remove the " : 1 "
Tim Matthews
Thanks. Another example where the type is chosen on template instantiation:template factorial(T, T n){ static if(n == 1) const factorial = 1; else const factorial = n * factorial!(T,n-1);}factorial!(int,5));
Tim Matthews
+2  A: 

Python:

Recursive

def fact(x): 
    return (1 if x==0 else x * fact(x-1))

Using iterator

import operator

def fact(x):
    return reduce(operator.mul, xrange(1, x+1))
Artur Carvalho
+2  A: 

two of many Mathematica solutions (although ! is built-in and efficient):

(* returns pure function *)
(FixedPoint[(If[#[[2]]>1,{#[[1]]*#[[2]],#[[2]]-1},#])&,{1,n}][[1]])&

(* not using built-in, returns pure function, don't use: might build 1..n list *)
(Times @@ Range[#])&
John the Statistician
+1  A: 

Java: functional

int factorial(int x) {
    return x == 0 ? 1 : x * factorial(x-1);
}
Josh Brown
yeah, well, funny if you don't have tail call optimization.
Svante
+3  A: 

Mathematica : using pure recursive functions

(If[#>1,# #0[#-1],1])&
John the Statistician
+4  A: 

Ruby: functional

def factorial(n)
    return 1 if n == 1
    n * factorial(n -1)
end
krujos
+3  A: 

Lua

function factorial (n)
  if (n <= 1) then return 1 end
  return n*factorial(n-1)
end

And here is a stack overflow caught in the wild:

> print (factorial(234132))
stdin:3: stack overflow
stack traceback:
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    ...
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:3: in function 'factorial'
    stdin:1: in main chunk
    [C]: ?
Jon Ericson
+9  A: 

F#: Functional

Straight forward:

let rec fact x = 
    if   x < 0 then failwith "Invalid value."
    elif x = 0 then 1
    else x * fact (x - 1)

Getting fancy:

let fact x = [1 .. x] |> List.fold_left ( * ) 1
Chris Smith
I didn't write this, I only improved the formatting.
Brad Gilbert
You can also get fancier with unfold: let factorial n = (1,1) |> Seq.unfold (fun (n,p) -> let p' = n*p in Some (p',(n+1,p'))) |> Seq.nth (n-1)
namin
@namim: or for something less overkill, "let fact x = [2 .. x] |> List.scan_left ( * ) 1"
Juliet
+1  A: 

Haskell: Functional

 fact 0 = 1
 fact n = n * fact (n-1)
Turambar
+40  A: 

C++: Template Metaprogramming

Uses the classic enum hack.

template<unsigned int n>
struct factorial {
    enum { result = n * factorial<n - 1>::result };
};

template<>
struct factorial<0> {
    enum { result = 1 };
};

Usage.

const unsigned int x = factorial<4>::result;

Factorial is calculated completely at compile time based on the template parameter n. Therefore, factorial<4>::result is a constant once the compiler has done its work.

cdv
The enum isn't needed if you just declare the result as a "static const int" field. I.e. "static const int result = n * factorial<n - 1>::result;".The "enum hack" is only needed for Visual Studio 6 C++ compiler, which didn't support templates properly.
pauldoo
A caveat with this solution is that, the ANSI C++ standard only enforces compilers to execute this kind of compile-time functions up to a limit - I believe 20 - of recursion levels. After that, you're in uncharted territory, left to the mercy of compiler creators.
Joe Pineda
I think factorial<20> is the largest factorial that can be represented by a signed 64-bit long, so that works out okay
Kip
@Kip is correct, 20! is less than 2^64, but 21! is larger than 2^64.
Wedge
pauldoo, but then you also have to define that static const integer. not doing so may end up in a compile error for some compiler (the standard allows compilers not to diagnose that violation - thus you often don't see it rejected)
Johannes Schaub - litb
litb: I thought the standard allowed const int's to be defined in the header only?
GMan
+1  A: 

This one not only calculates n!, it is also O(n!). It may have problems if you want to calculate anything "big" though.

long f(long n)
{
    long r=1;
    for (long i=1; i<n; i++)
        r=r*i;
    return r;
}

long factorial(long n)
{
    // iterative implementation should be efficient
    long result;
    for (long i=0; i<f(n); i++)
        result=result+1;
    return result;
}
1800 INFORMATION
+12  A: 

x86-64 Assembly: Procedural

You can call this from C (only tested with GCC on linux amd64). Assembly was assembled with nasm.

section .text
    global factorial
; factorial in x86-64 - n is passed in via RDI register
; takes a 64-bit unsigned integer
; returns a 64-bit unsigned integer in RAX register
; C declaration in GCC:
;   extern unsigned long long factorial(unsigned long long n);
factorial:
    enter 0,0
    ; n is placed in rdi by caller
    mov rax, 1 ; factorial = 1
    mov rcx, 2 ; i = 2
loopstart:
    cmp rcx, rdi
    ja loopend
    mul rcx ; factorial *= i
    inc rcx
    jmp loopstart
loopend:
    leave
    ret
cdv
No check for overflow!
Martin York
+2  A: 

Visual Basic: Linq

<Extension()> _
Public Function Product(ByVal xs As IEnumerable(Of Integer)) As Integer
    Return xs.Aggregate(1, Function(a, b) a * b)
End Function

Public Function Fact(ByVal n As Integer) As Integer
    Return Aggregate x In Enumerable.Range(1, n) Into Product()
End Function

This shows how to use the Aggregate keyword in VB. C# can't do this (although C# can of course call the extension method directly).

Konrad Rudolph
+5  A: 

PowerShell

function factorial( [int] $n ) 
{ 
    $result = 1; 

    if ( $n -gt 1 ) 
    { 
        $result = $n * ( factorial ( $n - 1 ) ) 
    } 

    $result 
}

Here's a one-liner:

$n..1 | % {$result = 1}{$result *= $_}{$result}
Jeff Hillman
+8  A: 

Recursive Prolog

fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.

Tail Recursive Prolog

fac(0,N,N).
fac(X,N,T) :- A is N * X, X1 is X - 1, fac(X1,A,T).
fac(N,T) :- fac(N,1,T).
Improved formatting
Brad Gilbert
i was expecting to find a prolog example. great! :-)
Paulo Guedes
+1  A: 

Bourne Shell: Functional

factorial() {
  if [ $1 -eq 0 ]
  then
    echo 1
    return
  fi

  a=`expr $1 - 1`
  expr $1 \* `factorial $a`
}

Also works for Korn Shell and Bourne Again Shell. :-)

Dave Webb
+1  A: 

Lisp recursive:

(defun factorial (x) 
   (if (<= x 1) 
       1 
       (* x (factorial (- x 1)))))
Alexander Stolz
recursive yes, but you should make it tail recursive to avoid the stack overflow.
Svante
+1  A: 

JavaScript Using anonymous functions:

var f = function(n){
  if(n>1){
    return arguments.callee(n-1)*n;
  }
  return 1;
}
Marius
+7  A: 

Oddball examples? What about using the gamma function! Since, Gamma n = (n-1)!.

OCaml: Using Gamma

let rec gamma z =
    let pi = 4.0 *. atan 1.0 in
    if z < 0.5 then
        pi /. ((sin (pi*.z)) *. (gamma (1.0 -. z)))
    else
        let consts = [| 0.99999999999980993; 676.5203681218851; -1259.1392167224028;
                        771.32342877765313; -176.61502916214059; 12.507343278686905;
                 -0.13857109526572012; 9.9843695780195716e-6; 1.5056327351493116e-7;
                     |] 
        in
        let z = z -. 1.0 in
        let results = Array.fold_right 
                          (fun x y -> x +. y)
                          (Array.mapi 
                              (fun i x -> if i = 0 then x else x /. (z+.(float i)))
                              consts
                          )
                          0.0
        in
        let x = z +. (float (Array.length consts)) -. 1.5 in
        let final = (sqrt (2.0*.pi)) *. 
                    (x ** (z+.0.5)) *.
                    (exp (-.x)) *. result
        in
        final

let factorial_gamma n = int_of_float (gamma (float (n+1)))
nlucaroni
+1  A: 

C: One liner, procedural

int f(int n) { for (int i = n - 1; i > 0; n *= i, i--); return n ? n : 1; }

I used int's for brevity; use other types to support larger numbers.

Tyler
One-liner? Really?
missingfaktor
+10  A: 

BASIC: old school

10 HOME
20 INPUT N
30 LET ANS = 1
40 FOR I = 1 TO N
50   ANS = ANS * I
60 NEXT I
70 PRINT ANS
Tyler
wow, good old times. :-)
Paulo Guedes
+6  A: 

Java 1.6: recursive, memoized (for subsequent calls)

private static Map<BigInteger, BigInteger> _results = new HashMap()

public static BigInteger factorial(BigInteger n){
    if (0 >= n.compareTo(BigInteger.ONE))
       return BigInteger.ONE.max(n);
    if (_results.containsKey(n))
       return _results.get(n);
    BigInteger result = factorial(n.subtract(BigInteger.ONE)).multiply(n);
    _results.put(n, result);
    return result;
}
rcreswick
Nice. And you can seed the memo-map to get the performance of the C# lookup approach.
Dov Wasserman
+2  A: 

Scheme : Functional - Tail Recursive

(define (factorial n)
  (define (fac-times n acc)
    (if (= n 0)
        acc
        (fac-times (- n 1) (* acc n))))
  (if (< n 0)
      (display "Wrong argument!")
      (fac-times n 1)))
grom
+9  A: 

Batch (NT):

@echo off

set n=%1
set result=1

for /l %%i in (%n%, -1, 1) do (
    set /a result=result * %%i
)

echo %result%

Usage: C:>factorial.bat 15

Jeff Hillman
Note that you need to have the registry patch to enable variable updates within loops!
Alex
Just out of curiosity, what patch is that? I certainly haven't ever modified my registry so I could do something like this.
Jeff Hillman
Works on my computer (Windows XP SP3) without any patches.
Alexander Prokofyev
@Jeff: See cmd /? and set /? for info about delayed variable expansion. If it's disabled by default, you need to either tweak the registry, launch cmd with the /v:on switch or just put put setlocal enabledelayedexpansion at the beginning of your batch file.
Helen
A: 

Haskell : Functional - Tail Recursive

factorial n = factorial' n 1

factorial' 0 a = a
factorial' n a = factorial' (n-1) (n*a)
grom
+3  A: 

Agda 2: Functional, dependently typed.

data Nat = zero | suc (m::Nat)

add (m::Nat) (n::Nat) :: Nat
 = case m of
     (zero ) -> n
     (suc p) -> suc (add p n)

mul (m::Nat) (n::Nat)::Nat
   = case m of
      (zero ) -> zero
      (suc p) -> add n (mul p n)

factorial (n::Nat)::Nat 
 = case n of
    (zero ) -> suc zero
    (suc p) -> mul n (factorial p)
Apocalisp
+21  A: 

C# Lookup:

Nothing to calculate really, just look it up. To extend it,add another 8 numbers to the table and 64 bit integers are at at their limit. Beyond that, a BigNum class is called for.

public static int Factorial(int f)
{ 
    if (f<0 || f>12)
    {
        throw new ArgumentException("Out of range for integer factorial");
    }
    int [] fact={1,1,2,6,24,120,720,5040,40320,362880,3628800,
                 39916800,479001600};
    return fact[f];
}
vzczc
Bravo. Perhaps the fastest implementation here, and as valid as it could be with that type signature.
Peter Burns
i think, many implementations can be faster for values from 0 to 12 because .NET can start slowly
valya
+27  A: 

Whitespace

   	.
 .
 	.
		.
  	.
   	.
			 .
 .
	 	 .
	  .
   	.
 .
  .
 			 .
		  			 .
 .
	.
.
  	 .
 .
.
	.
 	.
.
.
.

It was hard to get it to show here properly, but now I tried copying it from the preview and it works. You need to input the number and press enter.

Turambar
Wow, that was easy to understand :)
Shrivara
Makes even advanced languages like Haskell look downright obvious.
Jared Updike
+3  A: 

Delphi

facts: array[2..12] of integer;

function TForm1.calculate(f: integer): integer;
begin
    if f = 1 then
      Result := f
    else if f > High(facts) then
      Result := High(Integer)
    else if (facts[f] > 0) then
      Result := facts[f]
    else begin
      facts[f] := f * Calculate(f-1);
      Result := facts[f];
    end;
end;

initialize

  for i := Low(facts) to High(facts) do
    facts[i] := 0;

After the first time a factorial higher or equal to the desired value has been calculated, this algorithm just returns the factorial in constant time O(1).

It takes in account that int32 only can hold up to 12!

Ralph Rickenbach
I really dislike Delphi, but I love the fact this algorithm (unlike most of the others on this page) takes into account that factorial results don't change (and for large n are expensive) and you might as well only calculate a particular value once.
Steve Bosman
Improved formatting
Brad Gilbert
+22  A: 

Lazy K

Your pure functional programming nightmares come true!

The only Esoteric Turing-complete Programming Language that has:

Here's the Factorial code in all its parenthetical glory:

K(SII(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))))))))K))))))(S(K(S(K(S(SI(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))(S(S(KS)K))(S(SII)I(S(S(KS)K)I))))))))K)))))))
 (S(S(KS)K)(K(S(S(KS)K)))))))))(K(S(K(S(S(KS)K)))K))))(SII))II)

Features:

  • No subtraction or conditionals
  • Prints all factorials (if you wait long enough)
  • Uses a second layer of Church numerals to convert the Nth factorial to N! asterisks followed by a newline
  • Uses the Y combinator for recursion

In case you are interested in trying to understand it, here is the Scheme source code to run through the Lazier compiler:

(lazy-def '(fac input)
   '((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
       (* a n)))) 1 1))

(for suitable definitions of Y, cons, 1, 10, 42, 1+, and *).

EDIT:

Lazy K Factorial in Decimal

(10KB of gibberish or else I would paste it). For example, at the Unix prompt:

    $ echo "4" | ./lazy facdec.lazy
    24
    $ echo "5" | ./lazy facdec.lazy
    120

Rather slow for numbers above, say, 5.

The code is sort of bloated because we have to include library code for all of our own primitives (code written in Hazy, a lambda calculus interpreter and LC-to-Lazy K compiler written in Haskell).

Jared Updike
This makes lisp/scheme look like normal code...
RCIX
+11  A: 

C#: LINQ

    public static int factorial(int n)
    {
        return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
    }
aku
public static long factorial(int n){}
Chris S
public static long factorial(byte n){}
Chris Charabaruk
+5  A: 

The problem with most of the above is that they will run out of precision at about 25! (12! with 32 bit ints) or just overflow. Here's a c# implementation to break through these limits!

class Number
{
  public Number ()
  {
    m_number = "0";
  }

  public Number (string value)
  {
    m_number = value;
  }

  public int this [int column]
  {
    get
    {
      return column < m_number.Length ? m_number [m_number.Length - column - 1] - '0' : 0;
    }
  }

  public static implicit operator Number (string rhs)
  {
    return new Number (rhs);
  }

  public static bool operator == (Number lhs, Number rhs)
  {
    return lhs.m_number == rhs.m_number;
  }

  public static bool operator != (Number lhs, Number rhs)
  {
    return lhs.m_number != rhs.m_number;
  }

  public override bool Equals (object obj)
  {
     return this == (Number) obj;
  }

  public override int GetHashCode ()
  {
    return m_number.GetHashCode ();
  }

  public static Number operator + (Number lhs, Number rhs)
  {
    StringBuilder
      result = new StringBuilder (new string ('0', lhs.m_number.Length + rhs.m_number.Length));

    int
      carry = 0;

    for (int i = 0 ; i < result.Length ; ++i)
    {
      int
        sum = carry + lhs [i] + rhs [i],
        units = sum % 10;

      carry = sum / 10;

      result [result.Length - i - 1] = (char) ('0' + units);
    }

    return TrimLeadingZeros (result);
  }

  public static Number operator * (Number lhs, Number rhs)
  {
    StringBuilder
      result = new StringBuilder (new string ('0', lhs.m_number.Length + rhs.m_number.Length));

    for (int multiplier_index = rhs.m_number.Length - 1 ; multiplier_index >= 0 ; --multiplier_index)
    {
      int
        multiplier = rhs.m_number [multiplier_index] - '0',
        column = result.Length - rhs.m_number.Length + multiplier_index;

      for (int i = lhs.m_number.Length - 1 ; i >= 0 ; --i, --column)
      {
        int
          product = (lhs.m_number [i] - '0') * multiplier,
          units = product % 10,
          tens = product / 10,
          hundreds = 0,
          unit_sum = result [column] - '0' + units;

        if (unit_sum > 9)
        {
          unit_sum -= 10;
          ++tens;
        }

        result [column] = (char) ('0' + unit_sum);

        int
          tens_sum = result [column - 1] - '0' + tens;

        if (tens_sum > 9)
        {
          tens_sum -= 10;
          ++hundreds;
        }

        result [column - 1] = (char) ('0' + tens_sum);

        if (hundreds > 0)
        {
          int
            hundreds_sum = result [column - 2] - '0' + hundreds;

          result [column - 2] = (char) ('0' + hundreds_sum);
        }
      }
    }

    return TrimLeadingZeros (result);
  }

  public override string ToString ()
  {
    return m_number;
  }

  static string TrimLeadingZeros (StringBuilder number)
  {
    while (number [0] == '0' && number.Length > 1)
    {
      number.Remove (0, 1);
    }

    return number.ToString ();
  }

  string
    m_number;
}

static void Main (string [] args)
{
  Number
    a = new Number ("1"),
    b = new Number (args [0]),
    one = new Number ("1");

  for (Number c = new Number ("1") ; c != b ; )
  {
    c = c + one;
    a = a * c;
  }

  Console.WriteLine (string.Format ("{0}! = {1}", new object [] { b, a }));
}

FWIW: 10000! is over 35500 character long.

Skizz

Skizz
Isn't there a decimal type in C#? Using strings? ouch! What about GMP (the GNU MultiPrecision library in C, used by many languages for bignums).
Jared Updike
The decimal type has finite range, only much greater than doubles. Strings are really easy to print. You could use base 256 which would simplify the code a bit but would be awkward to convert to string. Swings and roundabouts I guess.
Skizz
What's why I started to learn Ruby. It has built in Bignum.
Alexander Prokofyev
@Alexander Prokofyev: Lots of languages have built-in bignum support.
Amuck
+16  A: 

Python: Functional, One-liner

factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)

NOTE:

  • It supports big integers. Example:

    print factorial(100) 93326215443944152681699238856266700490715968264381621468592963895217599993229915\ 608941463976156518286253697920827223758251185210916864000000000000000000000000

  • It does not work for n < 0.

J.F. Sebastian
operator.mul would be much faster than lambda x,y: x*y.
spiv
@spiv: `x*y` is 1.10-1.6 times slower then `mul`. math.factorial is faster then both. And memoized factorial is faster then math.factorial, etc. The question is not about performance.
J.F. Sebastian
+44  A: 

This is one of the faster algorithms, up to 170!. It fails inexplicably beyond 170!, and it's relatively slow for small factorials, but for factorials between 80 and 170 it's blazingly fast compared to many algorithms.

curl http://www.google.com/search?q=170!

There's also an online interface, try it out now!

Let me know if you find a bug, or faster implementation for large factorials.


EDIT:

This algorithm is slightly slower, but gives results beyond 170:

curl http://www58.wolframalpha.com/input/?i=171!

It also simplifies them into various other representations.

Adam Davis
Use MPFR (http://www.mpfr.org/). It allows floats with exponents in the 2^(2^32) range, or so...
Jared Updike
I managed to get it to work all the way up to 170.6243769!
Evan Fosmark
Any idea why it dies @ 171? must be some sort of upper limit on variable size...
TJB
I suspect that google's factorial algorithm has an limit to prevent inordinate amounts of processing time. Were I them, I'd simply use a table - and it could be that they felt the table needn't be any larger than 170 entries.
Adam Davis
I'm betting it's just 170 hard coded values
Chris S
That's a thing Wolfram Alpha performs better at than Google does :)
Moritz Beutel
Nice edit. I would vote this one up again.
Jared Updike
second one is pretty fast even:http://www58.wolframalpha.com/input/?i=9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999!
DShook
Chris S, surely not: Google can go beyond 170.http://www.google.com/search?q=170.62437!
Dykam
Google uses 1024bit numbers for internal representation. 171! is too big to fit in 1024 bits.
LiraNuna
@liraNuna - That's a great bit of information, thanks!
Adam Davis
@Adam: Google is using double-precision floats and you're hitting their maximum value.
Jon Harrop
yay!! `170.6243769563027208124443787857704267195526247611752350848214460792185169909237066410499619266308320574638750507720015864509844270281483286810591859944048382387248073012794174415578250989772916148232661861809004627715858001037512378786340697749539591336332530617682681!`
Lazer
... and the formatting of the page is destroyed!
Lazer
+1  A: 
J.F. Sebastian
As far as I am concerned this answer is unacceptable.
Brad Gilbert
@Brad: Could you elaborate?
J.F. Sebastian
It doesn't apear as if it was one file that it would run.
Brad Gilbert
It would be better to post them separately anyway.
Brad Gilbert
I would rather see these as a polyglot. http://en.wikipedia.org/wiki/Polyglot_%28computing%29
Brad Gilbert
Perhaps you should break up the code blocks.
Brad Gilbert
1. It does work as one file (how else I've got these microseconds). 2. The main function is `build_factorial_ext()`. The rest is there just for performance comparison. Therefore it would make no sense to post them separately. 3. It is *not* a polyglot. It just contains inline C++ in a Python module.
J.F. Sebastian
Really? Ok never mind.
Brad Gilbert
+4  A: 

Lambda Calculus

Input and output are Church numerals (i.e. natural number k is \f n. f^k n; so 3 = \f n. f (f (f n)))

(\x. x x) (\y f. f (y y f)) (\y n. n (\x y z. z) (\x y. x) (\f n. f n) (\f. n (y (\f m. n (\g h. h (g f)) (\x. m) (\x. x)) f)))
mweerden
+2  A: 

Ruby: Iterative

def factorial(n)
  (1 .. n).inject{|a, b| a*b}
end

Ruby: Recursive

def factorial(n)
  n == 1 ? 1 : n * factorial(n-1)
end
+3  A: 

Nemerle: Functional

def fact(n) {
    | 0 => 1
    | x => x * fact(x-1)
}
Cody Brocious
+3  A: 
#Language: T-SQL
#Style: Recursive, divide and conquer

Just for fun - in T-SQL using a divide and conquer recursive method. Yes, recursive - in SQL without stack overflow.

create function factorial(@b int=1, @e int) returns float as begin
  return case when @b>[email protected] then @e else 
      convert(float,dbo.factorial(@b,convert(int,@b+(@[email protected])/2)))
    * convert(float,dbo.factorial(convert(int,@b+1+(@[email protected])/2),@e)) end
end

call it like this:

print dbo.factorial(1,170) -- the 1 being the starting number
Hafthor
+2  A: 
#Language: T-SQL
#Style: Big Numbers

Here's another T-SQL solution -- supports big numbers in a most Rube Goldbergian manner. Lots of set-based ops. Tried to keep it uniquely SQL. Horrible performance (400! took 33 seconds on a Dell Latitude D830)

create function bigfact(@x varchar(max)) returns varchar(max) as begin
  declare @c int
  declare @n table(n int,e int)
  declare @f table(n int,e int)

  set @c=0
  while @c<len(@x) begin
    set @[email protected]+1
    insert @n(n,e) values(convert(int,substring(@x,@c,1)),len(@x)[email protected])
  end

  -- our current factorial
  insert @f(n,e) select 1,0

  while 1=1 begin
    declare @p table(n int,e int)
    delete @p
    -- product
    insert @p(n,e) select sum(f.n*n.n), f.e+n.e from @f f cross join @n n group by f.e+n.e

    -- normalize
    while 1=1 begin
      delete @f
      insert @f(n,e) select sum(n),e from (
        select (n % 10) as n,e from @p union all 
        select (n/10) % 10,e+1 from @p union all 
        select (n/100) %10,e+2 from @p union all 
        select (n/1000)%10,e+3 from @p union all 
        select (n/10000) % 10,e+4 from @p union all 
        select (n/100000)% 10,e+5 from @p union all 
        select (n/1000000)%10,e+6 from @p union all 
        select (n/10000000) % 10,e+7 from @p union all 
        select (n/100000000)% 10,e+8 from @p union all 
        select (n/1000000000)%10,e+9 from @p
      ) f group by e having sum(n)>0

      set @c=0
      select @c=count(*) from @f where n>9
      if @c=0 break
      delete @p
      insert @p(n,e) select n,e from @f
    end

    -- decrement
    update @n set n=n-1 where e=0

    -- normalize
    while 1=1 begin
      declare @e table(e int)
      delete @e
      insert @e(e) select e from @n where n<0
      if @@rowcount=0 break

      update @n set n=n+10 where e in (select e from @e)
      update @n set n=n-1 where e in (select e+1 from @e)
    end  

    set @c=0
    select @c=count(*) from @n where n>0
    if @c=0 break
  end

  select @c=max(e) from @f
  set @x=''
  declare @l varchar(max)
  while @c>=0 begin
    set @l='0'
    select @l=convert(varchar(max),n) from @f where [email protected]
    set @[email protected][email protected]
    set @[email protected]
  end
  return @x
end

Example:

print dbo.bigfact('69')

returns:

171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000
Hafthor
+31  A: 

I find the following implementations just hilarious:

The Evolution of a Haskell Programmer

Evolution of a Python programmer

Enjoy!

When I saw the question, I immediately thought of "The Evolution of a Haskell Programmer" :D
trinithis
+8  A: 

ruby recursive

(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1

usage:

factorial[5]
 => 120
AShelly
Improved formatting
Brad Gilbert
I would write that as (f=Hash.new{|h,k|h[k]=k*h[k-1]})[1]=1 or otherwise the calculated values are not stored
martinus
+2  A: 

Language Name: ChucK

Moog moog => dac;
4.0 => moog.gain;

for (0 => int i; i < 8; i++) {
    <<< factorial(i) >>>;
}

fun int factorial(int n) {
    1 => int result;
    if (n != 0) {
        n * factorial(n - 1) => result;
    }

    Std.mtof(result % 128) => moog.freq;
    0.25::second => now;

    return result;
}

And it sounds like this. Not terribly interesting, but, hey, it's just a factorial function!

Paul Reiners
+10  A: 

Brainf*ck

+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]

Written by Michael Reitzenstein.

TonJ
From http://www.blitzbasic.com/Community/posts.php?topic=36823.The output is placed in memory slot #2.
TonJ
Note: as a result, on the standard implementation, this can only compute up to 5!. (Memory cells are usually one byte.) See post #432010 for a solution.
A. Rex
+14  A: 

APL (oddball/one-liner):

×/⍳X
  1. ⍳X expands X into an array of the integers 1..X
  2. ×/ multiplies every element in the array

Or with the built-in operator:

!X

Source: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt

Christian Davén
+6  A: 
J.D. Fitz.Gerald
+1  A: 

Here is an interesting Ruby version. On my laptop it will find 30000! in under a second. (It takes longer for Ruby to format it for printing than to calculate it.) This is significantly faster than the naive solution of just multiplying the numbers in order.

def factorial (n)
  return multiply_range(1, n)
end

def multiply_range(n, m)
  if (m < n)
    return 1
  elsif (n == m)
    return m
  else
    i = (n + m) / 2
    return multiply_range(n, i) * multiply_range(i+1, m)
  end
end
This is *not* faster. What is the number of recursive calls for a given `n`? Additionally your solution is O(n) in space.
J.F. Sebastian
+2  A: 

Simple solutions are the best:

#include <stdexcept>;

long fact(long f)
{
    static long fact [] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 1932053504, 1278945280, 2004310016, 2004189184 };
    static long max     = sizeof(fact)/sizeof(long);

    if ((f < 0) || (f >= max))
    {   throw std::range_error("Factorial Range Error");
    }

    return fact[f];
}
Martin York
simple, but wrong !Thats why I hate languages without builtin arbitrary precision arithmetic !
blabla999
@blabla999: Not sure what you mean. This all integer based (this is not floating point).
Martin York
+2  A: 

Common Lisp: Lisp as God intended it to be used (that is, with LOOP)

(defun fact (n)
  (loop for i from 1 to n
        for acc = 1 then (* acc i)
        finally (return acc)))

Now, if someone can come up with a version based on FORMAT...

Matthias Benkard
mhmh - I always though god made pure lisp - and the devil added the rest... (just kidding)
blabla999
+2  A: 

Common Lisp: FORMAT (obfuscated)

Okay, so I'll give it a try myself.

(defun format-fact (stream arg colonp atsignp &rest args)
  (destructuring-bind (n acc) arg
    (format stream
            "~[~A~:;~*~/format-fact/~]"
            (1- n)
            acc
            (list (1- n) (* acc n)))))

(defun fact (n)
  (parse-integer (format nil "~/format-fact/" (list n 1))))

There has to be a nicer, even more obscure FORMAT-based implementation. This one is pretty straight-forward and boring, simply using FORMAT as an IF replacement. Obviously, I'm not a FORMAT expert.

Matthias Benkard
+12  A: 

Recursively in Inform 7

(it reminds you of COBOL because it's for writing text adventures; proportional font is deliberate):

To decide what number is the factorial of (n - a number):
    if n is zero, decide on one;
    otherwise decide on the factorial of (n minus one) times n.

If you want to actually call this function ("phrase") from a game you need to define an action and grammar rule:

"The factorial game" [this must be the first line of the source]

There is a room. [there has to be at least one!]

Factorialing is an action applying to a number.

Understand "factorial [a number]" as factorialing.

Carry out factorialing:
    Let n be the factorial of the number understood;
    Say "It's [n]".

Hugh Allen
This is valid code? lol.
Codygman
@Codygman: yes unfortunately.
Hugh Allen
+1  A: 

Scala: Recursive

  • Should compile to being tail recursive. Should!

.

def factorial( value: BigInt ): BigInt = value match {
  case 0 => 1
  case _ => value * factorial( value - 1 )
}
Calum
Even in a implementation which supports tail-recursion, this wouldn't be tail recursive, because the * operation is pending after the recursive call.
namin
+1  A: 

Occam-pi

PROC subprocess(MOBILE CHAN INT parent.out!,parent.in?)
INT value:
  SEQ
    parent.in ? value
      IF 
        value = 1
          SEQ
            parent.out ! value
        OTHERWISE
          INITIAL MOBILE CHAN INT child.in IS MOBILE CHAN INT:
          INITIAL MOBILE CHAN INT child.out IS MOBILE CHAN INT:
          FORKING
            INT newvalue:
            SEQ
              FORK subprocess(child.in!,child.out?)
              child.out ! (value-1)
              child.in ? newvalue
              parent.out ! (newalue*value)
:

PROC main(CHAN BYTE in?,src!,kyb?)
INITIAL INT value IS 0:
INITIAL MOBILE CHAN INT child.out is MOBILE CHAN INT
INITIAL MOBILE CHAN INT child.in is MOBILE CHAN INT
SEQ 
  WHILE TRUE
    SEQ
      subprocess(child.in!,child.out?)
      child.out ! value
      child.in ? value
      src ! value:
      value := value + 1
:
Dynite
+4  A: 

Icon

Recursive function

procedure factorial(n)
  return (0<n) * factorial(n-1) | 1
end

I've cheated a bit allowing negatives to return 1. If you want it to fail given a negative argument it's slightly less concise:

  return (0<n) * factorial(n-1) | (n=0 & 1)

Then

write(factorial(3))
write(factorial(-1))
write(factorial(20))

prints

6
2432902008176640000

Iterative generator

procedure factorials()
  local f,n
  f := 1; n := 0
  repeat suspend f *:= (n +:= 1)
end

Then

every write(factorials() \ 5)

prints

1
2
6
24
120

To understand this: evaluation is goal-directed and backtracks on failure. There is no boolean type, and binary operators which would return a boolean in other languages, either fail or return their second argument - with the exception of |, which in a single-value context returns its first argument if it succeeds, otherwise tries its second argument. (in a multiple-value context it returns its first argument then its second argument)

suspend is like yield in other languages, except that a generator is not explicitly called multiple times to return its results. Instead, every asks its argument for all values but doesn't return anything by default; it's useful with side-effects (in this case I/O).

\ limits the number of values returned by a generator, which in the case of factorials would be infinite.

Hugh Allen
A: 

FoxPro:

function factorial
    parameters n
return iif( n>0, n*factorial(n-1), 1)
Jiří Pospíšil
+1  A: 

OCaml

Lest anyone believe OCaml and oddball go hand-in-hand, I thought I would provide a sane implementation of factorial.

# let rec factorial n =
    if n=0 then 1 else n * factorial(n - 1);;

I don't think I made my case very well...

mbac32768
+2  A: 

AWK

#!/usr/bin/awk -f
{
    result=1;
    for(i=$1;i>0;i--){
        result=result*i;
    }
    print result;
}
dogbane
+1  A: 

Genuinely functional Java:

public final class Factorial {

  public static void main(String[] args) {
    final int n = Integer.valueOf(args[0]);
    System.out.println("Factorial of " + n + " is " + create(n).apply());
  }

  private static Function create(final int n) {
    return n == 0 ? new ZeroFactorialFunction() : new NFactorialFunction(n);
  }

  interface Function {
    int apply();
  }

  private static class NFactorialFunction implements Function {
    private final int n;
    public NFactorialFunction(final int n) {
      this.n = n;
    }
    @Override
    public int apply() {
      return n * Factorial.create(n - 1).apply();
    }
  }

  private static class ZeroFactorialFunction implements Function {
    @Override
    public int apply() {
      return 1;
    }
  }

}
Einar
+11  A: 

Erlang: tail recursive

fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).

fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
Alnitak
One-liner for the sake of it:> Fact = fun(N) when N > 0 -> lists:foldl(fun(X,Y)->X*Y end, 1, lists:seq(1,N)) end.
I GIVE TERRIBLE ADVICE
0! == 1 #SO comments must be at least 10 characters so here they are...
runrig
+2  A: 
#Language: T-SQL, C#
#Style: Custom Aggregate

Another crazy way would be to create a custom aggregate and apply it over a temporary table of the integers 1..n.

/* ProductAggregate.cs */
using System;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;

[Serializable]
[SqlUserDefinedAggregate(Format.Native)]
public struct product {
  private SqlDouble accum;
  public void Init() { accum = 1; }
  public void Accumulate(SqlDouble value) { accum *= value; }
  public void Merge(product value) { Accumulate(value.Terminate()); }
  public SqlDouble Terminate() { return accum; }
}

add this to sql

create assembly ProductAggregate from 'ProductAggregate.dll' with permission_set=safe -- mod path to point to actual dll location on disk.

create aggregate product(@a float) returns float external name ProductAggregate.product

create the table (there should be a built-in way to do this in SQL -- hmm. a question for SO?)

select 1 as n into #n union select 2 union select 3 union select 4 union select 5

then finally

select dbo.product(n) from #n
Hafthor
+4  A: 

The code below is tongue in cheek, however when you consider that the return value is limited to n < 34 for uint32, <65 uint64 before we run out of space for the return value with a uint, hard coding 33 values isn't that crazy :)

public static int Factorial(int n)
{
    switch (n)
    {
     case 1:
      return 1;
     case 2:
      return 2;
     case 3:
      return 6;
     case 4:
      return 24;
     default:
      throw new Exception("Sorry, I can only count to 4");
    }

}
Chris S
Funny, very non useful though.
Brad Gilbert
+1: very funny :-)
Nicola Bonelli
there is so much truth here - who needs factorials in a C-like language anyway ?
blabla999
why not use an array instead?
st0le
A: 

C# factorial using recursion in a single line

private static int factorial(int n){ if (n == 0)return 1;else return n * factorial(n - 1); }
milot
It's also tail-recursive.
Brad Gilbert
Are you sure it is?
Romain Verdier
+15  A: 

Perl6

sub factorial ($n) { [*] 1..$n }

I hardly know about Perl6. But I guess this [*] operator is same as Haskell's product.

This code runs on Pugs, and maybe Parrot (I didn't check it.)

Edit

This code also works.

sub postfix:<!> ($n) { [*] 1..$n }

# This function(?) call like below ... It looks like mathematical notation.
say 10!;
nwn
This has got to be the shortest one I have seen.
Brad Gilbert
Ok I guess there is one that is shorter, but who uses APL anyway. http://stackoverflow.com/questions/23930/factorial-algorithms-in-different-languages#81669
Brad Gilbert
multi postfix<!>($n){[*]1..$n}
Brad Gilbert
nwn
I just quickly posted a comment. The main point of the comment is TIMTOWTDI.
Brad Gilbert
http://stackoverflow.com/questions/237496/code-golf-factorials
Brad Gilbert
[*] 1..5 == 1 * 2 * 3 * 4 * 5; [+] 1..5 = 1 + 2 + 3 + 4 + 5
Brad Gilbert
Anonymous code block `say {[*]1..$^n}(5);`
Brad Gilbert
Uh oh. I might actually consider learning perl now.
Ellery Newcomer
Just don't try to learn Perl5 at the same time as trying to learn Perl6. Unless of course you want your head to explode.
Brad Gilbert
Rakudo now supports the postfix:<!> variant http://perlgeek.de/blog-en/perl-6/custom-operators-in-rakudo.writeback
Brad Gilbert
+2  A: 

Haskell:

factorial n = product [1..n]
Justice
+2  A: 

Eiffel


class
    APPLICATION
inherit
    ARGUMENTS

create
    make

feature -- Initialization

    make is
            -- Run application.
        local
            l_fact: NATURAL_64
        do
            l_fact := factorial(argument(1).to_natural_64)
            print("Result is: " + l_fact.out)
        end

    factorial(n: NATURAL_64): NATURAL_64 is
            --
        require
            positive_n: n >= 0
        do
            if n = 0 then
                Result := 1
            else
                Result := n * factorial(n-1)
            end
        end

end -- class APPLICATION
+3  A: 

PostScript: Tail Recursive

/fact0 { dup 2 lt { pop } { 2 copy mul 3 1 roll 1 sub exch pop fact0 } ifelse } def
/fact { 1 exch fact0 } def
plinth
+2  A: 

befunge-93

                                    v
>v"Please enter a number (1-16) : "0<
,:             >$*99g1-:99p#v_.25*,@
^_&:1-99p>:1-:!|10          < 
         ^     <

An esoteric language by Chris Pressey of Cat's Eye Technologies.

CodeSlave
+1  A: 

dc

Note: clobbers the e and f registers:

[2++d]se[d1-d_1<fd0>e*]sf

To use, put the value you want to take the factorial of on the top of the stack and then execute lfx (load the f register and execute it), which then pops the top of the stack and pushes that value's factorial.

Explanation: if the top of the stack is x, then the first part makes the top of the stack look like (x, x-1). If the new top-of-stack is non-negative, it calls factorial recursively, so now the stack is (x, (x-1)!) for x >= 1, or (0, -1) for x = 0. Then, if the new top-of-stack is negative, it executes 2++d, which replaces the (0, -1) with (1, 1). Finally, it multiplies the top two values on the stack.

Adam Rosenfield
+1  A: 

R - using S4 methods (recursively)

setGeneric( 'fct', function( x ) { standardGeneric( 'fct' ) } )
setMethod( 'fct', 'numeric', function( x ) { 
    lapply( x, function(a) { 
        if( a == 0 ) 1 else a * fact( a - 1 ) 
    } )
} )

Has the advantage that you can pass arrays of numbers in, and it will work them all out...

eg:

> fct( c( 3, 5, 6 ) )
[[1]]
[1] 6

[[2]]
[1] 120

[[3]]
[1] 720
tim_yates
+2  A: 

Perl (Y-combinator/Functional)

print sub {
  my $f = shift;
  sub {
    my $f1 = shift;
    $f->( sub { $f1->( $f1 )->( @_ ) } )
  }->( sub {
    my $f2 = shift;
    $f->( sub { $f2->( $f2 )->( @_ ) } )
  } )
}->( sub {
  my $h = shift;
  sub {
    my $n = shift;
    return 1 if $n <=1;
    return $n * $h->($n-1);
  }
})->(5);

Everything after 'print' and before the '->(5)' represents the subroutine. The factorial part is in the final "sub {...}". Everything else is to implement the Y-combinator.

runrig
Definitely one of the weirdest.
Brad Gilbert
+3  A: 

Forth (recursive):

: factorial ( n -- n )
    dup 1 > if
        dup 1 - recurse *
    else
        drop 1
     then
;
Anonymous
+14  A: 

XSLT 1.0

The input file, factorial.xml:

<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
  20
</n>

The XSLT file, factorial.xsl:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"                     
                xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:msxsl="urn:schemas-microsoft-com:xslt" >
  <xsl:output method="text"/>
  <!-- 0! = 1 -->
  <xsl:template match="text()[. = 0]">
    1
  </xsl:template>
  <!-- n! = (n-1)! * n-->
  <xsl:template match="text()[. > 0]">
    <xsl:variable name="x">
      <xsl:apply-templates select="msxsl:node-set( . - 1 )/text()"/>
    </xsl:variable>
    <xsl:value-of select="$x * ."/>
  </xsl:template>
  <!-- Calculate n! -->
  <xsl:template match="/n">
    <xsl:apply-templates select="text()"/>
  </xsl:template>
</xsl:stylesheet>

Save both files in the same directory and open factorial.xml in IE.

Danko Durbić
I just died a little.
jleedev
+2  A: 

J

   fact=. verb define
*/ >:@i. y
)
geocar
A: 

Iswim/Lucid:

factorial = 1 fby factorial * (time+1);

Chris Dodd
+1  A: 

Python, one liner:

A bit more clean than the other python answer. This, and the previous answer, will fail if the input is less than 1.

def fact(n): return reduce(int.mul,xrange(2,n))

+3  A: 

Clojure

Tail-recursive

(defn fact 
  ([n] (fact n 1))
  ([n acc] (if (= n 0) 
               acc 
               (recur (- n 1) (* acc n)))))

Short and simple

 (defn fact [n] (apply * (range 1 (+ n 1))))
Brian Carper
+1  A: 
Svante
A: 

Factor

USE: math.ranges

: factorial ( n -- n! ) 1 [a,b] product ;

+2  A: 

Scala

The factorial can be defined functionally as:

def fact(n: Int): BigInt = 1 to n reduceLeft(_*_)

or more traditionally as

def fact(n: Int): BigInt = if (n == 0) 1 else fact(n-1) * n

and we can make ! a valid method on Ints:

object extendBuiltins extends Application {

  class Factorizer(n: Int) {
    def ! = 1 to n reduceLeft(_*_)
  }

  implicit def int2fact(n: Int) = new Factorizer(n)

  println("10! = " + (10!))
}
namin
+3  A: 

Compile time in C++

template<unsigned i>
struct factorial
{ static const unsigned value = i * factorial<i-1>::value; };

template<>
struct factorial<0>
{ static const unsigned value = 1; };

Use in code as:

Factorial<5>::value
Chris Jefferson
+4  A: 

Haskell

factorial n = product [1..n]
Well, that is elegant.
akway
+5  A: 

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 [email protected](_: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]
Improved formatting
Brad Gilbert
Wow! I have no idea what he's talking about, but I'm sure if I understood it it would be really funny.
John M Gant
+2  A: 

Smalltalk, using a closure

    fac := [ :x | x = 0 ifTrue: [ 1 ] ifFalse: [ x * (fac value: x -1) ]].

    Transcript show: (fac value: 24) "-> 620448401733239439360000"

NB does not work in Squeak, requires full closures.

Adrian
+2  A: 

Smalltalk, memoized

Define a method on Dictionary

Dictionary >> fac: x
    ^self at: x ifAbsentPut: [ x * (self fac: x - 1) ]

usage

 d := Dictionary new.
 d at: 0 put: 1.
 d fac: 24
Adrian
+2  A: 

Smalltalk, 1-Liner

(1 to: 24) inject: 1 into: [ :a :b | a * b ]
Adrian
+3  A: 

Java Script: Creative method using "interview question" counting bits fnc.

function nu(x)
{
  var r=0
  while( x ) {
    x &= x-1
    r++
  }
  return r
}

function fac(n)
{
  var r= Math.pow(2,n-nu(n))

  for ( var i=3 ; i <= n ; i+= 2 )
    r *= Math.pow(i,Math.floor(Math.log(n/i)/Math.LN2)+1)
  return r
}

Works up to 21! then Chrome switches to scientific notation. Inspiration thanks lack of sleep and Knuth, et al's "concrete mathematics".

Tony Lee
+4  A: 

Nothing is as fast as bash & bc:

function fac { seq $1 | paste -sd* | bc; }  
$ fac 42
1405006117752879898543142606244511569936384000000000
$
Johannes Schaub - litb
+1  A: 

In MUMPS:

fact(N)
  N F,I S F=1 F  I=2:1:N S F=F*I
  QUIT F

Or, if you're a fan of indirection:

fact(N)
  N F,I S F=1 F I=2:1:N S F=F_"*"_I
  QUIT @F
Clayton
+2  A: 

Mathematica: non-recursive

fact[n_] := Times @@ Range[n]

Which is syntactic sugar for Apply[Times, Range[n]]. I think that's the best way to do it, not counting the built-in n!, of course. Note that that automatically uses bignums.

dreeves
+2  A: 

Common Lisp version:

(defun ! (n) (reduce #'* (loop for i from 2 below (+ n 1) collect i)))

Seems to be quite fast.

* (! 42)

1405006117752879898543142606244511569936384000000000
Nicolas Martyanoff
Why don't you loop for i from 2 upto n, instead of from 2 below (+ n 1)?
Svante
As you note, it's pretty fast on modern hardware, but it does use more memory than it needs to: it makes an O(n) list. Unfortunately, there's no built-in for LOOP for it, though ITERATE does provide a MULTIPLY clause.
Ken
A: 

Common Lisp, since noone has commited that yet:

(defun factorial (n)
  (if (<= n 1)
      1 
      (* n (factorial (1- n)))))
Pål GD
+3  A: 

Brainfuck: with bignum support!

Accepts as input a non-negative integer followed by newline, and outputs the corresponding factorial followed by newline.

>>>>,----------[>>>>,----------]>>>>++<<<<<<<<[>++++++[<----
-->-]<-<<<<]>>>>[[>>+<<-]>>[<<+>+>-]<->+<[>>>>+<<<-<[-]]>[-]
>>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]>>>>[-[>+<-]+>>>
>]<<<<[<<<<]<<<<[<<<<]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>+<<
<<-]<<<<]>>>>+<<<<<<<[<<<<]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>>>
+<<<-]>>>[<<<+>>+>-]<-[>>+<<[-]]<<[<<<<]>>>>[>[>+<-]>[<<+>+>
-]<<[>>>+<<<-]>>>[<<<+>>+>-]<->+++++++++[-<[-[>>>>+<<<<-]]>>
>>[<<<<+>>>>-]<<<]<[>>+<<<<[-]>>[<<+>>-]]>>]<<<<[<<<<]<<<[<<
<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-]>>[<<+>+>-]<->+<[>-<[-
]]>[-<<-<<<<[>>+<<-]>>[<<+>+>-]<->+<[>-<[-]]>]<<[<<<<]<<<<-[
>>+<<-]>>[<<+>+>-]+<[>-<[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<
<+>+>-]+<[>-<[-]]>]<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]<->+<[>>>
>+<<<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-]<--.<<
<<]++++++++++.

Unlike the brainf*ck answer posted earlier, this does not overflow any memory locations. (That implementation put n! in a single memory location, effectively limiting it to n less than 6 under standard bf rules.) This program will output n! for any value of n, limited only by time and memory (or bf implementation). For example, using Urban Muller's compiler on my machine, it takes 12 seconds to compute 1000! I think that's pretty good, considering the program can only move left/right and increment/decrement by one.

Believe it or not, this is the first bf program I've written; it took about 10 hours, which were mostly spent debugging. Unfortunately, I later found out that Daniel B Cristofani has written a factorial generator, which just outputs ever-larger factorials, never terminating:

>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-
]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<
<<<<<-[>+<-]]]]]]]]]]]>[<+>-]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>
>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[>+<-]<<<<]>>[->[-]
++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]

His program is much shorter, but he's practically a professional bf golfer.

A. Rex
+160  A: 

Polyglot: 5 languages, all using bignums

So, I wrote a polyglot which works in the three languages I often write in, as well as one from my other answer to this question and one I just learned today. It's a standalone program, which reads a single line containing a nonnegative integer and prints a single line containing its factorial. Bignums are used in all languages, so the maximum computable factorial depends only on your computer's resources.

  • Perl: uses built-in bignum package. Run with perl FILENAME.
  • Haskell: uses built-in bignums. Run with runhugs FILENAME or your favorite compiler's equivalent.
  • C++: requires GMP for bignum support. To compile with g++, use g++ -lgmpxx -lgmp -x c++ FILENAME to link against the right libraries. After compiling, run ./a.out. Or use your favorite compiler's equivalent.
  • brainf*ck: I wrote some bignum support in this post. Using Muller's classic distribution, compile with bf < FILENAME > EXECUTABLE. Make the output executable and run it. Or use your favorite distribution.
  • Whitespace: uses built-in bignum support. Run with wspace FILENAME.

Edit: added Whitespace as a fifth language. Incidentally, do not wrap the code with <code> tags; it breaks the Whitespace. Also, the code looks much nicer in fixed-width.

char //# b=0+0{- |0*/; #>>>>,----------[>>>>,--------
#define	a/*#--]>>>>++<<<<<<<<[>++++++[<------>-]<-<<<
#Perl	><><><>	 <> <> <<]>>>>[[>>+<<-]>>[<<+>+>-]<->
#C++	--><><>	<><><><	> < > <	+<[>>>>+<<<-<[-]]>[-]
#Haskell >>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]
#Whitespace	>>>>[-[>+<-]+>>>>]<<<<[<<<<]<<<<[<<<<
#brainf*ck > < ]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>*/
exp; ;//;#+<<<<-]<<<<]>>>>+<<<<<<<[<<<<][.POLYGLOT^5.
#include <gmpxx.h>//]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>>
#define	eval int	main()//>+<<<-]>>>[<<<+>>+>->
#include <iostream>//<]<-[>>+<<[-]]<<[<<<<]>>>>[>[>>>
#define	print std::cout	<< // >	<+<-]>[<<+>+>-]<<[>>>
#define	z std::cin>>//<< +<<<-]>>>[<<<+>>+>-]<->+++++
#define c/*++++[-<[-[>>>>+<<<<-]]>>>>[<<<<+>>>>-]<<*/
#define	abs int $n //><	<]<[>>+<<<<[-]>>[<<+>>-]]>>]<
#define	uc mpz_class fact(int	$n){/*<<<[<<<<]<<<[<<
use bignum;sub#<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-]
z{$_[0+0]=readline(*STDIN);}sub fact{my($n)=shift;#>>
#[<<+>+>-]<->+<[>-<[-]]>[-<<-<<<<[>>+<<-]>>[<<+>+>+*/
uc;if($n==0){return 1;}return $n*fact($n-1);	}//;#
eval{abs;z($n);print fact($n);print("\n")/*2;};#-]<->
'+<[>-<[-]]>]<<[<<<<]<<<<-[>>+<<-]>>[<<+>+>-]+<[>-+++
-}--	<[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<<+>+>-++
fact 0	= 1 -- ><><><><	> <><><	]+<[>-<[-]]>]<<[<<+ +
fact	n=n*fact(n-1){-<<]>>>>[[>>+<<-]>>[<<+>+++>+-}
main=do{n<-readLn;print(fact n)}-- +>-]<->+<[>>>>+<<+
{-x<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-]
<--.<<<<]+written+by+++A+Rex+++2009+.';#+++x-}--x*/;}
A. Rex
The largest factorial computable in one second (not counting output) on my computer by the various languages in this implementation: C++ gets 45000!, Haskell gets 35000!, Whitespace gets 11000!, Perl gets 2000!, and brainf*ck gets 350!.
A. Rex
Wow, somebody has some time on their hands. I'm actually considering this for the accepted answer.
Brad Gilbert
You asked for a polyglot. I deliver. =)
A. Rex
WTF +1 ~
Tim Matthews
After staring at this code for a few minutes, my eyes kept drifting unexplicably to the `offensive?` link....
AShelly
This is amazing and this answer should be the accepted one. Wow. My roommate and I just tried this in all the languages and are still in awe. Excellent job A. Rex
Justin Bennett
I love brainfuck.
Nosredna
This is now the accepted answer.
Brad Gilbert
This is insane.
GMan
My brain just imploded trying to understand this
lyrae
I am applauding this, it is so awesome.
Manuel Ferreria
This should be measured with WTFs per second.
Arnis L.
All I have to say is: brilliant, fucking brilliant.
John Bellone
[[email protected]:~]% g++ -lgmpxx -lgmp -x c++ -I/opt/local/include -o test test.cpptest.cpp:16:35: error: unterminated commentgcc version 4.2.1 (Apple Inc. build 5646):(
Steven Schlansker
@Steven Schlansker: It's a bug in the Stack Overflow display code that I don't know how to get around. (The code is being cut off above.) If you look at the revision history, it'll display the code correctly.
A. Rex
Hopefully got the spacing right, but that should have fixed the truncation issue.
random
@e.c.ho: You fixed the truncation issue but broke the Whitespace code. I've reverted back to my edit, which keeps the truncation issue fixed but makes the Whitespace work again. Thanks for your help! @Steven Schlansker: It should work now in all languages.
A. Rex
+1 for the AWESOMENESS
Pedro Ladaria
My Eyes .... My Eyes ....
Tim Post
+1  A: 

ActionScript: Procedural/OOP

function f(n) {
    var result = n>1 ? arguments.callee(n-1)*n : 1;
    return result;
}
// function call
f(3);
A: 

Common Lisp

I'm fairly sure this could be more effieicnet. It is my first lisp function other than "hello, world" and typing in the example code in the third chapter. Practical Common Lisp is a great text. This function does seem to handle large factorials well.

(defun factorial (x)
  (if (< x 2) (return-from factorial (print 1)))
  (let ((tempx 1) (ans 1))
  (loop until (equalp x tempx) do
       (incf tempx)
       (setf ans (* tempx ans)))
  (list ans)))
Phil
+2  A: 

Delphi iterative

While recursion can be the only decent solution to a problem, for factorials it is not. To describe it, yes. To program it, no. Iteration is cheapest.

This function calculates factorials for somewhat larger arguments.

function Factorial(aNumber: Int64): String;
var
  F: Double;
begin
  F := 0;
  while aNumber > 1 do begin
    F := F + log10(aNumber);
    dec(aNumber);
  end;
  Result := FloatToStr(Power(10, Frac(F))) + ' * 10^' + IntToStr(Trunc(F));
end;

1000000! = 8.2639327850046 * 10^5565708

stevenvh
I wanted to see many ways of writing a simple, well understood algorithm.
Brad Gilbert
Do I understand that this doesn't qualify?5! = 1 * 2 * 3 * 4 * 5thereforeln(5!) = ln(1) + ln(2) + ln(3) + ln(4) + ln(5)I must admit that I was kind of proud of myself when I "invented" this to compute large factorials on my TI-57, just for fun, many moons ago when I was 16.
stevenvh
+1  A: 

Hmm... no TCL

proc factorial {n} {
  if { $n == 0 } { return 1 }
  return [expr {$n*[factorial [expr {$n-1}]]}]
}
puts [factorial 6]

But of course that doesn't work for a damn for large values of n.... we can do better with tcllib!

package require math::bignum
proc factorial {n} {
  if { $n == 0 } { return 1 }
  return [ ::math::bignum::tostr [ ::math::bignum::mul [
    ::math::bignum::fromstr $n] [ ::math::bignum::fromstr [
      factorial [expr {$n-1} ]
    ]]]]
}
puts [factorial 60]

Look at all those ]'s at the end. This is practically LISP!

I'll leave the version for values of n>2^32 as an excersize for the reader

TokenMacGuy
Hmm... aren't these all examples of reasons NOT to use TCL? I'm converting to and from strings on each iteration. Is there a way to do this with tail-calls? does TCL have Tail Calls?(I cannot answer that last one)
TokenMacGuy
+2  A: 

Logo

? to factorial :n
> ifelse :n = 0 [output 1] [output :n * factorial :n - 1]
> end

And to invoke:

? print factorial 5
120

This is using the UCBLogo dialect of logo.

mweiss
+1  A: 

Mathematica, Memoized

f[n_ /; n < 2] := 1
f[n_] := (f[n] = n*f[n - 1])

Mathematica supports n! natively, but this shows how to make definitions on the fly. When you execute f[2], this code will make a definition f[2]=2 which will subsequently be executed no differently than if you'd hard-coded it; no need for an internal data structure; you just use the language's own function definition machinery.

jfklein
+1  A: 

Lisp : tail-recursive

(defun factorial(x)
  (labels((f (x acc)
             (if (> x 1)
                 (f (1- x)(* x acc))
                 acc)))
         (f x 1)))
+3  A: 

Agda2

It is Agda2, using the very nice Agda2 syntax.

module fac where

data Nat : Set where        -- Peano numbers
  zero : Nat
  suc : Nat -> Nat
{-# BUILTIN NATURAL Nat #-}
{-# BUILTIN SUC suc #-}
{-# BUILTIN ZERO zero #-}

infixl 10 _+_               -- Addition over Peano numbers
_+_ : Nat -> Nat -> Nat
zero + n    = n
(suc n) + m = suc (n + m)

infixl 20 _*_               -- Multiplication over Peano numbers
_*_ : Nat -> Nat -> Nat
zero * n = zero
n * zero = zero
(suc n) * (suc m) = suc n + (suc n * m)

_! : Nat -> Nat             -- Factorial function, syntax: "x !"
zero ! = suc zero
(suc n) ! = (suc n) * (n !)
fishlips
+1  A: 

Another ruby one.

class Integer
  def fact
    return 1 if self.zero?
    (1..self).to_a.inject(:*)
  end
end

This works if to_proc is supported on symbols.

Daniel Huckstep
+2  A: 

Perl, pessimal:

# Because there are just so many other ways to get programs wrong...
use strict;
use warnings;

sub factorial {
    my ($x)[email protected]_;

    for(my $f=1;;$f++) {
        my $tmp=$f;
        foreach my $g (1..$x) {
           $tmp/=$g;
        }
        return $f if $tmp == 1;
    }
}

I trust I get extra points for not using the '*' operator...

ijw
At least you started it out right, by using strict, and warnings.
Brad Gilbert
A: 
Gregory Higley
+1  A: 

Here's my proposal. Runs in Mathematica, works fine:

gen[f_, n_] := Module[{id = -1, val = Table[Null, {n}], visit},
  visit[k_] := Module[{t},
    id++; If[k != 0, val[[k]] = id];
    If[id == n, f[val]];
    Do[If[val[[t]] == Null, visit[t]], {t, 1, n}];
    id--; val[[k]] = Null;];
  visit[0];
  ]

Factorial[n_] := Module[{res=0}, gen[res++&, n]; res]

Update Ok, here's how it works: the visit function is from Sedgewick's Algorithm book, it "visits" all permutations of length n. Upon the visit, it calls function f with the permutation as an argument.

So, Factorial enumerates all permutations of length n, and for each permutation the counter res is increased, thus computing n! in O(n+1)! time.

nes1983
I wonder how this works. It seems it counts all possible permutations of length n, amirite?
Adrian
Yes exactly! And now I'm beyond the 15 character limit.
nes1983
A: 

Python:

def factorial(n):
    return reduce(lambda x, y: x * y,range(1, n + 1))
A: 

PHP - 59 chars

function f($n){return array_reduce(range(1,$n),'bcmul',1);}
Alix Axel
+2  A: 

*NIX Shell

Linux version:

seq -s'*' 42 | bc

BSD version:

jot -s'*' 42 | bc
worldi
A: 

SETL

...where Haskell and Python borrowed their list comprehensions from.

proc factorial(n);
    return 1 */ {1..n};
end factorial;

And the built-in INTEGER type is arbitrary-precision, so this will work for any positive n.

finnw
A: 

Befunge:

0&>:1-:v v *[email protected] 
  ^    _$>\:^
trinithis
A: 

CLOS

I see Common Lisp solutions abusing recursion, LOOP, and even FORMAT. I guess it's time for somebody to write a solution that abuses CLOS!

(defgeneric factorial (n))
(defmethod factorial ((n (eql 0))) 1)
(defmethod factorial ((n integer)) (* n (factorial (1- n))))

(Can your favorite language's object system dispatcher do that?)

Ken
A: 

Golfscript: designed for golfing, of course

~),1>{*}*
  • ~ evaluates the input string (to an integer)
  • ) increments the number
  • , is range (4, becomes [0 1 2 3])
  • 1> selects values whose index is 1 or bigger
  • {*}* folds multiplication over the list
  • Stack contents are printed when the program terminates.

To run:

echo 5 | ruby gs.rb fact.gs
nooodl
+1  A: 

FORTH, iterative 1 liner

: FACT 1 SWAP 1 + 1 DO I * LOOP ;
plinth
A: 

Oh fork() its another example in Perl

This will make use of your multiple core CPUs... although perhaps not in the most effective manner. The open statement clones the process with fork and opens a pipe from the child process to the parent. The work of multiplying numbers 2 at a time is split among a tree of very short lived processes. Of course, this example is a bit silly. The point is that if you actually had more difficult calculations to do then this example illustrates one way to divide up the work in parallel.

#!/usr/bin/perl -w

use strict;
use bigint;

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);
    }
}
Paul
A: 

In Io:

factorial := method(n,
    if (list(0, 1) contains(n),
       1,
       n * factorial(n - 1)
    )
)
prologic
+2  A: 

Scheme evolution

Regular Scheme program:

(define factorial
   (lambda (n)
     (if (= n 0)
         1
         (* n (factorial (- n 1))))))

Should work, but notice that calling this function on large numbers will extend the stack on every recursion, which is bad in languages like C and Java.

Continuation-passing style

(define factorial
  (lambda (n)
    (factorial_cps n (lambda (k) k))))

(define factorial_cps
  (lambda (n k)
    (if (zero? n)
        (k 1)
        (factorial (- n 1) (lambda (v)
                             (k (* n v)))))))

Ah, this way, we don't grow our stack every recursion because we can extend a continuation instead. However, C doesn't have continuations.

Representation-independent CPS

(define factorial
  (lambda (n)
    (factorial_cps n (k_))))

(define factorial_cps
  (lambda (n k)
    (if (zero? n)
        (apply_k 1)
        (factorial (- n 1) (k_extend n k))))

(define apply_k
  (lambda (ko v)
    (ko v)))
(define kt_empty
  (lambda ()
    (lambda (v) v)))
(define kt_extend 
  (lambda ()
    (lambda (v)
      (apply_k k (* n v)))))

Notice that responsibility for representation of the continuations used in the original CPS program has been shifted to the kt_ helper procedures.

Representation-independent CPS using ParentheC unions

Since representation of the continuations is in the helper procedures, we can switch to using ParentheC instead, with kt_ being a type designator.

(define factorial
  (lambda (n)
    (factorial_cps n (kt_empty))))

(define factorial_cps
  (lambda (n k)
    (if (zero? n)
        (apply_k 1)
        (factorial (- n 1) (kt_extend n k))))

(define-union kt
  (empty)
  (extend n k))
(define apply_k
  (lambda ()
    (union-case kh kt
      [(empty) v]
      [(extend n k) (begin
                      (set! kh k)
                      (set! v (* n v))
                      (apply_k))])))

Trampolined, registerized ParentheC program

That's not enough. We now replace all function calls by instead setting global variables and a program counter. Procedures are now labels suitable for GOTO statements.

(define-registers n k kh v)
(define-program-counter pc)

(define-label main
  (begin
    (set! n 5) ; what is the factorial of 5??
    (set! pc factorial_cps)
    (mount-trampoline kt_empty k pc)
    (printf "Factorial of 5: ~d\n" v)))

(define-label factorial_cps
  (if (zero? n)
      (begin
        (set! kh k)
        (set! v 1)
        (set! pc apply_k))
      (begin
        (set! k (kt_extend n k))
        (set! n (- n 1))
        (set! pc factorial_cps))))

(define-union kt
  (empty dismount) ; get off the trampoline!
  (extend n k))

(define-label apply_k
  (union-case kh kt
    [(empty dismount) (dismount-trampoline dismount)]
    [(extend n k) (begin
                    (set! kh k)
                    (set! v (* n v))
                    (set! pc apply_k))]))

Oh look, we have a main procedure now too. Now all that's left to do is save this file as fact5.pc and run it through ParentheC's pc2c:

> (load "pc2c.ss")
> (pc2c "fact5.pc" "fact5.c" "fact5.h")

Could it be? We got fact5.c and fact5.h. Let's see...

$ gcc fact5.c -o fact5
$ ./fact5
Factorial of 5: 120

Success! We have converted a recursive Scheme program into a non-recursive C program! And it only took several hours and many forehead-shaped impressions in the wall to do it! For convenience, fact5.c and and fact5.h.

erjiang
+3  A: 

Python: functional, recursive one-liner using short circuit boolean evaluation.

    factorial = lambda n: ((n <= 1) and 1) or (factorial(n-1) * n)
Robert William Hanks