factorial

Calculating large number factorial in java

see more detail in doc

Tutorial

Just type and run then check result

>cd code && javac Factorial.java && java Factorial 100

Performance test

multiplyByInt is the only algorithm without using jdk BigInteger

Base line is longMultiplication algorithm

jdk version:1.8.0_66 ,mac air 2.2 GHz Intel Core i7

100!

longMultiplication time cost: 3ms | mem cost: 12m
multiplyByInt cost: 30ms | mem cost: 12m
binarySplit cost: 0ms
prime cost: 1ms
moessner cost: 70ms

1000!

longMultiplication cost: 15ms
multiplyByInt cost: 63ms
binarySplit cost: 13ms
prime cost: 6ms
moessner cost: 26225ms

10000!

longMultiplication cost: 226ms
multiplyByInt cost: 381ms
binarySplit cost: 61ms
prime cost: 125ms
moessner cost: too slow!!

100000!

longMultiplication cost: 5392ms
multiplyByInt cost: 10250ms
binarySplit cost: 873ms
prime cost: 2291ms
moessner cost: too slow!!

1000000!

longMultiplication cost: 419096ms | max mem cost: 374874kb
multiplyByInt cost: 1218278ms | max mem cost: 21129kb
binarySplit cost: 27014ms | max mem cost: 328578kb
prime cost: 305147ms | max mem cost:372256kb
moessner cost: too slow!!

If you run my code use jdk version under 1.8, you will get a significantly performance difference when n is a large number. Because BigInteger had updated their multiply algorithm from Long multiplication(O(n^2)) to the Karatsuba algorithm(O(n^1.585)) or the Toom-Cook multiplication(O(n^1.465))

jdk version:1.7.0_60 ,mac air 2.2 GHz Intel Core i7