¿Cuántos dígitos hay en esta base?

Question

El problema es derivar una fórmula para determinar el número de dígitos que un número decimal dado podría tener en una base determinada.

Por ejemplo: El número decimal 100006 se puede representar por 17,11,9,8,7,6,8 dígitos en bases 2,3,4,5,6,7,8 respectivamente.

Bien la fórmula I derivado hasta ahora es así: (log10 (num)/log10 (base)) + 1.

en C/C++ utilicé esta fórmula para calcular los resultados dados anteriormente.

long long int size = ((double)log10(num)/(double)log10(base)) + 1.0;

Pero, lamentablemente, la fórmula no está dando respuesta correcta es algunos casos, como estos:

Number 8 in base 2 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 64 in base 2 : 1,0,0,0,0,0,0 
Number of digits: 7 
Formula returned: 6 

Number 64 in base 4 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 125 in base 5 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 128 in base 2 : 1,0,0,0,0,0,0,0 
Number of digits: 8 
Formula returned: 7 

Number 216 in base 6 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 243 in base 3 : 1,0,0,0,0,0 
Number of digits: 6 
Formula returned: 5 

Number 343 in base 7 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Así que el error es de 1 digit.I sólo quiero a alguien que me ayude a corregir la fórmula para que funcione para todos los casos posibles.

Editar: De acuerdo con la especificación de entrada tengo que hacer frente a casos como 10 mil millones, es decir 10^10, no creo log10() en C/C++ puede manejar este tipo de casos? Entonces, cualquier otro procedimiento/fórmula para este problema será muy apreciado.

Answer 1

Hay operaciones de flotación rápida en la configuración del compilador. Necesitas operaciones de floation precisas. Lo que pasa es que log10 (8)/log10 (2) siempre es 3 en matemáticas. Pero puede ser su resultado es 2.99999, para expandirse. Es malo. Debe agregar un pequeño aditivo, pero no 0.5. Debería ser .00001 o algo así.

Casi verdadera fórmula: solución

int size = static_cast<int>((log10((double)num)/log10((double)base)) + 1.00000001); 

realmente cierto

Debe comprobar el resultado de la fórmula. ¡Compexity es O(log log n) o O(log result)!

int fast_power(int base, int s) 
{ 
    int res = 1; 
    while (s) { 
     if (s%2) { 
      res*=base; 
      s--; 
     } else { 
      s/=2; 
      base*=base; 
     } 
    } 
    return res; 
} 

int digits_size(int n, int base) 
{ 
    int s = int(log10(1.0*n)/log10(1.0*base)) + 1; 
    return fast_power(base, s) > n ? s : s+1; 
} 

Esta comprobación es mejor que la prueba de fuerza bruta con base multiplicaciones.

Answer 2

Number of digits of a numeral in a given base

Answer 3

Debido a que su fórmula es correcta (acabo probé), yo creo que es un error de redondeo en su división, causando que el número sea sólo un poco menor que el valor entero que debería ser. Entonces cuando truncas a un número entero, pierdes 1. Intenta agregar 0.5 adicionales a tu valor final (de modo que truncar es en realidad una operación circular).

Answer 4

Puede ser beneficioso ajustar una función de redondeo (por ejemplo + 0.5) en su código en alguna parte: es bastante probable que la división produzca (ej.) 2.99989787, a la que se agrega 1.0, dando 3.99989787 y cuando eso se convierte en int, da 3.

Answer 5

Cualquiera de las siguientes funcionará:

>>> from math import * 
>>> def digits(n, b=10): 
...  return int(1 + floor(log(n, b))) if n else 1 
... 
>>> def digits(n, b=10): 
...  return int(ceil(log(n + 1, b))) if n else 1 
... 

la primera versión se explica en mathpath.org. En la segunda versión es necesario + 1 para dar la respuesta correcta para cualquier número n que es el número más pequeño con d dígitos en la base b. Es decir, aquellos números que están escritos 10 ... 0 en la base b. Observe que la entrada 0 debe tratarse como un caso especial.

ejemplos decimales:

>>> digits(1) 
1 
>>> digits(9) 
1 
>>> digits(10) 
2 
>>> digits(99) 
2 
>>> digits(100) 
3 

binario:

>>> digits(1, 2) 
1 
>>> digits(2, 2) 
2 
>>> digits(3, 2) 
2 
>>> digits(4, 2) 
3 
>>> digits(1027, 2) 
11 

