www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Frage zur C Syntax


Autor: Ruuud (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich programmiere unter CrossStudio einen 32 bit µC (AT91SAM7)

Nun will ich folgendes Berechnen:

//frequency tuning word = frequency * 2^32 / Clock DDS

U_INT32 ftw = frequency * 4294967296 / 400000000;


der Compiler bringt mir aber folgende Warnmeldung:

-> integer constant is too large for 'long' type


die Wanmeldung kann ich umgehen wenn ich es wie folgt berechne:

//frequency tuning word = frequency * 2^16 * 2*16 / Clock DDS


stimmt meine Rechnung oder bekomme ich da einen falschen Wert wegen 
Überlauf raus? Kann der µC (AT91SAM7) auch mit 64 bit Werten umgehen?

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Ruuud (Gast)

>die Wanmeldung kann ich umgehen wenn ich es wie folgt berechne:

>//frequency tuning word = frequency * 2^16 * 2*16 / Clock DDS


>stimmt meine Rechnung oder bekomme ich da einen falschen Wert wegen
>Überlauf raus?

Ich denke es passiert ein Überlauf

> Kann der µC (AT91SAM7) auch mit 64 bit Werten umgehen?

Probiers doch einfach AUS! Dauert 10 Sekunden! Definiere deine VAriablen 
als long long oder uint64_t

MFG
Falk

P.S. Es reicht aber auch eine 32 Bit Rechung. Siehe 
Festkommaarithmetik.

Autor: Tom (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du wirst mit Sicherheit einen falschen Wert bekommen, denn der Compiler 
wird zuerst durch dein ClockDDS dividieren und dann erst multiplizieren. 
Du solltest unbeding die Reihenfolge der Rechnenschritte erzwingen, in 
dem Du Klammern setzt.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Am einfachsten und genausten geht die Sache mit floats/doubles. Wenn du 
das mit Integern rechnest musst du entweder deutlich größere ints nehmen 
(in dem Fall bieten sich 64bit an), oder du teilst das in mehrere 
Multiplikationen/Divisionen auf, die für sich genommen keinen Überlauf 
produzieren. Ist allerdings die ungenaueste Variante.

Autor: reiner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>U_INT32 ftw = frequency * 4294967296 / 400000000;

warum machst du nicht einfach

u_int32 ftw

ftw = (u-int32)(freq * 10,737); //(4294967296/400000000 = 10,737)

hoffe die typecasts sind so jetz richtig, aber da dein faktor konstant 
ist soltte es so gehen...

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ I_ H. (i_h)

>Am einfachsten und genausten geht die Sache mit floats/doubles.

FALSCH! Auch du sollstes dich über Festkommaarithmetik 
informieren. Und über die diversen Probleme von Fliesskommazahlen.

>Multiplikationen/Divisionen auf, die für sich genommen keinen Überlauf
>produzieren. Ist allerdings die ungenaueste Variante.

Auch falsch.

@ reiner (Gast)

>ftw = (u-int32)(freq * 10,737); //(4294967296/400000000 = 10,737)

Das gleiche für dich Rainer. Konsultiere mal ein gute C-Buch und lies 
den Wikiartikel.

MFG
Falk

Autor: Ruuud (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klammern bringen da auch nichts! Der Fehlermeldung bezieht sich nur auf 
den Wert 2^32!

bei einer long long Variablen kommt die gleiche Fehlermeldung!

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Ruuud (Gast)

>bei einer long long Variablen kommt die gleiche Fehlermeldung!

Klar, weil der Compiler die Konstante 2^32 in Int packen will. Mach mal 
2^32LL

MfG
Falk

Autor: reiner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>   -> integer constant is too large for 'long' type

diese fehlermeldung kommt aus dem einzigen grund, dass 4294967296 (2^32) 
außerhalb des wertebereichs für 32-bit unsigned zahlen liegt, der ja nur 
von 0..2^31-1 geht...

das bei einer multiplikation immer ein überlauf stattfinden kann (außer 
signed 1.x format, und selbst da) ist klar, da gibt es nichts dran zu 
rütteln...

mfg

Autor: Ruuud (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke!!! Jetzt gehts :-)

Lösung:
U_INT32 ftw = frequency * 4294967296LL / 400000000;

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> //frequency tuning word = frequency * 2^32 / Clock DDS

2^32 tut nicht das, was du erwartest. ^ ist der bitweise
XOR-Operator. Einen Potenzoperator gibt es in C nicht.

> U_INT32 ftw = frequency * 4294967296 / 400000000;

4294967296 ist eins größer als die größte in 32 Bits darstellbare
Integerzahl, daher der Fehler

Im C99-Standard gibt es auch 64-Bit-Konstanten. Diese werden mit LL
bzw. ULL (unsigned) gekennzeichnet:
uint32_t ftw = frequency * 4294967296ULL / 400000000;

oder
uint32_t ftw = frequency * (1ULL << 32) / 400000000;

//frequency tuning word = frequency * 2^16 * 2*16 / Clock DDS

Das gibt zwar keine Warnung, liefert aber nicht das gewünschte
Ergebnis (s.o.).

> Kann der µC (AT91SAM7) auch mit 64 bit Werten umgehen?

Wenn der Compiler das unterstützt, was wahrscheinlich der Fall ist,
ja.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ yalu (Gast)

>> //frequency tuning word = frequency * 2^32 / Clock DDS

>2^32 tut nicht das, was du erwartest. ^ ist der bitweise
>XOR-Operator. Einen Potenzoperator gibt es in C nicht.

Es ist nur ein Kommentar ;-)

MFG
Falk

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Falk Brunner wrote:
> @ I_ H. (i_h)
>
> FALSCH! Auch du sollstes dich über Festkommaarithmetik
> informieren. Und über die diversen Probleme von Fliesskommazahlen.

Andersrum - du solltest dich mal ein bisschen mit Numerik beschäftigen. 
Es geht mit Floats/Doubles wirklich am genauesten, glaub es. Das liegt 
daran, dass *2^32 einfach 'ne Verschiebung vom Exponenten ist, sprich da 
ändert sich an der Mantisse nix.

>>Multiplikationen/Divisionen auf, die für sich genommen keinen Überlauf
>>produzieren. Ist allerdings die ungenaueste Variante.
>
> Auch falsch.

Und nochmal andersrum - das ist die ungenaueste Methode. Weil bei jeder 
Division gerundet wird.


Ich hab nicht viel Ahnung von Elektronik, aber Proggen tu ich schon 'ne 
ganze Weile.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Falk:

>> //frequency tuning word = frequency * 2^32 / Clock DDS

>2^32 tut nicht das, was du erwartest. ^ ist der bitweise
>XOR-Operator. Einen Potenzoperator gibt es in C nicht.

Es ist nur ein Kommentar ;-)

Das ist schon klar. Ich habe ihn aber ursprünglich so interpretiert,
dass das Code war, der auskommentiert wurde, weil er hinten und vorne
nicht funktioniert hat ;-)

Aber du hast recht, der Kommentar soll wohl tatsächlich erläuternde
Funktion haben.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ I_ H. (i_h)

>Andersrum - du solltest dich mal ein bisschen mit Numerik beschäftigen.
>Es geht mit Floats/Doubles wirklich am genauesten, glaub es.

Nöö. Schon gar nicht bei deinen "Argumenten". Mal ganz zu schweigen 
davon, dass am Ende ne 32 Bit Integer gebraucht wird, welche per SPI in 
einen DDS IC geladen wird.

>Ich hab nicht viel Ahnung von Elektronik, aber Proggen tu ich schon 'ne
>ganze Weile.

Was erstmal GAR NICHTS besagt.

MFG
Falk

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hab jetzt grad keine Zeit das ausführlich hinzuschreiben, mach ich 
heut Nachmittag. Aber mal eine Anregung für dich:

a/b-floor(a/b) <= b-1/b

Das heist wenn du mit Integern x/25 berechnest (mal'n einfaches 
Beispiel) beträgt die Abweichung absolut bis zu 24/25=0.96. Das gilt für 
jeden einzelnen Term in den du das da oben zerlegen könntest, desswegen 
ist die Abweichung davon ziemlich groß. Die Zerlegung in mehrere 
Multiply-Div mit 32bit Werten ist desswegen murks, also sehr ungenau.


Ausführlich später

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ruuud wrote:

> Kann der µC (AT91SAM7) auch mit 64 bit Werten umgehen?

Das muss er ja nicht native können, es genügt, wenn der Compiler das
emuliert.  Da das sogar der AVR-GCC auf einem 8bitter kann, gehe ich
stark davon aus, dass der ARM-GCC das ebenso kann.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So, also nun nochmal ein bisschen genauer.

Für 'ne Rechnung der Form a/b in Integern gilt offensichlich 
floor(a/b)-a/b<= (b-1)/b.
Üblicherweise rechnet man aber mit der relativen Abweichung, im Fall von 
a/b lässt sich die ausdrücken durch

abs( (floor(a/b)-a/b)/(a/b) ) <= abs( ((b-1)/b)/(a/b) ) = abs((b-1)/a)

bzw.

(b-1)/a

für positive Werte. Multiplikation mit Integern ist exakt, daher stört 
die nicht weiter. Wenn man sich das genauer anguckt, stellt man fest: je 
größer a und je kleiner b, desto kleiner die Abweichung.

Im Beispiel von (freq*2^32)/400e6 liegt die relative Abweichung zB. für 
Frequenzen im Bereich 1kHz..1MHz im Bereich 0.0931%..0.0000931%, also 
bei 1kHz zwischen 0 und 0.0931%, bei 1MHz zwischen 0 und 0.00000931%.

Rechnet man die Sache zB. folgendermaßen:

freq*10+(freq*7)/10+(freq*3)/100+(freq*7)/1000+(freq*167296)/400e6

was bei exakter Rechnung auch das selbe Ergebnis liefert, sehen die 
Abweichungen der Multiply-Div bei 1MHz so aus:
1. 0 (keine Division)
2. 0.000128%
3. 0.0033%
4. 0.01427%
5. 0.2391%

Die Abweichungen muss man noch mit dem absoluten Wert skalieren (die 
letzten sind wegen dem größeren Nenner absolut kleiner, wesswegen sich 
die relative Abweichung nicht so stark auswirkt), was zu folgender 
relativen Gesamtabweichung führt. Für 5 sähe das so aus:

5. 0.2391%*(167296/400e6)/(2^32/400e6) = 0.00000933%
4. 0.0000093
3. 0.00000922
2. 0.000008344
1. 0

macht in der Summe 0.0000 36%. In 64bit beträgt die Abweichung 0.0000 0 
9313%, also grad mal 1/4tel. Und weil ich zwar Theorie mag, aber der 
Bezug zur Praxis nicht fehlen sollte, hab ich mal 'n Prog geschrieben 
das für alle Frequenzen zwischen 1e6 und 2e6 nach beiden Methoden 
rechnet und die Abweichung mit 'ner Rechnung in long double vergleicht 
(der über jeden Zweifel erhaben ist).
Die größte beobachtete Abweichung lag für die simple 64bit Rechnung bei 
9.30645e-08 (ohne %) und bei der 32bit Rechnung bei 3.43283e-07.


Fazit: So ganz falsch ist die Theorie offensichtlich nicht. Und 
offensichtlich ist die 64bit Rechnung tatsache genauer. Und warum 
richtige Floats (long double hat 96bit) sowieso viel genauer sind, und 
das 32bit floats auch genauer sind (sogar im vgl. zu 64bit int), erklär 
ich jetzt nicht noch.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und für alle die immernoch zweifeln: Natürlich kann man die 
Gesamtabweichungen auch allgemein ausrechnen:

