www.mikrocontroller.net

Forum: Compiler & IDEs 16-bit (und mehr) Variable schnell multiplizieren


Autor: hickhack0 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Servus mal wieder,

ich stecke gerade an einem kleinen Problem fest.
Wie vielleich schon aus anderen Fragen bekannt, versuche ich so etwas 
Ähnliches wie eine HDD-Clock zu bauen. Doch das Ganze bei Drehzahlen 
zwischen ~800 und bis 15.000U/min.
Also hab ich meinen ATMEGA8515 auf 10MHz getaktet und lasse den 
16bit-Counter mit 64er Prescaler die Umlaufdauer mittels Input Capture 
zählen. ( => counterüberlauf bei rund 150 U/min und 625 Zählschritte bei 
15.000U/min ) programmiert wird übrigends in C. Naja Anfänger C.
Aus dem Ergebnis will ich erstmal errechnen, wieviele Takte dann in 
einem Grad Drehung vergehen.
Also: Zähler * 64  / 360 = Zähler * 8 / 45 ( Zählerstand * prescaler / 
360°/Umdrehung = das gleiche nur gekürzt)

Und hier liegt mein Problem. Die Berechnung dauert (zumindest in der 
Simulation) einfach ehwig. Zu lange für meine Anwendung. Es müssen u.U. 
Aktionen schon ab 0.5ms nach erscheinen des neuen Zählerstandes mit den 
Werten des neunen Zählerstandes ausgeführt werden. In Winkelgrad auf der 
Scheibe ausgedrückt: ab 45° nach InputCapture müssen möglichst exakt 
[max. +-0,25°] und auch bei schnell wechselnder Drehzahl Aktionen 
ausgeführt werden.

So und nun genauer zu meinen Fragen:

Der Zählerstand ist eine 16-bit Variable. Multipliziere ich ihn mit 8 
sind dann wohl schon minimum 3 bit mehr nötig. Kann das mein ATMEGA ohne 
zu Runden?

Anschließend muss ich den neunen Wert durch 45 Dividieren. Gibts da 
irgend welche Kniffe um diese Berechnung zu beschleunigen?
Ich meine einen 19-bit Wert ( wird dann wohl als 24-bit behandelt? ) auf 
einem 8-Bit System zu dividieren dauert doch bestimmt (wie meine tests 
auch zeigten) etwas länger?!

Und als letztes wollte ich noch wissen, ob mir jemand sagen kann, ob das 
ganze bei kleinen Zählerständen schneller von statten geht.
Denn wenn die Zeit kanpp wird (bei hohen Drehzahlen), ist der 
Zählerstand auch sehr klein, z.B. 625 bei Maximaldrehzahl. Die 625 mit 8 
zu multiplizieren und das Ergebnis 5000 durch 45 zu teilen, lässt sich 
ja problemlos mit 16-bit Variablen verrechnen und sollte damit deutlich 
schnller gehen als die 24-bit Variable, richtig?
Macht der Compiler/uC das auch automatisch, oder denkt er dass 24-bit 
nötig sind und rechnet munter mit 24-bit variablen.


Kann mir ansonsten vielleicht noch jemand Hinweise oder Tips geben?
(aber bitte kein: "lass es, ist zu hoch für dich!", das weiß ich selber 
;-) )

Besten Dank schonmal

Autor: andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich habe mich jetzt nich soo genau in dein problem hineingedacht, aber 
was mir auf Anhieb dazu einfällt:
1. compiler von -Os auf -O3 umstellen, hat bei mir schon mal 20% bei 
einer isr gebracht.

2.
teilen ist gaanz schlecht.
Welche absolute genauigkeit brauchst du?
für x*8/45 kannst du auch schreiben
(x*45)>>8, das ist nur 1,1% daneben und warscheinlich genauer als du 
brauchst. (auf den Überlauf bei *45 aufpassen!)

Autor: OlliW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo hickhack0,

