Article 140 - Fast Exponent Algorithm

Multiplication computation is a non-trivial task for computers. Performing exponent computation is often expanded out as a series of multiplication tasks. For large exponents, this task can be overwhelming.

Fourtunately, there are methods to reduce the number of multiplications. One such strategy is to apply the divide and conquer strategy recursively.

Let's discuss some examples. For the purpose of this article, we will only discuss positive integer exponents.

An integer raised to the exponent of 0, is simply 1.

An integer raised to the exponent of 1, is simply itself.

An integer raised to the exponent of 2, is the multiplication of itself with itself.

An integer raised to the exponent of 3, is the multiplication of itself with the result of the multiplication of itself with itself.

The idea should be quite clear, as the above examples is recursively defined.

With an exponent of 4, we require 3 mulitplications but with an exponent of 5, we require 4 multiplications. It seems that with an exponent of n, we require n - 1 multiplications. Can we do better? Of course!

If we divide the expanded results in half, we have equivalent sides, assuming the expansion contains an even number of elements. For odd scenarios, we can subtract one element, perform the computation, and multiply the last element afterwards.

By applying this strategy recursive, we have derived a logarithmic result, which is much better than the original linear approach.

The fast exponent algorithm that we derived.

int fastExponent( int number, int exponent ){
    switch( exponent ){
        case 0:
            return 1;
        case 1:
            return number;
        default:
            if( exponent % 2 == 0 ){
                return fastExponent( number, exponent / 2 ) 
                    * fastExponent( number, exponent / 2 );
            }
            else{
                return fastExponent( number, exponent / 2 + 1 ) 
                    * fastExponent( number, exponent / 2 );
            }
    }    
}

Comments (0)

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.