Effiziente Inverse (1 / x) für AVR

12

Ich versuche einen effizienten Weg zu finden, eine Inverse auf einem AVR zu berechnen (oder zu approximieren).

Ich versuche, die Impulsdauer für einen Schrittmotor so zu berechnen, dass ich die Geschwindigkeit linear variieren kann. Die Periode ist proportional zur Umkehrung der Geschwindigkeit (p = K/v ), aber ich kann mir keine gute Möglichkeit vorstellen, dies on the fly zu berechnen.

Meine Formel lautet

p = 202/v + 298; // p in us; v varies from 1->100

Beim Testen auf dem Arduino scheint die Division ignoriert zu werden, wenn sie pfest bei 298belassen wird (obwohl dies in avr-gcc möglicherweise anders wäre). Ich habe auch versucht, vin einer Schleife zu summieren , bis sie übersteigt 202, und die Schleifen zu zählen, aber das ist ziemlich langsam.

Ich konnte eine Nachschlagetabelle generieren und in Flash speichern, aber ich fragte mich, ob es einen anderen Weg gab.

Edit : Vielleicht sollte der Titel "effizient teilen" sein ...

Aktualisieren : Wie Pingswept hervorhebt, ist meine Formel für die Zuordnung der Periode zur Geschwindigkeit falsch. Das Hauptproblem ist jedoch die Divisionsoperation.

Bearbeiten 2 : Bei weiteren Untersuchungen arbeitet Divide am Arduino. Das Problem lag sowohl an der falschen obigen Formel als auch an einem int-Überlauf an einer anderen Stelle.

Peter Gibson
quelle
2
Ist v eine Ganzzahl oder ein Gleitkomma?
mjh2007,
Eine ganze Zahl, aber da es in uns eine Periode gibt, ist die ganzzahlige Division hier genau genug.
Peter Gibson
Sie können die Werte der 100 Ganzzahlen vorberechnen und eine Nachschlagetabelle mit Vorskalierern für die Multiplikation erstellen, wenn Sie sich wirklich mit der Geschwindigkeit befassen. Natürlich gibt es einen Gedächtnistausch.
RYS

Antworten:

7

Eine schöne Sache an der Spaltung ist, dass mehr oder weniger jeder das tut. Es ist ein hübsches Kernmerkmal der C-Sprache, und Compiler wie AVR-GCC (von der Arduino IDE aufgerufen) wählen den besten verfügbaren Divisionsalgorithmus, selbst wenn der Mikrocontroller keine Hardware-Divisionsanweisung hat.

Mit anderen Worten, Sie müssen sich keine Gedanken darüber machen, wie die Aufteilung implementiert wird, es sei denn, Sie haben einen sehr seltsamen Sonderfall.


Wenn Sie sich keine Sorgen machen, lesen Sie möglicherweise gerne die von Atmel empfohlenen Divisionsalgorithmen (einer optimiert für die Codegröße und einer optimiert für die Ausführungsgeschwindigkeit; es wird kein Datenspeicher benötigt). Sie sind drin:

http://www.atmel.com/dyn/resources/prod_documents/doc0936.pdf

Dies ist der Application Note "AVR200: Multiplizieren und Dividieren", der auf der Atmel-Seite für seine (relativ großen) Atmega-Prozessoren wie den Atmega 168 und Atmega 328 aufgeführt ist, die in den Standard-Arduinos verwendet werden. Die Liste der Datenblätter und Anwendungshinweise finden Sie unter:

http://www.atmel.com/dyn/products/product_card.asp?part_id=4720

Jack Schmidt
quelle
4

Sieht für mich so aus, als ob Sie nur eine Nachschlagetabelle mit 100 Einträgen benötigen. Schneller geht es nicht.

#define VALUE_FOR_V_EQUALS_ZERO 0
uint16_t formula_lookup[100] = {VALUE_FOR_V_EQUALS_ZERO, 500, 399, 365, 348, ..., 300};

...

//"calculate" formula
p = formula_lookup[v > 67 ? 67 : v];

