|
Anzeige
|
1 Durch Division in uC
Gast
#958087
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?
Gast
#958090
Achso, dabei handelt es sich um einen mega8/32. Das ganze sollte in ASM erledigt werden.. 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 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
Gast
#958101
Also am interessantesten ist wohl rechtsshift und compare (wähle ich mal so). Wie soll das funktionieren? ...
Gast
#958228
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. 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
Gast
#958302
Joi, das habe ich mir auch angeschaut, aber so richtig blick ich da nicht durch :( 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
Gast
#958322
Oder sollte ich alles 3 stellen im komme nach links verschieben? Dann sollte das wohl klappen ;)
Gast
#958349
@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.
Gast
#958449
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. >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
Gast
#958579
... Divisionsalgorithmen ... In welcher Applikationsnote von Atmel werden die oben genannten Algorithmen beschrieben? http://www.mikrocontroller.net/articles/AVR_Arithmetik http://users.i.com.ua/~birua/math32.html da gibts eine 32-Bit-Division für AVR in Assembler, die Atmel-Applikation geht nur bis 16 Bit http://www.atmel.com/dyn/resources/prod_documents/doc0936.pdf http://www.atmel.com/dyn/resources/prod_documents/AVR200.zip AVR200: Multiply and Divide Routines
Gast
#958694
@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?
Gast
#958743
Hallo Christoph, vielen Dank für den Link! Bernd 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
Gast
#958783
>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
Gast
#958789
> 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. (?) >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. 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. 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 Antwort schreibenBitte melde dich an, um einen Beitrag zu schreiben. |
Anzeige
|
