Forum: Mikrocontroller und Digitale Elektronik 1 Durch Division in uC


von Simon B. (Gast)


Lesenswert?

Gibts eine möglichkeit (zwecks frequenzmessung) 1/x zu dividieren?

Ich habe die Taktlänge T, welche sich zwischen 6 und 100 *10^-3 
bewegt...
Eigentlich währ das für mich sehr wichtig, weil ich die Frequenz nicht 
jede sekunde messen wollte...Dann hätte ich zwar direkt die Frequenz, 
jedoch ein relativ ungenaues Ergebnis.



Weiß jemand eine Lösung für das Problem?

von Simon B. (Gast)


Lesenswert?

Achso, dabei handelt es sich um einen mega8/32. Das ganze sollte in ASM 
erledigt werden..

von Bereits F. (Firma: D.ade) (bereitsfort)


Lesenswert?

zähle die impulse pro zeiteinheit und multipliziere auf die secunde
dann brauchst du nicht dividieren je größere die Torzeit und damit der 
zählerstand am ende der messung desto genauer die messung.

bei messung der Periodendauer und anschließender umrechnung kannst du 
entweder mit C-Routinen arbeiten , oder in asm mit rechtsshift + compare

bestimmt gibt es auch Floatingpointdivisionsroutinen in ASM aber das ist 
meines Wissens recht umständlich

von Aike T. (biertrinker)


Lesenswert?

Hi,

wo ist denn das Problem dabei? Floating-Point? Du könntest ja einfach 
z.B. 100/x rechnen statt 1/x, dann kannst du die nötige Genauigkeit ja 
auch selber anpassen und bekommst kein Ergebnis >1.
Dann musst du nur die Interpretation entsprechend anpassen.

viele Grüße

Biertrinker

von Bereits F. (Firma: D.ade) (bereitsfort)


Lesenswert?


von Simon B. (Gast)


Lesenswert?

Also am interessantesten ist wohl rechtsshift und compare (wähle ich mal 
so).

Wie soll das funktionieren?


...

von Thorsten (Gast)


Lesenswert?

Du könntest das ganze auch iterativ lösen. Für 1/b gilt die folgende 
Iteration:

x(i+1) = x(i) * (2 - b*x(i))

x konvergiert dabei gegen 1/b. Einzige Voraussetzung ist dabei, wenn ich 
mich nicht irre, dass der Startwert x(0) <= 1/b sein muss.

von Bereits F. (Firma: D.ade) (bereitsfort)


Lesenswert?

ies den link von 13.01

da wirds genau beschrieben

Beitrag "Re: 1 Durch Division in uC"

eben iterativ



http://www.avr-asm-tutorial.net/avr_de/quellen/div8d.asm

von Simon B. (Gast)


Lesenswert?

Joi,

das habe ich mir auch angeschaut, aber so richtig blick ich da nicht 
durch :(

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Bereits Fort wrote:
> ies den link von 13.01
>
> da wirds genau beschrieben
>
> Beitrag "Re: 1 Durch Division in uC"
>
> eben iterativ
>
> http://www.avr-asm-tutorial.net/avr_de/quellen/div8d.asm

Nein, was dort implementiert ist, ist die normale "Schuldivision", wie 
man sie per Papier & Bleistift macht.

Der iterative Ansatz verwendet die Funktion
die in 1/b einen Fixpunkt hat. Für
ist die Funktion eine Kontraktion, so daß eine Iteration mit Startwerten 
aus dem Intervall zum Fixpunkt 1/b konvergiert.

http://de.wikipedia.org/wiki/Fixpunktsatz_von_Banach

von Simon B. (Gast)


Lesenswert?

Oder sollte ich alles 3 stellen im komme nach links verschieben?

Dann sollte das wohl klappen ;)

von yalu (Gast)


Lesenswert?

@Thorsten:

Hast du zufälligerweise mal mit C30/C40-DSPs von TI gearbeitet, dass
du auf diese Idee gekommen bist? Dort wurde nämlich genau dieses
Verfahren angewendet, um einen 32-Bit-FP-Kehrwert zu bilden. Es gab
dort einen Befehl, der per Tabelle eine etwa 8 Bit genaue Näherung
geliefert hat. Schon nach zwei Iterationschritten hatte man die für
die 32-Bit-FP-Darstellung erforderliche Genauigkeit erreicht. Mit
einem ähnlichen Verfahren konnte man auf diesen DSPs auch
Quadratwurzeln sehr schnell berechnen.

> Einzige Voraussetzung ist dabei, wenn ich mich nicht irre, dass der
> Startwert x(0) <= 1/b sein muss.