BEARBEITEN Sie tatsächlich nur eine 68-Wert-Nachschlagetabelle, da Werte von v größer als 67 immer zu 300 ausgewertet werden.

vicatcu
quelle
Wie ich in der Frage sagte, habe ich mich gefragt, ob es einen anderen Weg gibt
Peter Gibson
3

Es gibt einige sehr gute Techniken, die im Buch "Hackers Delight" von Henry Warren und auf seiner Website hackersdelight.org erwähnt werden . Eine Technik, die mit kleineren Mikrocontrollern beim Teilen durch Konstanten gut funktioniert, finden Sie in dieser Datei .

timrorr
quelle
Diese sehen zum Teilen durch Konstanten gut aus, wie Sie sagen, gelten aber nicht wirklich für mein Problem. Er verwendet Techniken wie Vorberechnung der Umkehrung - Multiplikation mit ihr, dann Verschiebung.
Peter Gibson
Das ist ein exzellentes Buch!
Windell Oskay
3

Ihre Funktion scheint nicht das gewünschte Ergebnis zu liefern. Beispielsweise gibt der Wert 50 ungefähr 302 zurück, während 100 ungefähr 300 zurückgibt. Diese beiden Ergebnisse bewirken fast keine Änderung der Motordrehzahl.

Wenn ich Sie richtig verstehe, suchen Sie nach einer schnellen Möglichkeit, die Zahlen 1-100 (ungefähr) auf den Bereich 300-500 abzubilden, sodass 1 auf 500 und 100 auf 300 abbildet.

Vielleicht versuchen Sie: p = 500 - (2 * v)

Aber ich könnte falsch verstehen - versuchen Sie, die Einschaltdauer einer Rechteckwelle mit konstanter Frequenz zu berechnen? Was ist der 298?

pingswept
quelle
Ja danke, die Formel ist falsch. Der Punkt ist, eine lineare Beschleunigung vom Ausgang des Steppers zu erhalten, indem die Zielgeschwindigkeit in jedem Zeitintervall um eine Konstante variiert wird (Geschwindigkeit ++ sagen wir). Dies muss auf die Periode (Frequenz) abgebildet werden, in der eine + ve Flanke an die Schrittmotorsteuerung gesendet wird - daher die umgekehrte Beziehung (p = 1 / v).
Peter Gibson
Meinen Sie eine konstante Beschleunigung, dh eine linear ansteigende Geschwindigkeit?
Pingswept
Ah ja, ständige Beschleunigung, ich habe das verdorben, als ich die Frage ursprünglich geschrieben habe, und erinnere mich, dass ich sie auch dort behoben habe
Peter Gibson,
3

Eine effiziente Methode zur Annäherung an Teilungen sind Verschiebungen. zB wenn x = y / 103; Das Teilen durch 103 ist dasselbe wie das Multiplizieren mit 0,0097087. Um dies zu approximieren, wählen Sie zunächst eine „gute“ Verschiebungszahl (dh eine Basis-2-Zahl, 2,4,8,16,32 usw.).

Für dieses Beispiel ist 1024 eine gute Anpassung, da wir sagen können, dass 10/1024 = 0,009765. Dann ist es möglich, Folgendes zu codieren:

x = (y * 10) >> 10;

Denken Sie natürlich daran, dass die Variable y beim Multiplizieren nicht über ihren Typ hinausläuft. Es ist nicht genau, aber es ist schnell.


quelle
Dies ähnelt den Techniken in den von timrorr bereitgestellten Links und eignet sich gut zum Teilen durch Konstanten, jedoch nicht zum Teilen durch einen Wert, der zum Zeitpunkt der Kompilierung unbekannt ist.
Peter Gibson
3

Wenn Sie versuchen, eine Aufteilung auf eine CPU vorzunehmen, die die Aufteilung nicht unterstützt, finden Sie in diesem Wiki-Artikel eine wirklich coole Möglichkeit.

http://en.wikipedia.org/wiki/Multiplicative_inverse

