Huhu, analog zu meinem vorhergehenden Problem: Wieder einmal eine Meinungssuche. Ziel ists, eine 80-Bit-Festkommazahl (40.40) durch eine ebensolche Zahl zu dividieren, und zwar auf dem AVR. Folgende Ideen habe ich: - schnelle Schuldivision - Newton-Verfahren (Nullstelle suchen, also quasi Newton-Raphson), dann mit dem Kehrwert multiplizieren - Goldschmidt-Erweiterungsverfahren Die Schuldivision wäre prinzipiell am einfachsten, allerdings komme ich mit den Registern in Bedrängnis: In 10 Registern rotiert der Rest, 10 bräuchte ich für den Divisor und 10 für den Dividenten. Wobei für letzteren nochmals 10 weitere Register nötig sind, da ich ja vorher erweitern muss, damit die Nachkommastellen nicht verloren gehen. Alternativ alles im SRAM vorhalten und mit Zeigern arbeiten, allerdings würde das die Laufzeit vervielfachen, was mir irgendwie misfällt. Beim Newton-Verfahren müsste ich den Dividenten in den Bereich von 0.5 und 1 bringen, letztlich also rechtsschieben. Dabei geht doch wieder jede Menge Genauigkeit verloren, oder? Mit Goldschmidt habe ich mich zugegebenermaßen noch nicht weiter auseinandergesetzt. Das Prinzip kenne ich, nicht aber dessen Umsetzung auf 8-Bit-Hardware. Was also tun? Vielen Dank und Gruß, Sven
> schnelle Schuldivision Ich würde mal schauen ob du da nicht ggf. einztelne Teile der Rechnung Zeitweise in den RAM auslagern kannst (push/pop). (btw: gibt es auch eine langsame? ;) > Newton-Verfahren > Beim Newton-Verfahren müsste ich den Dividenten in den Bereich von 0.5 > und 1 bringen, letztlich also rechtsschieben. Dabei geht doch wieder > jede Menge Genauigkeit verloren, oder? mach halt ne 1.79 Zahl draus. > mit dem Kehrwert multiplizieren Wie bestimmst du den den Kehrwert? Wenn dir das einfach gelinngt dann nutzt das doch gleich un stat 80/80 rechnest du 80 * 1/80 ...
Läubi .. schrieb: >> schnelle Schuldivision > Ich würde mal schauen ob du da nicht ggf. einztelne Teile der Rechnung > Zeitweise in den RAM auslagern kannst (push/pop). (btw: gibt es auch > eine langsame? ;) Welche denn? Ich brauche sie ja allesamt in jedem Durchlauf des Algorithmus'. Allein das Rotieren würde dann in ein endloses ldd+ror+std ausarten. >> Newton-Verfahren >> Beim Newton-Verfahren müsste ich den Dividenten in den Bereich von 0.5 >> und 1 bringen, letztlich also rechtsschieben. Dabei geht doch wieder >> jede Menge Genauigkeit verloren, oder? > mach halt ne 1.79 Zahl draus. Wenn schon, dann eine 0.80-Zahl. Hm. >> mit dem Kehrwert multiplizieren > Wie bestimmst du den den Kehrwert? Wenn dir das einfach gelinngt dann > nutzt das doch gleich un stat 80/80 rechnest du 80 * 1/80 ... Das Newton-Verfahren dient der Bestimmung des Kehrwertes.
Was willst du denn da eigentlich dividieren - die Anzahl der Atome in unserer Galaxis / Anzahl der Sonnensysteme im Universum?? ;-)
Sven P. schrieb: > Alternativ alles im SRAM vorhalten und mit Zeigern arbeiten, allerdings > würde das die Laufzeit vervielfachen, was mir irgendwie misfällt. Warum? Hast Du überhaupt mal abgeschätzt, wie schnell Du die Division brauchst? Es lohnt nicht, irgendwas zu optimieren, wenn es keinen merkbaren Effekt hat. Peter
Sven P. schrieb: > Ich brauche sie ja allesamt in jedem Durchlauf des > Algorithmus'. Allein das Rotieren würde dann in ein endloses ldd+ror+std > ausarten. Jo, du setzt kurz deinen X-Zeiger, und dann ne schleife ld r16, X ror r16 st X+,r16 das ganze 10 mal, dauert doch nicht so lang.
Peter Dannegger schrieb: > Sven P. schrieb: >> Alternativ alles im SRAM vorhalten und mit Zeigern arbeiten, allerdings >> würde das die Laufzeit vervielfachen, was mir irgendwie misfällt. > > Warum? > Hast Du überhaupt mal abgeschätzt, wie schnell Du die Division brauchst? Ja schon, es ist mir auch bewusst, dass das immer noch schnell genug ist, das ist nicht das Problem. Die Sache ist damit schon schnell umgesetzt, allerdings interessierts mich halt, ob da nicht noch irgendwie eine anderer Ansatz exisitert. Rein aus Interesse an der Sache. > Es lohnt nicht, irgendwas zu optimieren, wenn es keinen merkbaren Effekt > hat. Jo.
Sven P. schrieb: > allerdings interessierts mich halt, ob da nicht noch > irgendwie eine anderer Ansatz exisitert Mein Ansatz: 1) Ich suche mir die ersten paar signifikanten Stellen, z.B. 16bit, dann bin ich im schlimsten Fall im zweiunddreißigstel Promille Bereich mit meiner Abweichung von ursprünglichen wert. 2) Dann nehme ich die normale Fließkommabibliothek meines Compilers. 3) Fertig. Viel schneller wird's wohl nicht gehen. (Was die Umsetzung betrifft.) Jetzt kommt sicher eine tolle Begründung, warum Du 80 signifikante Stellen brauchst? Oder soll das nur eine theoretische Übung sein?
Horst schrieb: > Jetzt kommt sicher eine tolle Begründung, warum Du 80 signifikante > Stellen brauchst? Oder soll das nur eine theoretische Übung sein? Das soll eine Studie sein und ein kleiner Tischrechner werden. Ein bisschen rumeiern und Fließkomma und solala kann ich auch alleine, dafür hätte ich hier nicht nachgefragt. PS: Das ist auch irgendwie typisch hier. Ich bin 22 Jahre alt, meines Erachtens weder ganz blöde noch minderbemittelt, also kurzum schon einigermaßen in der Lage, zu beurteilen, warum und wieso ich ein Problem habe und lösen möchte. Verzeihung. Also ja, wenn es hilft, es soll eine 'theoretische Übung' sein.
In diese Richtung ging auch meine Bemerkung weiter oben.... Ich kann mir einfach keinen vernünftigen Anwendungsfall vorstellen! Die einzigen 80 Bit Zahlen, die ich kenne, sind Fließkommazahlen mit Mantisse und Exponent in den 80 Bit.... Aber als zahlentheoretische Programmierübung ist es natürlich möglich...ich persönlich würde da aber lieber was "Vernünftiges" programmieren. Also nix für ungut!
Sehs doch mal anders: Das Festkommaformat ist 40.40, also jeweils 40 Vor- und Nachkommastellen. Vorne steht noch die Zweierkomplement-Darstellung dran, also 39 Bit. Das ergibt dezimal einen Wertebereich von etwa +-549755813888, also etwa 11,5 Stellen. Mein TI30 (Taschenrechner) rechnet insgesamt (Vor+Nachkomma) mit zehn Stellen, dafür aber mit einem laut Handbuch etwas unkonventionellen Fließkommaformat. So weit weg sind die 80 Bit wirklich nicht. Zumal ich es ganz und garnicht leiden kann, wenn ich mit einem Rechner arbeite, der zwar irgendwelche Ergebnisse ausspuckt, ich aber hinten und vorne nicht weiß, wie falsch diese denn sind. Bei dem 40.40-Festkommaformat hab ich einen klar definierten Wertebereich, in dem exakt gerechnet wird, fertig. Keine denormals, keine Lücken.
Nach einiger Spielerei habe ich mal einen Dividierer zusammengeflickt (siehe Anhang). Nach ersten Tests scheint der auch zu funktionieren, nur gefällt mir die Übergabe des Y-Zeigerregisters nicht so recht. Da arbeite ich momentan noch mit festen Adressen (push+pop nur, weil das Y-Register gleichzeitig für ein Arbeitsregister gebraucht wird); 'www' ist die Speicherstelle im SRAM, an der sich der Divisor befindet. Da ich die Sache aber lieber schön gekapselt und komplett auf dem Stack hätte, misfällt mir eine feste Speicherstelle, um Y zwischenzuspeichern, auch :-/
> Bei dem 40.40-Festkommaformat hab ich einen klar definierten > Wertebereich, in dem exakt gerechnet wird, fertig. Keine denormals, > keine Lücken. Das erkaufst du dir jedoch mit anderen Problemen durch die enge Begrenzung des Wertebereichs. Für viele Rechnungen in schon kleinen Zehnerpotenzen völlig unbrauchbar. Der VWLer kann nichtmal die Staatsschulden eintippen, geschweige denn damit rechnen. Der Physiker stößt schon bei einfachsten Größenumrechnungen an die Grenzen. Lichtjahr in m z.B. Der Chemiker kann nichtmal 'nen pH Wert ausrechnen. (10^14:1) Davon abgesehen sind die "Lücken" im Grunde immer noch da, da hier der dominante Faktor nicht die absolute numerische Ungenauigkeit einer einzelnen Zahl ist, sondern der entstehende Fehler (der aus den absoluten Einzelfehlern multipliziert und addiert wird) wird durch die gesamte Berechnung bestimmt. (Vgl/Lese dazu "Kondition von (Berechnungs-)matrizen") Für Taschenrechner bzw. andere Anwendungen, in denen der Wertebereich nicht eng definiert ist, ist Fixpunkt-Arithmetik keine sinnvolle Wahl imho.
Maxx schrieb: >> Bei dem 40.40-Festkommaformat hab ich einen klar definierten >> Wertebereich, in dem exakt gerechnet wird, fertig. Keine denormals, >> keine Lücken. > > Das erkaufst du dir jedoch mit anderen Problemen durch die enge > Begrenzung des Wertebereichs. Für viele Rechnungen in schon kleinen > Zehnerpotenzen völlig unbrauchbar. > > Der VWLer kann nichtmal die Staatsschulden eintippen, geschweige denn > damit rechnen. > Der Physiker stößt schon bei einfachsten Größenumrechnungen an die > Grenzen. Lichtjahr in m z.B. > Der Chemiker kann nichtmal 'nen pH Wert ausrechnen. (10^14:1) Dann sollte ich als Inschenör wohl die richtigen Einheiten wählen, hm? > Davon abgesehen sind die "Lücken" im Grunde immer noch da, da hier der > dominante Faktor nicht die absolute numerische Ungenauigkeit einer > einzelnen Zahl ist, sondern der entstehende Fehler (der aus den > absoluten Einzelfehlern multipliziert und addiert wird) wird durch die > gesamte Berechnung bestimmt. (Vgl/Lese dazu "Kondition von > (Berechnungs-)matrizen") So meinte ich das nicht -- deine Ausführungen sind mir bewusst. Im einfachsten Fall nehme ich meinen TI30 und rechne damit 'ungeschickt': Der kann zwar bis x*10^99 rechnen, hat dabei aber immer noch nur 10 Stellen, nach meinen Versuchen im Falle des TI30 sogar nur 10 zusammenliegende Stellen. D.h., nicht Gleitkomma, sondern eher Zahl plus Nullen. Die Rechnerei jenseits von meinethalben 10^30 erübrigt sich damit ohnehin, da stimmt bestenfalls noch die Größenordnung. In diesem Versuch ist es mir lieber, ich weiß um den beschränkten Wertebereich meines Rechners. Selbst wenn ich damit einen pH-Wert berechnen möchte, dann lasse ich halt bewusst einige Stellen weg ('teile') und merke mir den Fehler. Viel weiter komme ich mit meinem wissenschaftlichen Rechner auch nicht. Nur, dass der die Stellen still und mir u.U. unbewusst verschwinden lässt.
Sven P. schrieb: > Dann sollte ich als Inschenör wohl die richtigen Einheiten wählen, hm? Wenn dir das immer möglich ist. Würd' immer ein System vorziehen, dass das Komma um entsprechende Einheiten verschieben kann. > Der kann zwar bis x*10^99 rechnen, hat dabei aber immer > noch nur 10 Stellen, nach meinen Versuchen im Falle des TI30 sogar nur > 10 zusammenliegende Stellen. D.h., nicht Gleitkomma, sondern eher Zahl > plus Nullen. Die Rechnerei jenseits von meinethalben 10^30 erübrigt sich > damit ohnehin, da stimmt bestenfalls noch die Größenordnung. Genau das ist Gleitkomma. Eine begrenzte Mantisse wird über einen Faktor mit Exponent auf Genauigkeit vs Wertebereich getrimmt. Der relative Fehler bleibt dabei immer gleich und wird durch die Länge der Mantisse vorgegeben. (Bei dem TI30 dann irgendwo um die 10. signifikante Stelle) > In diesem Versuch ist es mir lieber, ich weiß um den beschränkten > Wertebereich meines Rechners. Selbst wenn ich damit einen pH-Wert > berechnen möchte, dann lasse ich halt bewusst einige Stellen weg > ('teile') und merke mir den Fehler. Ich bezweifle, dass du das bei den nötigen Logarithmusberechnungen von Summen hinbekommst. Bei produkten okay. Hier könnten (Hinzufügen von dissoziierenden Stoffmengen zu einer bestehenden wässrigen Lösung) z.B. Rechnungen wie ld(2,1*10^13 + 7,8*10^11) auftreten. (Wobei du sicher noch keinen Logarithmus drin hast) > Viel weiter komme ich mit meinem > wissenschaftlichen Rechner auch nicht. Nur, dass der die Stellen still > und mir u.U. unbewusst verschwinden lässt. Och. Der kriegt die Rechnung oben locker hin.
Man kann auch versuchen, einen Wald mit einer Nagelfeile abzuholzen - eine Lebensaufgabe. Übrigens: Ab Wieviel Bäumen kann man überhaupt von einem ´"Wald" sprechen - eine Frage für Philosophen - und natürlich für Juristen und Bürokraten (und damit eine sehr teuere)!!!!!!!!!!!!!!!!
Ich habe aber nicht um Belehrungen gebeten, warum das, was ich mache, schlecht ist, sondern ich habe eine m.M.n. recht konkrete Frage gestellt. Auch das ist irgendwie wieder typisch für dieses Forum. Wobei die ersten Antworten durchaus noch gute Denkansätze enthielten, auch über Sinn und Unsinn meines Problemes. Aber dass ich unzurechnungsfähig und weltfremd bin, weiß ich selber, auch ohne Schmitt GmbH & Co.KG.
Motiviert durch diesen Thread habe ich einfach mal dc http://en.wikipedia.org/wiki/Dc_(computer_program) für einen AVR compiliert: Beitrag "Just for fun: dc (an arbitrary precision calculator) port für AVR" Geht (wenn man vom gelegentlichen Problemen mit vollem RAM absieht).
Sven P. schrieb: > Da ich die Sache aber lieber schön gekapselt und komplett auf dem Stack > hätte, misfällt mir eine feste Speicherstelle, um Y zwischenzuspeichern, > auch :-/ Du kannst es einfach "C-like" machen, und dir diesen Bereich auf dem Stack schaffen. (z.B. mit ADIW, per RCALL 0, per push...) leider fehlt in deinem Code wie groß der Bereich sein soll. Da du recht extensiv "mov'st": vielleicht ist dir an der ein oder anderen Stelle der movw Befehl hilfreich?
Traurig, aber wahr: Dieses Forum ist für fast ALLE µC-Fragen ALLERERSTE Wahl, aber bei Mathematik-Implementation ist hier nicht viel zu holen! Egal ob optimiert-genaue Problemlösung mit Integer-Mathematik oder Festkomma. Als Antwort gibts immer nur: - Mach es doch mit der math.lib ..., oder: - Versteh nicht, warum willst du das überhaupt...
Naja das WIE war behandelt. Die offensichtlichen Konzeptfehler enthalten wir dir nicht vor, so gemein bin zumindest ich nicht. Musst ja nicht gegen die Wand laufen. "Warum" du das tust, also dennoch gegen die Wand läufst ist dann allerdings tatsächlich dir überlassen.
Also ein Taschenrechner, resp das Tischmodell. Ja. dann gibt es gar keine Zeitlichen Anforderungen an die Zeit. Der der Benutzer ist immer langsamer. Mach die Schuldivision, aber im RAM. Auch wenn das nun 10ms dauert... es koennten auch 100ms sein, und waere egal.
Was ist denn so schlimm daran wenn jemand 80-bit-Zahlen verarbeiten will? Ob das jetzt 48, 80 oder 8000 bit sind ist vom Konzept her ja ziemlich egal - wenn man schon seine eigenen Routinen schreibt, ist eine Aenderung der Laenge normalerweise trivial. Abgesehen davon gibt es durchaus praktische Anwendungen (z.B. Kryptographie), wo man so viele signifikante Stellen braucht. @Sven P: Ich habe vor einiger Zeit einmal selber die Grundrechnungsarten fuer beliebig lange Integer-Zahlen implementiert (der Wechsel zwischen Integer un Festkomma ist trivial). Geschrieben fuer Microchip PIC, aber nachdem der Code in C ist, sollte ein Portierung auf AVR kaum oder keine Aenderungen brauchen. Die Zahlen sind binaer gespeichert, aber es gibt auch Routinen um sie als text zu drucken, oder Textstrings in Binaerformat zu konvertieren. Link ist hier: http://www.mikroe.com/forum/viewtopic.php?f=13&t=17654&p=90224&hilit=arbitrary#p90224 (aufpassen, der erste Post mit dem Code hat einen Fehler in der Addier-Routine - Korrektur findest Du weiter unten im Thread). Wolfgang
Für meinen BASIC-Computer habe ich eine Fixkomma-Library geschrieben. Allerdings arbeitet die nicht binär, sondern in einer Art "Zwischending" in dem ein Byte jeweils 2 Dezimalstellen repräsentiert. Aber eben nicht BCD sondern binär 0...99. Die Genauigkeit ist (fast) wie die von BCD Berechnungen, die Geschwindigkeit aber ein ganzes Stück höher. Jörg
Uhh. Wolfgang M.: Daran werde ich mir ein Beispiel nehmen und die Chose mal unausgerollt (d.h. mit Schleifen) umsetzen. Zapp: Die meisten klassischen Tischrechner (HP z.B.) ließen sich programmieren. Unter Umständen fällt es dann schon ganz arg ins Gewicht, ob eine Routine 100ms länger braucht, oder nicht. Nein, davon war bisher nicht die Rede, das weiß ich auch. Aber unnütz verschenken will ich erstmal nichts, das ist ja gerade der Spaß beim Programmieren in Assembler. Läubi: Ich werds mal in der Art versuchen: Mit adiw/sbiw den Platz besorgen und freigeben, dabei eines der Zeigerregister als Basiszeiger missbrauchen. Joerg Wolfram: Hättest du da Quellen für mich? Fände ich super :-) Vielen Dank!
Joergs Loesung (jedes Byte entspricht zwei Stellen der Dezimalzahl) macht Konvertierung der Zahlen von/ins Textformat (z.B. zum Ausdrucken) natuerlich einfacher und auch schneller. Der Nachteil ist allerdings geringere Geschwindigkeit der Berechnungen selber (optimale Implementierung beider Varianten vorausgesetzt), weil eine gleich grosse Zahlen eben mehr Bytes benoetigt. Das faellt vor allem bei Multiplikation und Division ins Gewicht. Wenn also zwischen Eingabe und Ausgabe viele Rechenschritte liegen, wuerde ich meine Variante empfehlen. Wenn man - bei eine Taschenrechner durchaus moeglich - immer ein oder zwei Zahlen einliest, dann eine Rechenoperation ausfuehrt, und das Ergebnis wieder als Text ausgibt, ist Joergs Loesung potentiell schneller. Ehrlich gesagt habe ich seinerzeit auch zwischen diesen zwei Varianten geschwankt, mich dann aber fuer die rein binaere Loesung entschieden, weil ich das Endergebnis ohnehin binaer brauchte (48-bit-Tuningwort fuer einen DDS-Generator) und nie zurueckkonvertieren muss. Wolfgang
Bei der Ausfuehrung auf dem PIC gibt es uebrigens Riesenunterschiede in der Geschwindigkeit zwischen 16F- und 18F-Serie - letztere hat einen Harware-Multiplizierer, das merkt man gewaltig (meine Routinen sind auf 18F ca. 10x schneller bei Multiplikation und Division). Ob der Atmel einen Harware-Multiplizierer hat, weiss ich ehrlich gesagt nicht. Wolfgang
Wolfgang M. schrieb: > Ob der Atmel einen Harware-Multiplizierer hat, weiss ich ehrlich gesagt > nicht. Die ATmegas haben einen, die ATtinys nicht.
Thread beobachten
Seitenaufteilung abschaltenBitte 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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.