Ich würde sagen, dass der Startwert zwischen 0 und 2/b liegen muss.

Der Algorithmus konvergiert sehr schnell: mit jedem Iterationsschritt
wird die Anzahl der genauen Stellen des Ergebnisses fast verdoppelt.

Da auch ein ATmega eine schnelle Integer-Multiplikation hat, würde
sich das Verfahren dort prinzipiell ebenfalls anbieten, vor allem für
höhere Genauigkeiten (16 oder 32 Bit). Allerdings ist bei Integer-
zahlen der Zugriff auf die Tabelle nicht so leicht, da der relative
Fehler der Startwerte über den gesamten Wertebereich möglichst klein
sein sollte und deswegen die Indizierung nichtlinear erfolgt. Bei
Zahlen, die im normierten FP-Format vorliegen, hat man dieses Problem
nicht.

Aber zurück zum Topic:

Solange das noch niemand gewinnbringend auf dem AVR implementiert hat,
ist es für Simon sicher das Einfachste, die klassische Bitschieberei-
division zu einzusetzen, wie sie auf den bereits genannten Webseiten
beschrieben ist. Von Atmel gibt es irgendwo eine Appnote mit
Divisionsalgorithmen für unterschiedliche Bitbreiten, wahlweise auf
Geschwindigkeit oder Codegröße optimiert.

> Oder sollte ich alles 3 stellen im komme nach links verschieben?

So ähnlich. Liefert der Zähler, der die Länge einer Periode misst, den
wert t, dann rechnest du einfach f = a/t. Dabei ist a eine feste
Konstante, die vom Wertebereich von t und von der Einheit des
Ergebnisses abhängt. Je nachdem, wie groß a und t sind und wie genau
das Ergebnis sein soll, benötigst du einen Divisionsalgorithmus für 8,
16 oder 32 Bit.

von Simon B. (Gast)


Lesenswert?

Ich merke schon, dass Divisionen sehr kompliziert sind ;)
Ich werde mich mal duchwurschteln und zur not nachfragen...

Ich hatte nämlich ein ganz anderes Problem, nämlich einen 
Frequenzmesser.
Der funktioniert nun Prima und zwecks genauigkeit wollte ich halt die 
Taktlänge messen und nicht 1s lang flanken zählen.

von Hagen R. (hagen)


Lesenswert?

>Hast du zufälligerweise mal mit C30/C40-DSPs von TI gearbeitet, dass
>du auf diese Idee gekommen bist? Dort wurde nämlich genau dieses
>Verfahren angewendet, um einen 32-Bit-FP-Kehrwert zu bilden. Es gab

ist trivial, nennt sich Newton Iteration und ein bekanntes Verfahren in 
der Computer Arithmetik. Auf dem AVR hat es allerdings keinen Vorteil 
gegenüber einer Schoolboy Divison bis auf die Ausnahme das wenn man die 
Berechnung des Reziproken nur einmalig durchführen kann und anschließend 
mehrfach mit diesem Kehrwert und der HW-Multiplikation der ATmega eine 
Division durchführt. Wenn man also zb. mehrmals durch X dividieren 
möchte kann man einmalig das Reziproke von X = 1/X per Newton Iteration 
ausrechnen und dann jede Divison durch eine Multiplikation mit 1/X 
ersetzen. Wenn der AVR die HW-MUL unterstützt ist dies performanter als 
die Schoolboy Divison jedesmal durchzuführen. Für einen 8 Bit Wert 
benötigt man bei der Schoolboy Methode max. 8 Iterationen aus 
Subtration/Branch/Shift, bei der Newton Iteration max. 3 Iterationen aus 
Subtration/Multipliaktion. Man gewinnt also aus Sicht der benötigten 
Takte nicht sehr viel auf einem AVR.

>Ich hatte nämlich ein ganz anderes Problem, nämlich einen Frequenzmesser.
>Der funktioniert nun Prima und zwecks genauigkeit wollte ich halt die
>Taktlänge messen und nicht 1s lang flanken zählen.

Musst du ja auch nicht. Du kannst auch die Zeitspanne zwischen den 
Flanken per Input Capture messen und wenn dein MCU Takt zb. 2^x Hz ist 
kannst du einfach mit Links/Rechtsshifts die Multiplikation/Division 
durchführen um auf zb. 1 Sekunde zu normalisieren.