direkte Integerrechnung: (400e6-1)/2^32*f)=1/f * 0.09313
zusammengesetzte Integerrechnung: 1/f * 0.36

sprich die direkte Rechnung ist immer um den selben Faktor genauer.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man kann natürlich die Berechnung in mehrere kleinere Multiplikationen 
zerlegen ohne dabei Genauigkeit zu verlieren. Genau das macht der 
Compiler. Und deshalb kann man ihm das auch einfach überlassen.

Um mal wieder zum eigentlichen Thema zurückzukommen: wenn das Ziel ist 
dass das Integerergebnis möglichst genau dem wahren Wert entspricht, 
dann darf man die Nachkommastellen nicht einfach abschneiden wie das bei
(x * 2**32) / 400000000
passiert. Mit einer kleinen Addition vor der Division bekommt man das 
gerundete Ergebnis:
(x * 2**32 + 400000000/2) / 400000000

Autor: eProfi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
verwende mal die große Forumsuche nach
dds multiplikation division

und Du bekommst mehr als 100 Treffer.

z.B.
Beitrag "Rechnen mit AVR"

Fixed ist besser, schneller und genauer!
Denn: Du verbrauchst Bits und Rechenzeit für die Exponenten, welche bei 
Fixed-Point-Arithmetik fest sind, d.h. weder berechnet noch gespeichert 
werden müssen. Diese Bits verwendet man lieber in der Mantisse und 
gewinnt Genauigkeit.
Basta

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nochmal: Floats sind genauer! Und wahrscheinlich sogar schneller.

Autor: Johannes M. (johnny-m)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@eProfi:
Es geht hier nicht um AVRs (für die bei den meisten Compilern sowieso 
nur 32-Bit-Gleitkommatypen unterstützt werden), sondern um 32-Bitter 
(ARM). Dass es bei AVRs in den meisten Fällen (es gibt möglicherweise 
tatsächlich Ausnahmen) nicht sinnvoll ist, in float zu rechnen, hat hier 
glaub ich auch niemand ernsthaft bestritten...

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich wär mir garnet so sicher, dass Integer schneller sind, weder bei 8, 
noch bei 32 bit. Grund:

Selbst mit 'nem 64bit Integer kann man die Rechnung oben nicht so genau 
machen wie mit einem 32bit Float.
64bit Rechnungen sind aber auch auf einem 32bitter alles andere als 
einfach. Add geht noch, das sind idealerweise 2 Rechnungen. Multiply ist 
schon deutlich komplizierter, da braucht's 4 Multiplikationen und 8 
Additionen (4 64bit). Division dürfte noch schlimmer sein.
Dazu kommt, dass 32bit*32bit auf einigen CPUs (dürfte besonders uCs 
treffen) nicht direkt berechenbar ist.

'n 32bit Float ist dagegen deutlich einfacher handhabbar. Grad mal 24bit 
Mantisse, für'n Multiply reicht da Shift (Exponenten angleichen) und 
eine einzige Multiplikation. Division genauso. Addition ist etwas 
komplizierter.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ eProfi (Gast)

>Beitrag "Rechnen mit AVR"

>Fixed ist besser, schneller und genauer!

Meine Rede.

@ I_ H. (i_h)

>Nochmal: Floats sind genauer! Und wahrscheinlich sogar schneller.

Nö. Das ist nur in deiner kleinen Welt so.

@ I_ H. (i_h)

>Selbst mit 'nem 64bit Integer kann man die Rechnung oben nicht so genau
>machen wie mit einem 32bit Float.

HA. Selten so gelacht. Die 64 Bit INT Version erreicht die theoretisch 
mögliche Genauigkeit. Besser geht nicht, mit KEINEM Zahlensystem der 
Welt.

>64bit Rechnungen sind aber auch auf einem 32bitter alles andere als
>einfach.

???
Wo hast du deine Weisheiten her? Carry Arithmetik kann JEDER Prozessor, 
von 4Bit (alte Taschenrechner) bis 64 Bit (dicke CPUs von heute). Selbst 
ne Turingmaschine könnte das.

>Dazu kommt, dass 32bit*32bit auf einigen CPUs (dürfte besonders uCs
>treffen) nicht direkt berechenbar ist.

Muss es gar nicht. Das wird wunderbar durch oben genannte Carry 
Arithmetik erreicht.

>'n 32bit Float ist dagegen deutlich einfacher handhabbar. Grad mal 24bit
>Mantisse, für'n Multiply reicht da Shift (Exponenten angleichen) und
>eine einzige Multiplikation. Division genauso. Addition ist etwas
>komplizierter.

Beweise es an einem praktischen Beispiel!

MfG
Falk

Autor: der mechatroniker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Warum hat eigentlich noch niemand dran gedacht, den Ursprungsbruch 
erstmal passend zu kürzen? Da steckte doch immerhin 1024 als gemeinsamer 
Teiler drin, sprich 10 Bits verschenkt.

[c]U_INT32 ftw = (frequency * 4194304) / 390625;[c]

bzw. zur besseren Rundung

[c]U_INT32 ftw = (frequency * 4194304 + 195312) / 390625;[c]

könnte je nach Wertebereich für frequency (bis 1023) schon bei 
32-bittiger Arithmetik ausreichen. Wenn nicht, teilt man es nochmal in 2 
Teile:

[c]U_INT32 ftw = (((frequency * 2048 + 312) / 625) * 2048 + 312) / 
625;[c]

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst du nich einfach mal einsehen, dass du dich geirrt hast?

Falk Brunner wrote:
> @ eProfi (Gast)
>
>>Beitrag "Rechnen mit AVR"
>
>>Fixed ist besser, schneller und genauer!
>
> Meine Rede.

Es bleibt trotzdem falsch. Fixed ist nicht genauer. Ich warte 
immernoch auf eine Begründung deiner Aussage.
Floats sind, wenn man es so rechnet wie es oben dasteht, auch genauer 
als 64bit. Das liegt daran, dass Integer Division nunmal nicht rundet.

Von deiner zusammengesetzten Division (32bit waren für die Rechnung ja 
zu klein) warst du am Anfang auch überzeugt, dabei ist das die 
ungenauste Variante.


> @ I_ H. (i_h)
>
>>Selbst mit 'nem 64bit Integer kann man die Rechnung oben nicht so genau
>>machen wie mit einem 32bit Float.
>
> HA. Selten so gelacht. Die 64 Bit INT Version erreicht die theoretisch
> mögliche Genauigkeit. Besser geht nicht, mit KEINEM Zahlensystem der
> Welt.

Lies nochmal. Genauigkeit hört nicht bei der letzten Stelle vor'm Komma 
auf. Der Unterschied zwischen 64bit Int und 32bit Float ist bei den 
Zahlen nicht mehr groß, aber er ist da.
Ok, das ist sicher Ansichtssache. Ungenauer sind 32bit Floats aber in 
keinem Fall, weil 2^32 so'ne schöne Zahl ist.

>>64bit Rechnungen sind aber auch auf einem 32bitter alles andere als
>>einfach.
>
> ???
> Wo hast du deine Weisheiten her? Carry Arithmetik kann JEDER Prozessor,
> von 4Bit (alte Taschenrechner) bis 64 Bit (dicke CPUs von heute). Selbst
> ne Turingmaschine könnte das.

Aha. Du würdest also einfach eine Schleife machen, bei 1024*2048 einfach 
1024mal +2048? Nimm mal ein Stift und ein Blatt Papier. Darauf rechnest 
du 1024*2048 mit schriftlicher Addition.
Dann rechnest du 1024.1234 * 2048.5678. Dann zähl mal durch wieviele 
Zeilen du mehr geschrieben hast - du wirst drauf kommen, dass es doppelt 
so viele sind. Dann guckst du dir die Zeilen selber mal an und wirst 
feststellen, dass die auch doppelt so lang geworden sind.

Was stellst du fest? Richtig! Normale Multiplikation liegt in O(n^2)! 
Also 64bit Multiplikation dauert mindestens 4mal so lang wie 32bit. Die 
Additionen noch garnet mitgerechnet (die liegen ja nicht in O(1) sondern 
O(n)).
Ich hab's dir oben schon geschrieben - davon ausgehend das mul und add 
gleich lang brauchen (auf ausgewachsenen CPUs stimmt das sogar) braucht 
eine 64bit Multiplikation 12mal so lange wie eine 32bit! 2 add kannst du 
dir sparen, also dauert's noch 10mal so lang.


>>Dazu kommt, dass 32bit*32bit auf einigen CPUs (dürfte besonders uCs
>>treffen) nicht direkt berechenbar ist.
>
> Muss es gar nicht. Das wird wunderbar durch oben genannte Carry
> Arithmetik erreicht.

Sicher doch, du würdest das alles in 8bit Happen abarbeiten. Macht 
schlappe 64 Multiplikationen und 32 Additionen.
Aber wo du schon das Thema Carries ansprichst - die musst du natürlich 
auch noch auswerten, und inc und dec fallen auch nicht vom Himmel.

>>'n 32bit Float ist dagegen deutlich einfacher handhabbar. Grad mal 24bit
>>Mantisse, für'n Multiply reicht da Shift (Exponenten angleichen) und
>>eine einzige Multiplikation. Division genauso. Addition ist etwas
>>komplizierter.
>
> Beweise es an einem praktischen Beispiel!

Beweise du doch erstmal deine lustigen Aussagen. Mach mir mal eine 64bit 
Multiplikation auf'm 8bitter vor bei der du mit weniger als 64 
Multiplikationen auskommst. Wenn dir das zu aufwändig ist mach 'ne 16bit 
mul mit weniger als 4 8bit mul.

Autor: der mechatroniker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Das liegt daran, dass Integer Division nunmal nicht rundet.

Natürlich kann man auch bei Integer Divisionen korrekt runden, wie oben 
von mir sowie vorher schon von Andreas vorgeführt.

> Lies nochmal. Genauigkeit hört nicht bei der letzten Stelle vor'm Komma
> auf.

Wenn man das Ergebnis anschließend als Vergleichswert für einen Counter 
oder sonstwie in einem Zusammenhang, in dem nur int sinnvoll ist, 
einsetzt, dann schon.

Das der Aufwand für eine Multiplikation quadratisch mit der Länge der 
Multiplikanden wächst, liegt in der Natur der Sache und gilt bei floats 
genauso (hier ist die Länge der Mantisse entscheidend).

Grundsätzlich können 24 geltende Binärstellen bei float nicht genauer 
sein als 32 bei INT32.

Ausnahme: Der Programmierer hat die Darstellung nicht an die abzusehende 
Größenordnung der Werte angepaßt, oder diese Größenordnung entscheidet 
sich erst zur Laufzeit. Da oben das Wort Numerik vorkam: Bei 
Simulationen und ähnlichem kann letzteres schon mal passieren. Bei 
typischen µC-Anwendungen eher nicht.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
der mechatroniker wrote:
> [c]U_INT32 ftw = (((frequency * 2048 + 312) / 625) * 2048 + 312) /
> 625;[c]

Das ergibt allerdings nicht mehr das selbe Ergebnis.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@der mechatroniker

