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.
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.
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
