Schnellste Weg, um finden Sie die größte Potenz von 10, die kleiner als x

Gibt es keine schnelle Möglichkeit zu finden die größte Potenz von 10, die kleiner als eine gegebene Zahl?

Ich bin mit diesem Algorithmus, im moment, aber etwas in mir stirbt jedes mal wenn ich es sehe:

10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) )   //C

Ich umsetzen konnte einfach log10 und pow Funktionen für meine Probleme mit einer Schleife jeden, aber ich bin immer noch Fragen, wenn es ein bisschen Magie für dezimal-zahlen.

  • Was ist daran falsch? Es dauert .0161 Mikrosekunden im Durchschnitt durchzuführen 10**(int(math.log10(987654321987654321))), das ist eigentlich ziemlich beeindruckend.
  • reden wir über integers oder floats?
  • Der Schnellste Algorithmus ist wahrscheinlich, abhängig von der Größe der x. Sie werden wahrscheinlich wollen, um Profil zu einem hybrid-Ansatz.
  • In meinem Fall x ist eine ganze Zahl, aber ich denke, es sollte nicht ändern, dass viel (könnte cast float x in einen ganzzahligen Wert und Umgekehrt).
  • meine Antwort war schneller als andere, theoretisch, Es ist nützlich für die großen Nummern, die nicht 10-stellig.
InformationsquelleAutor peoro | 2010-12-22
  1. 6

    Einen alternativen Algorithmus ist:

    i = 1;
