Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fastest way to obtain a power of 10

Tags:

java

math

pow

I'll use Java as an example here, as it may be completely language-specific, but I'm generally interested in ways to do this.
Of course, the simplest and obvious way is this:

Math.pow(10, x)

but as far as I know, power is a fairly expensive operation. Thus I thought that there should be a better way, because it seems so obvious - I just need x zeroes after the 1!

Edit: Yes, this may be premature optimisation. The context is a rounding operation to n decimal places, which often uses something like this:

private final static int[] powersOf10 = {1, 10, 100, 1000, 10000};
public static double round(double number, int decimals) {
    if(decimals < 5)
        return Math.rint(number / powersOf10[decimals]) * powersOf10[decimals];
    double c = Math.pow(10, decimals);
    return Math.rint(number * c) / c;
}

This is the current rounding function I use, as you can see I already use a lookup table for the most used values, but I'm still curious whether there's some bit-magic or the like to improve this.

like image 210
xeruf Avatar asked Oct 27 '17 21:10

xeruf


2 Answers

The fastest way is

static final int[] POWERS_OF_10 = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
static int powerOfTen(int pow) {
  return POWERS_OF_10[pow];
}

...since no higher power of ten fits into an int. Sorry if you were expecting something cooler.

like image 185
Louis Wasserman Avatar answered Oct 15 '22 11:10

Louis Wasserman


This question is quite old, but for people landing here from a search, I hope this is useful.

I tested the performance of three approaches using JMH:

  1. Math.pow(10, exponent)
  2. Look up in an array, as per the accepted answer
  3. Look up in a hard-coded switch statement.

Here is the JMH benchmark code:

private static final long[] POWERS_OF_TEN = {
                       10L,
                      100L,
                    1_000L,
                   10_000L,
                  100_000L,
                1_000_000L,
               10_000_000L,
              100_000_000L,
            1_000_000_000L,
           10_000_000_000L,
          100_000_000_000L,
        1_000_000_000_000L,
       10_000_000_000_000L,
      100_000_000_000_000L,
    1_000_000_000_000_000L};

int exponent;

@Setup(Level.Iteration) public void randomExponent()
{
    exponent = RAND.nextInt(16);
}

@Benchmark public long mathPow()
{
    return (long) Math.pow(10, exponent);
}

@Benchmark public long arrayLookup()
{
    return POWERS_OF_TEN[exponent];
}

@Benchmark public long switchLookup()
{
    switch (exponent)
    {
        case 1:  { return                    10L; }
        case 2:  { return                   100L; }
        case 3:  { return                 1_000L; }
        case 4:  { return                10_000L; }
        case 5:  { return               100_000L; }
        case 6:  { return             1_000_000L; }
        case 7:  { return            10_000_000L; }
        case 8:  { return           100_000_000L; }
        case 9:  { return         1_000_000_000L; }
        case 10: { return        10_000_000_000L; }
        case 11: { return       100_000_000_000L; }
        case 12: { return     1_000_000_000_000L; }
        case 13: { return    10_000_000_000_000L; }
        case 14: { return   100_000_000_000_000L; }
        case 15: { return 1_000_000_000_000_000L; }
    }
    return 0L;
}

And (drumroll...) here are the results:

Benchmark                           Mode  Cnt    Score    Error   Units
PowerOfTenBenchmark.mathPow        thrpt   15   24.134 ± 32.132  ops/us
PowerOfTenBenchmark.arrayLookup    thrpt   15  515.684 ± 10.056  ops/us
PowerOfTenBenchmark.switchLookup   thrpt   15  461.318 ±  4.941  ops/us

So #2 array lookup is the fastest, confirming the accepted answer is correct.

If you think the POWERS_OF_TEN array literal initialiser is ugly (I agree), there is a shorter and possibly less error-prone way:

private static final long[] POWERS_OF_TEN = IntStream.range(0, 16)
    .mapToLong(i -> (long) Math.pow(10, i)).toArray();
like image 38
Will Hains Avatar answered Oct 15 '22 11:10

Will Hains