Editar: El PO afirma que la solución log puede no funcionar para grandes entradas.Yo no sé nada de eso, pero si es así, el siguiente código no debería romperse, ya que utiliza la aritmética de enteros solamente (esta vez en C):

unsigned int 
digits(unsigned long long n, unsigned long long b) 
{ 
    unsigned int d = 0; 
    while (d++, n /= b); 
    return d; 
} 

Este código será probablemente menos eficiente. Y sí, fue escrito para los puntos de oscuridad máximos. Simplemente utiliza la observación de que cada número tiene al menos un dígito, y que cada división por b que no rinde 0 implica la existencia de un dígito adicional. Una versión más fácil es la siguiente:

unsigned int 
digits(unsigned long long n, unsigned long long b) 
{ 
    unsigned int d = 1; 
    while (n /= b) { 
    d++; 
    } 
    return d; 
} 

Answer 6

Parece que la fórmula es correcta para mí:

Number 8 in base 2 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

log10(8) = 0.903089 
log10(2) = 0.301029 

Division => 3 

+1 => 4 

lo que es definitivamente sólo un error de redondeo.

Answer 7

Lo que queremos es el techo (= menor entero no mayor que) log _b (n + 1), en lugar de lo que estás calcular en este momento, suelos (1 + log b (n)).

Usted puede tratar de:

int digits = (int) ceil(log((double)(n+1))/log((double)base)); 

Answer 8

Utilizando la fórmula,

log(8)/log(2) + 1 = 4 

el problema está en la precisión del cálculo de logaritmo. Usando

ceil(log(n+1)/log(b)) 

debería resolver ese problema. Esto no es exactamente lo mismo que

ceil(log(n)/log(b)) 

porque esto da la respuesta 3 para n = 8 b = 2, ni es el mismo que

log(n+1)/log(b) + 1 

porque esto da la respuesta 4 para n = 7 b = 2 (cuando se calcula con precisión total).

realidad tengo algo curioso que resulta implementar y compilar la primera forma con g ++:

double n = double(atoi(argv[1])); 
double b = double(atoi(argv[2])); 
int i = int(std::log(n)/std::log(b) + 1.0); 

falla (IE da la respuesta 3), mientras que,

double v = std::log(n)/std::log(b) + 1.0; 
int i = int(v); 

tiene éxito (da la respuesta 4) En cuanto a un poco más creo una tercera forma

ceil(log(n+0.5)/log(b)) 

sería más estable, ya que evita el caso "crítico" cuando N (o N + 1 para la segunda forma) es una potencia entera de b (para valores enteros de n).

Answer 9

Problemas de redondeo de punto flotante.

log10(216)/log10(6) = 2.9999999999999996 

Pero no puede agregar 0.5 Como se ha sugerido, ya que no funcionaría para la siguiente

log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5 
log10(1296) = log10(6) = 4.0     // 1, 0, 0, 0, 0 

Tal vez el uso de la función log (valor base) sería evitar estos errores de redondeo.

Answer 10

Como han señalado otros, tiene un error de redondeo, pero las soluciones propuestas simplemente mueven la zona de peligro o la reducen, no la eliminan. Si sus números son enteros, puede verificar - usando aritmética entera - esa potencia de la base es menor o igual que su número, y la siguiente está por encima (la primera potencia es la cantidad de dígitos). Pero si usa la aritmética de coma flotante en cualquier punto de la cadena, entonces será vulnerable al error (a menos que su base sea una potencia de dos, y tal vez incluso entonces).

EDIT:
Aquí es solución bruta pero eficaz en la aritmética de enteros. Si sus clases enteras pueden contener números tan grandes como el número base *, esto dará la respuesta correcta.

 
    size = 0, k = 1; 
    while(k<=num) 
    { 
     k *= base; 
     size += 1; 
    } 

Answer 11

Creo que la única forma de eliminar el error de redondeo sin producir otros errores es usar o implementar logaritmos enteros.

Answer 12

Aquí es una solución en bash:

% digits() { echo $1 $2 opq | dc | sed 's/ .//g;s/.//' | wc -c; } 


% digits 10000000000 42 
7 

Answer 13

static int numInBase(int num, int theBase) 
{ 
    if(num == 0) return 0; 
    if (num == theBase) return 1; 
    return 1 + numInBase(num/theBase,theBase); 
}