while((i * 10) < x)
    i *= 10;
    • Das ist ein schreckliches Konzept im Hinblick auf die Komplexität der Berechnung. Ihre Methode ist O(n) in Bezug auf die Anzahl der bits, in der Erwägung, dass O(log(n)) ausreichend.
    • Ist alles ein Kompromiss. Für zahlen mit einer endlichen Bereich, O(n) könnte sehr gut sein, nur feiner, und diese option nimmt keinen zusätzlichen Platz (verglichen mit haben eine große lookup-Tabelle, precomputing eine Sequenz von Plätzen, usw.). Komplexität ist nicht das be-all and end-all, ob ein Algorithmus ist "gut" oder nicht. Es wäre relativ einfach, dies zu ändern, um Platz statt naiv-multiplizieren, bis es in der Nähe, aber das würde bedeuten, mehr code und könnte, in der Tat, verlangsamen, kleinere Eingänge. Die richtige Wahl hängt von den erwarteten Eingabedaten, nicht nur auf big-O-Leistung.
    • es ist besser, do it while((i = i * 10) < x); oder while (i<x) i*=10; und zählen-am Ende.
    • Komplexität ist nicht sein-alles und Ende-alles - sicher, aber in diesem Fall hat er ausdrücklich gebeten, Sie auf dem schnellsten Weg...
    • Die meisten (alle?) die Antworten, die ich bekam, sind viel billiger als mein Alter code. Diese Lösung ist die einfachste umgesetzt werden, sauber und wirklich einfach zu verstehen. Ich bin Umsetzung dieses, da ich denke, dass für meine durchschnittlichen Fall (im moment) es nicht brauchen zu Durchlaufen mehr als 4 oder 5 mal, so wird eine schnelle O(n) Lösung sollte ok sein; wenn ich sehe, dass es nicht noch genug, ich werde versuchen und implementieren von algorithmen als auch.
    InformationsquelleAutor Anon.
  2. 5

    Log und power sind teure Operationen. Wenn Sie wollen schnell, Sie wahrscheinlich wollen, um die IEEE binary exponent in der Tabelle, um die Ungefähre Leistung von zehn, und dann prüfen, ob die Mantisse Kräfte, die eine Veränderung von +1 oder nicht. Diese sollte 3 oder 4 integer Maschinen-Anweisungen (alternativ O(1) mit einem ziemlich kleinen-Konstante).

    Tabellen:

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

    dann Ihre Berechnung sollte sein:

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

    [Könnten Sie wirklich brauchen, dies zu schreiben, als assembler-squeeze-out jeden letzten Uhr.]
    [Dieser code nicht getestet.]

    Jedoch, wenn Sie darauf bestehen, tun Sie dies in python, der interpreter-overhead möglicherweise Sumpf die log/exp Zeit und es könnte keine Rolle spielen.

    So, wollen Sie schnell, oder wollen Sie kurz-zu-schreiben?

    BEARBEITEN 12/23: OP erzählt uns nun, dass sein "x" ist ein integraler Bestandteil. Unter der Annahme, dass es eine 64 (oder 32) bit-Ganzzahl, die meinen Vorschlag noch funktioniert, aber offensichtlich gibt es nicht ein "IEEE_Exponent". Die meisten Prozessoren haben ein "finde zuerst einen" Befehl, wird Ihnen sagen, die Anzahl der 0-bits auf der linken hand (wichtigsten) Teil des Wertes, z.B. führende Nullen; Sie dürften Dies ist im Grunde 64 (oder 32) minus die macht der zwei für den Wert. Angesichts exponent = 64 - leadingzeros, Sie haben die Kraft der zwei Exponenten und der rest des Algorithmus ist im wesentlichen unverändert (Änderungen Links für den Leser).

    Wenn der Prozessor nicht finden-ersten-Unterricht, dann ist wahrscheinlich die beste Wette ist, eine ausgewogene Diskriminierung Baum, um zu bestimmen, die Kraft von zehn. Für 64 bit, einen solchen Baum nehmen würde, höchstens 18 vergleicht, um zu bestimmen, der exponent (10^18 ~~ 2^64).

    • Nein, das werde ich nicht tun, dass in der python -das war eigentlich eine Sprache, unabhängig von Algorithmus - wollte nur zeigen, dass meine aktuelle Algorithmus in einem paar von Sprachen deutlicher machen, schlechte Idee, wahrscheinlich...
    • Protokoll und macht teure Operationen. Dies ist offensichtlich der Fall in Abwesenheit von hardware-Unterstützung für transzendente Operationen. Aber, wie langsam sind wir im Gespräch auf Verbraucher grade general purpose CPU (moderne x86 -, Power, x86_64...)?
    • Wenn Sie nicht möchten, zu verwenden, floating-point, eine ähnliche integer-Regelung arbeitet mit einem count-leading-zeros Montageanleitung.
    • Sogar mit integrierten floating-point -, die transcendentals einige Zeit dauern, ausführen. Der chip-Hersteller will nicht sagen, Sie präzise Uhr zählt nichts mehr, aber es ist schwer zu glauben, Sie implementieren eines high-precision-floating-point-long-in ein paar Uhren. Mein Schema, nur wenige integer-Anweisungen (auch das runterlaufen schwimmenden vergleichen kann, tatsächlich getan mit integer-Anweisungen, weil, wie IEEE definiert ist!) ist wahrscheinlich schwer zu schlagen. Ist dieser Wert? Wahrscheinlich nicht, es sei denn, die OP ist gerade von dieser wiederholt in einer inneren Schleife. Aber er hat nicht zu Fragen, ob die Mühe hat sich gelohnt :- }
    • Schöne Lösung! Ich werde das nicht implementieren das jetzt: es scheint ziemlich kompliziert, aber ich werde, im Fall optimieren müssen noch mehr die Lösung, die ich wählte.
    InformationsquelleAutor Ira Baxter
  3. 4

    Erstellen Sie ein array von Kräfte des 10. Durchsuchen Sie den größten Wert, der kleiner als x ist.

    Wenn x ist ziemlich klein, finden Sie möglicherweise, dass eine lineare Suche bietet bessere Leistung als eine binäre Suche, zum Teil aufgrund zu weniger Filiale mis-Vorhersagen.

    InformationsquelleAutor Dijkstra
  4. 3

    Der asymptotisch Schnellste Weg, soweit ich weiß, beinhaltet das wiederholte quadrieren.

    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

    Der Algorithmus nimmt logarithmischen Raum und Zeit in N, das ist linear in N ist der Darstellung Größe. [Die Zeit gebunden ist, ist wahrscheinlich ein bisschen schlechter, weil ich vereinfachte optimistisch]

    Beachten Sie, dass ich davon ausgegangen beliebig große ganze zahlen (aufpassen für überlauf!), da die naiv-mal-10-bis-über-Algorithmus ist wahrscheinlich schnell genug, beim Umgang mit 32-bit-Ganzzahlen.

    • +1 für den Algorithmus, aber was ist mit deinem Einzug?
    • Der Einzug vorgesehen. Es hält den Inhalt des iterator-block auf der rechten Seite der block-Trennzeichen.
    • Wie bei der vorherigen Lösung, es ist ein schöner! Ich werde das nicht implementieren das jetzt: es scheint ziemlich kompliziert, aber ich werde, im Fall optimieren müssen noch mehr die Lösung, die ich wählte.
    InformationsquelleAutor Craig Gidney
  5. 1

    Gegeben, dass diese Sprache unabhängig, wenn Sie können, Holen Sie sich die power von beiden, dass diese Zahl ist bedeutsam, z.B. y in x*2^y (das ist die Art, wie die Nummer gespeichert ist, aber ich bin mir nicht sicher, ich habe gesehen, eine einfache Möglichkeit zum Zugriff auf y in irgendeiner Sprache, die ich verwendet habe) dann, wenn 

    z = int(y/(ln(10)/ln(2)))

    (eine Fließkomma-division)

    10^z oder 10^(z+1) wird die Antwort sein, obwohl 10^z ist immer noch nicht so einfach (beg korrigiert werden).

    • Wenn Sie können, Holen Sie sich die Kraft von zwei, können Sie einfach nachschlagen z die in Tabelle (meine Antwort) auf Kosten eines memory access das ist viel billiger als ein float dividieren.
    InformationsquelleAutor aronp
  6. 1

    Ich denke der Schnellste Weg ist O(log(log(n))^2), wird die while-Schleife dauert O(log(log(n)) und es kann rekursive Aufruf endlicher Zeit (können wir sagen, dass O(c) wo sehen Sie konstant ist), dem ersten rekursiven Aufruf ist erfolgt log(log(sqrt(n))) Zeit Sekunde dauert .. und die Anzahl von sqrt in sqrt(sqrt(sqrt....(n)) < 10 ist log(log(n)) und Konstante, weil der Maschine Einschränkungen.

        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);
    }
    InformationsquelleAutor Saeed Amiri
  7. 1

    In Python:

    10**(len(str(int(x)))-1)

    InformationsquelleAutor HaPsantran
  8. 0

    Ich zeitlich die Methoden mit den folgenden Variationen in C++ für den Wert a ein size_t Typ (inlining wird die Leistung verbessert, ändert jedoch nicht die relative Reihenfolge).

    Versuchen 1: Vermehren, bis Sie die Nummer.

    size_t try1( size_t a )
{
  size_t scalar = 1ul;
  while( scalar * 10 < a ) scalar *= 10;
  return scalar;
}

    Versuch 2: Multiway-wenn (könnte auch programmiert werden, mit Hilfe einer lookup-Tabelle).

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

    Versuch 3: Modifiziert aus findPow10 von @Saaed Amiri, die verwendet Quadratur schneller finden sehr großen Mächte, als zu Versuchen 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;
}

    Versuchen 4: Lookup-Tabelle indiziert mit count leading zeros-Anweisung als pro @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 ist wie folgt (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

    Den lookup - /multiway-wenn beats alles, was in C++, erfordert aber wissen wir Ganzzahlen sind eine endliche Größe. try3 ist langsamer als try1 im test für kleinere Werte der loop-Ende-Wert für eine große Anzahl try3 beats try1. In python sind die Dinge schwierig, weil die ganzen zahlen sind nicht begrenzt, so würde ich kombinieren try2 mit try3 schnell zu verarbeiten zahlen bis zu einer bestimmten Grenze dann mit der möglicherweise sehr große zahlen.

    In python-denke ich-lookup mit Hilfe einer list comprehension ist wahrscheinlich schneller als ein Mehrwege-wenn.

    # where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]
    InformationsquelleAutor Justin Finnerty
Schreibe einen Kommentar