5
\$\begingroup\$

I have created what was a rather simple piece of code to calculate the factorial of a number, although I wanted to ensure that my program could calculate the factorial of any given number. To do this, the only data type I thought was relevant was BigInteger. The problem I had with this was that my code quickly became quite messy, nevertheless, it works! I have chosen to take the approach of using recursion to calculate the answer, as I felt it is the best way to keep the code short and efficient.

I have looked at others code on this site, and read the reviews given, and it seems most users have chosen to use int, which isn't a problem, although as I say, I don't want an IntegerOverflow to occur when the user gives their input.

Is there a way to "clean up" this code; or make it more efficient?

import java.math.BigInteger;
public class Factorial {
    public static void main (String [] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        System.out.print("Enter an integer to calculate the factorial of: ");
        BigInteger temp = sc.nextBigInteger();
        sc.close();
        System.out.println(temp + "! = " + calculateFactorial(temp));
    }

    private static BigInteger calculateFactorial (BigInteger n) {
        if (n.compareTo((new BigInteger("1"))) ==  -1) {
            return new BigInteger("1");
        } else {
            return (n.multiply(calculateFactorial(n.subtract(new BigInteger("1")))));
        }
    }
}
\$\endgroup\$
6
\$\begingroup\$

Fully qualified class names are rarely written in the body of the code; they are almost always imported instead.

If you want to close the Scanner, use a try-with-resources block. It calls close() even in the case of an intervening exception, and it is easier to see where the Scanner is valid.

temp is nearly never a good variable name. Even n would be better: it's a conventional variable name for some kind of integer.

It would be good practice to suppress the default constructor by defining a private Factorial() {} constructor.

calculateFactorial would be better named factorial, and it should probably be public.

Are you really going to compute the factorial of a number larger than Long.MAX_VALUE? You'll run into problems with stack overflow from recursion. (You should use iteration instead.) Even if that worked, you would still be dealing with numbers so large that I'm not sure BigInteger could handle.

\$\endgroup\$
  • \$\begingroup\$ Is there a limit to how large numbers BigInteger can handle? Is there a BiggerInteger class? ;-) \$\endgroup\$ – Simon Forsberg Jul 14 '15 at 10:35
  • 2
    \$\begingroup\$ @SimonAndréForsberg (2^63)! exceeds 10^10^20.23 — that is, the base-10 representation has over 10^20 digits. That's in the exabyte territory. \$\endgroup\$ – 200_success Jul 14 '15 at 10:40
5
\$\begingroup\$
\$\endgroup\$
3
\$\begingroup\$

The problem with this approach is that you're multiplying really big numbers by quite small numbers repeatedly, and this is particularly slow. A much faster approach takes the range of numbers to be multiplied and splits it recursively into smaller regions. This way the numbers don't get large until the end of the calculation. With an efficient multiplication algorithm (introduced, I think, in Java 8) this is much faster -- hundreds of times faster for decently large factorials.

public static BigInteger factorial (long n) {
  if (n < 2) {
    if (n >= 0) return BigInteger.ONE;
    throw new IllegalArgumentException("factorial of a negative integer")
  }
  return multRange(2, n);
}

private static BigInteger multRange(long m, long n) {
  switch (n - m) {
    case 0: return BigInteger.valueOf(m);
    case 1: return BigInteger.valueOf(m).multiply(n);
    case 2: return BigInteger.valueOf(m).multiply(m+1).multiply(n);
    /* default: fall through */
  }
  long mid = m + (n-m)/2;
  return multRange(m, mid).multiply(multRange(mid+1, n));
}
\$\endgroup\$
0
\$\begingroup\$

A try with resources block, and a simple and easy to understand ternary operator to compute a factorial. Note that I use a long rather than a BigInteger.

import java.util.Scanner;

public class Factorial {
  public static void main(String[] args) {
    try (Scanner input=new Scanner(System.in)) { //try with resources statement
      while (input.hasNextLong()) {
        System.out.println(factorial(input.nextLong()));
      }
    }
  }

  /**
   * Computes the factorial of a number recursively. Ternary Operator. Results of any number
   * that would result in an overflow of a Long will return 0, or a negative number. ex:
   * "100". 
   *
   * @param n
   *   The number to find the factorial of
   *
   * @return The factorial of n
   */
  private static long factorial(long n) {
    return n<=1 ? n : n*factorial(n-1);
  }// is n<=1 ? is so, return n, if not return n * the factorial of n-1.
}

Here is a way to "Cleanup" the code, a ternary operator method that not only cleans it up but also is a more efficient way of computing a factoring because a 'Long' is used rather than a BigInteger. A BigInteger is an Object requiring method calls to compute. An IntegerOverflow error won't occur here since we use a 'long' primitive data type. Long data types can hold a larger value than Integers (don't confuse boxing of primitives and their Object counterparts here, let me know if unclear). A BigInteger is unnecessary to use to compute a factorial. BigIntegers can hold massive numbers, and would be the best to compute nearly ANY factorial, but they will be slower due to the required method calls to retrieve the value and perform mathematical operations on. But, the same exact format of the method above can still be done, the ternary and all, with a BigInteger.

Some side notes, make sure to check for less than or equal to. If the number is too big when performing the operation, it'll roll over into the negatives.

\$\endgroup\$
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Quill Jul 20 '15 at 8:40
  • \$\begingroup\$ Question OP asked for a way to "Cleanup" or "Make 'it' more efficient", I present a ternary operator method that clean's up the code, and a (perhaps) more efficient way of computing a factoring because a 'Long' is used rather than a BigInteger, which is an Object requiring method calls to compute. OP also says they don't want an IntegerOverflow to occur, which won't with a Long primitive, therefore a BigInteger is unnecessary to use to compute a factorial which again, is slower. \$\endgroup\$ – Jahhein Jun 11 '16 at 4:49
  • \$\begingroup\$ Can you put that in the post please? \$\endgroup\$ – Quill Jun 11 '16 at 4:50
  • \$\begingroup\$ Ha, didn't expect you to even reply to this, apologies for the absence, lost the account. Will do though buddy. \$\endgroup\$ – Jahhein Jun 11 '16 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.