Factorial – Deeper analysis

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:

2. Recursive Factorial:

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:

4) Recursive factorial on BigInteger:

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:

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:

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

Factorial Charts

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.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

9 + 8 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.