Und was machst du, wenn der Nenner unbekannt ist? Noch 'ne Addition und 
2 Shifts.
Floats können durchaus genauer sein als größere Integer, das ist nunmal 
gerade die Eigenschaft von Floats, desswegen sind die Dinger so toll.
Guck dir mal den Wertebereich der Zahlen an. Integer sind's alle, die 
Frequenz hat, je nachdem was man braucht, vll 20..26 signifikante Bits 
(je nachdem in welchem Bereich die sich bewegen soll). Nach der 
Multiplikation mit 2^32 hat der Integerwert 52..56 Bits, nach der 
Division durch 400e6 sind es noch 23..29.
Wenn du das mit Integern durchziehst brauchst du mindestens 56 Bit um 
das berechnen zu können. Bei Float reichen 20..26 Bit + Exponent.

Also macht das mit 64bit Integern:
64bit mul oder 64bit shl 32
64bit Division (aua)

bei Float braucht's dagegen nur
8bit add auf den Exponenten
20..26bit Division

Ist doch offensichtlich was da schneller ist. Bis zu f=16MHz passen die 
Werte auch gut in den 32bit float rein, ab f=16MHz geht die Abweichung 
dann recht schnell nach oben, weil f nicht mehr in die Mantisse passt. 
Desswegen hab ich ja auch gleich am Anfang

> Am einfachsten und genausten geht die Sache mit floats/doubles

geschrieben. Früher durfte ich die Abweichungen von floats per Hand 
ausrechnen, ist aber schon etwas her und bevor ich jetzt was falsches 
hinschreibe, lass ich es lieber. Aber ich hab's mal getestet, für alle 
Frequenzen zwischen 1 und 16 MHz liegt die größte beobachtete Abweichung 
bei 5.95855e-08, im Bereich bis 20 MHz bei 1.03996e-07 (und das ist die 
Rechnung exakt so, wie sie sie auch im Programm ablaufen würde).
Da werden sich die Ungenauigkeit der Frequenz (je größer desto mehr Bit) 
und die vom Ergebnis (je größer die Frequenz desto weniger Bit vor'm 
Komma) gegenüber stehen.

Double ist schon genauer als man es jemals brauchen würde, entsprechend 
liegt die Abweichung auch bei 1.11012e-16.
Und je nach CPU ließe es sich auch ein bisschen einfacher als 64bit 
Integer rechnen, man bräuchte ein 16bit add (11bit exponent) und ein 
52bit div. Auf'm 32bitter sind die Werte recht ungünstig, auf'm 8bitter 
kann man ein 56bit div rechnen.


Aber mal ganz nebenbei bemerkt ist die Performance wahrscheinlich eh 
wurscht, und auf'm 32bitter sind floats/doubles eh kein Problem. Die 
64bit Speicher sind wahrscheinlich auch egal, aber als double ist die 
Rechnung  halt deutlich genauer.

