www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Div und anschließend Mul ohne Overflow und mit max. Präz.


Autor: Johannes Raschke (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich möchte mit einem MSP430 das Frequency Tuning Word eines DDS
berechnen. Die Formel dafür ist einfach:
FTW = (f*2^48)/Sysclk.

Das Problem: "long" Zahlen sind ja beim IAR nur 32 Bits breit. Die
Genauigkeit davon reicht mir; die letzten 2 Bytes des 48Bit - Wortes
werde ich also auf Null setzen.

Die Formel sieht dann so aus:

FTW = ((f*2^32)/Sysclk) << 16

(nehmen wir mal an, FTW ist 48Bit breit)
Trotztem ist die Berechnung schwierig:
f nutzt max. 28Bit, Sysclk 29Bit, das Ergebnis vor dem Shift also
31Bit. Blöderweise ist das Zwischenergebnis  f*2^32 arg groß und damit
nicht mehr verarbeitbar. Teile ich hingegen erst f/Sysclk, bleibt wegen
der Rundung nichts mehr übrig.
Ich bräuchte also eine Funktion, die mir gleichzeitig die Division und
die Multiplikation durchführt, und zwar abwechselnd schrittweise.
Bevor ich mir darüber jetzt den Kopf zerbreche, wollte ich mal fragen,
ob jemand von Euch das schonmal gemacht hat oder ein Konzept kennt...

Johannes

Autor: R2D2 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kennt IAR keinen long long Datentyp?
Bei'm GCC hab ich folgenden code im Einsatz:
        uint64_t data = fout;
        data  = data << 32;
        data /= DDS_MCLK;

Wenn nicht hab ich folgende Idee:
Überleg mal was du machst wenn du davon ausgehst, dass ein Mensch max.
2stellige Zahlen im Kopf dividieren kann. Du teilst die Aufgabe in eine
Reihe kleinerer Divisionen auf:
6789/4=?
zuerst versuchst du 6/4=1 Rest2
ok, 1 Ziffer muss ne 1 sein.
dann gehts weiter:
2*10+7=27
27/4=6 R3

3*10+8=38
38/4=9 R2

2*10+9=29
29/4= 7 R 3

Das Ergebnis is also 1697.
Wie du sieht wurd nirgends was mehr als 2 stelliges verwendet. Wie du
das jetzt auf das Dualsystem unter Benutzung der 32/32bit-Funktionen
anwendest, bleibt dir als kleine Übung überlassen.

Autor: Johannes Raschke (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi, R2D2.

Danke für Deine Antwort. Nach long long werde ich mal schauen, das wäre
natürlich die schnellste Möglichkeit.

Die Division, so wie Du sie beschreibst, ist nicht das Problem und mir
durchaus geläufig. Das Problem ist, dass bei der Division einer 28Bit
Zahl durch eine 29Bit Zahl nicht mehr viel übrigbleibt, wenn ich nicht
gerade Fließkommazaklen benutze. Rechne doch mal 123/246*492 mit
Integern - da kommt Null heraus, obwohl das Ergebnis in Wahrheit 246
ist!
Und wenn Du - in diesem Beispiel - nur 9 Bit zu Verfügung hast, reicht
das für alle Operanden und auch das Ergebnis, aber nicht für das
Zwischenergebnis 246*492.
Egal, wie man es dreht und wendet, so einfach ist es also nicht.
Deshalb suche ich einen Algorithmus, der eine solche Rechnung ausführen
kann, ohne die Wortbreite des Ergebnisses zu überschreiten. Es sei denn,
ich finde einen 64Bit Integer - Datentyp und dafür fertige
Multiplikations- und Divisionsroutinen...

Gruß

Johannes

Autor: R2D2 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich meine ja, das du mit dem um 32 bit geshifteten wert rechen sollst,
die einzelnen operanden bleiben aber weiterhin max. 32 bit breit,
obwohl dein wert 64 bit lang is. ich wollte dir damit erklären, wie du
eine 64bit division auf mehrere 32bit zurückführen kannst.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Warum teilst du nicht 2^32/Sysclk vor der Multiplikation mit f.
Ist natürlich nur einigermaßen genau wenn Sysclk viel kleiner 2^32.
Vor der Multiplikation sollte der Überlauf abgefangen werden.

Gruss
Markus

Autor: Johannes Raschke (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Markus

Sysclk ist max. 300E6, belegt also satte 29Bit. Deswegen würde nicht
mehr viel übrig bleiben...
Habe jetzt einfach mal unsigned long long int verwendet und werde es
die Tage mal ausprobieren, was herauskommt...


Viele Grüße

Johannes

Autor: Tom (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo
Solltest du mit long long kein Glück haben, lässt sich der Algorithmus
auch selbst implementieren. Unter
http://atmel.com/dyn/resources/prod_documents/DOC0936.PDF
ist eine 16 bit Division auf einem 8 bit Controller beschrieben. Das
lässt sich auch auf größere Zahlen übertragen.
Letztendlich ist es nichts anderes als der Divisionsalgorithmus aus der
Grundschule, aufs Binärsystem übertragen.
Computer können so einfach sein ;-)

Gruss
Tom

Autor: Peter Dannegger (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Ich hatte ein ähnliches Problem bei meinem Frequenzmesser, das
Zwischenergebnis konnte bis 56 Bit groß sein.

Ich habs dann einfach in Assembler geschrieben.


Es gibt für jeden MC Assemblerbeispiele für 16Bit-Rechnen, die man,
nachdem man das Prinzip verstanden hat, leicht auf beliebige Formate
aufbohren kann.
Oder einfach mal ins Assemblerlisting schauen, wenn man den Compiler
mit 16 oder 32 Bit Rechnungen füttert

Anbei meine 56Bit Routinen, sind allerdings für den AVR. Das Prinzip
sollte aber klar werden.


Peter

Autor: Johannes Raschke (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Cool, danke!

Johannes

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.