Wie erreicht der dc (calculator) beliebige Genauigkeit

Vom einfachen Programm zum fertigen Debian-Paket, Fragen rund um Programmiersprachen, Scripting und Lizenzierung.
Antworten
HansD
Beiträge: 234
Registriert: 29.04.2013 15:47:29
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: Berlin

Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von HansD » 10.04.2023 18:56:43

Ich habe mich mit jemandem über mathematische Berechnungen am Computer ausgetauscht. Er beharrt darauf, dass Computer grundsätzlich nicht exakt rechnen könnten.

Ich halte das trotz der Beschränkungen durch Datentypen und den Arbeitsspeicher für ein Scheinproblem. dc, der "arbitrary calculator" berechnet bei Bedarf sehr viele Nachkommastellen korrekt. Ich habe das nicht nur gelesen, sondern getestet. Man kann freilich erwidern, dass einem hunderttausend oder eine Million Nachkommastellen immer noch nicht genau genug sind; das ist aber offensichtlich ein absurder Anspruch, der nichts mehr mit einem normalen Bedarf zu tun hat.

Mich interessiert vor allem, wie dc die beliebige Genauigkeit erreicht. Im Web habe ich dazu bisher nichts gefunden, sicher auch deswegen, weil diese Frage nicht leicht mit Suchbegriffen eingegrenzt werden kann, ohne dass man nicht mehr unüberschaubar viele unpassende Links präsentiert bekommt.
  • Weiß jemand wie dc diese Genauigkeit erreicht?
  • Gibt es dazu eventuell eine Website oder sonstige Quelle, die das Rechenverfahren prinzipiell und vielleicht gar allgemein verständlich erläutert?

(Ich kenne auch bc und habe sowohl dc, bc als auch qalc installiert und benutze sie gelegentlich. Für schnelle Berechnungen benutze ich allerdings derzeit meist dc in einem Terminal. Ich suche also keine Tip(p)s für bessere Rechenprogramme, sondern ich will verstehen und erklären können, wie dc im Großen und Ganzen arbeitet, um exakte und genaue Ergebnisse sicherzustellen.)

Benutzeravatar
schorsch_76
Beiträge: 2542
Registriert: 06.11.2007 16:00:42
Lizenz eigener Beiträge: MIT Lizenz

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von schorsch_76 » 10.04.2023 19:35:32

Ein Beispiel:
https://de.m.wikipedia.org/wiki/MPFR
https://www.boost.org/doc/libs/1_81_0/l ... index.html

Es stimmt: Computer können nicht 100% genau rechnen. Nimm 1/3. Das kann ein Rechner nicht als float/double darstellen. Auch wenn als Zwischenergebnis nahe Null ist kann es Rundungsprobleme geben.

https://de.m.wikipedia.org/wiki/IEEE_754

Es kann aber mit Bruchzahlen berechnet werden. Das hat für den Rechner aber auch Nachteile.

Meine den obigen Bibliotheken kann fast beliebige Genauigkeit erreicht werden.

TuxPeter
Beiträge: 1961
Registriert: 19.11.2008 20:39:02
Lizenz eigener Beiträge: MIT Lizenz

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von TuxPeter » 10.04.2023 19:39:48

1. Solange Du mit Ganzzahlen rechnest, (und auch keine gebrochenen Zahlen durch Division erzeugst) und keinen Werte-Überlauf produzierst, bist Du auf der sicheren (100%-ig exakten) Seite. Der Wertebereich von 2 ^ 64 bei heutigen CPUs ist schon ganz hübsch groß. Sobald gebrochene Zahlen ins Spiel kommen benutzt man halt Fließkommazahlen, die sich gewissermaßen automatisch fokussieren. Und die sind immer ein wenig ungenau - halt im Rahmen der Auflösung des jeweiligen Datentyps. Weshalb man nicht unbedingt erwarten darf, dass (1/3) * 3 = 1 ergibt.
2) Wenn man es genauer haben will, kann man beispielsweise Algorithmen verwenden, die im Prinzip genauso rechnen wie wir das als schriftliches Rechnen in der Grundschule gelernt haben. Z.B. der Debianbc rechnet direkt im 10er System, und man kann angeben, wie viele Nachkommastellen man haben möchte. Obige Aufgabe kannst Du allerdings damit auch nicht exakt lösen, ebensowenig wie mit einer schriftlichen Division nach dem gängigen Algorithmus. Benutze statt des binären oder des 10er Systems ein 3er-Ssystem, dann geht es.