ich denke dein Problem ist nicht (nur) die Rechnerei sondern die 
+-0.25°. Du sagst bei 15000U/min hast du 625 Zählschritte/Umlauf => 
360°/625 = 0.576°, genauer kann es so nicht gehen => wenn du 0.25° haben 
musst, musst du die minimale Umdrehungsfrequenz bei der das noch geht 
nach oben setzen, deinen Zähler auf mehr als 16 bit aufbohren, oder 
oder...

Prescaler8?

x*8/45 und x*45/8 sind nicht das selbe

Division ist viel langsamer als Multiplikation

wegen der Division brauchst du nur bei google oder hier im Forum in der 
Suche Stichworte wie integer division constant etc eingeben, für die 
Division durch Konstanten gibt es ziemlich viel zu finden (und einiges 
davon ist auch nützlich :-))...

ich würde meinen du brauchst auch nicht die Anzahl der Takte pro Grad, 
sondern die Anzahl der Takte bis zum nächsten Event, und auch die Takte 
sollten dir nichts nützen, denn du hast ja den Timer mit Prescaler64, 
eigentlich können dir doch nur die Ticks des Timers etwas nützen...

das Einfachste ist es wenn man die Anzahl der Aktionen pro Umlauf als 
z.B. 256 oder 512 etc wählt, das nächst Einfache ist es ein Vielfaches 
einer solchen Zahl mit z.B. 3 oder 5 oder 7 oder 9 etc. zu nehmen (weil 
es dafür fertige effiziente Divisionsroutinen gibt), also z.B. 3*128 = 
384 oder 5*64=320 etc.

mir erschliessst sich der Sinn deiner Angabe von 0.5 ms nicht, bei 
15000U/min dauert ein Umlauf 4ms, 4ms/0.5ms = 8 => 8 Aktionen pro 
Umlauf?

Have fun,
  Olli

Autor: nee (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wieso 360 Grad 256 Grad ist meist besser.

Autor: hickhack0 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der tip mit dem -0s -03 ist schon mal was, da werd ich mich dran 
probieren.
Danke

> (x*45)>>8, das ist nur 1,1% daneben
ich komme auf 1,12% (also das gleiche), bei (x*46)>>8 sinds aber nur 
1,07% also genauer. wie auch immer du da drauf gekommen bist!
Danke, ein SEHR guter Ansatz für mich.

> auf den Überlauf bei *45 aufpassen!
Überlauf? also dass die 16-bit nicht ausreichen ( Ergebnisse > 65535 ) 
oder was ist der Überlauf?
Und was, wenn ich genau weiß, dass sie nicht ausreichen, was sie ja in 
den niederen Drehzahlen nicht werden?

@OlliW
Auch dir Danke
> +-0.25° [...] 360°/625 = 0.576°, genauer kann es so nicht gehen
Hab ich einen Gedankenfehler? oder liegts daran, dass ich 7 abgerundet 
habe?
wenn ich die 0,576° sauber runde komme ich auf 0,6° OK. => +-0,3° 
sollten ohne weitere Verluste drin sein? oder denke ich gerade falsch?
Abgesehen davon gleube ich ist in der ganzen rechnung der Wurm.
Wenn ich eine Strecke messe, 1/4 der Strecke bestimmen muss, und am ende 
der langen Messtrecke den cm abrunde, kann ich das viertel der strecke 
sogar auf +-1/8cm bestimmen!?
Beispiel: Messstrecke: 40,0-40,9999cm -> Gemessener Wert: 40cm
1/4 der Messtrecke ist also irgendwo zwischen 10,0cm und 10,24999cm
also grob 10,125cm +-0,125cm

> x*8/45 und x*45/8 sind nicht das selbe
richtige, aber x*8/45 = x*64/360 (64 = prescaler für x, 360° pro 
Umdrehung)

> mir erschliessst sich der Sinn deiner Angabe von 0.5 ms nicht
Jetz wo du's sagst und ich nochmal nachgerechnet hab... da muss sich ein 
fehler eingeschlichen haben. sorry

Autor: Uboot- Stocki (uboot-stocki)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Moin,

> lasse den 16bit-Counter mit 64er Prescaler die Umlaufdauer
> mittels Input Capture zählen. ( => counterüberlauf bei rund
> 150 U/min und 625 Zählschritte bei 15.000U/min )

ich verstehe nicht ganz warum Du überhaupt rechnen möchtest? Du könntest 
doch pro Umdrehung eine Konstante addieren. Wenn Du das geschickt 
machst, sparst Du Dir die rechnerei völlig.

Gruß

Andreas

Autor: Matthias Larisch (matze88)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eingehend auf Uboot-Stocki:

Warum programmiert man das ganze nicht als eine Art P-Regler?
Timer, der alle X Ticks das nächste Bild ausgibt. Y Bilder pro 
Umdrehung.
Nun weiß man, dass man einmal rum ist, hat aber erst Y-N Bilder 
geschafft. Also wird X verkleinert, auf
X * (Y-N)*X / (Y*X), gekürzt: X = X * (Y / Y - N / Y) = X * (1 - N / Y).

Falls diese "Regelschleife" die eigentlich keine ist da sie absolut 
stellt nicht gut funktioniert, könnte man auch nen D-Regler basteln, der 
einfach X um N verringert, wenn man zu schnell war, oder um N erhöht, 
wenn man zu langsam wahr. Muss man nur irgendwie abstimmen, dass das 
ganze dann nicht sichtbar schwingt (somit ein leicht wackelndes Bild 
entsteht).
[edit] absolut stellen tut se ja doch nicht, ist ja ein X=X*Z... oehm, 
ist das nicht sogar schon eine Art D-Regler?)[/edit]

