C++: how can I test if a number is power of ten?

Question

I want to test if a number double x is an integer power of 10. I could perhaps use cmath's log10 and then test if x == (int) x?

edit: Actually, my solution does not work because doubles can be very big, much bigger than int, and also very small, like fractions.

Answer 1

A lookup table will be by far the fastest and most precise way to do this; only about 600 powers of 10 are representable as doubles. You can use a hash table, or if the table is ordered from smallest to largest, you can rapidly search it with binary chop.

This has the advantage that you will get a "hit" if and only if your number is exactly the closest possible IEEE double to some power of 10. If this isn't what you want, you need to be more precise about exactly how you would like your solution to handle the fact that many powers of 10 can't be exactly represented as doubles.

The best way to construct the table is probably to use string -> float conversion; that way hopefully your library authors will already have solved the problem of how to do the conversion in a way that gives the most precise answer possible.

Answer 2

Your solution sounds good but I would replace the exact comparison with a tolerance one.

double exponent = log10(value);
double rounded = floor(exponent + 0.5);
if (fabs(exponent - rounded) < some_tolerance) {
    //Power of ten
}

Answer 3

I am afraid you're in for a world of hurt. There is no way to cast down a very large or very small floating point number to a BigInt class because you lost precision when using the small floating point number.

For example float only has 6 digits of precision. So if you represent 10⁹ as a float chances are it will be converted back as 1 000 000 145 or something like that: nothing guarantees what the last digits will be, they are off the precision.

You can of course use a much more precise representation, like double which has 15 digits of precision. So normally you should be able to represent integers from 0 to 10¹⁴ faithfully.

Finally some platforms may have a long long type with an ever greater precision.

But anyway, as soon as your value exceed the number of digits available to be converted back to an integer without loss... you can't test it for being a power of ten.

If you really need this precision, my suggestion is not to use a floating point number. There are mathematical libraries available with BigInt implementations or you can roll your own (though efficiency is difficult to achieve).

Answer 4

bool power_of_ten(double x) {
   if(x < 1.0 || x > 10E15) {
      warning("IEEE754 doubles can only precisely represent powers "
              "of ten between 1 and 10E15, answer will be approximate.");
   }
   double exponent;
   // power of ten if log10 of absolute value has no fractional part
   return !modf(log10(fabs(x)), &exponent);
}

Answer 5

Depending on the platform your code needs to run on the log might be very expensive.

Since the amount of numbers that are 10^n (where n is natural) is very small, it might be faster to just use a hardcoded lookup table.

(Ugly pseudo code follows:)

bool isPowerOfTen( int16 x )
{
  if( x == 10       // n=1
    || x == 100     // n=2
    || x == 1000    // n=3
    || x == 10000 ) // n=4
  return true;

  return false;
}

This covers the whole int16 range and if that is all you need might be a lot faster. (Depending on the platform.)

Answer 6

How about a code like this:

#include <stdio.h>
#define MAX 20
bool check_pow10(double num)
{
   char arr[MAX];
   sprintf(arr,"%lf",num);
   char* ptr = arr;
   bool isFirstOne = true;

   while (*ptr)
   {
     switch (*ptr++)
     {
       case '1':
                if (isFirstOne)
                   isFirstOne = false;
                else
                   return false;
                break;
       case '0':
                break;
       case '.':
                break;
       default:
                return false;
     }
   }

 return true;
}

int main()
{
  double number;
  scanf("%lf",&number);
  printf("isPower10: %s\n",check_pow10(number)?"yes":"no");
}

That would not work for negative powers of 10 though.
EDIT: works for negative powers also.

Answer 7

if you don't need it to be fast, use recursion. Pseudocode:

bool checkifpoweroften(double Candidadte)
     if Candidate>=10
         return (checkifpoweroften(Candidadte/10) 
     elsif Candidate<=0.1
         return (checkifpoweroften(Candidadte*10)
     elsif Candidate == 1
         return 1
     else 
         return 0

You still need to choose between false positives and false negatives and add tolerances accordingly, as other answers pointed out. The tolerances should apply to all comparisons, or else, for exemple, 9.99999999 would fail the >=10 comparison.

Answer 8

how about that:

bool isPow10(double number, double epsilon)
{
    if (number > 0)
    {
        for (int i=1; i <16; i++)
        {
            if ( (number >= (pow((double)10,i) - epsilon)) && 
                (number <= (pow((double)10,i) + epsilon)))
            { 
                return true;
            }
        }
    }
    return false;
}

I guess if performance is an issue the few values could be precomputed, with or without the epsilon according to the needs.

Answer 9

A variant of this one:

double log10_value= log10(value);
double integer_value;
double fractional_value= modf(log10_value, &integer_value);

return fractional_value==0.0;

Note that the comparison to 0.0 is exact rather than within a particular epsilon since you want to ensure that log10_value is an integer.

EDIT: Since this sparked a bit of controversy due to log10 possibly being imprecise and the generic understanding that you shouldn't compare doubles without an epsilon, here's a more precise way of determining if a double is a power of 10 using only properties of powers of 10 and IEEE 754 doubles.

First, a clarification: a double can represent up to 1E22, as 1e22 has only 52 significant bits. Luckily, 5^22 also only has 52 significant bits, so we can determine if a double is (2*5)^n for n= [0, 22]:

bool is_pow10(double value)
{
    int exponent;
    double mantissa= frexp(value, &exponent);

    int exponent_adjustment= exponent/10;

    int possible_10_exponent= (exponent - exponent_adjustment)/3;

    if (possible_10_exponent>=0 && 
        possible_10_exponent<=22)
    {
        mantissa*= pow(2.0, exponent - possible_10_exponent);

        return mantissa==pow(5.0, possible_10_exponent);
    }
    else
    {
        return false;
    }
}

Since 2^10==1024, that adds an extra bit of significance that we have to remove from the possible power of 5.