Effiziente Verfahren zur Berechnung von p^q (Potenzierung), wobei q eine ganze Zahl

Was ist ein effizienter Weg, um zu berechnen, pq, wobei q eine ganze Zahl?

InformationsquelleAutor q0987 | 2011-04-11
  1. 43

    Potenzierung durch Quadratur verwendet nur O(lg q) Multiplikationen.

    template <typename T>
T expt(T p, unsigned q)
{
    T r(1);

    while (q != 0) {
        if (q % 2 == 1) {    //q is odd
            r *= p;
            q--;
        }
        p *= p;
        q /= 2;
    }

    return r;
}

    Diese Arbeit sollte auf jeden monoid ( T , operator*), wo ein T konstruiert aus 1 ist die identity-element. Enthält alle numerischen Typen.

    Ausweitung auf signed q ist einfach: dividieren halt das eine durch das Ergebnis der oben für den absoluten Wert der q (aber wie immer vorsichtig sein, bei der Berechnung des absoluten Wertes).

    • I-1d dies, weil es ist nicht eine vollständige Antwort; Potenzierung durch Quadratur ist ein guter Algorithmus, aber es gibt auch andere Bedenken.
    • der OP bat um einen Vorschlag, nicht um eine komplette Lösung oder um einen Beweis der Richtigkeit.
    • In der Regel ich davon aus, dass jemand eine Frage stellen will, eine komplette Lösung. Selten werden Fragen erwartet, die Hälfte-Antworten.
    • Ich einen link gepostet, auf der Wikipedia-Seite, das deckt das meiste, was Sie wissen müssen, um die Implementierung dieses Algorithmus. Ich werde nicht zu erklären, Einzelheiten der Implementierung, wie die Rekursion versus iteration jedes mal; ich nehme an, die sind bekannt genug. Wenn der OP hat ein problem mit dieser Antwort, Sie können einen Kommentar schreiben zu Fragen, für weitere Klärung.
    • Wenn man die Erörterung von Fragen der Effizienz, ich sehe nicht, Rekursion versus iteration als eine Implementierung detail, sondern eine Kern-Frage angegangen werden, wie die Wahl Auswirkungen Effizienz.
    • wenn die OP hatte die naive pseudo-lineare Zeit-loop-Algorithmus im Kopf, dann ist dies genug von einer Verbesserung um Rekursion-vs.-iteration ein detail.
    • Und wenn die OP nicht, dann ist es auch nicht. Deshalb ist es wichtig, eine vollständige Antwort.
    • Tun downvotes wirklich weh, dass viel? 98 rep aus einem drei-Wort-link zu Wikipedia wirklich so wenig müssen Sie aber traurig sein, oder wütend auf jemand anderes Namen?
    • Ich vorstellen, es ist das Prinzip der Sache. Dennoch, ich Stimme mit Ihnen überein. 🙂
    • Ok, erweiterte diese Antwort mit code und Erklärung.
    • Wreschnig: Die üblichen standard für die Stimmen (wie offenbart durch das schweben auf der voting-Pfeile) "ist diese Antwort hilfreich", nicht "ist diese Antwort so vollständig, wie es möglich ist". Siehe auch meta.stackexchange.com/questions/2451/...
    • Ich bin nicht gewohnt Wähler. Ich glaube auch nicht "Rache upvoting" ein gutes Muster.
    • Wreschnig: ich bin damit einverstanden, dass kompensatorische upvoting sollte vermieden werden, und ich Tue es nicht. Ein upvote gibt viel mehr karma als ist weggenommen, von einem downvote. Doch viele Menschen tun dies, so drängt sich eine korrekte, aber unvollständige Antwort unter null werden in der Regel provozieren einen upvote zu null. Damit sollte auch vermieden werden...
    • Dieser liegt aktuell bei +17 - die meisten sammelte, wenn es war ein 3-Wort-link zu Wikipedia - und angenommen. Das ist schrecklich. Statt ALSO wirklich mir erlaubt, um zu bewerten Antworten, ich habe zu Stimmen, wie ich mich fühle, wird die Förderung ist die beste Antwort. Dies ist nicht die beste Antwort, also muss ich downvote es.
    • Zu pedantisch genaue, Potenzierung durch Quadratur ist nicht O(lg q), da ignoriert die Komplexität der Multiplikationen. Wenn Sie beschränken Sie sich auf die Maschine-Wort-Multiplikationen, dann werden Sie auch einschränken, der exponent ist, zu einem festen Bereich des Exponenten, in diesem Fall die Komplexität ist nur O(1).

    InformationsquelleAutor Fred Foo
  2. 12

    Unter der Annahme, dass ^ bedeutet Potenzierung und dass q ist Laufzeit-Variablen, verwenden Sie std::pow(double, int).

    EDIT: der Vollständigkeit halber wegen der Kommentare auf diese Antwort: habe ich die Frage gestellt Warum wurde std::pow(double, int) entfernt von C++11? über die fehlende Funktion und in der Tat pow(double, int) war nicht entfernt in C++0x, nur die Sprache geändert wurde. Es scheint jedoch, dass die Bibliotheken nicht wirklich optimieren es aufgrund Ergebnis Genauigkeit betrifft.

    Selbst gegeben, ich würde noch Verwendung pow bis die Messung hat mir gezeigt, dass es nötig optimiert werden.

    • Und angenommen, p kann genötigt zu verdoppeln.
    • Was ist das problem mit dieser Lösung? Die standard-Bibliothek ist wahrscheinlich, um eine hoch optimierte pow Funktion, wenn Laufzeit-Variabilität erforderlich ist.
    • Ich bekam einen downvote zu, wie @phimuemue.
    • Tatsächlich habe ich gerade überprüft, meine C++0x draft, und std::pow(double,int) ist nicht definiert. std::pow(double,double) und std::pow(float,float), und einige komplexere überladungen sind. Ich denke, das bedeutet, 1) eine Bibliothek mit std::pow(double,int) ist nicht-standard, und 2) wenn Sie spezielle case-integer-Wert verdoppelt die Laufzeit, das wäre beachtlichen Aufwand. Also ich war zwar nicht die downvoter, ich werde auch -1 diese.
    • Wreschnig entdeckte ich es in C++98 26.5/6 und nahm an, Sie würde nicht entfernen " - Funktionalität in 0x. Haben Sie entfernen es in C++0x (die ich nicht haben eine handliche Kopie der standard)?
    • B: kann ich nicht finden, eine C++98-PDF bei Google schnell, aber in meinem C++0x PDF, die einzige Erwähnung von pow auf primitiven Typen ist über C99 transklusion in 26,8, und es definiert nur pow für float,float, double,double und long double,long double.
    • (Natürlich in der Praxis würde ich nicht zweimal überlegen, über die Verwendung von std::pow, wenn verfügbar, aber wenn das Ziel ist, eine schnelle power-Funktion ohne Einschränkungen auf die Art der p - statt mit dem Ziel einige andere Berechnung erfordert eine power-Funktion, aber wahrscheinlich enthält einige niedrigere hängende Frucht - ich glaube nicht, dass es eine akzeptable Antwort. Auf der anderen Seite, ich denke, Stepanov das Training zu beschreiben, ist es von unschätzbarem Wert, obwohl ich std::pow.)
    • Schwer zu haben, eine Kopie von etwas, das gar nicht existiert. 🙂
    • Ihre Lösung richtig ist angesichts der Annahme, dass die std-Bibliothek immer implementiert die pow in der effizienteste Weg. Aber hier, ich bin mehr daran interessiert, wie man in dieser Umsetzung eher als, wie es zu benutzen. -- danke

    InformationsquelleAutor Mark B
  3. 9

    Ich nehme an ^ du meinst, power-Funktion, und nicht bitweise xor.

    Ist die Entwicklung eines effizienten power-Funktion für jede Art von p und jede positive integral q ist das Thema einen ganzen Abschnitt, 3.2, Stepanov und McJones Buch - Elemente der Programmierung. Die Sprache im Buch ist nicht C++, aber ist sehr leicht übersetzt in C++.

    Es umfasst mehrere Verbesserungen, einschließlich der Potenzierung durch Quadratur, die Umstellung auf tail recursion dann iteration, und Akkumulation-Variablen-Eliminierung, und bezieht sich die Optimierungen, die zu den Begriffen Art und Regelmäßigkeit und assoziative Operationen zu beweisen, es funktioniert für alle solche Typen.

    InformationsquelleAutor
Schreibe einen Kommentar