Auf den Bezier-Kurven und Arduino Speed, Teil Zwei

Wir werden vorbeikommen - und weiter

In meinem vorherigen Beitrag habe ich gezeigt, wie Sie die Geschwindigkeit der Punkteberechnung auf einer Bezier-Kurve (KB) verbessern können, indem Sie:

1. Transformationen von Berechnungsformeln - Beschleunigung ~ 3 mal.
2. Es gibt fast keine Beschleunigung von PT nach FT - aber es erlaubt 3.
3. Die Ersetzungsoperation der Division durch Multiplikation und Verschiebung ist eine Beschleunigung von weiteren 40%.

Am Ende des erwähnten Beitrags sagte ich, dass Berechnungen noch schneller durchgeführt werden können, aber was "der Junge sagte - der Junge tat".

Ich möchte Sie noch einmal an die Formel erinnern, die zur Berechnung des Punkts auf der KB erhalten wurde

$$

$$P = (A1 * und + B1) * und + C (=> 2 * 2 +)$$

Die nächste Geschwindigkeitssteigerung hängt mit der Besonderheit des Problems zusammen - wir müssen nicht nur den Wert von KB bei verschiedenen Werten des Parameters „und“ berechnen, sondern eine Reihe von Werten finden, wenn wir diesen Parameter um einen bekannten, darüber hinaus festen Wert (in unserem Fall) ändern (in diesem Fall erhöhen) Falleinheit), mit der Sie die unten beschriebene Technik anwenden können. Zu meiner Zeit wurde es die Differenzberechnungsmethode genannt (wenn das Gedächtnis mir recht tut, zumindest wurde es in Vorlesungen so genannt), das gesamte Internet steht zu Ihrer Verfügung, vielleicht gibt es (sogar sicher) einen anderen Namen.

Wir betrachten den Fall P = A * und (=> 1 *) und nehmen an, dass wir den Wert von P0 mit einem Argument u0 kennen. Dann kann der Wert mit dem nächsten Argument u0 + 1 berechnet werden als P = A * (u0 + 1) = A * u0 + A = P0 + A (=> 1+). Ohne an Präzision zu verlieren, konnten wir die Multiplikationsoperation durch die Additionsoperation ersetzen, die viel schneller ist.

Als komplexeres Beispiel P = A * und * und (=> 2 *) betrachten wir analog P = A * (und + 1) * (und + 1) = A * (und * und + 2 * und + 1). = A * und * und + 2 * A * und + A = P0 + 2 * A * und + A (=> 2 * 2 +). Auf den ersten Blick haben wir nichts gewonnen, aber wenn wir A '= 2 * A im Voraus berechnen, erhalten wir (=> 1 * 2 +), ein Gewinn ist durchaus möglich. Aber wir werden nicht bei dem stehen bleiben, was mit dem erhaltenen Ausdruck A '* erreicht wurde, und die uns bereits bekannte Technik anwenden, dann werden wir zwei Operationen mit zwei Variablen erhalten: P = P + A' + A; A '= A' + A (=> 3+). Wenn wir berücksichtigen, dass der Anfangswert von A 'mehr durch A erreicht werden kann, gibt es im Allgemeinen nur zwei Additionen anstelle von zwei Multiplikationen. Ja, wir mussten zwei zusätzliche Variablen erhalten, aber dies ist ein klassischer Austausch - wir zahlen mit Speicher für die Zeit.

Es bleibt nur die Berechnung der korrekten Anfangswerte, dies wird jedoch nur einmal zu Beginn der Iterationen durchgeführt, und wenn der Anfangswert des Parameters u = 0 ist, ist es im Allgemeinen trivial P = 0, A '= A. Wir werden unsere Methode an mehreren Iterationen testen (dies ist völlig unnötig, korrekt angewandte Mathematik kann nicht die falsche Antwort geben), aber es wird uns ermöglichen, besser zu verstehen, was passiert. Also
Iteration 0: und = 0; P = 0 (wahr); A '= A; A '' = 2 * A;
Iteration 1: und = 1; P = 0 + A '= 0 + A = A (wahr); A '= A' + A '' = A + 2 * A = 3 * A;
Iteration 2: und = 2; P = A + 3 · A = 4 · A (wahr); A '= 3 · A + 2 · A = 5 · A;
Iteration 3: und = 3; P = 9 * A (wahr); A '= 7 * A und so weiter.

Wir stellen den Zusammenhang zwischen den erhaltenen Formeln und der Newton-Methode zur Berechnung des Wertes einer Funktion in der Nähe eines Punktes mit einem bekannten Wert fest. Da unsere Funktion von zweiter Ordnung ist und alle Ableitungen ab der dritten gleich Null sind, können wir das ungefähre Gleichheitszeichen sicher durch das exakte Vorzeichen ersetzen. Der einzige Unterschied zu dieser Methode besteht darin, dass wir den Punkt, zu dem wir eine neue Nachbarschaft aufbauen, ständig verschieben, um zu vermeiden, dass Multiplikationsoperationen in der ursprünglichen Formulierung durchgeführt werden.

Schreiben Sie unseren ursprünglichen Ausdruck für KB in erweiterter Form neu

$$

$$P = A1 * und * und + B1 * und + C$$