Benutzeravatar
Meillo
Moderator
Beiträge: 8813
Registriert: 21.06.2005 14:55:06
Wohnort: Balmora
Kontaktdaten:

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von Meillo » 10.04.2023 19:43:40

(Edit: Andere waren schon schneller.)
HansD hat geschrieben: ↑ zum Beitrag ↑
10.04.2023 18:56:43
Ich habe mich mit jemandem über mathematische Berechnungen am Computer ausgetauscht. Er beharrt darauf, dass Computer grundsätzlich nicht exakt rechnen könnten.

Ich halte das trotz der Beschränkungen durch Datentypen und den Arbeitsspeicher für ein Scheinproblem. dc, der "arbitrary calculator" berechnet bei Bedarf sehr viele Nachkommastellen korrekt. Ich habe das nicht nur gelesen, sondern getestet. Man kann freilich erwidern, dass einem hunderttausend oder eine Million Nachkommastellen immer noch nicht genau genug sind; das ist aber offensichtlich ein absurder Anspruch, der nichts mehr mit einem normalen Bedarf zu tun hat.
Die Aussage der Person, mit der du geredet hast, hat ja auch nicht den Anspruch erhoben, dass sie mit ``einem normalen Bedarf'' zu tun haette. ;-) Das ist wie beim Rastern eines Kreises. Man kann ihn beliebig fein rastern, aber er wird nie ein wirklicher Kreis (im mathematischen Sinn) sein, sondern immer Stufen haben, egal wie fein man sie waehlt. In der Praxis ist es bei beliebig feiner Rasterung egal, und dennoch wird es nie perfekt sein. Ich sehe da keine Widersprueche. Es sind einfach verschiedene Dinge.



Die einfache Erklaerung kann ich dir nicht liefern, weil ich mich bishlang noch nicht naeher mit dem Thema beschaeftigt habe. Soweit ich es verstehe, gibt man zuvor an, wie viele Stellen Genauigkeit man haben will. Das ist frei waehlbar. Diese Genauigkeit wird dann berechnet.

Hier findest du den Code von dc aus 7th Edition Unix:
https://www.tuhs.org/cgi-bin/utree.pl?f ... md/dc/dc.c
Vielleicht hilft dir das weiter ... oder einer anderen Person, die hier mitliest und das gerne analysieren moechte. 8)
Use ed once in a while!

HansD
Beiträge: 234
Registriert: 29.04.2013 15:47:29
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: Berlin

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von HansD » 10.04.2023 20:41:44

TuxPeter hat geschrieben: ↑ zum Beitrag ↑
10.04.2023 19:39:48
1. Solange Du mit Ganzzahlen rechnest, (und auch keine gebrochenen Zahlen durch Division erzeugst) und keinen Werte-Überlauf produzierst, bist Du auf der sicheren (100%-ig exakten) Seite. Der Wertebereich von 2 ^ 64 bei heutigen CPUs ist schon ganz hübsch groß. Sobald gebrochene Zahlen ins Spiel kommen benutzt man halt Fließkommazahlen, die sich gewissermaßen automatisch fokussieren. Und die sind immer ein wenig ungenau - halt im Rahmen der Auflösung des jeweiligen Datentyps. Weshalb man nicht unbedingt erwarten darf, dass (1/3) * 3 = 1 ergibt.
[…]
Ich danke Dir für Deine Antwort, gleichwohl scheint dc beliebig genau zu rechnen. Hier ein Beispiel:

Bild

Ich muss mich noch genauer damit beschäftigen, es geht sicher um eine Aufteilung der Berechnung in Teilrechnungen beliebiger Anzahl.

HansD
Beiträge: 234
Registriert: 29.04.2013 15:47:29
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: Berlin

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von HansD » 10.04.2023 20:50:42

Meillo hat geschrieben: ↑ zum Beitrag ↑
10.04.2023 19:43:40
(Edit: Andere waren schon schneller.)

