Calculate the factorial of a number

From CodeCodex

Related content:

These while loops will calculate the Factorial of a number.

In mathematics, the factorial of a number (that cannot be negative and must be an integer) n, denoted by n!, is the product of all positive integers less than or equal to n. For example: 5! is 5*4*3*2*1.

[edit] Implementations

[edit] C/C++


int factorial ( int x ) {
    int ret = 1;
    for ( int i = 2; i <= x; i++ ) {
        ret = ret * i;
    }
    return ret;
}

[edit] C++

#include <numeric>
#include <functional>

int factorial(int num) {
  int *array = new int[num];
  for (int i = 0; i < num; i++)
    array[i] = i+1;
  int result = std::accumulate(array, array+num, 1, std::multiplies<int>());
  delete [] array;
  return result;
}

[edit] Common Lisp

;;; This is tail recursive. Remember that tail-recursion optimization isn't
;;; enabled by default in most CL compilers and interpreters
(defun ! (n)
    (labels
        ((fact1 (n m)
             (if (zerop n)
                 m
                 (fact1 (1- n) (* m n)))))
    (fact1 n 1)))

This is an optimized algorithm, you can find more about it and some other ways to increase its performance at [1].

(defun ! (n)
    (let ((shift 0))
        (labels ((fact1 (n m)
                    (cond
                        ((and (evenp n) (> m 1))
                            (incf shift (ash n -1))
                            (fact1 (ash n -1) (ash m -1)))
                        ((<= n m) n)
                        (t (* (fact1 n (ash m 1)) (fact1 (- n m)(ash m 1)))))))
        (ash (fact1 n 1) shift))))

[edit] Erlang

fact(0) -> 1;
fact(N) -> N*fact(N-1).

[edit] Java, C#

The code for the loop is the same for Java and C#:

Note: if you intend to use the program to generate large factorials (such as 20!, 50! etc.) then you should store and return the factorial as a BigInteger rather than a long or int.

int counter = 5;
long factorial = counter;
while (counter > 1)
   factorial *= --counter; // Multiply the decremented number.
                           //n! = n*(n-1)!

For Java the result is printed as follows:

System.out.println(factorial);

The equivalent in C# is:

System.Console.WriteLine(factorial);

Rather than using a loop, use a recursive method:

/**
 * A recursive factorial calculation method
 *
 * @param n the number to be factored
 * @return the factorial of n
 */
public static int factorial(int n) {
    return ((n == 0) ? 1 : n * factorial(n - 1));
}

[edit] Haskell

fact :: (Integral a) => a -> a
fact 0 = 1
fact n = n * fact (n-1)

For example:

> fact 5
120

A one-liner:

fact n = product [1..n]

Or more verbosely:

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

Pointfree:

fact = product . enumFromTo 1

[edit] Lua

-- ---------------------------------------------------------------------------
-- Function Factorial
--
-- This function returns the factorial of a given non-negative integer.
-- ---------------------------------------------------------------------------
function Factorial(aNumber)
  if (type(aNumber) ~= "number") then 
    error("Variable 'aNumber' is not a number!", 0) 
  end

  if (0 > aNumber) then 
    error("Variable 'aNumber' is negative!", 0) 
  end

  if (math.floor(aNumber) ~= aNumber) then 
    error("Variable 'aNumber' is not an integer!", 0) 
  end

  local numFactorial = 1

  for num = 2, aNumber do
    numFactorial = numFactorial * num
  end

  return numFactorial
end

[edit] OCaml

[edit] Example 1

 # let rec fact = function
     | 0 -> 1
     | n -> n * fact(n-1);;
 val fact : int -> int = <fun>

For example:

 # fact 5;;
 - : int = 120

[edit] Example 2

# let rec f n = if n=0 then 1 else n*f(n-1);;
val f : int -> int = <fun>

For example:

# f 5;;
- : int = 120

[edit] Example 3

# let fact n =
  let rec loop n acc = match n with
    | 0 -> acc
    | _ -> loop (n - 1) (n * acc)
  in loop n 1;;
val f : int -> int = <fun>

For example:

# fact 10;;
- : int = 3628800