Autor: Ralph (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die ganze Diskussion ist so doch absoluter Unsinn.

Die Frage muss heißen : Hat der eingesetzte µC eine FPU ?

Ist eine FPU vorhanden dann ist FLOAT OK und macht sowas einfacher.

Ist keine FPU vorhanden ist FLOAT totaler UNFUG.

   Der Compiler wandelt jeder Floatberechnung mit einer LIB in eine 
Integerberechung um.
==> Also kannst du auch direkt Integer rechnen.
Das hat den Vorteil das du die Genauigkeit und den Rechenaufwand selbst 
beeinflussen kannst. Bei der Lib weißt du nicht was der Compiler draus 
macht.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du schreibst, wenn du was sortieren musst, den Sortieralgorithmus 
wahrscheinlich auch jedesmal neu (am besten noch per Bubble Sort; den 
Introsort aus der C-Lib schlägst du nichtmal mit Merge- oder Quicksort).

- implementier mal in wenigen Zeilen C-Code eine Float-Addition, 
Multiplikation und Division (den Exponenten dabei nicht vergessen)
- benutze dabei keine 64bit Werte, benutze auf einem 8bitter nur 8bit 
Werte, auf einem 32bitter nur 32bit Werte, weil der rest wird ja eh auf 
8/32bit Operationen zurückgeführt (wenn schon dann bitte richtig)
- sei dabei schneller als die hochoptimierten Assemblerroutinen aus der 
Lib, verbrauche dabei trotzdem weniger Speicher, und eine gewisse 
Übersichtlichkeit und Abstraktion im Code wäre auch net falsch (willst 
die Werte ja vll auch mal ändern).
- führe zu jeder Rechnung einen Beweis, das die Abweichung unter einem 
bestimmten Wert liegt (so wie bei IEEE754 Floats).
- und das wichtigste: Sei dabei genauer als mit gleich großen Integern

Wenn du das schaffst, schließe ich mich deiner Meinung an.


Beim AVR-GCC sind die Floats leider etwas ungünstig implementiert, wenn 
man einmal einen benutzt wird sofort alles was es zu floats gibt 
eingebunden. Aber das sind auch nur ~3kB, und wenn man schon auf 'nem 
32bitter unterwegs ist... selbst beim AVR bekommt man da quasi keine 
Probleme.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
I_ H. wrote:

> Beim AVR-GCC sind die Floats leider etwas ungünstig implementiert, wenn
> man einmal einen benutzt wird sofort alles was es zu floats gibt
> eingebunden.

Quatsch.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei mir (GCC 4.irgendwas) sah das aber so aus. 1mal 'ne Float Addition 
und es kamen 3kb Code dazu, weiter Multiplikationen und Divisionen, und 
sogar Logarithmus haben an der Codegröße wenig geändert. Könnte aber 
auch am Makefile liegen.

Autor: Berti (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich würde die 2^32 shiften... und nicht mit dem wert multiplizieren

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Berti wrote:
> ich würde die 2^32 shiften... und nicht mit dem wert multiplizieren

Das sollte der Compiler automatisch erkennen.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ I_ H. (i_h)

>Es bleibt trotzdem falsch. Fixed ist nicht genauer. Ich warte
>immernoch auf eine Begründung deiner Aussage.

ganz einfach, weil zumindest auf dem AVR die Floats nur 24 Bit Mantisse 
haben, die INT Lösung aber mit 32 Bit arbeitet.

>Floats sind, wenn man es so rechnet wie es oben dasteht, auch genauer
>als 64bit. Das liegt daran, dass Integer Division nunmal nicht rundet.

Quark. Die kann auch runden. Und um das letzte LSB reden wir incht 
wirklich, eher um die 24/32 Bit.

>Von deiner zusammengesetzten Division (32bit waren für die Rechnung ja
>zu klein) warst du am Anfang auch überzeugt, dabei ist das die
>ungenauste Variante.

???

>Aha. Du würdest also einfach eine Schleife machen, bei 1024*2048 einfach
>1024mal +2048? Nimm mal ein Stift und ein Blatt Papier. Darauf rechnest

Mathematisch richtig, praktisch eher nicht so doll. Aber wir schweifen 
ab.

>Sicher doch, du würdest das alles in 8bit Happen abarbeiten. Macht
>schlappe 64 Multiplikationen und 32 Additionen.

Ja und? Gibts die Multiplikation bei Float umsonst?

>Beweise du doch erstmal deine lustigen Aussagen. Mach mir mal eine 64bit
>Multiplikation auf'm 8bitter vor bei der du mit weniger als 64
>Multiplikationen auskommst. Wenn dir das zu aufwändig ist mach 'ne 16bit
>mul mit weniger als 4 8bit mul.

Das ist gar nicht die Aufgabenstellung! Es ging um die Berechung von

U_INT32 ftw = frequency * 4294967296 / 400000000;

Das kann man wunderbar mit EINER einfachen 32x32 Bit 
Integer-Multiplikation lösen. Plus ein Shift.

// ftw = frequency * 2**32 * 2**25 / 400000000 / 2**25;
U_INT32 ftw = frequency * 3602879702ULL;
        ftw >>= 25;

Die Sache hat nur einen Haken. Die Rechung mit 32/64 Bit Integer ist auf 
dem AVR-GCC scheinbar etwas lieblos implementiert. Genaueres später. In 
Assembler sind es weniger als 100 Byte und ca. 600 Takte (Shift/Add, 
ohne Hardware MUL).

>Ist doch offensichtlich was da schneller ist. Bis zu f=16MHz passen die
>Werte auch gut in den 32bit float rein, ab f=16MHz geht die Abweichung

FALSCH! Eine DDS mit 32 Bit Akku und 40 MHz Takt hat eine Auflösung von

40 MHz / 2**32 = 0.009 Hz, rund 1/100 Hz. Mit 24 Bit Mantisse (16,8 
Millionen) geht da die Auflösung schon bei ~160 kHz in die Knie! Dass 
der RELATIVE Fehler immer bei ca. 1/2**24 liegt ist klar.

MFG
Falk

Autor: Ralph (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also die einfache Intergerlösung ist:

#define factor (U_INT32) ((4294967296 / 400000000)*1024) 
/*10995,11627776 ==> 10995*/


U_INT32 ftw = (frequency * factor) / 1024 ;

Die Abweichung bei frequeny = 100 zwischen Floatberechnung und 
Intergeberechung an der Stelle ist ftw(delta)0,01135525 ==> 
0,00105754006654024124145507813 % ==> da ftw aber eine Intergervariable 
ist, macht das keinen Unterschied.


Und jetzt zeig mir mal die FLOAT lib für einen µC ohne FPU, die das 
schneller und genauer hinbekommt.
Wenn du dir Genauigkeit erhöhen willst, dann ersetze 1024 mit zb 4096 
oder andere 2^x

Das hier sind auf einem ARM7TDMI < 20 Assemblerbefehle.

Abgesehen davon ist es Zeitverschwendung über Berechungsgenauigkeit im 
Bereich vom 1/1000 % oder noch weniger zu diskutieren, solange nicht die 
Genauigkit der Eingangssignale und der benötigten Ergebnisse definiert 
ist.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Falk Brunner wrote:
> @ I_ H. (i_h)
>
>>Es bleibt trotzdem falsch. Fixed ist nicht genauer. Ich warte
>>immernoch auf eine Begründung deiner Aussage.
>
> ganz einfach, weil zumindest auf dem AVR die Floats nur 24 Bit Mantisse
> haben, die INT Lösung aber mit 32 Bit arbeitet.

IEE754 Floats (die der GCC umsetzt) haben 23bit Mantisse. Du hast das 
sign-bit vergessen.

>>Ist doch offensichtlich was da schneller ist. Bis zu f=16MHz passen die
>>Werte auch gut in den 32bit float rein, ab f=16MHz geht die Abweichung
>
> FALSCH! Eine DDS mit 32 Bit Akku und 40 MHz Takt hat eine Auflösung von
>
> 40 MHz / 2**32 = 0.009 Hz, rund 1/100 Hz. Mit 24 Bit Mantisse (16,8
> Millionen) geht da die Auflösung schon bei ~160 kHz in die Knie! Dass
> der RELATIVE Fehler immer bei ca. 1/2**24 liegt ist klar.
>

Die INT Lösung hat übrigens garkeine Nachkommastellen. Mach mal mit Int 
1.2435Hz. Der einfache 32bit float spuckt nach der Rechnung einen Wert 
aus, der herrlich exakt 1.2435 entspricht (die Abweichungen dürften erst 
sehr spät anfangen). Rate mal was mit Integern rauskommt... 1

Was die Auflösung vom DDS jetzt mit der Geschwindigkeit der Berechnung 
zu tun haben soll, ist mir nicht so ganz klar. Deine Aussage ist aber 
eh, um dich mal zu zitieren, FALSCH! Die Auflösung geht bei 160kHz 
nicht in die Knie. Beweise das bitte.
Ich hab's für alle Frequenzen von 1Hz bis 2MHz ausrechnen lassen, es kam 
nix größeres als 5.95791e-08 raus. Ab 16MHz geht die Abweichung wie 
schon gesagt deutlich nach oben, weil der Float dann zu klein wird.

Deine 160kHz sind auch ein abenteuerlicher Wert. Wo hast du den her? Mal 
zum drüber nachdenken:

200kHz (offensichtlich >160kHz) brauchen für exakte Ganzzahldarstellung 
18 Bit - passen also problemlos in die Mantisse, Exponent 0.
Multiplizieren mit 2^32: Mantisse wird nicht verändert, Exponent geht um 
5 nach oben. Darstellung ist nach wie vor exakt.
Division durch 400e6: 400e6 lässt sich nicht exakt als float darstellen, 
wird zu 399'999'994.8, hat also eine Abweichung von 1.3e-8.
Das Ergebnis der Division (exakt 2147483.648) lässt sich vor'm Komma 
offensichtlich exakt darstellen - bleibt die Abweichung von 1.3e-8. Die 
bleibt so bestehen.

Bei 200kHz beträgt die Abweichung mit Floats also 1.3e-8 (bezogen auf 
die Stellen vor'm Komma, effektiv also 0). qed. Bei 40 MHz ist die 
Abweichung noch kleiner.


>>Sicher doch, du würdest das alles in 8bit Happen abarbeiten. Macht
>>schlappe 64 Multiplikationen und 32 Additionen.
>
> Ja und? Gibts die Multiplikation bei Float umsonst?

Es wird weniger multipliziert. Denk an O(n^2). Das was weniger 
multipliziert wird, wird addiert - O(n).

> Das kann man wunderbar mit EINER einfachen 32x32 Bit
Integer-Multiplikation lösen. Plus ein Shift.

Falsch. Das ist 'ne 32x64bit Multiplikation. Besser als 64x64bit, aber 
auch nicht gut. Damit C dir das als 32x32bit mul macht, muss das 
Ergebnis auch 32bit sein. Vor allem aber ist es häufig ungenauer als 
float.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was mir übrigens tierisch auf den Geist geht ist, dass du Falk
dir die Aussagen jedesmal zurechtinterpretierst und ein paar Beiträge 
später wieder den selben
Mist anbringst (du hast ja scheinbar keine Probleme mit einer etwas 
offensiveren Umgangsform).

Frei nach dem Motto:

(am Anfang vom Thread)
>>Multiplikationen/Divisionen auf, die für sich genommen keinen Überlauf
>>produzieren. Ist allerdings die ungenaueste Variante.
>Auch falsch.

(Beweis das dem so ist in der Mitte)

(am Ende)
>>Von deiner zusammengesetzten Division (32bit waren für die Rechnung ja
>>zu klein) warst du am Anfang auch überzeugt, dabei ist das die
>>ungenauste Variante.
>???

Oder:

>>Am einfachsten und genausten geht die Sache mit floats/doubles.
>*FALSCH*! Auch du sollstes dich über Festkommaarithmetik
>informieren. Und über die diversen Probleme von Fliesskommazahlen.

>>Am einfachsten und genausten geht die Sache mit floats/doubles.
>*FALSCH*! Auch du sollstes dich über Festkommaarithmetik
>informieren. Und über die diversen Probleme von Fliesskommazahlen.

(jeder der sich ein bisschen mit sowas beschäftigt hat weis, dass 
doubles in dem Fall viel genauer sind)

So zieht sich das durch den ganzen Thread, wenn dir irgend 'ne Aussage 
nicht in den Kram passt kommt
erstmal "FALSCH!" oder "*FALSCH*!" und das war's dann. Wenn man 'ne 
Begründung dazu schreibt wird die
wiederrum nur mit "FALSCH!" oder "*FALSCH*!" zerrissen, ohne das du auch 
nur einmal auf irgendwas eingehst.

Ich muss dich nicht davon überzeugen, ich hab nix davon. Deine Aussagen 
in dem Thread sind größerenteils falsch,
und deine Herangehensweise an das Thema macht für mich den Eindruck als 
hättest du von dem Thema allgemein nicht so
viel Ahnung. Du magst viel Ahnung von E-Technik haben, aber bei 
Informatik/Mathematik sieht's dünn aus (E-Techniker lernen auch nur
Mathe anzuwenden, nicht Mathe zu machen - in der E-Technik muss man auch 
kein Mathe machen).
Ob du das nun glaubst oder nicht ist mir inzwischen egal. Damit ist das 
Thema für mich erledigt.

Autor: ---- (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@I_h:
> Damit ist das Thema für mich erledigt.
Was Falk betrifft, ok. Da muss man sich nicht die Nerven holen. Deine 
Ausführungen waren aber sehr interessant und verständlich - ich habe 
einiges dazugelernt. Float ist pauschal gar nicht so "bäh", wie immer 
behauptet wird - es kommt ganz klar auf die Rechnung an.
 Also falls es dich drückt und du noch ein paar Sätze zum Thema 
schreiben willst, lass dich nicht abhalten. :-)

> Was mir übrigens tierisch auf den Geist geht ist, dass du Falk
> dir die Aussagen jedesmal zurechtinterpretierst und ein paar Beiträge
> später wieder den selben
> Mist anbringst (du hast ja scheinbar keine Probleme mit einer etwas
> offensiveren Umgangsform).
Und das ist auch der Unterschied zwischen Falk und khbuchegg/peda... 
Falk ist fachlich in vielen Punkte kompetent, muss aber immer offensiv 
diskutieren. Und wenn er merkt, dass er nicht 100% Recht hat, dann zieht 
er die Diskussion runter, um so abzulenken, dass er widerlegt wurde, 
statt sich zurückzunehmen oder den Fehler einzugestehen.
 Es kann halt nicht jeder so ruhig und sachlich bleiben.

----, (QuadDash).

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Ralph (Gast)

>Die Abweichung bei frequeny = 100 zwischen Floatberechnung und
>Intergeberechung an der Stelle ist ftw(delta)0,01135525 ==>
>0,00105754006654024124145507813 % ==> da ftw aber eine Intergervariable
>ist, macht das keinen Unterschied.

Für ne DDs soch relativ viel Fehler.

>Das hier sind auf einem ARM7TDMI < 20 Assemblerbefehle.

Und der Compiler setzt das auch so um?

>Abgesehen davon ist es Zeitverschwendung über Berechungsgenauigkeit im
>Bereich vom 1/1000 % oder noch weniger zu diskutieren, solange nicht die
>Genauigkit der Eingangssignale und der benötigten Ergebnisse definiert
>ist.

Es geht um eine DDS. Mit dem berechneten Parameter wird die Frequenz 
eingestellt, bei 40 MHz theoretisch mit 0,01 Hz Auflösung. Macht bei 
maximler Frequenz (20 MHz) 1/2^31 Auflösung.

@ I_ H. (i_h)

>IEE754 Floats (die der GCC umsetzt) haben 23bit Mantisse. Du hast das
>sign-bit vergessen.

Sogar noch eins schlechter.

>Die INT Lösung hat übrigens garkeine Nachkommastellen.

Brauch sie auch nicht bei intelligenter Anwendung von 
Festkommaarithmetik.

>zu tun haben soll, ist mir nicht so ganz klar. Deine Aussage ist aber
>eh, um dich mal zu zitieren,

Lern mal zitieren.

http://www.afaik.de/usenet/faq/zitieren/

>Ich hab's für alle Frequenzen von 1Hz bis 2MHz ausrechnen lassen,

Für ALLE? In welchem Raster 1 Hz? Das sind NICHT alle. Die DDS hat 
ÜBERALL eine Auflösung von hier ~0,01 Hz.

160.000 * 100 = 16.000.000 also praktisch die 24 Bit Mantisse von der 
ich sprach. Da es nur 23 sind, passiert das sogar schon bei ~ 80 kHz. 
Sprich du kannst eine Frequenz von 1 MHz mit einer Zahl mit 23 Bit 
Mantisse nicht auf 0.01 Hz genau angeben.

>nix größeres als 5.95791e-08 raus. Ab 16MHz geht die Abweichung wie
>schon gesagt deutlich nach oben, weil der Float dann zu klein wird.

Nöö, eher. Siehe oben.

>Deine 160kHz sind auch ein abenteuerlicher Wert. Wo hast du den her? Mal
>zum drüber nachdenken:

Siehe oben.

>Bei 200kHz beträgt die Abweichung mit Floats also 1.3e-8 (bezogen auf
>die Stellen vor'm Komma, effektiv also 0). qed. Bei 40 MHz ist die
>Abweichung noch kleiner.

" . . . seht ihr den Mond dort stehen, er ist nur halb zu sehen, und ist 
doch rund und schön. So sind wohl manche Sachen, die wir getrost 
belachen, weil unsre Augen sie nicht sehn . . ."

>> Das kann man wunderbar mit EINER einfachen 32x32 Bit
>>Integer-Multiplikation lösen. Plus ein Shift.

>Falsch. Das ist 'ne 32x64bit Multiplikation. Besser als 64x64bit, aber
>auch nicht gut.

Nö. Siehe nächstes Posting. 32x32 Bit reicht VOLLKOMMEN aus.

>Mist anbringst (du hast ja scheinbar keine Probleme mit einer etwas
>offensiveren Umgangsform).

???
Wenn du kuscheln willst bis du im falschen Forum. Hier geht um harte 
Argumente und Diskussionen. May the better one win. ;-)

>(Beweis das dem so ist in der Mitte)

Welcher Beweis? Nur weil DU was hingeschrieben hast? Wer hat das noch 
befürwortet?

>>>Am einfachsten und genausten geht die Sache mit floats/doubles.
>>*FALSCH*! Auch du sollstes dich über Festkommaarithmetik
>>informieren. Und über die diversen Probleme von Fliesskommazahlen.

>(jeder der sich ein bisschen mit sowas beschäftigt hat weis, dass
>doubles in dem Fall viel genauer sind)

Aber nicht floats. Und auf nem AVR sind doubles auch nur Floats (jaja, 
der OP hat nen ARM).

>wiederrum nur mit "FALSCH!" oder "*FALSCH*!" zerrissen, ohne das du auch
>nur einmal auf irgendwas eingehst.

Kannst du nicht lesen oder willst du nicht? Ich habe meine Aussagen 
begründet. Mit mehreren Rechnungen.

>Ich muss dich nicht davon überzeugen, ich hab nix davon. Deine Aussagen
>in dem Thread sind größerenteils falsch,
>und deine Herangehensweise an das Thema macht für mich den Eindruck als
>hättest du von dem Thema allgemein nicht so
>viel Ahnung. Du magst viel Ahnung von E-Technik haben, aber bei
>Informatik/Mathematik sieht's dünn aus (E-Techniker lernen auch nur
>Mathe anzuwenden, nicht Mathe zu machen - in der E-Technik muss man auch
>kein Mathe machen).

Wenn DU das so sagts, muss es ja stimmen. Ausserdem machen E-Techniker 
Dinge, die praktisch funktionieren und bauen keine akademischen 
Luftschlösser.

>Ob du das nun glaubst oder nicht ist mir inzwischen egal. Damit ist das
>Thema für mich erledigt.

Die beleidigte Leberwurst ist auch ein beliebter Abgang aus ner 
Diskussion. Der Märtyrertod im Internet. Naja.

MfG
Falk

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ ---- (Gast)

>Und das ist auch der Unterschied zwischen Falk und khbuchegg/peda...
>Falk ist fachlich in vielen Punkte kompetent, muss aber immer offensiv
>diskutieren. Und wenn er merkt, dass er nicht 100% Recht hat, dann zieht
>er die Diskussion runter, um so abzulenken, dass er widerlegt wurde,
>statt sich zurückzunehmen oder den Fehler einzugestehen.
> Es kann halt nicht jeder so ruhig und sachlich bleiben.

Klar, von jemanden der sich hinter dem Namen --- versteckt ist diese 
Aussage auch sehr ernst zu nehmen. Nix als dummes Gelaber. Wenn ich mich 
verhaue, dann stehe ich dazu! Du stehst nicht mal zu deinem Namen!

MFG
Falk

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So, hier mal ein paar Real World Examples. Das Ganze auf AVR-GCC 
20060421, nicht soo ganz taufrisch.
// compiliert und simuliert mit ATmega8
#include <avr/io.h>

// DDS frequency tuning word calculation
// frequency unit is 1 Hz, but can be extended to 1/128 Hz

// we use 64 bit constants (unsigned long long, ULL)

#define F_DDS 40000000ULL                       // system clock for DDS
#define ACCU_SIZE 4294967296ULL                 // 32 Bit DDS Accu
#define sel 1                                   // select ftw function

#if (sel==0)
uint32_t ftw_fix_1 (uint32_t freq) {
  uint64_t tmp;

  tmp = freq * ACCU_SIZE / F_DDS;

  return tmp;
}
#endif

#if (sel==1)
uint32_t ftw_fix_2 (uint32_t freq) {
  uint64_t tmp;

  // tmp = freq * ACCU_SIZE * 2^25 / F_DDS / 2^25; 
  // ACCU_SIZE / F_DDS = 107,3741824
  // ACCU_SIZE * 2^25 / F_DDS = 3602879702

  tmp = freq * 3602879702ULL;
  tmp >>= 25;

  return tmp;
}
#endif

#if (sel==2)
uint32_t ftw_float_1 (uint32_t freq) {
  float tmp;

  tmp =  (float)freq * ACCU_SIZE / F_DDS;

  return tmp;
}
#endif

#if (sel==3)
uint32_t ftw_float_2 (uint32_t freq) {
  float tmp;

  // tmp = freq * ACCU_SIZE / F_DDS;

  tmp =  freq * 107.3741824;

  return tmp;
}
#endif

int main (void) {
//  volatile uint32_t x;
  
//  x = ftw_fix(1000);
//  x = ftw_fix_2(1000);
//  x = ftw_float_1(1000);
//  x = ftw_float_2(1000);

  return 0;
}

Dabei wurden folgende Parameter ermittelt, alles mit Optimierungsstufe 
-Os.

Resources      FLASH  RAM  Takte

fix_1           5124  256  4671
fix_2           1302    0  1639
float_1          862    0  1088
float_2          704    0   593

optimal          210    0    98       32x32 Bit INT Multiplikation

overhead         110    0             Compileroverhead + main


Scheint so, als ob Float doch besser ist? Nein, denn erstens rechnet 
Float nur mit 24 Bit Mantisse auf dem AVR und zweitens scheint die 
Arithmetik mit grossen Zahlen auf dem AVR-GCC noch EINIGES an 
Optimierungspotential zu haben. Schauen wir mal genau hin.

uint32_t ftw_fix_1 (uint32_t freq) {
  uint64_t tmp;

  tmp = freq * ACCU_SIZE / F_DDS;

  return tmp;
}

Das Ganze einfach hingeschrieben mit ULL Suffix erzeugt eine komplette 
64 Bit Integerrechnung, Multiplikation UND Division, sieht man im 
Listfile sehr gut. Ist das normal? Ich dachte der Compiler tut 
Konstanten ausrechnen und zusammenfassen? Und wozu werden 5kB Code 
benötigt? Und 256 Byte SRAM? Fragen über Fragen.

uint32_t ftw_fix_2 (uint32_t freq) {
  uint64_t tmp;

  // tmp = freq * ACCU_SIZE * 2^25 / F_DDS / 2^25; 
  // ACCU_SIZE / F_DDS = 107,3741824
  // ACCU_SIZE * 2^25 / F_DDS = 3602879702

  tmp = freq * 3602879702ULL;
  tmp >>= 25;

  return tmp;
}

Mit etwas Brain 2.0 und dem Wissen über Festkommaarithmetik kann man 
das Ganze "mundgerecht" aufbereiten. Um die maximale Genauigkeit zu 
erzielen wird der Faktor ACCU_SIZE / F_DDS mit 2^25 erweitert, um den 
maximalen 32 Bit Wertebereich nutzen zu können. EIGENTLICH ist das 
eine ganz einfache, kompakte und schnelle 32x32=64 Bit Multiplikation, 
doch Pustekuchen! :-( Wenn man die Rechnung in 32 Bit durchführt (Suffix 
UL stall ULL) werden die oberen 32 Bit weggeschmissen und das Ergebnis 
ist wertlos! Obwohl die Funktion die vollen 64 Bit berechnet! Der zweite 
Skandal ist die Schiebeoperation! Die verbraucht sage und schreibe 384 
Byte und dauert 888 Takte! Hallo? Was soll denn DAS?

Wäre der Compiler nicht so stur und unfähig und würde das Ergebnis der 
32x32 Bit Multiplikation nicht wegschmeissen, wäre die Funktion gerade 
mal 100 Byte lang und würde komplett nur 92 Takte dauern! Wie kann man 
dem Compiler das halbwegs beibringen, ohne tierisch mit Inlineassembler 
und anderen Tricks zu arbeiten?

uint32_t ftw_float_1 (uint32_t freq) {
  float tmp;

  tmp =  (float)freq * ACCU_SIZE / F_DDS;

  return tmp;
}

Das Ganze direkt als Floatrechnung hingeschrieben ist aller Erwartung 
zum Trotz wesentlich kleiner als die 64 Bit Integerlösung. Aber auch 
hier wird multipliziert und dividiert, allerdings recht effizient.

uint32_t ftw_float_2 (uint32_t freq) {
  float tmp;

  // tmp = freq * ACCU_SIZE / F_DDS;

  tmp =  freq * 107.3741824;

  return tmp;
}

Wenn dem Compiler wieder ein wenig auf die Sprünge geholfen wird, dann 
reicht eine einzige Multiplikation. Die Wandlung INT-Float bzw. Float-> 
INT fällt wenig ins Gewicht.

Schlussfolgerung. An der Arithmetik für 32/64 Bit Integer sowie 
Schiebeopertionen muss noch EINIGES m AVR-GCC gemacht werden, auch wenn 
das nicht das tägliche Brot eines 8-Bit Mikrocontrollers ist. Wie sieht 
das auf anderen Compilern und anderen Zielplattformen aus? ARM, MSP430, 
8051, PC?

MFG
Falk

P.S. Als vorübergehenden Workaround würde ich trotz 24 Bit Mantisse auf 
Version float_2 ausweichen. ;-)

Autor: ---- (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> Es kann halt nicht jeder so ruhig und sachlich bleiben.
> Klar, von jemanden der sich hinter dem Namen --- versteckt ist diese
> Aussage auch sehr ernst zu nehmen. Nix als dummes Gelaber. Wenn ich mich
> verhaue, dann stehe ich dazu! Du stehst nicht mal zu deinem Namen!
Es kann halt nicht jeder so ruhig und sachlich bleiben.

----, (QuadDash).

Autor: Helmi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@falk

uVision 3 Arm Compiler

ftw_fix_1   2.333uS 440Byte
ftw_fix_2   2.167uS 352Byte
ftw_float_1 1.083uS 360Byte
ftw_float_2 2.167uS 824Byte

CPU Clock 12MHz

Gruss Helmi

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Helmi (Gast)

>uVision 3 Arm Compiler

16 oder 32 Bit?

>ftw_fix_1   2.333uS 440Byte
>ftw_fix_2   2.167uS 352Byte
>ftw_float_1 1.083uS 360Byte
>ftw_float_2 2.167uS 824Byte

>CPU Clock 12MHz

Sieht schon wesentlich besser aus, aber immer noch weit vom einfachen 
32x32 Bit Mul entfernt. Naja, Assembler rulez ;-)

MFG
Falk

Autor: Helmi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Code Optimization:
  Opt 6 Common tail merging
  Favor execution speed
  Thumb Mode

Gruss Helmi

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
GCC (ARM) 4.1.0 mit -Os:
<ftw_fix_2>:
   0:  e59f3014   ldr  r3, [pc, #20]  ; 1c <.text+0x1c>
   4:  e92d4070   stmdb  sp!, {r4, r5, r6, lr}
   8:  e0865093   umull  r5, r6, r3, r0
   c:  e1a00ca5   mov  r0, r5, lsr #25
  10:  e3a04000   mov  r4, #0  ; 0x0
  14:  e1800386   orr  r0, r0, r6, lsl #7
  18:  e8bd8070   ldmia  sp!, {r4, r5, r6, pc}
  1c:  d6bf94d6   ssatle  r9, #32, r6, ASR #9

Allerdings rechnen ftw_fix_1 und ftw_fix_2 nicht das selbe (setz z.B. 
mal 40005000 ein), und beide Funktionen runden nicht.

Autor: Helmi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@falk

Hier die Zeiten fuer den ARM Mode:

ftw_fix_1   2.083uS 512Byte
ftw_fix_2   2.500uS 436Byte
ftw_float_1 1.000uS 420Byte
ftw_float_2 1.917uS 8288Byte

Gruss Helmi

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Helmi (Gast)

>ftw_float_2 1.917uS 8288Byte

Sicher? Oder Tippfehler?

MFG
Falk

Autor: Helmi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
*** CODE SEGMENT '?PR?ftw_fix_1?A?main':
   17: uint32_t ftw_fix_1 (uint32_t freq) {
 00000000  E92D4000  STMDB       R13!,{LR}
 00000004  E1A01000  MOV         R1,R0 ; freq
 00000008  ---- Variable 'freq' assigned to Register 'R1' ----
 00000008            ; SCOPE-START
   20:   tmp = freq * ACCU_SIZE / F_DDS;
 00000008  E1A00001  MOV         R0,R1 ; freq
 0000000C  E3A01000  MOV         R1,#0x0000
 00000010  E3A02000  MOV         R2,#0x0
 00000014  E3A03001  MOV         R3,#0x1
 00000018  EBFFFFF8  BL          ?C?QMUL?A  ; Targ=0x0 ; ?C?QMUL?A
 0000001C  E5102000  LDR         R2,=0x2625A00
 00000020  E3A03000  MOV         R3,#0x0
 00000024  EBFFFFF5  BL          ?C?UQDIV?A  ; Targ=0x0 ; ?C?UQDIV?A
 00000028  ---- Variable 'tmp' assigned to Register 'R0/R1' ----
   22:   return tmp;
 00000028  E1A02000  MOV         R2,R0
 0000002C  E1A03001  MOV         R3,R1
 00000030  E1A00002  MOV         R0,R2
 00000034            ; SCOPE-END
   23: }
 00000034  E8BD0008  LDMIA       R13!,{R3}
 00000038  E12FFF13  BX          R3
 0000003C          ENDP ; 'ftw_fix_1?A'

*** CODE SEGMENT '?PR?ftw_fix_2?A?main':
   27: uint32_t ftw_fix_2 (uint32_t freq) {
 00000000  E92D4030  STMDB       R13!,{R4-R5,LR}
 00000004  E1A01000  MOV         R1,R0 ; freq
 00000008  ---- Variable 'freq' assigned to Register 'R1' ----
 00000008            ; SCOPE-START
   34:   tmp = freq * 3602879702ULL;
 00000008  E1A00001  MOV         R0,R1 ; freq
 0000000C  E3A01000  MOV         R1,#0x0000
 00000010  E5102000  LDR         R2,=0xD6BF94D6
 00000014  E3A03000  MOV         R3,#0x0
 00000018  EBFFFFF8  BL          ?C?QMUL?A  ; Targ=0x0 ; ?C?QMUL?A
 0000001C  E1A04000  MOV         R4,R0 ; tmp
 00000020  E1A05001  MOV         R5,R1 ; tmp
 00000024  ---- Variable 'tmp' assigned to Register 'R4/R5' ----
   35:   tmp >>= 25;
 00000024  E1A00385  MOV         R0,R5,LSL #7
 00000028  E1A04CA4  MOV         R4,R4,LSR #25
 0000002C  E1A05CA5  MOV         R5,R5,LSR #25
 00000030  E1844000  ORR         R4,R4,R0
   37:   return tmp;
 00000034  E1A02004  MOV         R2,R4
 00000038  E1A03005  MOV         R3,R5
 0000003C  E1A00002  MOV         R0,R2
 00000040            ; SCOPE-END
   38: }
 00000040  E8BD0030  LDMIA       R13!,{R4-R5}
 00000044  E8BD0008  LDMIA       R13!,{R3}
 00000048  E12FFF13  BX          R3
 0000004C          ENDP ; 'ftw_fix_2?A'

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Andreas Schwarz (andreas)

>Allerdings rechnen ftw_fix_1 und ftw_fix_2 nicht das selbe (setz z.B.
>mal 40005000 ein)

Geht sinnvoll nur bis 20.000.000.

>, und beide Funktionen runden nicht.

Ja, ist hier erstmal vernachlässig. Und bei 1/100 Hz Auflösung meist zu 
verschmerzen ;-)

MfG
Falk

Autor: Helmi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tipp fehler  888Byte

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Andreas Schwarz (andreas)

>Allerdings rechnen ftw_fix_1 und ftw_fix_2 nicht das selbe (setz z.B.
>mal 40005000 ein)

Ja, weil ich hier 3602879702ULL aufgerundet habe. Setz mal 3602879701ULL 
ein.

MfG
Falk

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Helmi (Gast)

>Tipp fehler  888Byte

Dennoch merkwürdig. Eine einfache Multilikation braucht mehr Platz und 
Zeit als Multiplikation UND Division?

MFg
Falk

Autor: Helmi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
*** CODE SEGMENT '?PR?ftw_float_1?A?main':
   42: uint32_t ftw_float_1 (uint32_t freq) {
 00000000  E92D4000  STMDB       R13!,{LR}
 00000004            ; SCOPE-START
   45:   tmp =  (float)freq * ACCU_SIZE / F_DDS;
 00000004  E3A01000  MOV         R1,#0x0
 00000008  ---- Variable 'tmp' assigned to Register 'R1' ----
   47:   return tmp;
 00000008  E1A00001  MOV         R0,R1 ; tmp
 0000000C  EBFFFFFB  BL          ?C?CASTF?A  ; Targ=0x0 ; ?C?CASTF?A
 00000010            ; SCOPE-END
   48: }
 00000010  E8BD0008  LDMIA       R13!,{R3}
 00000014  E12FFF13  BX          R3
 00000018          ENDP ; 'ftw_float_1?A'

Das ist der Code den er aus deiner Source gemacht hat

*** CODE SEGMENT '?PR?ftw_float_2?A?main':
   52: uint32_t ftw_float_2 (uint32_t freq) {
 00000000  E92D4000  STMDB       R13!,{LR}
 00000004  E1A01000  MOV         R1,R0 ; freq
 00000008  ---- Variable 'freq' assigned to Register 'R1' ----
 00000008            ; SCOPE-START
   57:   tmp =  freq * 107.3741824;
 00000008  E1A00001  MOV         R0,R1 ; freq
 0000000C  EBFFFFFB  BL          ?C?FCASTU?A  ; Targ=0x0 ; ?C?FCASTU?A
 00000010  E5101000  LDR         R1,=0x42D6BF95
 00000014  EBFFFFF9  BL          ?C?FPMUL?A  ; Targ=0x0 ; ?C?FPMUL?A
 00000018  E1A01000  MOV         R1,R0 ; tmp
 0000001C  ---- Variable 'tmp' assigned to Register 'R1' ----
   59:   return tmp;
 0000001C  E1A00001  MOV         R0,R1 ; tmp
 00000020  EBFFFFF6  BL          ?C?CASTF?A  ; Targ=0x0 ; ?C?CASTF?A
 00000024            ; SCOPE-END
   60: }
 00000024  E8BD0008  LDMIA       R13!,{R3}
 00000028  E12FFF13  BX          R3
 0000002C          ENDP ; 'ftw_float_2?A'

Gruss Helmi

Autor: Helmi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe jetzt deine beiden Konstanten

#define F_DDS 40000000ULL
#define ACCU_SIZE 4294967296ULL

nach

#define F_DDS 40000000.0
#define ACCU_SIZE 4294967296.0

geaendert

*** CODE SEGMENT '?PR?ftw_float_1?A?main':
   42: uint32_t ftw_float_1 (uint32_t freq) {
 00000000  E92D4000  STMDB       R13!,{LR}
 00000004  E1A01000  MOV         R1,R0 ; freq
 00000008  ---- Variable 'freq' assigned to Register 'R1' ----
 00000008            ; SCOPE-START
   45:   tmp =  (float)freq * ACCU_SIZE / F_DDS;
 00000008  E1A00001  MOV         R0,R1 ; freq
 0000000C  EBFFFFFB  BL          ?C?FCASTU?A  ; Targ=0x0 ; ?C?FCASTU?A
 00000010  E5101000  LDR         R1,=0x4F800000
 00000014  EBFFFFF9  BL          ?C?FPMUL?A  ; Targ=0x0 ; ?C?FPMUL?A
 00000018  E5101000  LDR         R1,=0x4C189680
 0000001C  EBFFFFF7  BL          ?C?FPDIV?A  ; Targ=0x0 ; ?C?FPDIV?A
 00000020  E1A01000  MOV         R1,R0 ; tmp
 00000024  ---- Variable 'tmp' assigned to Register 'R1' ----
   47:   return tmp;
 00000024  E1A00001  MOV         R0,R1 ; tmp
 00000028  EBFFFFF4  BL          ?C?CASTF?A  ; Targ=0x0 ; ?C?CASTF?A
 0000002C            ; SCOPE-END
   48: }
 0000002C  E8BD0008  LDMIA       R13!,{R3}
 00000030  E12FFF13  BX          R3
 00000034          ENDP ; 'ftw_float_1?A'

1300Byte 2.417uS

Gruss Helmi

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@----

Bei Floats lässt sich die Abweichung recht bequem berechnen, weil die 
immer die selbe (maximale) relative Abweichung haben. In der Numerik 
gibt's dafür das Kapitel Fehlerfortpflanzung, wo man sich damit 
beschäftigt, wie sich Fehler an Eingabewerten auf das Ergebnis einer 
Rechnung auswirken.
Damit kann man quasi eine obere Grenze angeben, über die die Abweichung 
nicht hinausgeht. Für die 4 Grundrechenarten ist das relativ schnell 
vorgemacht:

Die Zahlendarstellung von Fließkommazahlen fängt ja da an ungenau zu 
werden, wo die Mantisse zu ende ist. Darüber lässt sich eine obere 
Abweichung angeben, wenn man eine beliebige Zahl als float darstellt - 
die bezeichnet man üblicherweise mit der Maschienengenauigkeit.
Dadurch wird aus einer Zahl a wenn sie als 32bit float dargestellt wird 
zB. die Zahl a(1+eps), wobei der Betrag von eps zB. für single float bis 
zu 1.196046e-07 beträgt (kann ja auch sein, das die Abweichung mal 0 
wird - größer als 1.196046e-07 wird sie aber nicht).

Die Abweichung für die einzelnen Werte werden üblicherweise über 
(r(x)-x)/x dargestellt, r(x) ist dabei der ungenaue Wert von x. Das 
sieht zB. so aus:

x(1+eps)-x/x = x*eps/x = eps -> ist die relative Abweichung wenn man x 
als float darstellt.

Bei der Addition sieht das dann so aus:

(x(1+eps1)+y(1+eps2) - x+y)/(x+y) = (x*eps1+y*esp2)/(x+y)
= eps1/(1+y/x) + esp2/(1+x/y)
(irgendwie scheinen die math tags net zu funzen)

Das Ergebnis muss man ein bisschen interpretieren: eps1 und 2 sind die 
Abweichungen für x und y, beide können sowohl negativ, als auch positiv 
sein. Es könnte also passieren, dass esp1+eps2=0, dann wäre das Ergebnis 
exakt.
Weil man das aber nicht weis rechten man mit dem schlimmsten, in dem 
Fall wäre das schlimmste eps1=eps2=1.196046e-07.
Die Aussage von der Gleichung ist nun, dass die Abweichung vom Ergebnis 
von den Eingabewerten abhängt. y/x wird maximal je größer y im vergleich 
zu x, für x/y ist's genau umgekehrt. Beide können sich im Bereich 
0..unendlich bewegen.
Für x=y ergibt sich zB. 1/2*eps1+1/2*eps2, also wenn man eps1 und 2 
maximal annimmt kommt wieder 1.196046e-07 raus - die Genauigkeit 
verschlechtert sich also durch die Addition 2 gleicher Zahlen nicht.
Für zB. x = 10y kommt eps1/1.1 + eps2/11 raus - im worst case auch eps.

Allgemein gilt also, dass die Addition (positiver) Zahlen die 
Genauigkeit nicht verschlechtert. Weichen die Eingangswerte um bis zu 
eps ab, weicht das Ergebnis auch um bis zu eps ab.


Für Subtraktion sieht das folgendermaßen aus:

( x(1+eps1)-y(1+eps2) - (x-y) ) / (x-y)
= (x*eps1-y*eps2)/(x-y)


Hier sieht die Sache schon anders aus. eps kann ja sowohl negativ, als 
auch positiv sein. Sei eps2=-eps1. Dann entspricht das

(x+y)*eps1/(x-y)

Im Fall x-y nahe 0 wird die Abweichung also ziemlich groß. Es ist daher, 
wenn man eine sehr genaue Rechnung braucht, eine schlechte Idee Floats 
ähnlicher Größe voneinander zu subtrahieren, dann kann sonstwas 
rauskommen. Gleiches gilt natürlich auch für die Addition von 2 
betragsmäßig gleichen, aber vorzeichenmäßig unterschiedlichen Zahlen.

Für Multiplikation:

(x*(1+eps1)*y*(1+esp2)-x*y)/(x*y)
= (1+eps1)(1+eps2) - 1 = 1+eps1+eps2+eps1*eps2 -1

Das kann man runden. eps1 und 2 sind schon sehr kleine Werte, eps1*eps2 
ist also noch viel kleiner, kann man weglassen

~ eps1+eps2

Bei der Multiplikation erhöht sich also die relative Abweichung. Aber um 
zB. um Faktor 10 ungenauer zu sein (also 1.2e-6 statt e-7) braucht's 
schon 10 Multiplikationen.

für Division:

(x*(1+esp1)/(y*(1+esp2) - x/y)/(x/y)
= (1+eps1)/(1+eps2)-1

im worst case (wieder eps1=-eps2)

= 2*eps1


Darauf aufbauend kannst du zB. für jede Rechnung die maximale Abweichung 
bestimmen. Für den Fall hier im Thread sind das zB. 2 Rechnungen

a=f*2^32
b=a/400e6

für a gilt, dass eps1 unbekannt ist (also worst case mit +1.2e-7 
annehmen) und eps2 0 ist (2^32 lässt sich exakt als float darstellen). 
Die Abweichung ist also zwischen -1.2e-7 und +1.2e-7.
Für die Division ist eps1 dem von eben, eps2 hatte ich mit -1.3e-8 
berechnet (weicht ja nach unten ab). Macht also schlimmstenfalls 1.29e-7 
- für alle f! Also egal ob man da 13 Milliherz oder 35 Gigaherz 
reinsteckt, die Abweichung bleibt stets unter 1.29-e7.
Wenn man den Bereich von f einschränkt (zB. auf 0..16MHz) kann man über 
eps von f noch genauere Aussagen machen, nämlich das die Abweichung in 
dem Bereich noch kleiner ist.

Desswegen sind floats so toll. Und da kann falk denen andichten was er 
will, die Abweichung ist trotzdem stets kleiner-gleich 1.29-e7 allgemein 
und 5.6e-8 im Bereich ganzzahliger Frequenzen bis 16MHz.

Bei doubles liegt eps übrigens im Bereich -2.2e-16 bis +2.2e-16.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ I_ H. (i_h)

>- für alle f! Also egal ob man da 13 Milliherz oder 35 Gigaherz
>reinsteckt, die Abweichung bleibt stets unter 1.29-e7.

Ja, die RELATIVE Abweichug ist bei Fliesskomma immer gleich, das war 
selbst mir minderbemitteltem E-Techniker bekannt. Siehe meine Postings. 
Ändert aber nix an der Tatsache, dass die ABSOLUTE Auflösung einer DDS 
Über den GESAMTEN Wertebereich konstant ist, im Beispiel ~0,01 Hz. 
Macht bei 16 MHz eine relative Auflösung von 0,01 Hz / 16 MHz = 
0,000000000625 = 0.00625e-7 und ist damit in der Anforderung höher als 
es eine 32Bit Fliesskommazahl bieten kann.

>Wenn man den Bereich von f einschränkt (zB. auf 0..16MHz) kann man über
>eps von f noch genauere Aussagen machen, nämlich das die Abweichung in
>dem Bereich noch kleiner ist.

Wieviel kleiner denn? Von 1.29e-7 auf 0.9e-7? So what, 23 Bit Mantisse 
sind nun mal nicht 32 Bit, da fehlen 9 Bit oder der Faktor 512.

>Desswegen sind floats so toll. Und da kann falk denen andichten was er
>will, die Abweichung ist trotzdem stets kleiner-gleich 1.29-e7 allgemein
>und 5.6e-8 im Bereich ganzzahliger Frequenzen bis 16MHz.

Hat nie jemand bestritten. Aber man erreicht nicht die theoretisch 
mögliche Auflösung, die ist um den Faktor 512 grösser. Und das ändert 
nix an der Überlegenheit von Festkommaarithmetik zur Lösung dieses 
Problems. Von den Compilerproblemchen mal abgesehen.

>Bei doubles liegt eps übrigens im Bereich -2.2e-16 bis +2.2e-16.

Schon klar. 1 / 2^N  wobei N die Bitanzahl der Mantisse ohne Vorzeichen 
ist.

MfG
Falk

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also gut, einen Beitrag schreib ich noch zu dir.

Du solltest vielleicht doch mal richtig hingucken und überlegen bevor du 
antwortest. Es ging um
U_INT32 ftw = frequency * 4294967296 / 400000000;

Was du gemacht hast, ist folgendes: Du hast dir die Rechnung in 64bit so 
zurechtgebogen, das du im Endeffekt auch Fließkomma gemacht hast - die 
Mantisse von der CPU, den Exponenten per Hand (es ist kein fixed point, 
beliest dich mal was fixed point bedeutet). Was dabei rausgekommen ist, 
ist, wie du es ja selber festgestellt hast, saumäßig ineffizient und 
viel zu groß. Mal ganz abgesehen davon, dass du auf 32MHz limitiert 
bist, wenn du 1/128Hz als Auflösung benutzt.

Ich kann dir auch gern die Routinen für 96bit long double mit 8bit 
Integern in C implementieren. Das dürfte dann ähnlich groß werden wie 
dein Code, benutzt einzig und allein Integer, und hat 'ne Auflösung 
jenseits von gut und böse. Der Praxiswert entspricht deinem Beispiel.
Im Endeffekt kannst du mit jedem Integer alles machen. Du kannst auch 
daherkommen und alles mit nand Operationen implementieren. Damit bist du 
noch viel genauer als mit 96bit, emulier einfach einen 128bit float. Es 
geht aber nicht um irgendwelche Operationen, sondern die, die dastehen.

Das der Integercode größer und langsamer als der float code ist, ist 
auch garkeine Überraschung. Das eine ist 'ne fertige, optimierte Lib, 
das andere C-Code.

Assembler ist immer schneller und kürzer als C. In Zeiten 
superskalarer Architekturen (ok, in der Zeit befinden wir uns seit 12 
Jahren... dann eben in Zeiten von realistischen 3-issue cpus) mit endlos 
langen Pipelines ist das Optimieren per Hand zwar alles andere als 
einfach, aber auch da schlägt man problemlos jeden Compiler. Auch den 
icc. Die Fähigkeit von 'nem Compiler (egal für welche ISA) liegt nicht 
darin, kurze, hochoptimierte Routinen auszuspucken - das hat bisher kein 
Compiler geschafft - sondern Megabytes von Code so aufeinander 
abzustimmen, dass die am schnellsten laufen. Da verliert jeder Mensch 
den Überblick.


Also nochmal zum ursprünglichen Problem: Offenslichtlich sind floats 
kürzer und schneller, und - bei seinem Beispiel ist die Frequenz auf 1 
Hz genau - auch genau genug, genauer als die einfache Rechnung mit 
Int64. Soll die Frequenz genauer sein nimmst du einfach doubles, die 
schaffen im Bereich bis 32MHz (dann läuft dir dein int64 über) 'ne 
Auflösung von 6.6e-9 Hz. Dagegen sind 1/128 Spielzeug, obwohl da auch 
mit 64bit gerechnet wird.


Der letzte Punkt: Deine Codebeispiel sind sinnlos. Weil: Du rechnest 
mit einem 40MHz DDS. Ich rechne, wie der Threadstarter, mit einem 
400MHz DDS (10mal so viel!).
Also bevor du dich jetzt hinsetzt, erstmal ein optimales Wertepaar mit 
einem brauchbaren Bereich bestimmst, die Frequenz die der DDS anzeigen 
soll noch umständlich umrechnest, und dann feststellst das die ganze 
Sache viel zu groß wird und es dann mit inline assembler implementierst 
(die Frequenz muss bei 1/128Hz zB. vor'm Funktionsaufruf erstmal 
geshifted werden), nimm einfach einen double wenn's 1/128Hz sein soll, 
sonst einen float.

Das hab ich im ersten Beitrag von mir zu dem Thema geschrieben. Jetzt 
hat's ca. 50 Beiträge gebraucht um das zu bestätigen.


PS das 32bit*32bit 32bit ergibt ist übrigens keine Schwäche vom 
Compiler, sondern von C... wie auch so ziemlich allen anderen 
verbreiteten Hochsprachen (und wahrscheinlich auch allen weniger 
verbreiteten).

Autor: der mechatroniker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> PS das 32bit*32bit 32bit ergibt ist übrigens keine Schwäche vom
> Compiler, sondern von C... wie auch so ziemlich allen anderen
> verbreiteten Hochsprachen (und wahrscheinlich auch allen weniger
> verbreiteten).

Da hast du einerseits recht. Laut C-Standard darf der Compiler bei einer 
Multiplikation 32x32 bit gar nicht das High-DWORD behalten, selbst wenn 
das Ergebnis danach in ein int64 gespeichert wird.

Da aber andererseits aus genau diesem Grund ständig Programmierer einen 
der beiden Operanden in ein int64 casten (bzw. eine Konstante gleich als 
ULL definieren), würde ich es nach Jahrzehnten der Compilerentwicklung 
eigentlich für selbstverständlich halten, daß die Datenflußanalyse 
erkennt, daß die High-DWORDS der Operanden null sein müssen (da ja 
gerade aus einem int32 konvertiert) und in diesem Fall tatsächlich eine 
32bit*32bit=64bit-Multiplikation erzeugen.

Daß dies nicht selbstverständlich ist, ist sehr wohl eine Schwäche des 
Compilers.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
I_ H. wrote:
> Es ging um
>
> U_INT32 ftw = frequency * 4294967296 / 400000000;
>
> Was du gemacht hast, ist folgendes: Du hast dir die Rechnung in 64bit so
> zurechtgebogen, das du im Endeffekt auch Fließkomma gemacht hast - die
> Mantisse von der CPU, den Exponenten per Hand (es ist kein fixed point,
> beliest dich mal was fixed point bedeutet).

Das ist Fixed Point. Dass man zwischen Berechnungen das Komma 
verschiebt um den Wertebereich möglichst gut auszunutzen ist 
selbstverständlich. Floating Point ist es, wenn die Position des Kommas 
von der Variablen abhängig ist.

> saumäßig ineffizient

Im Anhang eine Fixed Point-Version für die ursprüngliche Frage. Der 
ARM-GCC braucht dafür gerade mal eine Multiplikation und drei 
Additionen. Der maximale Fehler bis zur theoretischen Obergrenze von 200 
MHz ist 0.5; bei der float32-Version ist er 64.

Autor: der mechatroniker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hab mir gerade mal ein wenig vom avr-gcc generierten Assemblercode 
angeschaut, das ist ja zum Beklopptwerden:

x >> 8 mit long ergibt eine Registerumkopieraktion (sinnvoll)

x >> 9 mit long ergibt eine 9x durchlaufene Schleife über ">> 1". Die 
Schreibweise x >> 8 >> 1 ändert da ebensowenig etwas dran wie x >> 1 >> 
8.

Das Aufteilen von >>8 und >>1 in zwei Statements (igitt!) hat 
tatsächlich den gewünschten Effekt, mit einem kleinen Schönheitsfehler: 
Das Register, welches bei der Kopieraktion nullgesetzt wurde, wird beim 
>>1 trotzdem mitgeshiftet, selbst mit O3.

x >> 16 wird wieder als Aufforderung zum Registerkopieren erkannt.

Und das Beste zum Schluß:

Sämtliche Shifts mit long long -- egal wie konstant und wie durch 8 
teilbar der rechte Operand ist -- führen selbst mit -O3 stur zu einem 
Aufruf von __ashrdi3 (arghhh...)

Um es mal positiv auszudrücken: Sowohl die Shiftereien als auch die 
Behandlung des Datentyps long long im avr-gcc bieten Möglichkeiten zur 
weiteren Optimierung ;-)

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es ist schon lustig, wie ihr aneinander vorbei diskutiert.

Der eine guckt sich den relativen Fehler an, der andere den absoluten. 
Der eine rechnet mit 1 Hz Auflösung, der nächste mit 0.01 Hz. Der eine 
mit 40 MHz der andere mit 400 MHz.

Falk hat insoweit recht, wenn er sagt, das 23 Bit nicht genauer sein 
können als 32 oder 64 Bit,

I_ H. hat aber "mehr" recht, weil er ein sehr aufmerksamer Beobachter 
ist, Er hat nämlich in der originalen Aufgabe (korrekt) bemerkt, dass 
"frequency" nur 1-Hz-Schritte machen kann, da nicht skaliert.

Falk ging nicht von 400 MHz aus, sondern von 40 MHz, weil Falk aus der 
Praxis vermutet, dass die 400 MHz vermutlich ein Tipfehler bei der 
Anzahl der Nullen ist.

Für I_ H. ist alles von 99.5 bis 100.4999 Hz gleich 100 Hz. Denn mehr 
gibt der Input "frequency" auch nicht her.

Falk will bei 100 Hz aber minimal 99.995 Hz und maximal 100.004999 Hz, 
auch wenn die nächste Stufe erst wieder bei 100.995 bis 101.004999 Hz 
ist.

Und so geht es munter drüber und drunter.

Die theoretischen Ausführung von I_ H. sind, soweit ich sie überflogen 
habe, korrekt.

Vielleicht solltet ihr das Problem erst mal genauer definieren. Mit 
Wischi-Waschi-Angaben kommt man nicht weiter.

An diesem Beispiel sieht man wieder, dass Theorie und Praxis eben 
zusammen gehören. Dem Praktiker würde so manche Theorie gut tun, um 
überhaupt zu erkennen was sinnvoll ist und was nicht, und dem 
Theoretiker würde etwas Praxis gut tun, um zu erkennen dass die Aufgabe 
evtl. einfach falsch ist.

Ansonsten, für die Praxis ist es sehr, sehr oft das Einfachste, eine 
32-Bit-Multiplikation mit 64-Bit-Ergebniss zu machen und die unteren 32 
Bits einfach in die Tonne zu werfen und über das eine Bit Rundungsfehler 
unter den Tisch fallen zu lassen.

Der theoretisch begabte Praktiker würde aber noch weiter Denken und sich 
mal überlegen, ob die Taktquelle seines DDS-Generators wirklich ein OCXO 
besser als 10^-10 ist...

Der Pragmatiker würde mit seinem ARM einfach "double" verwenden wenn die 
Berechnung nur alle Jubeljahre nötig ist und hätte in der Zeit in der 
Theoretiker und Praktiker noch über eine simple Berechnung streiten das 
komplette Programm schon fertig geschrieben...

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn ihr unbedingt kompliziert rechnen wollt...
int32u ftw(int32u f)
{
  return (int32u) ((f>>8)*(pow(2.0f, 40.0f)/400e6))+(int32u) ((f&0xFF)*(pow(2.0, 32.0f)/400e6));
  
}

zur besseren Lesbarkeit mal mit rausgezogenen konstanten:
int32u ftw(int32u f)
{
  float const1=pow(2.0f, 40.0f)/400e6;
  float const2=pow(2.0, 32.0f)/400e6;
  
  uint32 ret=(f>>8)*const1;
  ret+=(f&0xFF)*const2;
  
  return ret;
}

Unübersichtlicher als double, benutzt aber nur 32bit Werte. Das shift-8 
und and 0xFF lässt sich auf'm 8bitter mit Byteschubserei erledigen, 1mal 
24bit*24bit + 1mal 8bit*24bit ist auf'm 8bitter theoretisch deutlich 
kürzer als 1mal 32bit*64bit (bzw. 32bit*32bit mit 64bit Ergebnis).
Und wenn die 400MHz 'n Tippfehler sein sollten kann er das einfach und 
schnell umändern.

Die Genauigkeit ist über den ganzen Bereich gleich der von int64 
(limitiert von f), das Potenzial ist aber größer. Wenn man die Float 
Multiplikation mit 2mal 16bit*24bit macht (also >>16 und &0xFFFF) geht's 
noch genauer. Dürfte auch noch schneller sein.


Vor allem in Anbetracht der Tatsache, dass float, wenn die Hardware 
nicht da ist, über Funktionsaufrufe abgewickelt wird und integer in 
place gemacht wird, ist es ganz einfach besser immer mit float/double zu 
rechnen.
Bei den ganzen Beispielen hier ging es nur um eine einzige Rechnung, bei 
der, wenn der Code nicht handoptimiert ist (asm), float schon kürzer 
ist.

Wenn's nun aber noch mehr zu rechnen gibt (zB. weil der User die 
Frequenzen für den DDS in 1/100stel und nicht 1/128 Schritten festlegen 
soll) ändert sich an der Programmgröße wenig.
Die Bit- und Byteschubserei von Falk muss man jedesmal neu und anders 
implementieren, sprich das braucht jedesmal Speicher.
Floats und Doubles sind so allgemeingültig, dass sich nur die Werte der 
Rechnung verändern. 'ne Routine für float mul kann dann aber von allen 
Rechnungen gleichermaßen benutzt werden.
Und wenn es 20 Rechnungen gibt darf Falk das 20mal in Assembler 
aufschreiben, weil der GCC den Code nicht so gut hinbekommt (was kein 
Wunder ist - die Zeiten der Bitschieberreien sind auf allen 
Architekturen auf denen der GCC ernsthaft zum Einsatz kommt schon ewig 
vorbei, auf x86 sind 32bit Rechnungen zB. schneller als 8bit Rechnungen 
- da der gcc nur für den x86 protected mode compiliert hat der die 
Bitschieberzeiten garnet mitbekommen, so wie jeder Compiler der heute 
noch ersthaft im Einsatz ist).


PS Die große böse Theorie da oben ist übrigens noch sehr praxisnah, 
richtige Theorie sieht anders aus... ein echter Mathematiker würde das 
garnet anfassen ;).

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
mal'n Beispiel:
double freq;

