Factorial Programs (Fortran and C Family)

Factorial Fun

 There are many computer programming languages and many more being developed all the time.  Usually the first program when learning a new language is "Hello World!", which outputs the text "Hello World!" to the screen.
For engineers, scientist and mathematicians the next program should be the factorial.  The factorial is symbolized with an exclamation point, !, after a positive integer.  It occurs often in probability and series.  The factorial is the product of all integers from one up to and including the number.

• 1! = 1
• 2! = 1*2 = 2
• 3! = 1*2*3 = 6
• 4! = 1*2*3*4 = 24
• 5! = 1*2*3*4*5 = 120

 The factorial increases rapidly showing computer artifacts due to limited precision.

The following example programs in various computer languages take a number from the user, without checking if it is valid, to keep the code simple, and returns its factorial.  Each example includes an introduction and detailed description.

The following programs have two loops.  A loop is where a section of code repeats by going back to the start of the loop.  The outer loop takes the number from the user and has a test to see if 0 was entered.  The inner loop computes the factorial by multiplying the numbers from 1 to the input number, 'n'.

FORTRAN

 FORTRAN is short for formula translation and it was the first successful computer language.  It allowed people to use something similar to standard mathematical formulas to program a computer for performing a calculation.  FORTRAN is still used extensively for computing, because there are many numerical libraries, it is easy to learn, and very efficient at number crunching.   FORTRAN was standardized by ANSI and later ISO/IEC.  FORTRAN 66 and FORTRAN 77 standards were similar, however, Fortran 90, Fortran 95 and on dropped some notation and added new features. The major change was that FORTRAN 77 was fixed format based on Hollerith punched cards that had 80 columns while later versions became free form.  FORTRAN compilers are still supposed to accept FORTRAN 77 input files.  In FORTRAN 77 columns 1-5 are identifier numbers, column 6 is a marker for continuation of the previous line, columns 7-72 are for the program statements and columns 73-80 are for identification information.  Also, a C in column 1 marks a comment line that is ignored by the compiler.  The final identification columns were very useful if the stack of cards was dropped.  FORTRAN also ignores the case so that 'FACTORIAL', 'factorial' and 'Factorial' are the same thing to the compiler. 

FORTRAN 77

 1:      PROGRAM FACTORIAL
 2:C     A program to compute the factorial of a number.
 3:C23456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 
 4:      INTEGER*8 K  
 5:C     INTEGER*4 N -- Optional statement 
 6:   20 CONTINUE  
 7:      WRITE(6,300)  
 8:      READ * , N  
 9:      IF ( N .LT. 1 ) STOP  
