The answers provided in the questions were collected using:
- Default eclipse 2023-06 IDE for Mac
- No special java vm args
- jdk 1.8
- Mac Studio M1 (10 core)
Question : How many digits are there in 123456789 factorial?
Answer : 260,959,261 digits.
Question : How long does it take to compute 123456789 factorial?
- Answer 1 : Using prime sieve method, it takes 28,244,345 ms.
- Answer 2 : Using recursive method, StackOverflowError.
Question : If the result of 123456789 factorial was written to a plain text file, how big will it be?
Answer : 263.6 MB.
Here's the full java code:
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
public class FactorialUsingPrimeSieveMethod {
private int findExponent(int input, int prime) {
int q = input, m = 0;
if (prime > input) {
return 0;
}
if (prime > input / 2) {
return 1;
}
while (q >= prime) {
q /= prime;
m += q;
}
return m;
}
private boolean[] initializeSieve(int input) {
boolean sieve[] = new boolean[input + 1];
Arrays.fill(sieve, true);
for (int p = 2; p * p <= input; p++) {
if (sieve[p] == true) {
for (int i = p * p; i <= input; i += p) {
sieve[i] = false;
}
}
}
return sieve;
}
private int[] selectPrimeNumbers(int input) {
ArrayList<Integer> primeTable = new ArrayList<Integer>();
boolean sieve[] = initializeSieve(input);
for (int i = 2; i <= input; i++) {
if (sieve[i] == true) {
primeTable.add(i);
}
}
return primeTable.stream().mapToInt(i -> i).toArray();
}
private int[] generateExponentTable(int input, int[] primeTable) {
ArrayList<Integer> exponentTable = new ArrayList<Integer>();
for (int prime : primeTable) {
exponentTable.add(Integer.valueOf(findExponent(input, prime)));
}
return exponentTable.stream().mapToInt(i -> i).toArray();
}
private LinkedList<BigInteger> runParallelExponentiation(int[] primeTable, int[] exponentTable) {
int proc = Runtime.getRuntime().availableProcessors();
ExecutorService executorService = Executors.newFixedThreadPool(proc);
List<Future<BigInteger>> futureList = new ArrayList<Future<BigInteger>>();
LinkedList<BigInteger> intermediate = new LinkedList<BigInteger>();
for (int i = 0; i < primeTable.length; i++) {
Callable<BigInteger> worker = new PrimeSieveExponentiationWrapper(primeTable[i], exponentTable[i]);
Future<BigInteger> submit = executorService.submit(worker);
futureList.add(submit);
}
for (Future<BigInteger> future : futureList) {
try {
intermediate.add(future.get());
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
}
executorService.shutdown();
return intermediate;
}
private synchronized BigInteger runParallelMultiplication(LinkedList<BigInteger> intermediate) {
BigInteger one = BigInteger.ONE;
int proc = Runtime.getRuntime().availableProcessors();
ExecutorService executorService = Executors.newFixedThreadPool(proc);
final LinkedList<BigInteger> roundaboutList = intermediate;
while (roundaboutList.size() != 1) {
System.out.println(" Current size = " + roundaboutList.size());
BigInteger x = intermediate.pollLast();
System.out.println(" Size after first poll = " + roundaboutList.size());
BigInteger y = intermediate.pollLast();
System.out.println(" Size after second poll = " + roundaboutList.size());
Callable<BigInteger> worker = new PrimeSieveMultiplicationWrapper(x, y);
Future<BigInteger> submit = executorService.submit(worker);
try {
roundaboutList.addFirst(submit.get());
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
}
executorService.shutdown();
return one.multiply(roundaboutList.getFirst());
}
private BigInteger factorial(int input) {
BigInteger result = BigInteger.ONE;
int[] primeTable = selectPrimeNumbers(input);
int[] exponentTable = generateExponentTable(input, primeTable);
final LinkedList<BigInteger> intermediate = runParallelExponentiation(primeTable, exponentTable);
BigInteger product = runParallelMultiplication(intermediate);
return result.multiply(product);
}
private void exportToFile(BigInteger result, int n) {
String toParse = result.toString();
String parsedResult = toParse.replaceAll("(.{100})", "$1\n");
String path = System.getProperty("user.home") + File.separator + "results" + File.separator + String.valueOf(n)
+ ".txt";
try {
File fileName = new File(path);
if (!fileName.exists()) {
fileName.getParentFile().mkdirs();
fileName.createNewFile();
}
FileWriter writer = new FileWriter(fileName);
writer.write(parsedResult);
writer.flush();
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
private void recordExecTime(FactorialUsingPrimeSieveMethod calculator, int n) {
long startTime = System.currentTimeMillis();
BigInteger result = calculator.factorial(n);
long endTime = System.currentTimeMillis();
System.out.println(n + "! took " + (endTime - startTime) + " ms using prime sieve method. Result has = "
+ result.toString().length() + " digits");
//exportToFile(result, n);
}
public static void main(String[] args) {
FactorialUsingPrimeSieveMethod calculator = new FactorialUsingPrimeSieveMethod();
calculator.recordExecTime(calculator, 12345);
calculator.recordExecTime(calculator, 123456);
calculator.recordExecTime(calculator, 1234567);
calculator.recordExecTime(calculator, 12345678);
calculator.recordExecTime(calculator, 123456789);
}
class PrimeSieveExponentiationWrapper implements Callable<BigInteger> {
int prime;
int exponent;
public PrimeSieveExponentiationWrapper(int prime, int exponent) {
this.prime = prime;
this.exponent = exponent;
}
@Override
public BigInteger call() throws Exception {
// System.out.println(" Calculating " + prime + " ^ " + exponent);
return BigInteger.valueOf(prime).pow(exponent);
}
}
class PrimeSieveMultiplicationWrapper implements Callable<BigInteger> {
private BigInteger x;
private BigInteger y;
PrimeSieveMultiplicationWrapper(BigInteger x, BigInteger y) {
this.x = x;
this.y = y;
}
@Override
public BigInteger call() throws Exception {
if (x == null) {
if (y == null) {
return BigInteger.ONE;
} else {
return y;
}
}
return x.multiply(y);
}
}
}
