C ++: как я могу проверить, является ли число степенью десяти?

Question

Я хочу проверить, является ли число double x целочисленной степенью 10. Я мог бы, возможно, использовать cmath's log10 и затем проверить, если x == (int) x?

edit: На самом деле, мое решение не работает, потому что double может быть очень большим, намного большим, чем int, а также очень маленьким, как дроби.

Answer 1

Таблица поиска будет, безусловно, самым быстрым и точным способом сделать это; только около 600 степеней из 10 представляются как двойники. Вы можете использовать хеш-таблицу, или, если таблица упорядочена от наименьшего к наибольшему, вы можете быстро найти ее с помощью бинарного кода.

Это имеет то преимущество, что вы получите «удар» тогда и только тогда, когда ваш номер будет как можно ближе к IEEE, удвоенному до некоторой степени 10. Если это не то, что вы хотите, вам нужно быть более точным в отношении как именно вы хотели бы, чтобы ваше решение обрабатывало тот факт, что многие степени 10 не могут быть точно представлены как двойные числа.

Лучший способ построить таблицу - это использовать string -> float translation; таким образом, мы надеемся, что авторы вашей библиотеки уже решили проблему конвертации таким образом, чтобы дать максимально точный ответ.

Answer 2

Ваше решение звучит хорошо, но я бы заменил точное сравнение на допуск.

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

Answer 3

Боюсь, ты в мире обид. Невозможно преобразовать очень большое или очень маленькое число с плавающей запятой в класс BigInt, потому что вы потеряли точность при использовании небольшого числа с плавающей запятой.

Например, float имеет только 6 цифр точности. Поэтому, если вы представляете 10 ⁹ как float, скорее всего, он будет преобразован обратно как 1 000 000 145 или что-то в этом роде: ничто не гарантирует, какими будут последние цифры, они не соответствуют точности. *

Конечно, вы можете использовать гораздо более точное представление, например double, которое имеет 15 цифр точности. Поэтому обычно вы должны быть в состоянии представить целые числа от 0 до 10 ¹⁴ точно.

Наконец, некоторые платформы могут иметь тип long long с еще большей точностью.

Но в любом случае, как только ваше значение превысит количество доступных цифр для преобразования обратно в целое число без потерь ... вы не можете проверить его на степень десяти.

Если вам действительно нужна эта точность, я не советую использовать число с плавающей запятой. Существуют математические библиотеки, доступные в реализациях BigInt, или вы можете создавать свои собственные (хотя эффективность трудно достичь).

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

В зависимости от платформы, которую ваш код должен запускать в журнале, может быть очень дорого.

Поскольку количество чисел, равных 10 ^ n (где n натурально), очень мало, может быть быстрее просто использовать жестко заданную таблицу поиска.

(следует страшный псевдокод:)

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;
}

Это охватывает весь диапазон int16, и если это все, что вам нужно, это может быть намного быстрее. (В зависимости от платформы.)

Answer 6

Вариант это один:

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

return fractional_value==0.0;

Обратите внимание, что сравнение с 0.0 является точным, а не внутри конкретного эпсилона, поскольку вы хотите убедиться, что log10_value является целым числом.

РЕДАКТИРОВАТЬ: Так как это вызвало небольшую полемику из-за возможной неточности log10 и общего понимания, что вы не должны сравнивать двойные числа без эпсилона, вот более точный способ определить, является ли двойная степень степенью 10 используя только свойства степеней 10 и двойников IEEE 754.

Во-первых, уточнение: двойное число может представлять до 1E22, поскольку 1e22 имеет только 52 значащих бита. К счастью, 5 ^ 22 также имеет только 52 значащих бита, поэтому мы можем определить, является ли удвоение (2*5)^n для 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;
    }
}

Начиная с 2^10==1024, это добавляет дополнительный бит значимости, который мы должны удалить из возможной степени 5.

Answer 7

как насчет этого:

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;
}

Я думаю, что если производительность является проблемой, то несколько значений могут быть предварительно вычислены с или без эпсилона в зависимости от потребностей.

Answer 8

если вам не нужно, чтобы это было быстро, используйте рекурсию. Псевдокод:

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

Вам все еще нужно выбирать между ложными срабатываниями и ложными отрицаниями и соответственно добавлять допуски, как указывали другие ответы. Допуски должны применяться ко всем сравнениям, в противном случае, например, 9.99999999 не выполнит сравнение> = 10.

Answer 9

Как насчет кода, подобного этому:

#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");
}

Это не сработает для отрицательных сил 10, хотя.
РЕДАКТИРОВАТЬ: работает и для отрицательных сил.