Project Euler : Fast Factorial Computation

The problem in Project Euler asked the summation of all the digits in . I searched over the net for fast factorial algorithms and came across this site:

Fast Factorial Functions

I implemented the Poor Man’s algorithm to solve the problem. However, I wasn’t able to find out the logic behind the working of the algorithm. Poor Man’s algorithm for factorial returned no good searches. I need to keep looking.

The code given at the above site is in C++. It was a child’s play to convert it into Java. It was mostly copy-paste and remove any C++ specific method to Java one.

Below is the Java code:

public class Problem_20 {
	private long N;

	public String factorial(int n) {
		if (n < 0)
			return "n > 0 required as input";
		if (n < 2)
			return "1";
		DecInteger p = new DecInteger(1);
		DecInteger r = new DecInteger(1);
		N = 1;
		int h = 0, shift = 0, high = 1;
		int log2n = (int) Math.floor(Math.log(n) * 1.4426950408889634);
		while (h != n) {
			shift += h;
			h = n >> log2n--;
			int len = high;
			high = h - 1 | 1;
			len = (high - len) / 2;
			if (len > 0) {
				p = DecInteger.multiply(p, product(len));
				r = DecInteger.multiply(p, r);
			}
		}
		r = DecInteger.multiply(r, DecInteger.pow2(shift));

		return r.toString();
	}

	private DecInteger product(int n) {
		int m = n / 2;
		if (m == 0)
			return new DecInteger(N += 2);
		if (n == 2)
			return new DecInteger((N += 2) * (N += 2));
		return DecInteger.multiply(product(n - m), product(m));
	}

	public static void main(String[] args) {
		int n = 100;
		Problem_20 p = new Problem_20();
		String val = p.factorial(n);
		int sum = 0;
		for (int i = 0; i < val.length(); i++)
			sum += val.charAt(i) - '0';
		System.out.println(sum);
	}
}

class DecInteger {
	private final static long mod = 100000000L;
	private int[] digits;
	private int digitsLength;

	public DecInteger(long value) {
		digits = new int[] { (int) value, (int) (value >> 32) };
		digitsLength = 2;
	}

	private DecInteger(int[] digits, int length) {
		this.digits = digits;
		digitsLength = length;
	}

	public static DecInteger pow2(int e) {
		if (e < 31)
			return new DecInteger((int) Math.pow(2, e));
		return DecInteger.multiply(DecInteger.pow2(e / 2), DecInteger.pow2(e - e / 2));
	}

	public static DecInteger multiply(DecInteger a, DecInteger b) {
		int alen = a.digitsLength, blen = b.digitsLength;
		int clen = alen + blen + 1;
		int[] digits = new int[clen];
		for (int i = 0; i < alen; i++) {
			long temp = 0;
			for (int j = 0; j < blen; j++) {
				temp = temp + a.digits[i] * (long) b.digits[j] + digits[i + j];
				digits[i + j] = (int) (temp % DecInteger.mod);
				temp = temp / DecInteger.mod;
			}
			digits[i + blen] = (int) temp;
		}
		int k = clen - 1;
		while (digits[k] == 0)
			k--;
		return new DecInteger(digits, k + 1);
	}

	public String toString() {
		StringBuffer val = new StringBuffer(digitsLength * 10);
		for (int j = 0; j < digitsLength; j++)
			val.insert(0, digits[j]);
		return val.toString();
	}
}

Popularity: 25% [?]

Related posts:

1. Project Euler : Sum Of Digits In a^b
2. Project Euler : Digits Of Sum of 1^1 + 2^2 + 3 ^ 3 …
3. Project Euler : Largest Product Of Five Consequtive Digits
4. Project Euler : First Triangle Number To Have Over Five Hundred Divisors
5. Project Euler : Numbers That Are Fifth Powers Of Their Digits