Außerdem muss der Regler dann noch mit diversen Konstanten so 
eingestellt werden, dass er schnell genug reagiert (Kompromiss zwischen 
Schwingen und Reaktionszeit, eventuell dann auch auf PID Regler gehen, 
der ist stabiler.)

Matthias

Autor: OlliW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Der tip mit dem -0s -03 ist schon mal was, da werd ich mich dran
du musst vermeiden dass der Compiler seine eigenen Routinen unsinnig oft 
benutzt, bei mir klappt das nur wenn ich -O2 nehme, kann aber natürlich 
vom Program abhängen, keine Ahnung, wollte ich nur darauf hinweisen auch 
-O2 zu probieren

> x*8/45 und x*45/8 sind nicht das selbe
und du brauchst doch x*8/45 und nicht x*45/8, oder? was interessiert 
dann der  Fehler bei (x*46)>>8, nur das wollte ich sagen...

>ich verstehe nicht ganz warum Du überhaupt rechnen möchtest?
weil sich die Umdrehungszahl ändert, und man so jedesmal eine neue 
Konstante braucht. korrigier mich hickhack0 wenn ich das falsch verstehe

>Warum programmiert man das ganze nicht als eine Art P-Regler?
weil das nur geht wenn die Änderungen der Umdrehungsfrequenz sehr 
langsam vonstatten geht (die Umdrehungsfrequenz kann sich deutlich bei 
jeder Umdrehung ändern, , und weil eine Division durch eine Konstante 
wenn man es nicht gerade naiv den Compiler überlässt und die bekannten 
"Tricks" benutzt kein Problem sein sollte

integer division constant etc in google lieferte z.B.
http://www.hackersdelight.org/divcMore.pdf (der Klassiker, mit dem bin 
ich gut zurechtgekommen)
http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx
http://www.cs.uiowa.edu/~jones/bcd/divide.html (noch ein Klassiker, mit 
dem bin ich nicht so zurechtgekommen)
:
:
Hinweis: ich habe ähnliches auf einen ATTiny gemacht, der hat keinen 
HW-Multiplikator, der ATmega hat einen, den sollte man mitnutzen, kann 
sein das diese Seiten daher nicht 100% passen

vielleicht sagts du einfach mal wieviele Zeilen pro Umlauf du gerne 
hättest...

Ciao,
  Olli

Autor: hickhack0 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Uiuiui. Das Thema division ist mir ertmal zu hoch glaube ich. Da fehlen 
mir noch ein paar Basics (die ich hoffenltich bald in meinem E-Technik 
Studium ab Oktober kennen lerne).

