Using Faster Integer Power in Java

ACMer

10 years ago

In Java Math Package, there is a pow function with returns double type. However, we can speed up this if only integer (long type) parameters are required, i.e. compute integer power where a and b are both type of long.

The first version is easy, complexity of .

    public static long pow1(long a, long b) {
        long re = 1;
        while (b-- > 0) {
            re *= a;
        }
        return re;
    }

	public static long pow1(long a, long b) {
		long re = 1;
		while (b-- > 0) {
			re *= a;
		}
		return re;
	}

The second version reduces the complexity by where it is based on the fact that . So each time reduces the exponent to its half.

    public static long pow2(long a, long b) {
        long re = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                re *= a;        
            }
            b >>= 1;
            a *= a; 
        }
        return re;
    }

	public static long pow2(long a, long b) {
		long re = 1;
		while (b > 0) {
			if ((b & 1) == 1) {
				re *= a;		
			}
			b >>= 1;
			a *= a;	
		}
		return re;
	}

The third version would be to use the inbuilt (long)Math.pow(). The fourth version would be to leave the return-value as double (without type casting).

We use the System.currentTimeMillis() to measure the time differences for above four versions. The whole Java code is:

public class Test {
    private static long[] arr = new long[10000000];
    private static double[] arr2 = new double[10000000];
 
    public static long pow1(long a, long b) {
        long re = 1;
        while (b-- > 0) {
            re *= a;
        }
        return re;
    }
 
    public static long pow2(long a, long b) {
        long re = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                re *= a;        
            }
            b >>= 1;
            a *= a; 
        }
        return re;
    }
 
    public static void main(String[] args) {
        final long startTime1 = System.currentTimeMillis(); 
        for (int i = 0; i < arr.length; i ++) {
            arr[0] = pow1(2, 64);
        }
        final long endTime1 = System.currentTimeMillis();
 
        final long startTime2 = System.currentTimeMillis(); 
        for (int i = 0; i < arr.length; i ++) {
            arr[0] = pow2(2, 64);
        }
        final long endTime2 = System.currentTimeMillis();       
 
        final long startTime3 = System.currentTimeMillis(); 
        for (int i = 0; i < arr.length; i ++) {
            arr[0] = (long)Math.pow(2, 64);
        }
        final long endTime3 = System.currentTimeMillis();   
 
        final long startTime4 = System.currentTimeMillis(); 
        for (int i = 0; i < arr.length; i ++) {
            arr2[0] = Math.pow(2, 64);
        }
        final long endTime4 = System.currentTimeMillis();           
 
        System.out.println("Total execution time (pow1): " + (endTime1 - startTime1) );
        System.out.println("Total execution time (pow2): " + (endTime2 - startTime2) );
        System.out.println("Total execution time ((long)Math.pow): " + (endTime3 - startTime3) );       
        System.out.println("Total execution time (Math.pow): " + (endTime4 - startTime4) );         
    }
}

public class Test {
	private static long[] arr = new long[10000000];
	private static double[] arr2 = new double[10000000];

	public static long pow1(long a, long b) {
		long re = 1;
		while (b-- > 0) {
			re *= a;
		}
		return re;
	}

	public static long pow2(long a, long b) {
		long re = 1;
		while (b > 0) {
			if ((b & 1) == 1) {
				re *= a;		
			}
			b >>= 1;
			a *= a;	
		}
		return re;
	}

	public static void main(String[] args) {
		final long startTime1 = System.currentTimeMillis();	
		for (int i = 0; i < arr.length; i ++) {
			arr[0] = pow1(2, 64);
		}
		final long endTime1 = System.currentTimeMillis();

		final long startTime2 = System.currentTimeMillis();	
		for (int i = 0; i < arr.length; i ++) {
			arr[0] = pow2(2, 64);
		}
		final long endTime2 = System.currentTimeMillis();		

		final long startTime3 = System.currentTimeMillis();	
		for (int i = 0; i < arr.length; i ++) {
			arr[0] = (long)Math.pow(2, 64);
		}
		final long endTime3 = System.currentTimeMillis();	

		final long startTime4 = System.currentTimeMillis();	
		for (int i = 0; i < arr.length; i ++) {
			arr2[0] = Math.pow(2, 64);
		}
		final long endTime4 = System.currentTimeMillis();			

		System.out.println("Total execution time (pow1): " + (endTime1 - startTime1) );
		System.out.println("Total execution time (pow2): " + (endTime2 - startTime2) );
		System.out.println("Total execution time ((long)Math.pow): " + (endTime3 - startTime3) );		
		System.out.println("Total execution time (Math.pow): " + (endTime4 - startTime4) );			
	}
}

with the result:

Wow, the second version is fastest, around 4-5 times faster than the first naive version. The first version is even faster than the Math.pow() with or without type casting (which doesn’t make much differences).

The same principle also applies to other programming languages, such as C/C++ although the performance speed-ups may vary slightly.

Relevant Post:

[1] helloacm.com/compute-powermod-abn/

–EOF (Coding For Speed) —