Difference between revisions of "Calculate the factorial of a number"

From CodeCodex

(Erlang)
 
(52 intermediate revisions by 34 users not shown)
Line 1: Line 1:
These while loops will calculate the [http://en.wikipedia.org/wiki/Factorial Factorial] of a number:
+
{{Infobox See Also Math}}
 +
These [[while loop]]s will calculate the [http://en.wikipedia.org/wiki/Factorial Factorial] of a number.
  
===Visual Basic / QBasic===
+
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.
  
Dim counter as Integer : counter = 5
+
==Implementations==
Dim factorial as Long : factorial = 1
+
===C/C++===
While (counter > 0)
+
  factorial = factorial * counter    'Multiply
+
  counter = counter - 1              'Decrement
+
Wend
+
Print factorial                      'Prints out the result.
+
  
===REALbasic===
+
<pre class='c'>
  
Dim counter as Integer = 5
+
int factorial ( int x ) {
Dim factorial as Integer = 1
+
    int ret = 1;
While counter > 0
+
    for ( int i = 2; i <= x; i++ ) {
  factorial = factorial * counter     //Multiply
+
        ret = ret * i;
  counter = counter - 1              //Decrement
+
     }
Wend
+
    return ret;
MsgBox Str( factorial )              // Prints out the result.
+
}
 +
</pre>
  
===C or C  ===
+
===C++===
 +
<pre class="c">
 +
#include <numeric>
 +
#include <functional>
  
unsigned int counter = 5;
+
int factorial(int num) {
unsigned long factorial = 1;
+
  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;
 +
}
 +
</pre>
  
while (counter > 0)
+
===Common Lisp===
  factorial *= counter--; /*Multiply, then decrement.*/
+
<pre>
+
;;; This is tail recursive. Remember that tail-recursion optimization isn't
printf("%i", factorial);
+
;;; 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)))
 +
</pre>
 +
This is an optimized algorithm, you can find more about it and some other ways to
 +
increase its performance at [http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf].
 +
<pre>
 +
(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))))
 +
</pre>
  
===Recursive approach in C or C  ===
+
===Erlang===
 +
<pre>
 +
fact(0) -> 1;
 +
fact(N) -> N*fact(N-1).
 +
</pre>
  
unsigned long factorial(unsigned long f)
+
===Java, C#===
{
+
The code for the loop is the same for Java and C#:
    if (f) return(f * factorial(f - 1))
+
    return 1;
+
}
+
+
printf("%i", factorial(5));
+
  
===Perl===
+
''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="perl">
+
sub factorial {
+
    my $n = shift;
+
    my $f = 1;
+
    $f *= $n-- while $n > 0;    # Multiply, then decrement
+
    return $f;
+
}
+
  
sub recursive_factorial {
+
<pre class="java">
    my $n = shift;
+
int counter = 5;
    return $n * recursive_factorial($n - 1) if $n;
+
long factorial = counter;
    return 1;
+
while (counter > 1)
}
+
  factorial *= --counter; // Multiply the decremented number.
 +
                          //n! = n*(n-1)!
 +
</pre>
  
print factorial 5;
+
For Java the result is printed as follows:
print recursive_factorial 5;
+
<pre class="java">
</HIGHLIGHTSYNTAX>
+
System.out.println(factorial);
 +
</pre>
  
===Tcl (Tool command language)===
+
The equivalent in C# is:
  
set counter 5
+
<pre class="c#">
set factorial 1
+
System.Console.WriteLine(factorial);
while {$counter > 0} {
+
</pre>
  set factorial [expr $factorial * $counter]
+
  incr counter -1
+
}
+
puts $factorial
+
  
proc factorial n {
+
Rather than using a loop, use a recursive method:
  if {$n <= 0} {
+
    return 1
+
  } else {
+
    return [expr {$n * [factorial [expr {$n - 1}]]}]
+
  }
+
}
+
  
===Java, Csharp===
+
<pre class="java">
 +