> vielleicht sagts du einfach mal wieviele Zeilen pro Umlauf du gerne
> hättest.
Naja Zeilen pro Umlauf sinds ja gar nicht. Ich habe einen Zeiger auf der 
Scheibe, der möglichst präziese Drehzahl unabhängig ( und wie gescheiben 
auch bei starken schwankungen ) an einer erst mal festen (später 
drehzahlabhängigen) position bleibt.

Genaugenommen habe ich auch noch kein FESTES Konzept wie's laufen soll, 
ich versuche erstmal alles mögliche. Mein aktueller Plan war jetzt 
jedenfalls mit dem 16-bit Inputcapture (64er-Prescaler triffts sehr 
schön ohne Überlauf) die Umlaufdauer zu bestimmen und mit dem 8-bit 
Timer ohne Prescaler (bzw. mit dessen Compare-Match- und 
Overflow-Interrupt) die LED zu den Zeitpunkten x und y ein- und 
auszuschalten.
Wie genau ich die Berechnung zwischen InputCapture und Timer anstelle, 
versuche ich noch zu erforschen. Tips sind natürlich immer gern gelesen.

Nur als Hintergrundinforamtion: Das Ganze ist jetzt erst mal ein Model 
und wird später eine elektronische Zünd- und Einspritzanlage für einen 
1-Zylinder Rennmotor. Daher auch die Schnellen Drehzahlschwankungen. 
1.000 -> 10.000 U/min in einer halben sekunde sind schon fast langsam 
und andersrum beim schalten gibts keine ganz so krasse 
drehzahldifferenz, aber sehr schnell und danach muss wieder optimale 
leistung anstehen!
Ach ja, unsere Test haben ergeben, dass eine Abweichung von nur 1 Grad 
vom optimalen Zeitpunkt bis zu 0,7PS ausmachen! Daher muss ich recht 
genau am perfekten Zeitpunkt sein.

Autor: OlliW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Hickhack,

von dem Motorzeugs habe ich keine Ahnung, aber ich habe das bei meinem 
Fall (nur ca. 2500U/min max und 48 Zeilen pro Umlauf) nur mit dem 16 bit 
Timer gelöst. Das ICP nicht wie üblich benutzen sondern wie "früher" den 
Timer auf Null stellen (ich weis igitigit... :-), und dann den OCRA 
Interrupt nehmen... also bei ICP den Timer auf null, den Zeitabstand 
ausrechnen, OCRA darauf setzen, und dann bei jedem OCRA Interrupt diesen 
einfach um diese Konstante erhöhen. Suche auch mal bei Elektor, die 
haben im Dez 2008 oder Dez 2007 oder so (auf alle Fälle Dez) so ein 
rotierendes Ledkreisel Projekt gehabt, für das man sich den 
Artikel+Program+Alles kostenlos herunterladen kann. Ich fand die dortige 
Lösung nicht "gut" aber gibt Ideen. Ob dies alles dein Problem lösen 
kann weis ich natürlich nicht...

>Uiuiui. Das Thema division ist mir ertmal zu hoch glaube ich.
habe ich zu erst auch gedacht, aber wenn man sich ein bischen einliest 
macht es fasst Sinn... :-)

Olli

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

Du willst einen 16Bit unsigned Wert mit 8 multiplizieren und durch 45 
teilen!

Der Faktor 8/45 liegt bemerkenswert nahe an 91/512, also muss man mit 91 
multiplizieren und dann durch 512 teilen, was einem Rechtsshift des 
integer Wertes um 9 Positionen entspricht.

91 kann man darüberhinaus mit Zweierpotenzen so darstellen (128-32-4-1)

Die entsprechende Integerrechnung macht in Deinem Eingangszahlenbereich 
von 625-65535 einen maximalen Fehler von ca. 0.1% .

Math rulez!
Cheers
Detlef

  unsigned short z;
  signed int     s,v;

   z=625;

   v =  z;
   s = -v;
   v <<=2;
   s -= v;
   v <<=3;
   s -= v;
   v <<=2;
   s += v;
   s >>=9;
   printf("%f %d %d\n",1.0-(z*8.0/45.0)/s,s,z);