Um den Kehrwert von x nur durch Multiplikation und Subtraktion zu approximieren, kann man eine Zahl y erraten und y dann wiederholt durch 2y - xy2 ersetzen. Sobald die Änderung in y ausreichend klein wird (und bleibt), ist y eine Annäherung an den Kehrwert von x.

mjh2007
quelle
Interessant, ich frage mich, wie dies im Vergleich zu den anderen genannten Methoden
Peter Gibson
1

Dieser Prozess hier sieht mcu-freundlich aus, obwohl er möglicherweise etwas portiert werden muss.

Obwohl es so aussieht, als ob die LUT einfacher wäre. Sie würden nur 100 Bytes benötigen, weniger, wenn Sie eine Interpolation verwenden, und da die LUT mit Konstanten gefüllt ist, könnte der Compiler sie sogar im Codebereich anstelle des Datenbereichs lokalisieren.

ajs410
quelle
Ich habe etwas Ähnliches versucht, indem ich den Divisor summiert habe, bis er der Dividende entspricht oder diese übersteigt, aber ich habe festgestellt, dass er ziemlich langsam ist. Anscheinend ist die LUT der richtige Weg - mit avr-gcc benötigen Sie spezielle Makros in <avr / progmem.h>, um sie in Flash zu speichern.
Peter Gibson
1

Stellen Sie sicher, dass die Division als Gleitkomma ausgeführt wird. Ich verwende Microchip nicht AVR, aber wenn Sie C18 verwenden, müssen Sie Ihre Literale zwingen, als Gleitkomma behandelt zu werden. Z.B. Ändern Sie Ihre Formel in:

p = 202.0/v + 298.0;

mjh2007
quelle
1

Du willst schnell, also los geht's ... Da der AVR die Normalisierung nicht effizient ausführen kann (nach links verschieben, bis du nicht mehr verschieben kannst), ignoriere alle Pseudo-Gleitkomma-Algorithmen. Der einfachste Weg für eine sehr genaue und schnellste Ganzzahldivision in einem AVR ist über eine wechselseitige Nachschlagetabelle. In der Tabelle werden Reziprozitäten gespeichert, die mit einer großen Zahl skaliert sind (z. B. 2 ^ 32). Sie implementieren dann eine vorzeichenlose 32 x vorzeichenlose 32 = vorzeichenlose 64-Multiplikation im Assembler, also answer = (Zähler * inverseQ32 [Nenner]) >> 32.
Ich implementierte die Multiplikationsfunktion mit dem Inline-Assembler (umhüllt mit einer AC-Funktion). GCC unterstützt 64-Bit "Long Longs". Um das Ergebnis zu erzielen, müssen Sie jedoch 64-Bit mit 64-Bit multiplizieren, nicht 32x32 = 64, da die 8-Bit-Architektur in C eingeschränkt ist.

Nachteil dieser Methode ist, dass Sie 4K x 4 = 16K Flash verwenden, wenn Sie durch ganze Zahlen von 1 bis 4096 teilen möchten.

Eine sehr genaue Division ohne Vorzeichen wird jetzt in etwa 300 Zyklen in C erreicht.

Sie können die Verwendung von skalierten 24-Bit- oder 16-Bit-Ganzzahlen in Betracht ziehen, um eine höhere Geschwindigkeit und eine geringere Genauigkeit zu erzielen.

Nick
quelle
1
p = 202/v + 298; // p in us; v varies from 1->100

Der Rückgabewert Ihrer Gleichung lautet bereits, p=298da der Compiler zuerst dividiert und dann addiert. Verwenden Sie die ganzzahlige Auflösung mit dem folgenden Wert:

p = ((202*100)/v + (298*100))/100 

Dies zu verwenden ist dasselbe Multiplizieren a*fmit a = Ganzzahl f = Bruch.

Das ergibt r=a*faber f=b/cdann r=a*b/cdoch noch nicht, da die Position der Operatoren die End- r=(a*b)/coder Multiv-Funktion ergibt, eine Art, Bruchzahlen nur unter Verwendung von Ganzzahlen zu berechnen.

Nepermath
quelle