Eine andere Möglichkeit ist es den Timer T1 durch dein Meßsignal zu 
takten. Parallel dazu den 2. Timer so einstellen das er nach exakt 1 
Sekunde ein Interrupt auslösst. Dann hast du im Counter T1 die Anzahl 
der Takte deines Meßsignales in 1 Sekunde, was der Frequenz des Signales 
entspräche.

Gruß Hagen

von Bernd (Gast)


Lesenswert?

... Divisionsalgorithmen ...

In welcher Applikationsnote von Atmel werden die oben genannten 
Algorithmen beschrieben?

von Christoph db1uq K. (christoph_kessler)


Lesenswert?


von yalu (Gast)


Lesenswert?

@Hagen Re:
> ist trivial, nennt sich Newton Iteration und ein bekanntes Verfahren
> in der Computer Arithmetik.

Wo das Vefahren herkommt, ist mir schon klar, das wurde ja schon in
der Schule gelehrt. In der Computerarithmetik habe ich es bisher aber
noch nicht oft gesehen. Hast du vielleicht ein paar Beispiele für
Prozessoren oder Laufzeitbibliotheken, die für die Division ebenfalls
das Newton-Verfahren verwenden?

von Bernd (Gast)


Lesenswert?

Hallo Christoph,

vielen Dank für den Link!

Bernd

von Hagen R. (hagen)


Lesenswert?

Fast alle Langzahl Bibliotheken benutzen Newton. Nicht nur zur Division 
sondern auch für Wurzel, transzendente Konstanten usw. zb. HPFloat, GMP, 
Miracl und auch mein DECMath. Newton wird häufig benutzt weil sie eine 
quadratische Konvergenz hat, dh. man nähert sich mit quadratischer 
Geschwindigkeit dem finalen Ergebnis und oft kann man mit reinen 
Multiplikationen/Quadrierungen arbeiten die sehr schnell sind im 
Vergleich zu Divisionen. In meinem DECMath benutze ich Newton zb. zur 
Berechnung des modularen multiplikativen Inversen wobei der Modulus 2^k 
ist, also x = y^-1 mod 2^k. Oder zur Berechnung der modularen 
Quadaratwurzel, also a = b^1/2 mod 2^k wobei mit 2-adischen Zahlen 
gerechnet wird und es gilt (a^2 * b) mod 2^k == 1 mod 2^k.
Ich kenne mich aber nur in diesem Bereich konkret aus, also der 
Berechnung mit super großen Zahlen auf PCs.

Auch viele andere Algortihmen sind an Newton angelehnt, bzw. 
Erweiterungen davon. zb. "Fast Recursive Division" nach Christoph 
Burnikel & Joachim Ziegler, MPI-I-98-1-022, October 1998, 
Forschungsbericht,  Max Planck Institut für Informatik. Dieser 
Algortihmus implementiert die schnelle rekursive Karatsuba Divison 
aufbauen auf Subtraktionen und Multiplikation und arbeitet letzendlich 
ebenfalls wie Newton benutzt aber auch noch den Karatsuba Trick.
Oder Wurzel: INRIA, "Karatsuba Square Root" by Paul Zimmermann Research 
Report No 3805, file: RR-3805.ps, zur Berechnung der Wurzel.

Aber grundsätzlich nutzt man Newton zur Berechnng des 
Kehrwertes/Reziproken um dann nachfolgende, in den eigenen Berechnngen, 
langsammere Division mit schneleren Multiplikationen zu ersetzen. Es ist 
also eine Precomputation des Kehrwertes die nur dann Sinn macht wenn das 
Verhältnis des Aufwandes für diese Precomputation wesentlich kleiner ist 
als für die später stattfindenen Divisionen die durch Multipliaktionen 
ersetzt werden sollen. Deswegen sagte ich ja das dies auf einem AVR 
selten Sinn macht.

Gruß Hagen

von A. Einstein (Gast)


Lesenswert?

>Aber grundsätzlich nutzt man Newton zur Berechnng des
>Kehrwertes/Reziproken um dann nachfolgende, in den eigenen Berechnngen,
>langsammere Division mit schneleren Multiplikationen zu ersetzen.

Newtonverfahren = Tangentenverfahren (geometrisch).

Gruss A. Einstein

von yalu (Gast)


Lesenswert?

> Fast alle Langzahl Bibliotheken benutzen Newton.

Ah, dort wird das also auch noch verwendet.

> Newton wird häufig benutzt weil sie eine quadratische Konvergenz
> hat, dh. man nähert sich mit quadratischer Geschwindigkeit dem
> finalen Ergebnis und oft kann man mit reinen Multiplikationen/
> Quadrierungen arbeiten die sehr schnell sind im Vergleich zu
> Divisionen.