Autor: der mechatroniker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei einigen avr-gcc-Versionen (k.A. obs aktuell noch so ist) muss man
   s >>=9;
durch
   s >>=1;
   s >>=8;
ersetzen, wenns um Speed geht. (sonst Assembler-Code = gruselig ;-) )

Autor: OlliW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@detlef: soweit ich die oben angegebenen Referenzen verstehe ist das 
genau der Weg den die gehen, nur das zusätzlich noch der Fehler am Ende 
durch Ausrechnen des Restes korrigiert wird. In diesen Referenzen steht 
aber auch das wenn ein HW-Multiplizier vorhanden ist (was beim ATmega so 
ist) es noch effizienter ist diesen auch zu nutzen...

ich habe auch beobachtet das es effizienter sein kann gleich einfach 
z.B.
v =  (z<<7)-(z<<5)-(z<<2)-z;
hinzuschreiben, ich erkläre mir dass so das der Compiler sich dann 
"leichter" tut zu optimieren bzw. ihm das völlig überlässt, habe aber 
natürlich keine Ahnung, lohnt sich m.M. nach aber es zumindest mal 
auszuprobieren...

Olli

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>ch das wenn ein HW-Multiplizier vorhanden ist (was beim ATmega so ist) es >>noch 
effizienter ist diesen auch zu nutzen...

ja klar, wenn ein Hardware Multiplizierer da ist sollte man den auch 
nutzen.

>> v =  (z<<7)-(z<<5)-(z<<2)-z;
>>  s >>=1;
>>  s >>=8;
>>(sonst Assembler-Code = gruselig ;-)

Ja, die Megas haben keinen Barrelshifter, die müssen immer einzeln 
schieben. Ich glaube, dass sowas s >>=8; vom Compiler als Bytekopiererei 
erkannt und effizient implementiert wird. Ich habe meinen Code oben mit 
dem sequentiellen Schieben so geschrieben um den Compiler drauf 
hinzuweisen, dass er die Zwischenergebnisse der Einzelschiebeaktionen 
verwenden soll.

Man braucht ja eigentlich auch kein 4Byte-integer, 3Byte Integerwerte 
reichen. Wenn man das letzte an Schnelligkeit rausschlagen muß sollte 
ein kurzes inline-Assembler Codestück gute Dienste tun.

Wie dem auch sei, das ganze läßt sich sehr schnell machen, 1 oder 2 
Dutzend Assemblerbefehle sollten ausreichen.

Cheers
Detlef

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Compiler erkennt sogar /= 256 statt >= 8 als Bytekopiererei. 
Teufelszeug! Bei heutigen Compilern reicht es, wenn man einfach eine 
Multiplikation hinschreibt, wenn man auch eine Multiplikation meint und 
nicht einen Shift hinschreibt.
Das kann u.U. verwirrend sein. Einen Shift sollte man benutzen, wenn man 
wirklich binär shiften möchte.

Autor: OlliW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Bei heutigen Compilern reicht es, wenn man einfach eine
>Multiplikation hinschreibt, wenn man auch eine Multiplikation meint und
>nicht einen Shift hinschreibt.

ich habe das bei einem ATtiny für avr-gcc explizit getestet und aus z*91 
macht der (bei mir zumindest) nicht von selber (z<<7)-(z<<5)-(z<<2)-z 
oder ähnliches sondern ruft einen "seiner" (laaangsaaammeen) 
mult-Routinen auf...

Autor: der mechatroniker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Olli: Das Statement von Simon K. gilt für Multiplikationen mit 
Zweierpotenzen.

Autor: OlliW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
OK, dann habe ich das falsch verstanden :-) DANKE für den Hinweis!

Autor: hickhack0 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke jungs, ihr seid wirklich SEHR hilfreich, komme kaum nach alles 
auszuprobieren und zu verinnerlichen was ihr da scheibt. liegt aber auch 
daran, dass ich arg mit meinem Compiler kämpfe.
Dazu werde ich aber ein neues Thema eröffnen, dann google und co. 
liefern mir keine auch nur ähnlichen problemestellungen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.