Moyen le plus rapide pour trouver la plus grande puissance de 10 plus petit que x
https://stackoverflow.com/questions/4513707
-
12-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
est-il un moyen rapide de trouver la plus grande puissance de 10 plus petit qu'un nombre donné?
J'utilise cet algorithme, pour le moment, mais quelque chose en moi meurt chaque fois que je le vois:
10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) ) // C
Je pourrais mettre en œuvre des fonctions de log10 et pow simples pour mes problèmes avec une boucle chaque, mais je me demande s'il y a quelque chose de magique bits pour les nombres décimaux.
La solution
Un autre algorithme est:
i = 1;
while((i * 10) < x)
i *= 10;
Autres conseils
Log et la puissance sont des opérations coûteuses. Si vous voulez rapide, vous voulez probablement rechercher l'exposant binaire IEEE dans le tableau pour obtenir la puissance approximative de dix, puis vérifier si les forces de mantisse un changement de +1 ou non. Cela devrait être 3 ou 4 entier instructions machine (en variante O (1) avec une très faible constante).
tables données:
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]);
}
alors votre calcul doit être:
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];
[Vous pourriez vraiment besoin d'écrire cela comme assembleur pour faire sortir toutes les horloges dernier.] [Ce code n'a pas été testé.]
Cependant, si vous insistez pour le faire cela en python, les frais généraux de l'interpréteur peut inonder le temps log / exp et peut-être pas question.
Alors, voulez-vous jeûnez, ou voulez-vous court à écrire?
EDIT 12/23: OP nous dit maintenant que son "x" fait partie intégrante. En supposant que c'est un 64 (ou 32) entier bits, ma proposition fonctionne toujours, mais de toute évidence il n'y a pas un « IEEE_Exponent ». La plupart des processeurs ont une instruction « trouver première » qui vous indiquera le nombre de bits 0 sur la main gauche (le plus important) une partie de la valeur, par exemple, des zéros à gauche; vous avez probablement c'est essentiellement 64 (ou 32) moins la puissance de deux pour la valeur. Compte tenu de l'exposant = 64 - leadingzeros, vous avez la puissance de deux exposants et la plupart du reste de l'algorithme est essentiellement inchangée (Modifications gauche pour le lecteur).
Si le processeur ne dispose pas d'une instruction de trouver-première un, puis probablement le meilleur pari est un arbre de discrimination équilibrée afin de déterminer la puissance de dix. Pour 64 bits, un tel arbre faudrait au plus 18 compare pour déterminer l'exposant (10 ^ 18 ^ ~~ 2 64).
Créer un tableau de puissances de 10. Recherche par elle pour la plus grande valeur inférieure à x.
Si x est assez petite, vous pouvez constater que la recherche linéaire offre de meilleures performances qu'une recherche binaire, due en partie à moins de faux-prédictions de branchement.
La façon la plus rapide asymptotiquement, pour autant que je sache, implique équerrage répétée.
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
L'algorithme prend du temps et de l'espace logarithmique dans du N, qui est linéaire à la taille de la représentation des N. [Le temps lié est probablement un peu plus mal parce que je simplifié avec optimisme]
Notez que je supposais arbitrairement grands nombres entiers (attention en cas de débordement!), Depuis les temps-10 jusqu'à ce qu'elles soient plus naïves algorithme est probablement assez rapidement en traitant avec juste des entiers de 32 bits.
Étant donné que cela est indépendant de la langue, si vous pouvez obtenir la puissance de deux que ce nombre est significatif, par exemple y en x * 2 ^ y (ce qui est la façon dont le numéro est enregistré, mais je ne suis pas sûr ont vu un moyen facile d'accès y dans une langue que je l'ai utilisé) alors si
z = int(y/(ln(10)/ln(2)))
(une division à virgule flottante)
10 ^ z ou 10 ^ (z + 1) sera votre réponse, bien que 10 ^ z est toujours pas si simple (BEG à corriger).
Je pense que la façon la plus rapide est O (log (log (n)) ^ 2), la boucle While prend O (log (log (n)) et il peut être appel récursif temps fini (on peut dire O (c ) où voir est constant), premier appel récursif est prend log (log (sqrt (n))) deuxième temps prend .. et le nombre de sqrt dans sqrt (sqrt (sqrt .... (n)) <10 est log (log (n)) et constant, en raison des limitations de la machine.
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)
J'ai chronométré les méthodes avec les variations suivantes en C ++ pour la valeur a étant un type de size_t (inline améliore les performances, mais ne change pas l'ordre relatif).
Essayez 1:. Multiplier jusqu'au numéro trouver
size_t try1( size_t a )
{
size_t scalar = 1ul;
while( scalar * 10 < a ) scalar *= 10;
return scalar;
}
Essayez 2:. Multivoie si (peut également être programmé à l'aide d'une table de consultation)
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 )))))))))))))))))));
}
Essayez 3. Modifié de findPow10 de @Saaed Amiri, qui utilise équarrissage pour trouver plus rapidement des pouvoirs très étendus que Try 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;
}
Essayez 4:. Table de recherche indexée à l'aide de l'instruction zéros en tête de comptage selon @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 est la suivante (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
La recherche / multivoies si tout-bat en C ++, mais exige que nous savons entiers sont d'une taille finie. try3 est plus lente que try1 dans ce test pour les petites valeurs de la valeur de fin de boucle, pour un grand nombre try3 battements try1. Dans les choses python sont rendues difficiles parce que les entiers ne sont pas limités donc je combiner avec try2 try3 pour traiter rapidement les numéros jusqu'à une limite fixe alors gérer le nombre potentiellement très importantes.
En python Je pense que recherche l'aide d'une compréhension de liste est probablement plus rapide qu'un multivoies-si.
# where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]
