Div und anschließend Mul ohne Overflow und mit max. Präz.

[Johannes Raschke (Gast)]

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

[R2D2 (Gast)]

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.

[Johannes Raschke (Gast)]

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

[R2D2 (Gast)]

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.

[Markus (Gast)]

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

[Johannes Raschke (Gast)]

@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

[Tom (Gast)]

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

[Peter Dannegger (Gast)]

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

[Johannes Raschke (Gast)]

Cool, danke!

Johannes