void sendFreq(double f)
{
  send2DDS(f*4294967296.0 / 400000000.0);
}

void parseInput
{
  // user wants to increase freq by 0.01
  if(..) freq+=0.01;
  
  // decrease by 0.01
  if(..) freq-=0.01;

  // increase by 1
  if(..) freq+=1;

  // dec by 1
  if(..) freq-=1;

  // send freq to dds
  if(..) send2DDS(freq);
}

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
I_ H. wrote:
> Bei den ganzen Beispielen hier ging es nur um eine einzige Rechnung, bei
> der, wenn der Code nicht handoptimiert ist (asm), float schon kürzer
> ist.

Hast du gelesen was ich geschrieben habe?

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Unbekannter (Gast)

>Es ist schon lustig, wie ihr aneinander vorbei diskutiert.

>Der Pragmatiker würde mit seinem ARM einfach "double" verwenden wenn die
>Berechnung nur alle Jubeljahre nötig ist und hätte in der Zeit in der
>Theoretiker und Praktiker noch über eine simple Berechnung streiten das
>komplette Programm schon fertig geschrieben...

Amen. ;-)

MFG
Falk

Autor: der, der das alles hier verursacht hat (Ruuud) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

wollte mich nochmal für die große Resonaz auf mein Frage bedanken.
Ich hab zwar nicht alles Verstanden was ihr da geschrieben habt aber ich 
denke es reicht aus um meinen DDS-Chip richtig zu programmieren....

