Ich habe eine herausfordernde Frage aus einer mathematischen, algorithmischen und metaprogrammierenden Rekursionssicht. Betrachten Sie die folgende Erklärung:
%Vor% basierend auf dem Beispiel der std::ratio Operationen wie std::ratio_add . Gegeben, zwei std::ratio R1 und R2 Diese Operation sollte R1^R2 genau dann berechnen, wenn R1^R2 eine rationale Zahl ist. Wenn es irrational ist, dann sollte die Implementierung fehlschlagen, wie wenn man versucht, zwei sehr große Ratios zu multiplizieren und der Compiler sagt, dass es einen ganzzahligen Überlauf gibt.
Drei Fragen:
Sie benötigen zwei Bausteine für diese Berechnung:
Hinweis: Ich benutze int als Typ für Zähler und Nenner, um etwas Tipparbeit zu sparen, ich hoffe, der Hauptpunkt kommt rüber. Ich extrahiere den folgenden Code aus einer funktionierenden Implementierung, aber ich kann nicht garantieren, dass ich keinen Tippfehler irgendwo machen werde;)
Der erste ist ziemlich einfach: Sie verwenden x ^ (2n) = x ^ n * x ^ n oder x ^ (2n + 1) = x ^ n * x ^ n * x Auf diese Weise instanziieren Sie die wenigsten Vorlagen, z. x ^ 39 berechnet man so etwas: x39 = x19 * x19 * x x19 = x9 * x9 * x x9 = x4 * x4 * x x4 = x2 * x2 x2 = x1 * x1 x1 = x0 * x x0 = 1
%Vor%Der zweite ist etwas knifflig und funktioniert mit einem Belichtungsalgorithmus: Mit x und N wollen wir eine Zahl r finden, so dass r ^ N = x
Dieser Algorithmus gibt die größte ganze Zahl s an, die s ^ N & lt; = x
folgtÜberprüfen Sie, ob s ^ N == x. Wenn ja, ist die N-te Wurzel von x ganzzahlig, sonst nicht.
Jetzt schreiben wir das als Kompilierprogramm:
grundlegende Schnittstelle:
%Vor%Helfer:
%Vor%Endpunkt der Rekursion, wobei das Intervall nur aus einem Eintrag besteht:
%Vor%helper um Multiplikation zu erkennen Überlauf (Sie können den Boost-Header für c ++ 11 constexpr-numeric_limits austauschen, denke ich). Gibt true zurück, wenn die Multiplikation a * b überläuft.
%Vor%Jetzt müssen wir calculate_left implementieren, das berechnet, ob die Lösung von x ^ N vom Mittelwert oder vom Mittelwert übrigbleibt. Wir wollen in der Lage sein, beliebige Wurzeln zu berechnen, also eine naive Implementierung wie static_pow & gt; x wird sehr schnell überlaufen und falsche Ergebnisse liefern. Daher verwenden wir folgendes Schema: Wir wollen berechnen, ob x ^ N & gt; B
lässt dies jetzt als Metaprogramm schreiben
%Vor%Endpunkt wo i == N
%Vor%Endpunkte für den Kurzschluss
%Vor%Helfer, um den nächsten Wert von x * A zu berechnen, takex Überlauf in Rechnung zu Compiler-Warnungen zu beseitigen:
%Vor%Also, das sollte es sein. Wir brauchen einen zusätzlichen Helfer
%Vor%Nun können wir ratio_pow wie folgt implementieren:
%Vor%Ich hoffe also, zumindest die Grundidee kommt rüber.
Ja, das ist möglich.
Definieren wir R1 = P1 / Q1, R2 = P2 / Q2 und R1 ^ R2 = R3 = P3 / Q3. Nehmen Sie weiterhin an, dass P und Q Co-Primzahlen sind.
%Vor% R1^P2 ist bekannt und hat eine eindeutige Faktorisierung in Primzahlen 2^a * 3^b * 5^c * ... Beachten Sie, dass a, b, c negativ sein kann, da R1 P1/Q1 ist. Nun ist die erste Frage, ob alle a,b,c Vielfache des bekannten Faktors Q2 sind. Wenn nicht, scheitern Sie direkt. Wenn ja, dann R3 = 2^(a/Q2) * 3^(b/Q2) * 5^(c/Q2) ... .
Alle Divisionen sind entweder genau oder das Ergebnis existiert nicht, so dass wir in unseren Templates reine Ganzzahlmathematik verwenden können. Das Factoring einer Zahl ist in Templates ziemlich einfach (partielle Spezialisierung auf x%y==0 ).
Beispiel: 2 ^ (1/2) = R3 - & gt; a = 1, b = 0, c = 0, ... und a%2 != 0 - & gt; unmöglich. (1/9) ^ (1/2) - & gt; a = 0, b = -2, b% 2 = 0, möglich, Ergebnis = 3 ^ (- 2/2).
Tags und Links algorithm math c++ c++11 metaprogramming