[edit] Pascal

 program Factorial
 var
   Counter, Factorial: integer;
 begin
   Counter := 5;
   Factorial := 1;
   while Counter > 0 do begin
     Factorial := Factorial * Counter;
     Counter := Counter - 1;
   end;
   Write(Factorial);
 end.

[edit] Perl

Memoized example:

my %table;
$table{0} = 1; # Manually linking input '0' to output '1' in the look-up table.

sub factorial {
    my $number = shift;
    my $factorial;

    if ( exists $table{$number} ) {
        return $table{$number}; # Input found in the look-up table, returning stored value.
    }
     else {
        $factorial = factorial($number - 1) * $number;
    }

    $table{$number} = $factorial; # Inserting newly calculated value into new table.

    return $factorial;
}

factorial(24);

sub factorial {
    my $n = shift;
    my $f = 1;
    $f *= $n-- while $n > 0;    # Multiply, then decrement
    return $f;
}

sub recursive_factorial {
    my $n = shift;
    return $n * recursive_factorial($n - 1) if $n;
    return 1;
}

sub functional_factorial {
    my $n = shift;
    return $n * recursive_factorial($n - 1) if $n;
    return 1;
}

print factorial 5;
print recursive_factorial 5;

use List::Util qw(reduce);

sub functional_factorial {
    my $n = shift;
    return reduce {$a * $b} 1, 1..$n; # the extra "1" enables it to work for n = 0
}

[edit] Python

import operator
def factorial(num):
    return reduce(operator.mul, range(1, num + 1), 1) # the "1" initial value allows it to work for 0

in Python 2.6+:

import math
math.factorial(num)

[edit] Ruby

def factorial(num)
  (1..num).inject(1) {|a, b| a * b} # the "1" initial value allows it to work for 0
end

or shorter

def factorial(num)
  (1..num).reduce(:*)
end

Recursive version:

def factorial(num)
  num<1 ? 1 : factorial(num-1)*num
end

As a hacked in Integer method:

class Integer
  # Example: 3.! 
  def !
    (1..self).inject(1,:*)
  end
end

[edit] QBasic / Visual Basic

 Dim counter as Integer : counter = 5
 Dim factorial as Long : factorial = 1
 While (counter > 0)
   factorial = factorial * counter     'Multiply
   counter = counter - 1               'Decrement
   WEND
End

[edit] REALbasic

Dim counter as Integer = 5
Dim factorial as Integer = 1
While counter > 0
  factorial = factorial * counter     //Multiply
  counter = counter - 1               //Decrement
Wend
MsgBox Str( factorial )               // Prints out the result.

[edit] Scheme

Recursive:

(define (fac n)
  (if (= n 0)
      1
      (* n (fac (- n 1)))))
;give fac a value of 5
(fac 5)

Iterative:

(define (fac-iter n)
  (let loop ((i n)
             (result 1))
    (if (= n 0)
        result
        (loop (- n 1) (* result n)))))

[edit] Tcl (Tool command language)

 set counter 5
 set factorial 1
 while {$counter > 0} {
   set factorial [expr $factorial * $counter] 
   incr counter -1 
 }
 puts $factorial

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

or in functional style

proc ! n {expr {$n<2? 1: $n*[! [incr n -1]]}}

[edit] Zsh

factorial() {
	local -F1 a
	local b number
	a=1 ; b=1
	number=5 # Limited to 170
	while (( b++ < number )) { (( a = a * b )) }
	print "${a%.*}"
}

number=({1..5})
print $((${(j:*:)number}))

Or using GNU tools

seq -s \* 5 | bc

[edit] Source

http://en.wikipedia.org/wiki/While_loop

Retrieved from "http://www.codecodex.com/wiki/Calculate_the_factorial_of_a_number"

Calculate the factorial of a number

Calculate the factorial of a number

From CodeCodex

Contents

[edit] Implementations

[edit] C/C++

[edit] C++

[edit] Common Lisp

[edit] Erlang

[edit] Java, C#

[edit] Haskell

[edit] Lua

[edit] OCaml

[edit] Example 1

[edit] Example 2

[edit] Example 3

[edit] Pascal

[edit] Perl

[edit] Python

[edit] Ruby

[edit] QBasic / Visual Basic

[edit] REALbasic

[edit] Scheme

[edit] Tcl (Tool command language)

[edit] Zsh

[edit] Source