Die Aussage der Person, mit der du geredet hast, hat ja auch nicht den Anspruch erhoben, dass sie mit ``einem normalen Bedarf'' zu tun haette. ;-) Das ist wie beim Rastern eines Kreises. Man kann ihn beliebig fein rastern, aber er wird nie ein wirklicher Kreis (im mathematischen Sinn) sein, sondern immer Stufen haben, egal wie fein man sie waehlt. In der Praxis ist es bei beliebig feiner Rasterung egal, und dennoch wird es nie perfekt sein. Ich sehe da keine Widersprueche. Es sind einfach verschiedene Dinge.
Ich bin nicht sicher, ob der gute Mann wirklich so tief gedacht hat. Ursprünglich hat er sich nur beklagt, dass MS Excel keine exakte Spaltenaddition hinbekäme. Was gemäß einer kurzen Recherche, die ich durchgeführt habe, nur ein Konfigurationsproblem zu sein scheint, also davon abhängt, wie Excel eingestellt ist.

Du hast allerdings Recht, Deinem salomonischer Standpunkt kann man diesfalls nicht in vernünftigerweise widersprechen.

Mir lässt so etwas einfach nicht immer ohne Weiteres zur Ruhe kommen, ich will es verstehen und endgültig klären. Vermutlich ist die Antwort wieder 42.

HansD
Beiträge: 234
Registriert: 29.04.2013 15:47:29
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: Berlin

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von HansD » 10.04.2023 20:56:14

Danke für die Links, ich werde versuchen, in den nächsten Tagen darin zu lesen. :-)

HansD
Beiträge: 234
Registriert: 29.04.2013 15:47:29
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: Berlin

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von HansD » 10.04.2023 21:05:16


Benutzeravatar
Meillo
Moderator
Beiträge: 8813
Registriert: 21.06.2005 14:55:06
Wohnort: Balmora
Kontaktdaten:

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von Meillo » 10.04.2023 21:11:55

HansD hat geschrieben: ↑ zum Beitrag ↑
10.04.2023 20:41:44
Ich danke Dir für Deine Antwort, gleichwohl scheint dc beliebig genau zu rechnen.
Ja, genau. dc kann *beliebig* genau rechnen ... in anderen Worten: dc kann das Ergebnis beliebig genau annaehern ... auf 100 Stellen, auf 1000 Stellen, auf 1 Mio Stellen -- du kannst es dir aussuchen --, aber sowas wie 1/3 kann nicht *exakt* berechnet werden, weil jede beliebige Stellenanzahl immer eine Annaeherung bleiben wird.
Use ed once in a while!

Benutzeravatar
Meillo
Moderator
Beiträge: 8813
Registriert: 21.06.2005 14:55:06
Wohnort: Balmora
Kontaktdaten:

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von Meillo » 10.04.2023 21:30:31

Das scheint mir die passende Erklaerung zu sein, wie Programme in der Art von dc technisch funktionieren: https://de.wikipedia.org/wiki/Langzahlarithmetik (die englische Seite ist etwas ausfuehrlicher)
Use ed once in a while!

tobo
Beiträge: 1989
Registriert: 10.12.2008 10:51:41

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von tobo » 10.04.2023 21:31:13

Die beiden Programmierer haben hier eigentlich ziemlich gut beschrieben, wie ihr Programm technisch funktioniert:
https://wolfram.schneider.org/bsd/7thEd ... /dc/dc.pdf

PS:
Und hier noch im Original:
http://squoze.net/UNIX/v7/files/doc/26_dc.pdf
Zuletzt geändert von tobo am 11.04.2023 08:51:37, insgesamt 1-mal geändert.

HansD
Beiträge: 234
Registriert: 29.04.2013 15:47:29
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: Berlin

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von HansD » 11.04.2023 02:46:36

tobo hat geschrieben: ↑ zum Beitrag ↑
10.04.2023 21:31:13
Die beiden Programmierer haben hier eigentlich ziemlich gut beschrieben, wie ihr Programm technisch funktioniert:
https://wolfram.schneider.org/bsd/7thEd ... /dc/dc.pdf
Danke, ich habe mir Teile davon eben genau durchgelesen.

Benutzeravatar
schorsch_76
Beiträge: 2542
Registriert: 06.11.2007 16:00:42
Lizenz eigener Beiträge: MIT Lizenz

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von schorsch_76 » 11.04.2023 16:53:29

