C++: ¿cómo puedo probar si un número es potencia de diez?

Question

Quiero probar si un número double x es una potencia entera de 10. Podría quizás usar cmath's log10 y luego probar si x == (int) x?

edit: En realidad, mi solución no funciona porque los dobles pueden ser muy grandes, mucho más grandes que int, y también muy pequeños, como fracciones.

Answer 1

Una tabla de búsqueda será, de lejos, la forma más rápida y precisa de hacerlo; solo alrededor de 600 poderes de 10 son representables como dobles. Puede usar una tabla hash, o si la tabla se ordena de la más pequeña a la más grande, puede buscarla rápidamente con chuleta binaria.

Esto tiene la ventaja de que recibirá un "golpe" si y solo si su número es exactamente el doble IEEE más cercano a una potencia de 10. Si esto no es lo que quiere, necesita ser más preciso sobre exactamente cómo le gustaría que su solución maneje el hecho de que muchos poderes de 10 no se pueden representar exactamente como dobles.

La mejor manera de construir la tabla es probablemente usar cadena -> conversión flotante; De esta manera, con suerte, los autores de tu biblioteca ya habrán resuelto el problema de cómo hacer la conversión de forma que ofrezca la respuesta más precisa posible.

Answer 2

Su solución suena bien pero reemplazaría la comparación exacta por una de tolerancia.

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

Answer 3

Dependiendo de la plataforma que su código necesita para ejecutarse en el registro puede ser muy caro.

Dado que la cantidad de números que son 10^n (donde n es natural) es muy pequeña, podría ser más rápido simplemente usar una tabla de búsqueda codificada.

(pseudo código feo sigue :)

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

Esto cubre toda la gama Int16 y si eso es todo lo que necesita podría ser mucho más rápido. (Dependiendo de la plataforma.)

Answer 4

¿Qué tal un código como el siguiente:

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

Eso no funcionaría para potencias negativas de 10 sin embargo.
EDITAR: funciona para potencias negativas también.

Answer 5

si no necesita que sea rápido, utilice recursividad. Pseudocódigo:

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 

Todavía es necesario elegir entre falsos positivos y falsos negativos y añadir tolerancias en consecuencia, como otras respuestas señalaron. Las tolerancias deberían aplicarse a todas las comparaciones, o bien, por ejemplo, 9.99999999 fallaría la comparación> = 10.

Answer 6

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 7

Me temo que te espera un mundo de dolor. No hay forma de arrojar un número de coma flotante muy grande o muy pequeño a una clase BigInt porque perdió precisión al usar el número de coma flotante pequeño. Por ejemplo, float tiene solo 6 dígitos de precisión.Entonces, si representa 10 como float es probable que se convierta de nuevo como 1 000 000 145 o algo así: nada garantiza cuáles serán los últimos dígitos, están fuera de la precisión.

Por supuesto, puede utilizar una representación mucho más precisa, como double que tiene 15 dígitos de precisión. Por lo tanto, normalmente debería poder representar enteros de 0 a 10 fielmente.

Finalmente, algunas plataformas pueden tener un tipo long long con una precisión cada vez mayor.

Pero de todos modos, tan pronto como su valor exceda el número de dígitos disponibles para convertir de nuevo a un número entero sin pérdida ... no puede probarlo por ser una potencia de diez.

Si realmente necesita esta precisión, mi sugerencia es no utilizar un número de coma flotante. Hay bibliotecas matemáticas disponibles con las implementaciones BigInt o puede hacer las suyas propias (aunque la eficacia es difícil de lograr).

Answer 8

¿qué tal que:

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

supongo que si el rendimiento es un problema de los pocos valores podrían ser calculado previamente, con o sin la épsilon de acuerdo con las necesidades.

Answer 9

Una variante de this uno:

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

return fractional_value==0.0; 

Tenga en cuenta que la comparación a 0.0 es exacta y no dentro de un épsilon particular, ya que desea asegurarse de que log10_value es un entero.

EDIT: Dado que esto generó un poco de controversia debido a log10 posiblemente impreciso y la comprensión genérica de que no debe comparar dobles sin épsilon, aquí hay una manera más precisa de determinar si un doble es una potencia de 10 usando solo se duplican las propiedades de potencias de 10 y IEEE 754.

Primero, una aclaración: un doble puede representar hasta 1E22, ya que 1e22 tiene solo 52 bits significativos. Por suerte, 5^22 también Sólo hay 52 bits significativos, por lo que podemos determinar si un doble es (2*5)^n para 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; 
    } 
} 

Desde 2^10==1024, que añade un poco más de importancia que hay que eliminar de la potencia posible de 5.