Calculate the factorial of a number

From CodeCodex

Revision as of 07:44, 26 December 2009 by 65.7.166.232 (Talk)

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.

Implementations

C/C++

Calculate a factorial recursively in C: <highlightsyntax language="c"> unsigned long factorial(unsigned long f) {

  if (f) return(f * factorial(f - 1))
  return 1;

}

printf("%i", factorial(5)); </highlightsyntax> Calculate a factorial iteratively in C: <highlightsyntax language="c"> unsigned int counter = 5; unsigned long factorial = 1;

while (counter > 0)

 factorial *= counter--; /*Multiply, then decrement.*/

printf("%i", factorial); </highlightsyntax>

C++

<HIGHLIGHTSYNTAX language="cpp">

  1. include <numeric>
  2. 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;

} </HIGHLIGHTSYNTAX>

Common Lisp

<highlightsyntax language="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)))

</highlightsyntax> This is an optimized algorithm, you can find more about it and some other ways to increase its performance at [1]. <highlightsyntax language="lisp"> (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))))

</highlightsyntax>

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.

<highlightsyntax language="java122"> int counter = 5; long factorial = counter; while (counter > 1)

  factorial *= --counter; // Multiply the decremented number.
                          //!n = n*(n-1)

</highlightsyntax>

For Java the result is printed as follows: <highlightsyntax language="java122"> System.out.println(factorial); </highlightsyntax>

The equivalent in C# is:

<highlightsyntax language="csharp"> System.Console.WriteLine(factorial); </highlightsyntax>

Rather than using a loop, use a recursive method:

<highlightsyntax language="java122"> /**

* 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));

} </highlightsyntax>

Haskell

<highlightsyntax language="haskell">fact :: (Integral a) => a -> a fact 0 = 1 fact n = n * fact (n-1)</highlightsyntax> For example:

> fact 5
120

A one-liner: <highlightsyntax language="haskell">fact n = product [1..n]</highlightsyntax> Or more verbosely: <highlightsyntax language="haskell">fact n = foldl (*) 1 [1..n]</highlightsyntax> Pointfree: <highlightsyntax language="haskell">fact = product . enumFromTo 1</highlightsyntax>

OCaml

Example 1

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

For example:

 # fact 5;;
 - : int = 120

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


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

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.

Perl

Memoized example:

<highlightsyntax language=perl> 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); </highlightsyntax>

<HIGHLIGHTSYNTAX language="perl"> 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; </HIGHLIGHTSYNTAX>

<HIGHLIGHTSYNTAX language="perl"> 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

} </HIGHLIGHTSYNTAX>

Python

<HIGHLIGHTSYNTAX language="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

</HIGHLIGHTSYNTAX>

in Python 2.6+: <HIGHLIGHTSYNTAX language="python"> import math math.factorial(num) </HIGHLIGHTSYNTAX>

Ruby

<HIGHLIGHTSYNTAX language="ruby"> def factorial(num)

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

end </HIGHLIGHTSYNTAX> or shorter <HIGHLIGHTSYNTAX language="ruby"> def factorial(num)

  (1..num).reduce(:*)

end </HIGHLIGHTSYNTAX>

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.

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.

Scheme

Recursive: <highlightsyntax language="scheme"> (define (fac n)

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

(fac 5) </highlightsyntax>

Iterative: <highlightsyntax language="scheme"> (define (fac-iter n)

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

</highlightsyntax>

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

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

Source