/**
 +
* 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));
 +
}
 +
</pre>
  
The code for the loop is the same for Java and Csharp:
+
===Haskell===
 +
<pre>fact :: (Integral a) => a -> a
 +
fact 0 = 1
 +
fact n = n * fact (n-1)</pre>
 +
For example:
 +
<pre>
 +
> fact 5
 +
120
 +
</pre>
  
''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 double rather than a long or int, due to the far greater size of double-precision values.''
+
A one-liner:
 +
<pre>fact n = product [1..n]</pre>
 +
Or more verbosely:
 +
<pre>fact n = foldl (*) 1 [1..n]</pre>
 +
Pointfree:
 +
<pre>fact = product . enumFromTo 1</pre>
  
int counter = 5;
+
===Lua===
long factorial = counter;
+
<pre class="lua">
while (counter > 1)
+
-- ---------------------------------------------------------------------------
    factorial *= --counter; // Multiply the decremented number.
+
-- Function Factorial
//!n = n*(n-1)
+
--
 +
-- 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
  
For Java the result is printed as follows:
+
  if (0 > aNumber) then
 +
    error("Variable 'aNumber' is negative!", 0)
 +
  end
  
System.out.println(factorial);
+
  if (math.floor(aNumber) ~= aNumber) then
 +
    error("Variable 'aNumber' is not an integer!", 0)  
 +
  end
  
The equivalent in C# is:
+
  local numFactorial = 1
  
System.Console.WriteLine(factorial);
+
  for num = 2, aNumber do
 +
    numFactorial = numFactorial * num
 +
  end
  
Rather than using a loop, use a recursive method:
+
  return numFactorial
 
+
end
<pre>
+
    /**
+
    * 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));
+
    }
+
 
</pre>
 
</pre>
  
Line 137: Line 176:
 
</pre>
 
</pre>
  
===Pascal===
 
  
 +
====Example 3====
 +
<pre>
 +
# 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>
 +
</pre>
 +
For example:
 +
<pre>
 +
# fact 10;;
 +
- : int = 3628800
 +
</pre>
 +
 +
===Pascal===
 +
<pre class="pascal">
 
  program Factorial
 
  program Factorial
 
  var
 
  var
Line 151: Line 206:
 
   Write(Factorial);
 
   Write(Factorial);
 
  end.
 
  end.
 +
</pre>
 +
 +
===Perl===
 +
Memoized example:
 +
 +
<pre>
 +
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);
 +
</pre>
 +
 +
<pre>
 +
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;
 +
</pre>
 +
 +
<pre>
 +
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
 +
}
 +
</pre>
  
 
===Python===
 
===Python===
import operator
+
<pre class="python">
def factorial(num):
+
import operator
    return reduce(operator.mul, range(1, num   1))
+
def factorial(num):
 +
    return reduce(operator.mul, range(1, num + 1), 1) # the "1" initial value allows it to work for 0
 +
</pre>
  
===Scheme===
+
in Python 2.6+:
 +
<pre class="python">
 +
import math
 +
math.factorial(num)
 +
</pre>
  
  (define (fac n)
+
===Ruby===
 +
<pre class="ruby">
 +
def factorial(num)
 +
  (1..num).inject(1) {|a, b| a * b} # the "1" initial value allows it to work for 0
 +
end
 +
</pre>
 +
or shorter
 +
<pre class="ruby">
 +
def factorial(num)
 +
  (1..num).reduce(:*)
 +
end
 +
</pre>
 +
Recursive version:
 +
<pre class="ruby">
 +
def factorial(num)
 +
  num<1 ? 1 : factorial(num-1)*num
 +
end
 +
</pre>
 +
As a hacked in Integer method:
 +
<pre class="ruby">
 +
class Integer
 +
  # Example: 3.!
 +
  def !
 +
    (1..self).inject(1,:*)
 +
  end
 +
end
 +
</pre>
 +
 
 +
===QBasic / Visual Basic===
 +
<pre class="vb">
 +
  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
 +
</pre>
 +
 
 +
===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:
 +
<pre>
 +
(define (fac n)
 
   (if (= n 0)
 
   (if (= n 0)
 
       1
 
       1
 
       (* n (fac (- n 1)))))
 
       (* n (fac (- n 1)))))
;give fac a value of 5
+
;give fac a value of 5
(fac 5)
+
(fac 5)
 +
</pre>
  
 +
Iterative:
 +
<pre>
 +
(define (fac-iter n)
 +
  (let loop ((i n)
 +
            (result 1))
 +
    (if (= n 0)
 +
        result
 +
        (loop (- n 1) (* result n)))))
 +
</pre>
  
===Common Lisp===
+
===Tcl (Tool command language)===
 
<pre>
 
<pre>
;;; This is tail recursive. Remember that tail-recursion optimization isn't
+
set counter 5
;;; enabled by default in most CL compilers and interpreters
+
set factorial 1
(defun ! (n)
+
while {$counter > 0} {
    (labels
+
  set factorial [expr $factorial * $counter]
        ((fact1 (n m)
+
  incr counter -1
            (if (zerop n)
+
}
                m
+
puts $factorial
                (fact1 (1- n) (* m n)))))
+
    (fact1 n 1)))
+
 
</pre>
 
</pre>
This is an optimized algorithm, you can find more about it and some other ways to
+
or
increase its performance at [http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf].
+
 
<pre>
 
<pre>
(defun ! (n)
+
proc factorial n {
    (let ((shift 0))
+
  if {$n <= 0} {
        (labels ((fact1 (n m)
+
    return 1
                    (cond
+
  } else {
                        ((and (evenp n) (> m 1))
+
    return [expr {$n * [factorial [expr {$n - 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))))
+
 
</pre>
 
</pre>
 +
or in functional style
 +
<pre class="tcl">
 +
proc ! n {expr {$n<2? 1: $n*[! [incr n -1]]}}
 +
</pre>
 +
 +
===Zsh===
 +
<pre>
 +
factorial() {
 +
local -F1 a
 +
local b number
 +
a=1 ; b=1
 +
number=5 # Limited to 170
 +
while (( b++ < number )) { (( a = a * b )) }
 +
print "${a%.*}"
 +
}
 +
</pre>
 +
 +
Or
 +
 +
<pre>
 +
number=({1..5})
 +
print $((${(j:*:)number}))
 +
</pre>
 +
 +
Or using GNU tools
 +
 +
<pre>
 +
seq -s \* 5 | bc
 +
</pre>
 +
 
==Source==
 
==Source==
* [http://en.wikipedia.org/wiki/While_loop]
+
* [http://en.wikipedia.org/wiki/While_loop http://en.wikipedia.org/wiki/While_loop]
 +
 
  
[[Category:Visual Basic]]
 
[[Category:QBasic]]
 
[[Category:REALbasic]]
 
 
[[Category:C]]
 
[[Category:C]]
[[Category:C plus plus]]
+
[[Category:C++]]
[[Category:Perl]]
+
[[Category:Tcl]]
+
[[Category:Java]]
+
 
[[Category:C sharp]]
 
[[Category:C sharp]]
 +
[[Category:Common Lisp]]
 +
[[Category:Erlang]]
 +
[[Category:Haskell]]
 +
[[Category:Java]]
 +
[[Category:Objective Caml]]
 
[[Category:Pascal]]
 
[[Category:Pascal]]
 +
[[Category:Perl]]
 
[[Category:Python]]
 
[[Category:Python]]
 +
[[Category:QBasic]]
 +
[[Category:REALbasic]]
 +
[[Category:Ruby]]
 
[[Category:Scheme]]
 
[[Category:Scheme]]
 +
[[Category:Tcl]]
 +
[[Category:Visual Basic]]
 +
[[Category:Zsh]]
 +
 
[[Category:Math]]
 
[[Category:Math]]
[[Category:Common Lisp]]
 

Latest revision as of 23:17, 1 May 2012

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.

Implementations[edit]

C/C++[edit]


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

C++[edit]

#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;
}

Common Lisp[edit]

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

Erlang[edit]

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

Java, C#[edit]

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

Haskell[edit]

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

Lua[edit]

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

OCaml[edit]

Example 1[edit]

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

For example:

 # fact 5;;
 - : int = 120

Example 2[edit]

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

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

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

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
}

Python[edit]

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)

Ruby[edit]

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

QBasic / Visual Basic[edit]

 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

REALbasic[edit]

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

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

Tcl (Tool command language)[edit]

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

or

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

Zsh[edit]

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