Calculate the factorial of a number

From CodeCodex

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.

Contents

[edit] Implementations

[edit] C/C++

Calculate a factorial recursively in C: 


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

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

Calculate a factorial iteratively in C: 


unsigned int counter = 5;
unsigned long factorial = 1;

while (counter > 0)
factorial *= counter--; /*Multiply, then decrement.*/

printf("%i", factorial);

[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] 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] 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

[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
Print factorial                       'Prints out the result.

[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}]]}]
  }
}

[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%.*}"
}

Or 

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

Or using GNU tools 

seq -s \* 5 | bc

[edit] Source

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