ach, 400 Mhz war kein Tippfehler

@ Falk

kommst du eigentlich aus dem Schwabenland ;-)

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ der, der das alles hier verursacht hat (Ruuud) (Gast)

>ach, 400 Mhz war kein Tippfehler

OK, ändert an meinen Aussagen aber nix prinzipielles.

>@ Falk
>kommst du eigentlich aus dem Schwabenland ;-)

???
Warum?

MFG
Falk

Autor: eProfi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
für eine Ausgangsfrequenz von z.B. 12,345678MHZ braucht man das FTW von
12345678*2y32/4e8=132560708,14236672 (0x07E6B744).

Und wie berechnet man diesen Wert? Mit einer 32x32-Bit-Mul, wie ich sie 
schon in Beitrag "Rechnen mit AVR" beschrieb.
Das ist doch exakt dieselbe Problemstellung, nur statt 180MHz 400MHz.

Die Berechnung dauert auf einem 20MHz 8-Bit-AVR knappe 5µs incl.Loads 
etc. Auf einem 32-Bitter deutlich unter 1µs.

                                        dez         hex
Gewünschte Frequenz in Hz            12345678 = 0x00BC614E
mit 16 skaliert (1/16Hz Auflösung)  197530848 = 0x0BC614E0
mit 2y28 skal.Umrechnungsfaktor    2882303762 = 0xABCC7712 
(2y32/4e8*2y28=2y60/4e8=2882303761,51711744)
beide multipliziert                     0x07E6B7442A2197C0
                                          ========
                                          07e6b744

