Sunday, May 7, 2017

Head or Tail, Who the Factorial Cares?

Based on the blog post http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044
the obvious question came up to see if the performance really noticeable and worth worrying about.  It seems that Oracle does not really concerned about the issue.  In this case, it is not the speed of the algorithm that is an issue, but the limited size of the stack that needs to be used in an optimized manner in order to avoid stack overflow condition.  Based on the code below, my tests show head recursion performs a little bit better than the suggested tail recursion ( when the StarkOverflowError is thrown ).  Over all, it seems like the glory goes to iterative recursion method and not head or tail argument. 

Note: I know that factorial is not what this code is testing, multiplication rises much too fast, so it was replaced, on purpose, by addition operations.


public class TestUtilization{
    public static void main(String args[]){
        final long NUM=5350;    //tailFactorial becomes unstable around 5250-5300, headFactorial 5300-5350
        long time=System.currentTimeMillis();
        System.out.println(IterativeFactorial(NUM));
        System.out.printf("Iterative implementation  time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        time=System.currentTimeMillis();
        System.out.println(headFactorial(NUM));
        System.out.printf("Head Factorial  time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));  
        /*time=System.currentTimeMillis();
        System.out.println(tailFactorial(NUM));
        System.out.printf("Tail Call Optimization time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
         */ 
    }
    //Tail Call Optimization
    public static long tailFactorial (long x){
        if (x == 0)
            return 1;
        return tailFactorial(x,1);
    }
    public static long tailFactorial (long x, long current_factorial){
        if (x == 0)
            return current_factorial;
        return tailFactorial(x - 1, current_factorial + x);
    }
    //head recursion
    public static long headFactorial (long x){
        if (x == 0)
            return 1;
        return x+headFactorial(x-1);
    }
    //iterative implementation
    public static long IterativeFactorial(long n) {
        long result = 1;
        for (long t=n; t > 1; t--)
            result += t;
        return result;
    }
    private static String getTime(long millis){
        long second = (millis / 1000) % 60;
        long minute = (millis / (1000 * 60)) % 60;
        long hour = (millis / (1000 * 60 * 60)) % 24;
        return String.format("%02d:%02d:%02d:%04d", hour, minute, second, millis);
    }
}

No comments:

Post a Comment