10:      K=1  
11:      DO 10 I=1,N  
12:       K = K*I  
13:   10 CONTINUE  
14:      WRITE(*,*) N,'! = ',K  
15:      GOTO 20  
16:  300 FORMAT("Enter a number > 0, or 0   
17:     &to quit")  
18:      END  

 Note: the line numbers are not part of the code and should be removed to compile the code.
Line Descriptions:

1. The PROGRAM statement is where the code starts. There must be exactly one PROGRAM statement for any code.
2. A Comment line ignored by the compiler but tells what the program does.
3. A comment line I use to track what columns I am using
4. Define K to be a double precision ( 8 Bytes) number
5. A comment line ignored by the compiler, by default variables with names begining with i,j,k,l,m or n are single precision integers number
6. The statement number is and address where the code may go to later. The CONTINUE statement does not do anything but indicates to go on to the next statement
7. A WRITE statement indicates to write or output to file pointer 6, which is the standard output, using format 300
8. READ from standard input a number, N. The read is list directed which means the read format is determined from the comma separated list of variables to read
9. If N is less than 1 stop the program
10. Set K equal to one, Otherwise K would start as some random number.
11. DO begins a loop that ends at marker 10. A loop is where the section of code between the DO and the '10 CONTINUE' is repeated. The loop variable I starts at 1 and increases by 1 each loop until it reaches K. 'I' will be N for the last time that the loop is repeated.
12. The variable K is set to K times I. Each time through the loop K is multiplied by a larger I value.
13. Marks the end of the loop 10
14. A List directed write statement which will write (output) according to the type of variable in the comma separated list. Note the text between the quotation marks is output as text. The first star indicates to write to standard output or unit 6.
15. GOTO sends the program to the statement labeled 20. Note that the statement number does not need to be in order which makes things confusing and GOTO statements are discouraged.
16. The format for the write on line 5. In this case only instructions are output as text.
17. The & in column 6 indicates that this is a continuation of the previous line with a space in column 72 after "to"
18. The end of the program. Only one end statement should be in a program file and a STOP is assumed before the end in FORTRAN 77. A STOP quits the program and an END marks the end of the program source code.

Exercises -
Save the code as fact.f
Compile the code.  "gfortran fact.f"
Run the code " ./a.out"
Enter the following numbers 1,2,3,4,5,10,12,13,14,19,20,21,22,64,65,66,100,one
Comment out line 4 by putting a C in column 1 and recompile
Enter the following numbers 1,2,3,4,5,10,12,13,14,32,33,34,100,one

Fortran 95

  In Fortran 90+ the column does not matter. Indentation is to help make the code readable.  At this level there is not much difference between Fortran 90 series and FORTRAN 77 series.

 1:PROGRAM FACTORIAL  
 2:  ! Program to compute the factorial of a number  
 3:  INTEGER (KIND=8) K  
 4:  DO  
 5:    WRITE( *,'(A)',ADVANCE='NO') 'Enter a number > 0 or 0 to quit :'  
 6:    READ *, N  
 7:    IF ( N < 1 ) EXIT  
 8:    K=1  
 9:    DO I=1,N  
10:      K = K*I  
11:    END DO  
12:    WRITE(UNIT=*,FMT="(I6,'! = ',I20)") N,K  
13:  END DO  
14:END  

Line Description

1. Still only one Program statement per program.  The main entry point and starting place of the program.
2. Comments start with an exclamation point. It can start anywhere on a line and continues to the end of the line
3. Named parameters now modify the variable definition.  Kind=8 sets the variable kind to 8 which is an 8 byte length
4. A 'DO' without anything else starts an infinite loop.  The loop repeats from a matching 'END DO'.  The 'DO' and 'END DO' can have names that must match.
5. Write to unit * (standard output) with format 'A' ( Text of any length ) and parameter ADVANCE set to no.  With Advance='NO' the program will not go to the next line, but will stay at the end of the line.
6. List directed read from unit * (standard input) the value for N
7. Test N and exit the DO if it is less than 1.
8. Iniitialize K to 1.  If not initialized K would be some random number
9. Start of the loop with index 'I' increasing from 1 up to and including N
10. Set 'K' to be 'K' times 'I', The value of K will be changed.
11. The end of the loop with index 'I'
12. Write to standard output with format of a 6 digit integer (I6) then the text '! = ', then a 20 digit integer
13. The end of the do loop without an index,  The code will return to the start of the DO
14. The END of the program.

Exercises -
Save the code as fact.f95
Compile the code.  "gfortran fact.f95"
Run the code " ./a.out"
Enter the following numbers 1,2,3,4,5,10,19,20,21,22,64,65,66,100
Comment out line 3 by putting an exclamation mark before INTEGER and recompile
Enter the following numbers 1,2,3,4,5,10,12,13,14,32,33,34,100

C Family

The 'C' family of programming languages, C,Objective C, Java, C++ have a similar syntax and appearance. They all use curly braces , {}, to group sets of commands. Parenthesis, (), are used for argument (or parameter) list where argument list are passed on to functions. Square brackets, [], are array indecies. Note that in C++ the parenthesis and square brackets can have there meaning changed though overloading.  These languages are case sensitive so that 'main', 'Main' and 'MAIN' are three different functions.

C

'C' is a minimal language with almost limitless capability, but few safeguards or programming aids.  'C' is available on almost all computing devices from embedded processors in toys to Supercomputers.  It is easy to make mistakes in 'C'.  The programmer must be very precise and complete for effective programming.  This language is also very well defined.  Check out http://www.ioccc.org/ for unique 'C' code examples that are very hard to read.

 1:#include <stdio.h>
 2:/* Program for computing the factorial of a number */
 3:int main(int nvar, char** vars) {
 4:  int n,i;
 5:  long long int k;
 6:  while( 1 ) {
 7:    printf("Enter a number > 0, or 0 to quit :");
 8:    scanf("%d\n",&n);
 9:    if( n < 1 ) break;
10:    for(i=1,k=1;i<=n;i++) {
11:      k *= i;
12:    }
13:    printf("%d! = %Ld\n",n,k);
14:  }
15:}

Line Descriptions

1. Includes the file stdio.h in this file before it is compiled.  stdio.h is the standard input/output header file.  It contains declarations for input and output functions used later.  Header files are usually located in the directory /usr/include, /usr/share/include or some other system location.
2. A comment begins with '/*' and ends with '*/'.  The compiler ignores everything (except a '/*' - why?) between the symbols.  It can include multiple lines.
3. This is the start point of all 'C' programs.  The first int indicates that the program will return an integer to the shell.  The arguments nvar and vars pass command line values to the program.  An optional main statement could be 'void main() {' which would ignore command line arguments.
4. Declares variables n and i to be integers.  An integer has a size that is efficient for the hardware, usually 4 bytes.  All variables in C must be declared, that is have there types defined.
5. Declares variable k to be at least 8 bytes.
6. A 'while' will repeat its statement as long as its argument is true.  In 'C' a number other than 0 is true.  This statement will repeat the code between curly braces forever.  Because 1 is always considered true.
7. This will  output the text.  By default it ends on the same line.
8. Read from standard input a decimal number and put it in the memory location of n.  In 'C' all arguments are passed as a copy of the value, so we gave the scanf function a copy of the memory location of 'n' rather than a copy of n.  scanf can then change the value at the memory location effectively changing n.
9. If n is less than 1 leave (break out of) the loop.  This will send the code to line 15 which will then end the program.  Alternatives to the break could be a 'return' or 'exit'.
10. The beginning of the factorial loop.  The 'for' statement has three parts inside the parenthesis separated by semicolons, ;, The first is an initialization where we set i=1 and k=1.  The next is an exit test performed at the start of the loop.  If this test is false the control will go past the end of the loop.   The third part updates index values.  'i++' indicates to add 1 to 'i' at the end of the loop.
11. This will replace the value of k with the current value of k times the value of i.  The *= shortens the statement from 'k = k * i'.
12. This curly brace ends the factorial calculation loop.  The code goes back to line 10.
13. Write the result to standard output with a format.  In the format %d indicates to write n as a decimal number and %Ld indicates to write k as a long long decimal number.  The %Ld format may not work on all compilers.
14. This curly brace ends the while loop.  The code goes back to line 6.
15. This curly brace ends the main function and hence the program.

Exercises -
Save the code as fact.c
Compile the code.  "gcc fact.c"
Run the code " ./a.out"
Enter the following numbers 1,2,3,4,5,10,19,20,21,22,64,65,66,100
Remove both longs from line 5 and recompile
Enter the following numbers 1,2,3,4,5,10,12,13,14,32,33,34,100
Put the longs back and remove the L from the printf in line 13 and recompile
Enter the following numbers 1,2,3,4,5,10,12,13,14,32,33,34,100

C++

C++ stands for C plus class.  Classes are an object oriented programming construct that is very useful for separating code into lots of parts.  Object oriented programming is good for graphical interfaces and data centric operations.  For our simple program there is not much difference but in another post including a graphical interface the code will change significantly.  The main difference in is the input and output statements.

 1:#include <iostream>
 2:// Program for computing the factorial of a number
 3:int main(int nvar, char** vars) {
 4:  int n,i;
 5:  long long int k;
 6:  while( 1 ) {
 7:    std::cout << "Enter a number > 0, or 0 to quit :";
 8:    std::cin >> n;
 9:    if( n < 1 ) break;
10:    for(i=1,k=1;i<=n;i++) {
11:      k *= i;
12:    }
13:    std::cout << n << "! = " << k << std::endl;
14:  }
15:}

Line Descriptions

1. Includes the iostream header for input and output
2. A one line comment starts with '//' and runs to the end of the line.
3. The main entry point - see C code line 3
4. Declarations for n and i
5. Declaration for k
6. Begin main loop
7. std:: is an indicator that the next item is in namespace std.  This is meant to avoid conflicts where an item may have naming conflicts.  We could have named a variable cout which would be different than the cout in the std namespace.  This namespace practice helps to isolate local variables from system or library variables.
   cout is an output stream connected to standard output.
   '<<' sends the next item to the output stream.  How it is sent depends on the item and other formatting information set on the stream.   Note that '<<' is the left shift operator by default.
   By default the stream stays at the last operation.
8. cin is an input stream connected to standard input.
   '>>' sends data to the next item.  A pointer to the memory location is not needed.   Note that '>>' is the right shift operator by default.
9. Exit condition test.
10. Loop for calculating the factorial
11. k = k * i
12. end of factorial loop
13. Sends the value of n, then the string "! = ", then value of k and finally a new line or carriage return to standard output.
14. end of the main loop.
15. end of the main function and the program.

Exercises -
Save the code as fact.cpp
Compile the code.  "g++ fact.cpp"
Run the code " ./a.out"
Compare what happens in the C++ code with what happens in the C code when you enter "Five".  Hint: For console programs a [Ctrl]C will stop a running program.

Java

Java was written to remove many problems in programming C++ by eliminating some features and maintaining stricter object orientation.   Java does not have direct access to pointers and has automatic garbage collection.  One of the major difficulties in C and C++ is memory leaks.  A memory leak is where the program allocates ( or reserves ) memory for a variable but does not properly deallocate (or free) the memory when it is done with the variable.  Another problem is when the memory is deallocated before being done with the variable.  Garbage collection is where the system keeps track of when the variable is no longer needed and will free the memory automatically.  Java also checks array bounds which is a problem often causing segmentation faults in other languages. 
Java is partially an interpreted language, that is the code runs one command at a time. Running java code involves two steps, first the code is compiled into "bytecode" with javac, then the bytecode, in a .class file, is run by an interpreter, "java". The interpreter is specific for each platform while the bytecode is independent of the computer platform. The interpreter is probably written in C for each platform. Java is a slow language and uses a lot of memory but it will run on most platforms. Java also has strong security mechanisms so that it is relatively safe to run programs downloaded from the internet, If you do not allow the program extra privileges.

 1:import java.io.*;
 2:class Fact {
 3:    /** Program to compute the factorial of a number*/
 4:    public static void main(String[] args) {
 5:        int i,n;
 6:        long k;
 7:        String nstr;
 8:        try{
 9:            InputStreamReader cin = new InputStreamReader(System.in);
10:            BufferedReader br = new BufferedReader(cin);
11:            while(true) {
12:                System.out.print("Enter a number > 0, or 0 to quit :");
13:                nstr = br.readLine();
14:                n = Integer.parseInt(nstr);
15:                if( n < 1) break;
16:                k = 1;
17:                for( i=1; i<=n; i++) {
18:                    k *= i;
19:                } // for(  i 
20:                System.out.println(n+"! = "+k); // Display the result.
21:           } // while(true)
22:       } catch( IOException ioe) {
23:            System.out.println(ioe);
24:       } finally {
25:            System.out.println("Leaving now!!");
26:       } // try
27:    } // main
28:} // class Fact

Line Descriptions

1. The import makes classes available to this program.  The star '*' is short for all so this import makes all of the classes in java/io available for this program.
2. Defines a class named Fact.  The file name should be the same as the main class with a ".java" appended.
3. A comment.  Comments in java can be multi-line starting with '/*' and ending with '*/' or to the end of the line starting with //.  The special three character start of a comment /** makes the comment appear in the documentation generated with javadoc or Doxygen.
4. This is the program starting main entry point.  In Java there can a main function in each class.  This is very handy because the main function can be a test function so each class can be executed by itself.  The qualifiers before main are : public - The function or data are available to all other classes in the code.  static - Indicates this is part of the class and there is only one.  When a class is instantiated (created) this is not copied.  Also, the class does not need to be instantiated to use this function or data.
5. Declares i and n to be of type int,  Numbers in Java are defined to be specific sizes so that an 'int' is always 4 Bytes instead of an efficient size for the hardware.
6. Declares k to be of type 'long' which is an eight byte integer.
7. The java io system reads only bytes, characters or Strings.  So the program needs a String object.
8. Error handling is enforced in Java.  The io methods may throw an exception (error) so our program must define a section of code we will try to run and if it fails we will catch the exception (error) and possibly do something to fix the problem.
9. The program needs a reader which can take data from a stream and convert it to characters.  System.in is the standard input InputStream.  An InputStream can only read bytes of data.
10. A BufferedReader can read a line of input as a String object.  This one is connected to the InputStreamReader created in line 9.  So now the BufferedReader sequence is System.in -[bytes]-> cin -[characters]-> br -[String]->.
11. Begin the outer loop that ends on line 21
12. Write the prompt to standard output (System.out)
13. Read a line from the BufferedReader br.
14. Convert the String nstr to an decimal integer by parsing it.
15. Test if the user wants to leave the loop and hence the program
16. initialize the value of k to 1.  The compiler will force the programmer to initialize all variables.
17. The loop to compute the factorial with i starting at 1 and increasing by 1 each loop until it is not less than or equal to n.
18. Reset k to be equal to k times i
19. end of the factorial for loop.  I have added a comment (//) to mark what this curly brace is closing.
20. Write the result.  println will write a String to the stream.  A String '+' a number will convert the number to a String and add it to the String. Therefore, n+"! = "+k, is a String.
21. End of the main loop with a comment to indicate what is ended
22. A catch will run a section of code if an Exception of the type in the catch is thrown in the matching try block.  In other words, if there was a problem in the input/output (IOException) run the following code block .
23. Write a statement to standard output about what was the problem.
24. A finally will be ran at the end of the matching try block whether or not an exception happened.
25. Write that the code is done to standard output.
26. End of the try/catch/finally code.
27. End of the main function with a comment
28. End of the class Fact with an optional comment.

Exercises -
Save the code as Fact.java
Compile the code "javac Fact.java"
Run the code "java Fact"
Test various numbers as above.

Java has a class for arbitrary precision integers called BigInteger.  The following code uses this class instead of a built-in long integer type for k.

import java.io.*;
import java.math.BigInteger;

class BigFact {
    /** Class to compute the factorial of a number to arbitrary precision*/
    public static void main(String[] args) {
        int i,n;
        BigInteger k;
        String nstr;
        try{
            InputStreamReader cin = new InputStreamReader(System.in);
            BufferedReader  br = new BufferedReader(cin);
            while(true) {
                System.out.print("Enter a number > 0 or 0 to quit :");
                nstr = br.readLine();
                n = Integer.parseInt(nstr);
                if( n < 1) break;
                k = BigInteger.ONE;
                for(i=1;i<=n;i++) {
                    k = k.multiply(BigInteger.valueOf(i));
                }
                System.out.println(n+"! = "+k.toString()); // Display the result.
           } // while(true)
       } catch( IOException ioe) {
            System.out.println(ioe);
       } finally {
            System.out.println("Leaving now!!");
       }
    } // main
} // class BigFact
 

Save the code as BigFact.java
Compile the code "javac BigFact.java"
Run the code "java BigFact"
Test various numbers as above.
Note what is in the low order decimal places for 100! and see if this helps to explain the results of 64!, 65! and 66! above.

C Note

The C programming languages are rentrant, that is a method can call itself.  This feature is often illustrated with a factorial computation program such as

#include <stdio.h>
/* Program for computing the factorial of a number */

long long int factorial(int i) {
 if( i == 1) return 1;
 return i*factorial(i-1);
}

int main(int nvar, char** vars) {
  int n;
  long long int k;
  while( 1 ) {
    printf("Enter a number > 0 or 0 to quit :");
    scanf("%d",&n);
    if( n < 1 ) break;
    k = factorial(n);
    printf("%d! = %Ld\n",n,k);
  }
}

This is an inefficient way to compute factorial because each entry into the function 'factorial' has some extra overhead.  In Java with larger numbers this could overflow the stack resulting in a program crash.