Für Berechnungen mit dieser Methode benötigen wir 2+ für den ersten Term (und zwei Variablen), 1+ für den zweiten Term (und eine Variable) und 2+, um alles zu addieren (=> 5+). Es ist zu erwarten, dass selbst dieser (falsche) Ansatz im Vergleich zu 2 * 2 + einen Gewinn bringt, aber alles ist viel besser. Offensichtlich ist die Additionsoperation additiv (danke, Kapitän), sodass Sie die Begriffe gruppieren und die konstanten Begriffe durch neue Ausdrücke ersetzen können, was den folgenden Algorithmus ergibt:

1. Die Anfangswerte von P = C; A '= A1 + B1; A '' = 2 * A1;
2. im nächsten Schritt P = P + A '; A '= A' + A '' (=> 2+), was zweifellos schneller ist als Horners Schema.

Wir implementieren unseren Algorithmus in Form eines Programms (dies ist nicht so trivial, wie es scheinen mag, da ich der Einfachheit halber die Notwendigkeit von Schichten vergessen habe, aber es ist nicht zu schwierig ... für 20 Minuten), erhalten wir die rechnerische Komplexität (=> 2 + 1 >>) und messen Geschwindigkeit - es stellte sich heraus, dass 140 Zyklen pro Zyklus um das Dreifache erhöht wurden, aber dies ist fast ein ideales Ergebnis. Was wir tun müssen, um die ideale Option (in gewissem Sinne) zu erhalten, ist, auf die Dimension der Operanden in den Formeln zu achten. Jetzt führen wir alle Operationen mit langen (32-Bit) Ganzzahlen aus, und dies kann an einigen Stellen unnötig sein. Wenn wir die Kapazität der Operanden auf das erforderliche Minimum reduzieren, können wir einen Gewinn von 20 bis 25 Prozent erzielen. Dies erfordert jedoch, dass wir zum Assembler wechseln (C verfügt nicht über die für solche Operationen geeigneten Mittel) und die Daten des ursprünglichen Problems sorgfältig analysieren. Ob es an dem Leser liegt, zu entscheiden, ob er dies tut, haben wir die Berechnungen im Vergleich zum „naiven“ Ansatz bereits mehr als 1900/140 = 13-mal beschleunigt.

Die letzte Bemerkung zur Implementierung des Algorithmus ist, dass wir die Divisionsoperation immer noch ausschließen, indem wir sie durch konstante Multiplikation ändern, was wir bei der Erzeugung der Anfangsdaten und der Verschiebung um ein konstantes Vielfaches von 8 berücksichtigen. Dies kann auf verschiedene Weise mit leicht unterschiedlichen Ausführungszeiten erfolgen, wobei solche Experimente einem neugierigen Leser überlassen bleiben .

Ein Problem trat jedoch völlig unerwartet auf - wir sehen deutlich zwei Additionsoperationen für 32-Bit-Zahlen, die 4 + 4 = 8 Taktzyklen dauern sollten, weitere 8 * 3 * 2 = 48 Taktzyklen zum Senden von Operanden, 4 Taktzyklen zum Empfangen des Verschiebungsergebnisses, 4 ein Taktzyklus zum Aufrufen des Berechnungsverfahrens und zum Zurückkehren sowie 4 Taktzyklen zum Organisieren des Zyklus - von wo aus weitere 60 Taktzyklen nicht klar sind. Früher haben wir dies vor dem Hintergrund von Hunderten von Taktzyklen einfach nicht bemerkt, aber jetzt können Sie darauf achten. Übermäßige Maßnahmen waren leicht zu finden - im Zyklus gab es unnötige Debugging-Vorgänge. Wenn Sie alles sorgfältig bereinigen, bleiben nur 120 Maßnahmen übrig und der Zweck jeder ist verständlich (nicht, damit es vollständig verständlich wäre, aber immer noch). Als nächstes finden wir die Ausführungszeit des leeren Zyklus heraus - 22 Takte. Ich frage mich, was sie die ganze Zeit dort tun, aber na ja, und löschen die tatsächliche Berechnungszeit, die 98 Zyklen betragen wird. Beachten Sie, dass sich die Schätzung der erhaltenen Arbeitsbeschleunigung ändert: Anstelle von 1900/140 = 13 erhalten wir (1900-50) / (140-40) = 19-mal, was praktisch keinen Sinn ergibt, da der Zyklus noch erforderlich ist, Sie ihn jedoch noch weiter erhöhen können Selbstwertgefühl.

Und die letzte Bemerkung - wie leicht zu sehen ist, haben wir erst begonnen, Flöhe zu suchen und zu beseitigen, als wir uns mit großen Hirschkäfern befassten und ihre (Flöhe-) Existenz offensichtlich und darüber hinaus bedeutsam wurde. Ich empfehle genau diesen Ansatz (und ich bin mit dieser Empfehlung nicht allein), wenn ich Programme hinsichtlich der Leistung optimiere.

Nun, abschließend zum Hinweis „in gewissem Sinne“: Wenn wir beim Ändern des Parameters (der die Zeit darstellt) über die sequentielle Berechnung der Koordinaten des nächsten Punkts im Konstruktionsbüro sprechen, kann der vorgeschlagene Algorithmus (nach allen Optimierungen) nicht mehr verbessert werden. Wenn Sie jedoch die Aufgabe neu formulieren und beispielsweise das Ziel festlegen, einfach ein Designbüro auf dem Bildschirm aufzubauen (ohne Bezug zur Zeit), gibt es eine vielversprechende Methode, das Schlüsselwort "Brezenheim", aber "dies ist eine völlig andere Geschichte", die ich in einem separaten Beitrag behandeln werde (Vielleicht eines Tages, wenn es der älteren Schwester nichts ausmacht).