Und was sehen wir, wenn wir die oberen 32 Bits des Ergebnisses 
anschauen?
Ding-Dong, das gesuchte FTW.
Beachte: wenn man vorher klug skaliert und eine passende union 
verwendet, braucht man fast nicht mehr schieben, sondern verwendet 
einfach das Upper-Longword.


also:
#define LO 0  //je nach Endianess
#define HI 1
#define LOLO 0
#define LOHI 1
#define HILO 2
#define HIHI 3
union {U_INT64 U64;U_INT32 U32[2];U_INT16 U16[4];} ftw;
U_INT32 frequ;   //in Hz
U_INT32 frequ16; //in 1/16tel Hz (0..268.435455,9375 Hz), also mehr als 
die halbe Basisfrequenz


frequ16 = frequ * 16;
ftw.U64 = frequ16 * 0xABCC7712ULL; //32x32->64-Bit-Mul, hoffentlich 
erkennt er es als solche, ansonsten ULL statt UL
send2DDS(ftw.U32[HI]);
bzw.
send2DDS(ftw.U16[HIHI],ftw.U16[HILO]); //in 16-Bit-Häppchen mundgerecht 
für die Übertragung, falls diese mit 16 Bits geschieht.

Sonst noch Fragen, I_ H. ?


Da stellen sich aber mir noch ein paar Fragen:
- muss es denn gerade 400 MHz Basisfrequenz sein? Hier ein Vielfaches 
von 2 verwendet, und die Berechnung reduziert sich auf ein Geschiebe.

- warum überhaupt den Umweg über die Frequenz nehmen? Das ftw ist doch 
proportional zur Frequenz. Wenn man diese z.B. um 1 Hz erhöhen will, 
kann man genauso gut 10,73741824 zum ftw addieren, natürlich wieder in 
Festkomma-Arithmetik:
ftw.U64 += 0xABCC77118; //32Vorkomma.32Nachkommabits

Oder um einen Halbton höher (*1,059463094359295):
ftw.U64 = ftw.U32[HI] * 0x10F38F92EULL;
Oder um einen Halbton tiefer (/1,059463094359295 = *0,9438743126816935):
ftw.U64 = ftw.U32[HI] *  0xF1A1BF39ULL;

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ eProfi (Gast)

>Sonst noch Fragen, I_ H. ?

>proportional zur Frequenz. Wenn man diese z.B. um 1 Hz erhöhen will,
>kann man genauso gut 10,73741824 zum ftw addieren, natürlich wieder in
>Festkomma-Arithmetik:

There are just 10 kinds of people in the world. Those who understand 
binary and those who don't.

SCNR
Falk

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.