Ja, das ist nachvollziehbar.

Vielen Dank für die Info :)

> Aber grundsätzlich nutzt man Newton zur Berechnng des Kehrwertes/
> Reziproken um dann nachfolgende, in den eigenen Berechnngen,
> langsammere Division mit schneleren Multiplikationen zu ersetzen.

Dass man bei mehreren Divisionen durch den gleichen Divisor am besten
erst den Kehrwert des Divisors bildet, so dass man anschließend nur
noch multiplizieren muss, ist klar. Aber das hat doch eigentlich
nichts mit dem Newton-Verfahren zu tun, man kann die Kehrwertbildung
doch genauso gut per Schuldivision oder mit einem beliebigen anderen
Verfahren durchführen. (?)

von Hagen R. (hagen)


Lesenswert?

>nichts mit dem Newton-Verfahren zu tun, man kann die Kehrwertbildung
>doch genauso gut per Schuldivision oder mit einem beliebigen anderen
>Verfahren durchführen. (?)

Korrekt, aber um noch schneller zu sein ersetzt man nun diese 
Precomputation der Division, also Berechnung des Kehrwertes auch noch 
durch schnellere Verfahren, eben 1/X ohne Divisionen sondern mit 
Multiplikationen durch die Newton Iteration. Genauer gesagt: man 
benötigt eine Eingangs-Division die aber mit wesentlich kleineren Zahlen 
arbeitet und eine Approximation des Ergebnisses darstellt. Die 
restlichen fehlenden Bits, also der überwiegende Teil für die zu 
erreichende Genauigkeit, wird dann durch Multiplikationen etc.pp. 
ausgerechnet. Im Grunde arbeitet sogar D.Knuth Division oder die Barret 
Reduktion ebenfalls nach dieser Methode.

Das alles sind annerkannte und auch oft angewendete Verfahren, qausi 
Grundlagenwissen, die man aber in den Tiefen jeder numerischen 
Bibliothek suchen muß. Ein Anwender solcher Bibliotheken erkennt dieses 
Wissen immer erst dann wenn er bis an die Basics diese Bibliotheken zu 
verstehen versucht.

Das Ziel ist immer das Gleiche: Performance.

Anderes Beispiel: bekannt ist was man mit FFTs so alles machen kann, 
weniger bekannt ist das man mit der FFT auch in der Numerik bei den 
Multiplikationen/Quadrierungen diese FFTs anwendet. Man multipliziert 
asymptothisch am performantesten zwei Zahlen mit der FFT, genauer gesagt 
mit der modularen Fermat Fast Fourier Transformation nach A. Schönhage 
und S. Strassen.

Gruß Hagen

PS: ich habe fast 4 Jahre an diesem Thema im Hobby gearbeitet um das 
alles zu verstehen und auch real zu implementieren. Ok, darin enhalten 
sind natürlich auch noch so alles was es zum Thema Kryptographie, 
hauptsächlich asymmetrische, zu wissen und zu implementieren gibt.

von Christoph db1uq K. (christoph_kessler)


Lesenswert?

Wenn ich in Ganzzahlarithmetik einen 32 Bit Kehrwert bilden will, muß 
ich dann 2^64 (oder 2^63?) durch die 32 bit-Zahl teilen? Das wäre dann 
ein 64 Bit-Divisor, wenn auch ein sehr einfacher. Oder gibt es einen 
Trick um mit 32/32 Bit auszukommen?
Mit 64/32 klappte das jedenfalls in meinem ersten Versuch, einen 
hochauflösenden Reziprokzähler zu programmieren. Die 32/32-Bit-Routine 
von A.Birua ließ sich einfach auf 64/32 erweitern.

von Hagen R. (hagen)


Lesenswert?

hängt nur von deiner zu realisierenden Genauigkeit ab. Du kannst auch 
16/32 Reziproke erzeugen mit dann maximal 16 Bit Genauigkeit in den 
nachfolgenden Operationen. Diese Reziproke arbeiten dann meistens in 
modularen Ringen zu zb. 2^16.

Möchtest du per Reziprok also zb. 64 Bit Zahlen dividieren mit einer 64 
Bit Genauigkeit dann sollte das Reziproke auf 64 Bit genau sein, 
logisch. Die eigentliche Divisionsoperation (per Multiplikation) erzeugt 
dann Zwischenergebnisse die 128 Bit groß sein können. Also alle deine 
Basisoperationen benötigen dann intern eine Auflösung von mindestens 128 
Bit.
Logisch, 2^x*2^y==2^(x+y)

Gruß Hagen

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.