Ich kann mal berichten von einem Problem das wir ca. 2000 hatten an einer Maschine. Das weis ich noch genau da ich sehr lange gesucht hatte um das Problem zu finden.

Die Maschine zog per Servo ein Band in ein Werkzeug. Das wurde mit dem Servo eingeschoben und dann nochmal mechanisch korrigiert. Die Sollposition wurde als float berechnet und dann gerundet. Erster Versuch: Inkrementell aufsummieren. "a = a + 0.15". Nach einiger Zeit (ca. 30 min) passten die Positionen nicht mehr und es gab mechanische Probleme. Zweiter Versuch: "a = counter * 0.15". Hier war das Problem wieder vorhanden nur nach längerer Zeit. Ein Wechsel auf Double verzögerte das Problem weiter aber es trat immer wieder auf und die Maschine konnte nicht zuverlässig arbeiten. Nachdem wir das auf Integer Arithmetik umgestellt hatten war das Problem behoben. Es konnten halt keine kleineren Positionen angefahren werden was aber auch nicht notwendig war. Hier ist die Floatingpoint Ungenauigkeit uns auf die Füße gefallen.

HansD
Beiträge: 234
Registriert: 29.04.2013 15:47:29
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: Berlin

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von HansD » 11.04.2023 23:37:38

schorsch_76 hat geschrieben: ↑ zum Beitrag ↑
11.04.2023 16:53:29
Ich kann mal berichten von einem Problem das wir ca. 2000 hatten an einer Maschine. Das weis ich noch genau da ich sehr lange gesucht hatte um das Problem zu finden.

Die Maschine zog per Servo ein Band in ein Werkzeug. Das wurde mit dem Servo eingeschoben und dann nochmal mechanisch korrigiert. Die Sollposition wurde als float berechnet und dann gerundet. […] Ein Wechsel auf Double verzögerte das Problem weiter aber es trat immer wieder auf […]. Nachdem wir das auf Integer Arithmetik umgestellt hatten war das Problem behoben. Es konnten halt keine kleineren Positionen angefahren werden was aber auch nicht notwendig war. Hier ist die Floatingpoint Ungenauigkeit uns auf die Füße gefallen.
:THX: Danke, so ein konkretes Beispiel aus der Praxis finde ich spannend und besonders wertvoll.

Benutzeravatar
hikaru
Moderator
Beiträge: 13585
Registriert: 09.04.2008 12:48:59

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von hikaru » 12.04.2023 00:32:47

schorsch_76 hat geschrieben: ↑ zum Beitrag ↑
11.04.2023 16:53:29
nkrementell aufsummieren. "a = a + 0.15". Nach einiger Zeit (ca. 30 min) passten die Positionen nicht mehr und es gab mechanische Probleme.
Ein wunderschönes Beispiel dafür, wie man IT-Probleme erschaffen kann, die es gar nicht geben müsste! ;)

Fall A: Hättet ihr nicht in Füßen und Daumengliedern gerechnet*, sondern in "richtigen" Einheiten dann wären 0,15" = 0,381cm und es wäre sicher aufgefallen, dass das 38100nm sind, weil SI-Präfixe im metrischen System offensichtlich sind.
Fall B: Der Servo hatte sicher eine mechanisch bedingte Mindestschrittweite. Wäre die bekannt gewesen**, dann hätte man den Einschub in Vielfachen dieser Schrittweite ausdrücken können.

Beide Fälle sind mit reiner Integer-Arithmetik lösbar, ohne sich eine Fixed-Point-Krücke zu bauen.


*) bzw. die Maschine euch dazu gezwungen
**) hätte der Hersteller sie dokumentiert

Benutzeravatar
schorsch_76
Beiträge: 2542
Registriert: 06.11.2007 16:00:42
Lizenz eigener Beiträge: MIT Lizenz

Re: Wie erreicht der dc (calculator) beliebige Genauigkeit

Beitrag von schorsch_76 » 12.04.2023 04:55:43

https://de.m.wikipedia.org/wiki/Maschinengenauigkeit

Es war natürlich ein deutlich komplizierter Aufgabe als oben beschrieben. Ich habe das gekürzt aber das Hauptproblem war der Float Rundungsfehler und das ein Igelrad eine Teilung von 39 hatte, der Servo auf Grad Positionen positionierte.... Hat sich halt alles summiert :lol:

Antworten