La manera más rápida de encontrar la mayor potencia de 10 más pequeño que x
https://stackoverflow.com/questions/4513707
-
12-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Hay alguna forma rápida de encontrar la mayor potencia de 10 más pequeño que un número dado?
Estoy usando este algoritmo, por el momento, pero algo dentro de mí muere en cualquier momento lo veo:
10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) ) // C
Me podría implementar funciones log10 y pow simples para mis problemas con un bucle de cada uno, pero todavía me estoy preguntando si hay algo de magia bits para los números decimales.
Solución
Un algoritmo alternativo es:
i = 1;
while((i * 10) < x)
i *= 10;
Otros consejos
Registro y poder son operaciones costosas. Si usted quiere rápidamente, es probable que desee para buscar el exponente binario IEEE en la tabla para obtener la potencia aproximada de diez y, a continuación, comprobar si las fuerzas de la mantisa un cambio en +1 o no. Esto debería ser 3 o 4 entero instrucciones de máquina (alternativamente O (1) con una bastante pequeña constante).
mesas dado:
int IEEE_exponent_to_power_of_ten[2048]; // needs to be 2*max(IEEE_exponent)
double next_power_of_ten[600]; // needs to be 2*log10(pow(2,1024)]
// you can compute these tables offline if needed
for (p=-1023;p>1023;p++) // bounds are rough, see actual IEEE exponent ranges
{ IEEE_exponent_to_power_of_ten[p+1024]=log10(pow(2,p)); // you might have to worry about roundoff errors here
next_power_of_ten[log10(pow(2,p))+1024]=pow(10,IEEE_exponent_to_power_of_ten[p+1024]);
}
a continuación, su cálculo debe ser:
power_of_ten=IEEE_exponent_to_power_of_10[IEEE_Exponent(x)+1023];
if (x>=next_power_of_ten[power_of_ten]) power_of_ten++;
answer=next_power_of_ten[power_of_ten];
[Es posible que realmente se necesita para escribir esto como ensamblador para exprimir hasta la última reloj.] [Este código no probado.]
Sin embargo, si usted insiste en hacer esto en Python, la sobrecarga intérprete puede inundar el momento de registro / exp y puede que no importa.
Así que, ¿quiere rápidamente, o quieres corto a escribir?
EDITAR 12/23: OP ahora nos dice que su "x" es integral. Bajo el supuesto de que se trata de un entero de 64 bits (o 32), mi propuesta sigue funcionando pero obviamente no hay una "IEEE_Exponent". La mayoría de los procesadores tienen una instrucción de "buscar primero" que le indicará el número de bits 0 en la mano izquierda (el más significativo) parte del valor, por ejemplo, ceros a la izquierda; es probable que esto es, en esencia, de 64 (o 32) menos la potencia de dos para el valor. Dada exponente = 64 - leadingzeros, que tienen el poder de dos exponente y la mayor parte del resto del algoritmo es esencialmente sin cambios (modificaciones deja para el lector).
Si el procesador no tiene un hallazgo, primero en una instrucción, entonces probablemente la mejor opción es un árbol de la discriminación equilibrada para determinar la potencia de diez. Para 64 bits, tal árbol tomaría como máximo 18 compara para determinar el exponente (10 ^ 18 ~~ 2 ^ 64).
Crea una serie de potencias de 10. Buscar a través de él para el valor más grande menor que x.
Si x es bastante pequeño, es posible que una búsqueda lineal proporciona mejor rendimiento que una búsqueda binaria, debido en parte a un menor número de sucursales predicciones erróneas.
La forma asintótica más rápido, por lo que yo sé, consiste en elevar al cuadrado repetidas.
func LogFloor(int value, int base) as int
//iterates values of the form (value: base^(2^i), power: 2^i)
val superPowers = iterator
var p = 1
var c = base
while c <= value
yield (c, p)
c *= c
p += p
endwhile
enditerator
//binary search for the correct power
var p = 0
var c = 1
for val ci, pi in superPowers.Reverse()
if c*ci <= value
c *= ci
p += pi
endif
endfor
return p
El algoritmo toma tiempo logarítmica y el espacio en N, que es lineal al tamaño de la representación de N. [El tiempo unido es probablemente un poco peor porque he simplificado optimismo]
Tenga en cuenta que asumí arbitrariamente grandes números enteros (cuidado con desbordamiento!), Desde los tiempos-10-hasta-sobre ingenuas algoritmo es probablemente lo suficientemente rápido cuando se trata de sólo números enteros de 32 bits.
Dado que esta es independiente del lenguaje, si se puede obtener la potencia de dos que este número es significativo que, por ejemplo, y en x * 2 ^ Y (que es la forma en que se almacena el número, aunque no estoy seguro de que me han visto una forma fácil de acceder y en cualquier idioma que he utilizado) entonces si
z = int(y/(ln(10)/ln(2)))
(una división de coma flotante)
10 ^ Z o 10 ^ (z + 1) será su respuesta, aunque 10 ^ z es todavía no es tan simple (BEG a ser corregido).
Creo que la forma más rápida es O (log (log (n)) ^ 2), el bucle while toma O (log (log (n)) y puede ser recursivo duración de la llamada finita (podemos decir O (c ) donde ver es constante), primera llamada recursiva es toma log (log (sqrt (n))) tiempo de segunda toma .. y el número de sqrt en sqrt (sqrt (sqrt .... (n)) <10 es log (log (n)) y constante, debido a las limitaciones de la máquina.
static long findPow10(long n)
{
if (n == 0)
return 0;
long i = 10;
long prevI = 10;
int count = 1;
while (i < n)
{
prevI = i;
i *= i;
count*=2;
}
if (i == n)
return count;
return count / 2 + findPow10(n / prevI);
}
En Python:
10 ** (len (str (int (x))) - 1)
I timed los métodos con las siguientes variaciones en C ++ para la a valor siendo un tipo size_t (inlining mejora el rendimiento, pero no cambia ordenación relativa).
Trate. 1: Multiplicar hasta el número hallazgo
size_t try1( size_t a )
{
size_t scalar = 1ul;
while( scalar * 10 < a ) scalar *= 10;
return scalar;
}
Trate 2:. Multiway si (también podría ser programado usando una tabla de consulta)
size_t try2( size_t a )
{
return ( a < 10ul ? 1ul :
( a < 100ul ? 10ul :
( a < 1000ul ? 100ul :
( a < 10000ul ? 1000ul :
( a < 100000ul ? 10000ul :
( a < 1000000ul ? 100000ul :
( a < 10000000ul ? 1000000ul :
( a < 100000000ul ? 10000000ul :
( a < 1000000000ul ? 100000000ul :
( a < 10000000000ul ? 1000000000ul :
( a < 100000000000ul ? 10000000000ul :
( a < 1000000000000ul ? 100000000000ul :
( a < 10000000000000ul ? 1000000000000ul :
( a < 100000000000000ul ? 10000000000000ul :
( a < 1000000000000000ul ? 100000000000000ul :
( a < 10000000000000000ul ? 1000000000000000ul :
( a < 100000000000000000ul ? 10000000000000000ul :
( a < 1000000000000000000ul ? 100000000000000000ul :
( a < 10000000000000000000ul ? 1000000000000000000ul :
10000000000000000000ul )))))))))))))))))));
}
Trate 3:. Modificado de findPow10 de @Saaed Amiri, que utiliza la cuadratura a encontrar más rápidamente muy grandes potencias de tratar 1
size_t try3( size_t a )
{
if (a == 0)
return 0;
size_t i, j = 1;
size_t prev = 1;
while( j != 100 )
{
i = prev;
j = 10;
while (i <= a)
{
prev = i;
i *= j;
j *= j;
}
}
return prev;
}
Trate. 4: tabla de búsqueda indexada mediante conteo que lleva la instrucción ceros según @Ira Baxter
static const std::array<size_t,64> ltable2{
1ul, 1ul, 1ul, 1ul, 1ul, 10ul, 10ul, 10ul,
100ul, 100ul, 100ul, 1000ul, 1000ul, 1000ul,
1000ul, 10000ul, 10000ul, 10000ul, 100000ul,
100000ul, 100000ul, 1000000ul, 1000000ul,
1000000ul, 1000000ul, 10000000ul, 10000000ul,
10000000ul, 100000000ul, 100000000ul,
100000000ul, 1000000000ul, 1000000000ul,
1000000000ul, 1000000000ul, 10000000000ul,
10000000000ul, 10000000000ul, 100000000000ul,
100000000000ul, 100000000000ul, 1000000000000ul,
1000000000000ul, 1000000000000ul, 1000000000000ul,
10000000000000ul, 10000000000000ul, 10000000000000ul,
100000000000000ul, 100000000000000ul, 100000000000000ul,
1000000000000000ul, 1000000000000000ul, 1000000000000000ul,
1000000000000000ul, 10000000000000000ul, 10000000000000000ul,
10000000000000000ul, 100000000000000000ul, 100000000000000000ul,
100000000000000000ul, 100000000000000000ul, 1000000000000000000ul,
1000000000000000000ul };
size_t try4( size_t a )
{
if( a == 0 ) return 0;
size_t scalar = ltable2[ 64 - __builtin_clzl(a) ];
return (scalar * 10 > a ? scalar : scalar * 10 );
}
Timing es la siguiente (gcc 4.8)
for( size_t i = 0; i != 1000000000; ++i) try1(i) 6.6
for( size_t i = 0; i != 1000000000; ++i) try2(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) try3(i) 6.5
for( size_t i = 0; i != 1000000000; ++i) try4(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) pow(10,size_t(log10((double)i)))
98.1
Las operaciones de búsqueda / de múltiples vías, si supera todo en C ++, pero requiere que sabemos enteros son de un tamaño finito. try3 es más lento que try1 en esta prueba para valores más pequeños del valor final del bucle, para un gran número try3 latidos try1. En Python cosas se hacen difíciles porque los números enteros no están limitados por lo que combinaría con try2 try3 a procesar rápidamente números hasta un límite fijo y luego manejar los posiblemente números muy grandes.
En Python Creo que las operaciones de búsqueda utilizando una lista por comprensión es probablemente más rápido que un multivía-si.
# where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]
