Coding up to Factorial 23 in Java

Question

I need to write up factorial up to 23! I can do factorial up to 20! but after that I am lost because the number gets too big. I cannot use BigInteger.

I have to store the 0s from the rightmost digit so example outputs:

10! = 3628800 --> fac=36288, num10 = 2

23! = 2585..976640000 --> fac= 2585..97664, num10 = 4

import java.util.Scanner;

public class Factorial10{
    public static void main(String[] args){
        long fac;       // long: factorial is very large
        long pre_fac;       // to check overflow
        int i, n;
        int num10;

        Scanner sc = new Scanner(System.in);

        System.out.print("n? ");
        n = sc.nextInt();

        // Start from fac = 0! = 1
        for(i= 1, fac= 1L; i<n; i++){
            pre_fac = fac;
            fac *= i;

            // check if overflowed
            if(pre_fac != fac /i){
                System.out.println("Overflowed at " + i + "! = " + fac);
                fac = pre_fac;      // roll back to the previous, unoverflowed
                break;
            }
        }

        System.out.println((i-1) + "! = " + fac + "(fac = , num10 = )");
    }
}
```

Answer 1

Most miss a crucial part of your question:

I have to store the 0s from the rightmost digit

10 has the factors 2 and 5, so you only need to store how often each number between 1 and 23 can be divided by 2 and 5.

For example, with 10:

i    1 2 3 4 5 6 7 8 9 10    SUM
div2 0 1 0 2 0 1 0 3 0  1      8
div5 0 0 0 0 1 0 0 0 0  1      2

As we can see, the minimum of both sums is 2, so 10! should end with 00.
Indeed, 10! is 3628800.
The math behind this is 10! = x * 2^8 * 5^2, for some x that can't be divided by 2 or 5.

An other observation is that the number of 5s increases much slower, so we can skip counting the 2s.

With this knowledge, we can calculate the number of ending 0s by checking how often each number divides 5:

private static int numZerosInFactorial(int n) {
    int divBy5 = 0;
    for (int i = 1; i <= n; i++) {
         for (int j = i; (j % 5) == 0; j /= 5) {
             divBy5++;
         }
    }
    return divBy5;    
}

(There are are a few small improvements you can do to the above method)

The other question now is: Do you really need the value of n!?
And if yes, with what precision? Is it fine to calculate n! with double now?

---

Thanks to a comment from Michael, I noticed that we can in fact calculate the factorial without the zeros and then use string concatenation to display the result.

When calculating the factorial without zeroes, we have to basically do the opposite of what we did in numZerosInFactorial, so instead of multiplying with a multiple of 5, we divide by 2:

private static long factorialWithoutZeroes(int n) {
    long result = 1;
    for (int i = 1; i <= n; i++) {
        long div = 1;
        int j;
        for (j = i; (j % 5) == 0; j /= 5) {
            div *= 2;
        }
        result = result / div * j;
    }
    return result;
}

The final result would be:

// We have already read n from stdin
long fac = factorialWithoutZeroes(n);
int num10 = numZerosInFactorial(n);
System.out.println(n + "! = " + (fac + "0".repeat(num10)) + " (fac = " + fac + " , num10 = " + num10 + ")");

Indeed, this approach works up to n == 23. And the output format is a good hint that this is the expected approach.

Answer 2

Have you try to use double instead of long. As documentation in Double.Max - it can hold up to 1.7976931348623157e+308

Answer 3

Just implement your own kind of big integer:

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    int[] factorial = factorial(n);
    for (int i = factorial.length - 1; i >= 0; i--) {
      System.out.print(factorial[i]);
    }
  }

  static int[] factorial(int n) {
    int[] factorial = { 1 };
    for (int i = 1; i <= n; i++) {
      factorial = multiply(factorial, i);
    }
    return factorial;
  }

  static int[] multiply(int[] multiplicand, int multiplicator) {
    int carry = 0;
    for (int j = 0; j < multiplicand.length; j++) {
      multiplicand[j] = multiplicand[j] * multiplicator + carry;
      carry = multiplicand[j] / 10;
      multiplicand[j] %= 10;
    }
    while (carry > 0) {
      multiplicand= Arrays.copyOf(multiplicand, multiplicand.length + 1);
      multiplicand[multiplicand.length - 1] = carry % 10;
      carry /= 10;
    }
    return multiplicand;
  }
}

Try it online!

Answer 4

If you can't use BigInteger, then you could try implementing your own big number library:

How to handle very large numbers in Java without using java.math.BigInteger

Answer 5

You can use the class BigDecimal of java.lang.math

But that can take all your memory.

Is there any replacement of long double in java?