Using Faster Integer Power in Java

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 $tex_ad68cb15ab4e6c9d3aa23d421625d67a Using Faster Integer Power in Java general integer integer power Java$ where a and b are both type of long.

The first version is easy, complexity of $tex_a398053b1f28ba2b1a7a1a30339fb34b Using Faster Integer Power in Java general integer integer power Java$ .

    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 $tex_b175e740bf5324575efdda3bc3d7b3c5 Using Faster Integer Power in Java general integer integer power Java$ where it is based on the fact that $tex_3e8b2eb7c05215c332a0fd3f3d0fba9e Using Faster Integer Power in Java general integer integer power Java$ . 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:

java-integer-power Using Faster Integer Power in Java general integer integer power Java

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) —

GD Star Rating
loading...

682 words Last Post: Using a Faster Approach to Judge if a Integer is power of Two
Next Post: Using Faster Exponential Approximation

The Permanent URL is: Using Faster Integer Power in Java (AMP Version)