java.net > All Articles > http://today.java.net/pub/a/today/2007/11/06/creating-java-me-math-pow-method.html

Creating a Java ME Math.pow() Method

When developing applications for mobile devices using Java, you may require mathematical methods not available on your particular Java VM. This article will specifically address the absence of the "power" method, Math.pow(), in Java ME. We will illustrate three different algorithms for developing an ME equivalent and proffer the best of the three as a possible programming solution to our problem.

To discuss this problem, we look at both integer and fractional power parameters, restricting our analysis to the positive real numbers. We show the relative ease of finding a solution set for integer problems and fractional problems, regardless of the sign of the exponent. In most cases, we will use the example problem n = 82/3, where we seek either a good estimate or the actual solution for n. Without the availability of the initial exponent up front, other solutions to this problem (including Newton's method and the secant method) are not readily programmed. Although there are some workarounds for the bisection method, we (instead) focus on three methods not traditionally investigated. The first is a simple (yet sometimes inefficient) geometric decay algorithm, while the second method leverages the Math.sqrt() method and guarantees convergence to an approximate solution in no more than 11 iterations. The third and final method uses the Taylor series approximation for the logarithm followed by the Euler transformation on the Taylor series.

An ME Math.pow() Method for Integer Solutions

Traditionally, the Java Math.pow() method contains two parameters. These parameters include the base and the exponent. Let's assume (initially) that both of these parameters are integers, and we seek a programming solution for the Math.pow() method in ME using the same parameters as the Java method. Here the programming solution is fairly simple, as shown in Example 1. In this example, we simply run a multiplicative loop indexed by the value of the exponent.

Example 1

int pow( int x, int y)  /*we define the power method with
        base x and power y (i.e., x^y)*/
{
    int z = x; 

    for( int i = 1; i < y; i++ )z *= x;

    return z;
}

Of course, one may find the need to evaluate non-integer powers. A simple solution for the positive reals (without having access to the Math.pow() method) could involve the use of the Math.log(). For example, consider 8^2/3. Taking the natural logarithm results in 2/3*ln(8) = 1.386294361. To obtain the final solution, take the exponent of 1.386294361, specifically e^1.386294361 = 4. In this case, one would not have the need for the power function. Sadly, Java ME doesn’t support the Math.log() method either. Without either the Math.pow() or the Math.log() methods, we look at a naive "brute force" heuristic, an application of the Math.sqrt() method, and a Taylor series approximation of the natural logarithm (as well as Euler's e) for solutions to our Java ME problem.

An ME Math.pow() Using a Geometric Decay Algorithm as a Brute Force Solution

Earlier implementations of Java ME excluded the floating point primitive data types, float and double. More recently, these data types have been added. We will now substitute the integer arguments in our Math.pow() declaration with the double data type.

You may require fractional exponents for use in your Java ME Math.pow() power method. The first approach to building Math.pow() that we provide is a naive "brute force" heuristic using a geometric decay algorithm. In simple terms, a decay algorithm starts with a value greater than the known solution and applies a method to decay that value until it reaches a close approximation to the solution (see Example 2 for an illustration of a simple linear decay algorithm). In our case, we will further illustrate a geometric form that converges towards the solution from above.

Example 2

/* This example illustrates a simplistic decay algorithm that we will assume
converges to our desired solution (a positive integer) */

int n; // assume that n is the solution to the number we are trying to find

int varX = 1000;  //assume that we know the solution is less than or equal to 1000

while( varX > 0 )
{
    varX -= 1; // decrement by 1
            
    if( varX == n)return varX;
}

In Example 2, we decrement from 1000 until we find the desired number, assuming that the number we desire is a positive integer. This type of algorithm forms the basis for our brute force heuristic.

Using a similar approach, we apply this algorithm when encountering fractions. Let's assume that we seek a value for n where n = 82/3. To use a decay algorithm, we must first find an appropriate starting point that is equal to or larger than the solution itself. Doing so for the positive real numbers with positive exponents is fairly simple. To program this solution for our example, we cube both sides, resulting in n3=82. Of course, this equation is equivalent to n3=64. Our starting value, then, becomes 64, as we know that n must be smaller than 64 (since n3 = 64). Note that this same reasoning would apply for any positive value of the exponent, given our restriction to the positive reals. Now, we might design a loop to generate a solution for n that is "close enough" to our desired number. We turn to Example 3, which is appropriate for all positive base numbers and positive exponents.

Example 3

double pow( double x, double y )  //we define our new power method for fractions
{
    int den = 1000; // specify arbitrary denominator
    int num = (int)(y*den); // find numerator
    int s = (num/den)+1;
        
    /***********************************************************************
    ** Variable 's' provides the power for which we multiply the base to find
    ** our starting search value.  For example, if we seek a solution for
    ** n = 8^(2/3), then we will use 8^2 or 64 as our starting value (which is
    ** generated in our next section of code.)  Why?  The solution for our
    ** problem (given that the base is positive) will always be less than or
    ** equal to the base times the numerator power. 
    ************************************************************************/

    /***********************************************************************
    ** Because we set the denominator to an arbitrary high value,
    ** we must attempt to reduce the fraction. In the example below,
    ** we find the highest allowable fraction that we can use without
    ** exceeding the limitation of our primitive data types.
    ************************************************************************/

    double z = Double.MAX_VALUE;

    while( z >= Double.MAX_VALUE )
    {
        den -=1; // decrement denominator
        num = (int)(y*den); // find numerator
        s = (num/den)+1; // adjust starting value

        // find value of our base number to the power of numerator
        z = x;
                
        for( int i = 1; i < num; i++ )z *= x;
    }

    /***********************************************************************
    ** Now we are going to implement the decay algorithm to find
    ** the value of 'n'.
    ************************************************************************/

    /***********************************************************************
    ** We now find 'n' to the power of 's'. We will then decrement 'n',
    ** finding the value of 'n' to the power of the denominator. This
    ** value, variable 'a', will be compared to 'z'. If the 'a' is nearly
    ** equal to 'z', then we will return 'n', our desired result.
    ************************************************************************/
        
    double n = x; // We define 'n' as our return value (estimate) for 'x'.

    // find 'n' to the power of 's'.
        
    for( int i = 1; i < s; i++)n *= x;

    // Begin decay loop
    while( n > 0 )
    {
        double a = n; //proxy for n

        // find 'a', the value of 'n' to the power of denominator
        for( int i = 1; i < den; i++ )a *= n;

        // compare 'a' to 'z'. Is the value within the hundred-thousandth?
        // if so, return 'n'.
        double check1 = a-z;
        double check2 = z-a;
                
        if( check1 < .00001|| check2 > .00001 ) return n;

        n *= .999;// We arbitrarily use a decay of .1% per iteration
    }
        
    // value could not be found, return -1.
    return -1.0;
}

This example demonstrates the use of the decay algorithm. You should notice that the value of n (the estimate for our solution) is decremented arbitrarily by .1 percent. You may want to alter this value depending on your programming precision requirements. Also, you might consider including programming logic that compares the previous iteration solution with the current iteration and then continues iterating if there is improvement, but returns the previous value if the solution has regressed.

The solution described only handles positive exponents. What happens if you have negative values? We address this contingency next.

Handling Negative Exponents

To add another layer of complexity, assume that we are passing negative exponents to our Math.pow() method. In the case that the exponent is negative, a simple solution is to convert the base number to a fraction, making the exponent positive. For example, 8-2 may be converted to (1/8)2. Programmatically, we will divide 1 by our base number, x, and multiply our exponent, y, by -1 (see Example 6).

Example 6

if( y < 0 )
{
    x = (1/x); // convert base number to fraction
    y *= -1; // make exponent positive
}

We have now finished discussing the "brute force" geometric decay algorithm for estimating power functions in Java ME. The reader should note that the naive "brute force" heuristic has performance issues for large base and exponent numerator combinations. Consider the example of 85/2. The starting value using this algorithm would be 85 = 32,768. Using a decay of .1 percent, a total of 5196 iterations would be required to find the solution--hardly optimal. With this fact in mind and without proffering improved heuristic search algorithms, we turn to a secondary approximation, which provides more reasonable iterative requirements.

An ME Math.pow() Using Math.sqrt() Methods

The second approach to developing our Math.pow() method is to leverage the use of the Math.sqrt() method (see Example 7). Using the Math.sqrt() method requires that we have an estimate for our power that has an even denominator. For example, n = 82/3 => n3 = 82 is a tricky problem, as we need the cube root, not the square root. In order to adjust for this problem in our example, we simply square each side one more time: n3 = 82 => n6 = 84. We can then proceed to find our solution in exactly two iterations.

Of course, our ME Math.pow() method does not start with numerators and denominators for the exponent. Instead, we are passed a real number. We convert this real number to a fraction with an even denominator and then take the appropriate number of square roots to solve for n. In our n = 82/3 example, we convert as follows:

n = 82/3 => n = 8683/1024 => n1024 = 8683

We selected 1024 as our denominator as 10 iterations of the square root function produces the value for n. Specifically, (n1024)(1/(2^10)) = n. Of course, we may have to scale down the number of iterations depending on the size of the right-hand side of the equation. We illustrate this approach in Example 7.

Example 7

double pow(double x, double y)
{          
    //Convert the real power to a fractional form
    int den = 1024; //declare the denominator to be 1024

    /*Conveniently 2^10=1024, so taking the square root 10
    times will yield our estimate for n.  In our example
    n^3=8^2    n^1024 = 8^683.*/

    int num = (int)(y*den); // declare numerator

    int iterations = 10;  /*declare the number of square root
        iterations associated with our denominator, 1024.*/

    double n = Double.MAX_VALUE; /* we initialize our         
        estimate, setting it to max*/

    while( n >= Double.MAX_VALUE && iterations > 1)
    {
        /*  We try to set our estimate equal to the right
        hand side of the equation (e.g., 8^2048).  If this
        number is too large, we will have to rescale. */

        n = x;
                
        for( int i=1; i < num; i++ )n*=x;

        /*here, we handle the condition where our starting
        point is too large*/
        if( n >= Double.MAX_VALUE )
        {
            iterations--;  /*reduce the iterations by one*/
                        
            den = (int)(den / 2);  /*redefine the denominator*/
                        
            num = (int)(y*den); //redefine the numerator
        }
    }
        
    /*************************************************
    ** We now have an appropriately sized right-hand-side.
    ** Starting with this estimate for n, we proceed.
    **************************************************/
        
    for( int i = 0; i < iterations; i++ )
    {
        n = Math.sqrt(n);
    }
        
    // Return our estimate
    return n;
}
            

The Taylor Series Approximation of the Natural Logarithm and Euler's e

One of the easiest ways to produce a Math.pow() method for the positive reals is to link a few methods involving use of the Taylor series. Assume we want the power y = xb. That is equivalent to ln(y) = b*ln(x). Further, we may use the Taylor series expansion for estimating the natural logarithm of x as follows.

ln(x) = (x-1) –(x-1)2/2 + (x-1)3/3 -  (x-1)4/4….if |x-1|<=1 OR

ln(x) = 1/(x/(x-1)) + 1/(x/(x-1))2 + 1/(x/(x-1))3… if |x|>1

Since x is positive, the entire domain of x is covered by these equations. This alternating series provides a very close approximation to the logarithm of the base. Multiplying this logarithm by the exponent yields ln(y), the right-hand side of our equation, ln(y)=b*ln(x). Now, we simply need to find eln(y), and we are done. We use another Taylor series expansion to finish this process. ex = 1 + x + x2 / 2! + x3 / 3! + … Using these two formulae, we have a solution for our problem, as shown in Example 8.

Example 8

double pow(double a, double b)
{
    // true if base is greater than 1
    boolean gt1 = (Math.sqrt((a-1)*(a-1)) <= 1)? false:true;
         
    int oc = -1; // used to alternate math symbol (+,-)
    int iter = 20; // number of iterations
    double p, x, x2, sumX, sumY;
        
    // is exponent a whole number?
    if( (b-Math.floor(b)) == 0 )
    {
        // return base^exponent
        p = a;
        for( int i = 1; i < b; i++ )p *= a;
        return p;
    }
        
    x = (gt1)?
            (a /(a-1)): // base is greater than 1
            (a-1); // base is 1 or less
                
    sumX = (gt1)?
            (1/x): // base is greater than 1
            x; // base is 1 or less
        
    for( int i = 2; i < iter; i++ )
    {
        // find x^iteration
        p = x;
        for( int j = 1; j < i; j++)p *= x;
            
        double xTemp = (gt1)?
                (1/(i*p)): // base is greater than 1
                (p/i); // base is 1 or less
            
        sumX = (gt1)?
                (sumX+xTemp): // base is greater than 1
                (sumX+(xTemp*oc)); // base is 1 or less
                    
        oc *= -1; // change math symbol (+,-)
    }
        
    x2 = b * sumX;
        
    sumY = 1+x2; // our estimate
                
    for( int i = 2; i <= iter; i++ )
    {
        // find x2^iteration
        p = x2;
        for( int j = 1; j < i; j++)p *= x2;
            
        // multiply iterations (ex: 3 iterations = 3*2*1)
        int yTemp = 2;
        for( int j = i; j > 2; j-- )yTemp *= j;
            
        // add to estimate (ex: 3rd iteration => (x2^3)/(3*2*1) )
        sumY += p/yTemp;
    }
        
    return sumY; // return our estimate
}

In nearly all cases the estimate returned by the Taylor series approximation is more precise than the decay algorithm approach, while the Math.sqrt() method also provides better results. The Taylor series approach uses fewer computing cycles but becomes unstable when values approach zero. The Math.sqrt() results provide excellent approximations, normally to the third digit. See Table 1 for a comparison of the methods using several arbitrarily assigned positive real variables. We can see that for practical applications, the Math.sqrt() or Taylor series methods appear to be superior for most values.

Table 1: Comparison of the Decay Algorithm and Square-Root Approaches

Programming Considerations and Conclusions

This article has addressed three approaches to developing a Math.pow() method in Java ME. While the naive "brute force" geometric decay heuristic is interesting and potentially useful for small problems, the Math.sqrt() adaptation is probably better for most ranges of applications. The best method is probably the Taylor series approximation. Clearly, these three examples do not encompass the only methods for accomplishing the task (e.g., bisection and others located in the references), and we would hope that others provide more efficient techniques that consume fewer resources. One final note: if you are required to develop such a method, consider its application, required parameters, and desired results and precision.

Resources

• Sample code for this article

java.net RSS Feeds Feedback  | FAQ  | Press | Terms of Use Privacy  |  Trademarks | Site Map   Your use of this web site or any of its content or software indicates your agreement to be bound by these Terms of Participation.   Copyright © 1995-2008 Sun Microsystems, Inc. Powered by Sun Microsystems, Inc., O'Reilly and CollabNet