Factorial is quite a popular interview question for junior developers, but last time I failed because of it. That makes me wonder what I’ve done wrong and I’ll try to analyze it as deep as possible.
Please read the article to the end, it describes my process of finding good way to analyse this problem. Not all code snippets are correct, but problems are mentioned.
WHAT is factorial?
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example:
5! = 5 * 4 * 3 * 2 * 1
The value of 0! is 1, according to the convention for an empty product.
I didn’t know either what is a source of this 0, so I leave a link to empty product problem.
What I’ve done on the interview, and many times before, was 2 simplest implementations I’ve known:
1. Iterative Factorial:
|
1 2 3 4 5 6 |
private static long iterativeFactorial(int x) { long result = 1; for(int i=x; i>0;i--) result*=i; return result; } |
2. Recursive Factorial:
|
1 2 3 4 5 6 |
public static long recursiveFactorial(long x) { if (x == 0) return 1; else return x * recursiveFactorial(x - 1); } |
It was said at the begining that we consider only positive integer numbers. Thats why there are no lower bariers od less than 0 numbers.
Above codes works fine, but which is better, faster, stronger..? no, just first 2.
Problem 1:
I used long as a result holder. First tests shows that it is out at factorial of 21. It’s not too much for some interesting speed tests. long scope on Java 8 in 64-bit environment is: 0 – 264-1
Advice 1: use BigInteger
So quick correction of the code and I could test for n=1000.
Corrected code:
3) Iterative factorial on BigInteger:
|
1 2 3 4 5 6 |
private static BigInteger bigIterativeFactorial(int x) { BigInteger result = BigInteger.ONE; for (int i = x; i > 0; i--) result = result.multiply(BigInteger.valueOf(i)); return result; } |
4) Recursive factorial on BigInteger:
|
1 2 3 4 5 6 |
public static BigInteger bigRecursiveFactorial(int x) { if (x == 0) return BigInteger.ONE; else return bigRecursiveFactorial(x - 1).multiply(BigInteger.valueOf(x)); } |
It works perfectly for n=1000, so I’ve tried to meassure a time of theese methods realization. What I wanted to do was as simple time test as possible:
|
1 2 3 4 5 6 7 |
private static void meassureIterativeFactorial(int x) { final long start, end; start = System.currentTimeMillis(); bigIterativeFactorial(x); end = System.currentTimeMillis(); System.out.println(end - start); } |
I’ve done the same for recursive method and loop it 100 times.
Here what I get (THIS RESULTS ARE WRONG, be aware.):
Results for Iterative factorial:
| Iteration | Test 1 | Test 2 | Test 3 | Test 4 | Test 5 | Mean Average [ms] |
| 1 | 10 | 18 | 15 | 13 | 13 | 13.8 |
| 10 | 3 | 6 | 6 | 7 | 5 | 5.4 |
| 20 | 2 | 3 | 4 | 2 | 3 | 2.8 |
| 50 | 1 | 2 | 2 | 1 | 2 | 1.6 |
| 100 | 1 | 1 | 2 | 1 | 1 | 1.2 |
Results for Recursive factorial:
| Iteration | Test 1 | Test 2 | Test 3 | Test 4 | Test 5 | Mean Average [ms] |
| 1 | 12 | 15 | 15 | 11 | 23 | 15.2 |
| 10 | 5 | 8 | 6 | 4 | 4 | 5.4 |
| 20 | 1 | 3 | 3 | 2 | 2 | 2.2 |
| 50 | 1 | 1 | 1 | 1 | 1 | 1 |
| 100 | 1 | 1 | 1 | 0 | 1 | 0.8 |
Conclusion:
Something is wrong. First meassure takes a lot of time, and each iteration the algorithm goes faster.
Good for Java! Bad for me.
Creating microbenchmarks is really complex problem, and my naive thinking that I’ll finish this article in 1 hour gone down after finding out more resources.
Useful sources about microbenchmarks in Java:
And awesome presentation, done by Aleksey Shipilev here:
And another article by the same author:
I found out how hard it is to prepare proper microbenchmark with some reliable results.
Thats why I choose to use JMH – “JMH is a Java harness for building, running, and analysing nano/micro/milli/macro benchmarks written in Java and other languages targetting the JVM.”
Resources about this project:
+ One additional thing I found , plugin to IntelliJ IDEA, which allow You to use JMH same as JUnit tests:
With such tool set, creating proper microbenchmarks wasn’t so hard.
Final code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.math.BigInteger; import java.util.concurrent.TimeUnit; /** * Created by Filip Kubala on 2016-07-07. */ @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @State(Scope.Thread) public class Factorial { private static final int n = 1000; public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder() .include(Factorial.class.getSimpleName()) .warmupIterations(5) .measurementIterations(10) .threads(1) .forks(1) .build(); new Runner(opt).run(); } public static BigInteger bigRecursiveFactorial(int x) { if (x == 0) return BigInteger.ONE; else return bigRecursiveFactorial(x - 1).multiply(BigInteger.valueOf(x)); } private static BigInteger bigIterativeFactorial(int x) { BigInteger result = BigInteger.ONE; for (int i = x; i > 0; i--) result = result.multiply(BigInteger.valueOf(i)); return result; } @Benchmark public void measureBigIterativeFactorial() { bigIterativeFactorial(n); } @Benchmark public void measureBigRecursiveFactorial() { bigRecursiveFactorial(n); } } |
Final results:
| n=100 | ||
| measureBigIterativeFactorial | measureBigRecursiveFactorial | |
| Min | 6067 | 6078 |
| Max | 6779 | 6650 |
| Avg | 6255 | 6320 |
| n=1000 | ||
| measureBigIterativeFactorial | measureBigRecursiveFactorial | |
| Min | 368482 | 313854 |
| Max | 463480 | 376920 |
| Avg | 411436 | 337864 |
| n=10000 | ||
| measureBigIterativeFactorial | measureBigRecursiveFactorial | |
| Min | 42243727 | 35937671 |
| Max | 52307619 | 37790154 |
| Avg | 43974218 | 36816328 |
Conclusion:
If we take only time as a comparing factor it came clearly that Recursive Factorial is faster than iterative and it’s really strange for me. As far as I know with recursive code GC have much more to clean than with iterative approach.
According to fact that benchmarking is hard, maybe I’ve made some mistake here?
Probably I won’t leave this problem at this state and find out if I get correct results.
Feel free to comment!
Stay tuned.