Rundungsfehler in BASIC

  • Hallo,


    gerade habe ich den Studenten vorgeführt, wie Zählschleifen in BASIC realisiert werden und bin im Emulator auf folgendes Phänomen gestoßen:


    10 FOR I=1 TO 10 STEP 0.1
    20 PRINT I
    30 NEXT I


    Die Ausgabe stimmt bis 3.7 - 3.8 wird allerdings bereits als 3.7999999999 dargestellt und so geht es auch weiter bis 8.9999999999. Dann geht es bei normal weiter bis 9.7 - als nächstes kommt dann 9.8000000001 usw.


    Das selbe passiert auch im Emulator. Gibt es irgendwo Informationen über diesen Rundungsfehler? (Er hängt natürlich damit zusammen, dass in BASIC nicht zwischen INTEGER- und REAL-Zahlen unterschieden wird. Aber Assembler kennt diese Unterscheidung auch nicht! Werden also im Assembler beim Interpretieren von BASIC alle Variablen intern als REAL-Zahlen behandelt?)


    S.

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

    • Offizieller Beitrag

    Höchst interessant ... ich habe das mal eben auf meinem CBM 8032 ausprobiert, mit exakt dem gleichen Ergebnis. Auch auf dem CBM 720 siehts nicht anders aus.


    Edit: Auf dem PC mit GWBASIC ist's noch schlimmer:

  • Interessant! Das kannte ich bisher nicht. Weiss da jemand mehr :)?


    Witzig ist auch, dass die Ausgabe mit folgender Zeile einwandfrei - also ohne Rundungsfehler - funktioniert:

    Code
    20 PRINT USING "##.###"; i


    Btw, die Variablen kann man schon als "Real" oder "Integer" definieren. So wird bei einigen Programmen aus Geschwindigkeitsgründen ein "DEFINT a-z" vorangestellt, um dem BASIC Interpreter damit zu sagen, dass alle Variablen ganzzahlig sind. Dadurch kann man noch etwas Geschwindigkeit herausholen. Genauso kann man mit "DEFREAL" Fließkommazahlen definieren.

  • Zitat

    INK 1,4


    ... war klar ;)


    1,8 mein lieber, eins komma acht ;)


    Gruß
    Tom

    • Offizieller Beitrag

    Interessant! Das kannte ich bisher nicht. Weiss da jemand mehr :)?


    Witzig ist auch, dass die Ausgabe mit folgender Zeile einwandfrei - also ohne Rundungsfehler - funktioniert:

    Code
    20 PRINT USING "##.###"; i


    Naja, damit ist der Fehler nicht weg, sondern nur nicht mehr sichbar, er wird einfach wieder weggerundet. Es ist eben nur die AUSGABE richtig ...


    Btw, die Variablen kann man schon als "Real" oder "Integer" definieren. So wird bei einigen Programmen aus Geschwindigkeitsgründen ein "DEFINT a-z" vorangestellt, um dem BASIC Interpreter damit zu sagen, dass alle Variablen ganzzahlig sind. Dadurch kann man noch etwas Geschwindigkeit herausholen. Genauso kann man mit "DEFREAL" Fließkommazahlen definieren.


    Interessant, was es für Unterschiede bei den BASIC-Dialekten gibt.
    Beim Commodore-BASIC werden Integer-Variablen durch ein %-Zeichen gekennzeichnet, so wie Zeichenketten durch ein $-Zeichen. Also z.B. A%.

  • Mal aus der CPC-Sicht, weil ich da zufälligerweise das Format inzwischen kenne. Aber auch grundsätzlich zur Zahlendarstellung:


    0,1 lässt sich binär nur sehr schlecht darstellen, ebenso 0,2.


    Die Mantisse im CPC ist vier Bytes lang, und die Umrechnung von 0,1 ergibt (,=wie gehabt im Deutschen .=Trennzeichen zur besseren Darstellung):


    0,1100.1100.1100.1100.1100.1100.1100.1101


    Ja, 0,1 binär ist periodisch (!). Und die letzte Stelle ist auch noch gerundet.



    Der Exponent - also das 5. Byte im CPC - ist 125. Von dieser Zahl muss 128 abgezogen werden, ergibt -3)


    (Mantisse als Ganzzahl) dividiert durch 2^(Anzahl der Bits in der Mantisse) * 2^(Exponent - 128):
    (3435973837 / 2^32) * 2^(125-128)


    Das ergibt also für die diese Zahl alleine schon einen recht hohen Fehlerfaktor. Rückgerechnet ins Dezimalsystem ist das:


    0,10000000000582076609134674072266



    In der Schleife wird jetzt 100 mal auf 1 die Zahl 0,1 addiert, aber eben das fehlerhaft dargestellte 0,1. Das führt irgendwann zu einem Rundungsfehler, der nicht mehr ignoriert werden kann.


    WANN der Fehler auftritt hängt von der internen Genauigkeit der Fließkommazahlen ab, und davon wie gerundet wird.
    Beim CPC hast du ungefähr eine Genauigkeit von 9 Dezimalstellen nach dem Komma (mal besser, mal schlechter). Andere BASICs liegen da vielleicht in etwa gleich.


    Die Formatierung von Octoate zwingt BASIC anscheinend dazu, bei den Zwischenschritten jedes Mal zu runden. Was dann dazu führt, dass die Abweichung in der internen Darstellung von 0,1 nicht kumuliert.


    Ein Step von 0.25 zum Beispiel muss problemlos durchlaufen, weil da auch das interne binäre Format eindeutig bleibt. Und wenn nicht, dann geh ich jede Wette ein, dass dieses BASIC dann einen Bug hat.

  • 1,8 mein lieber, eins komma acht

    hatte erst auf eins komma sieben getippt...
    na ja, auf jeden Fall die gleich Farbnummer wie deine CPC Einschaltmeldung !!! :P

  • MaV:


    Respekt, eine sehr gute Erklärung und sehr fundiert erläutert. Danke dafür +1 !!!


    Gruß
    Tom

  • Interessant, was es für Unterschiede bei den BASIC-Dialekten gibt.
    Beim Commodore-BASIC werden Integer-Variablen durch ein %-Zeichen gekennzeichnet, so wie Zeichenketten durch ein $-Zeichen. Also z.B. A%.


    Das ist in Locomotive BASIC auch so. Mit DEFINT und DEFREAL kann man das aber schon vorher festlegen und braucht sich nachher nicht mehr darum zu kümmern. Lesbarer ist aber wohl eher die % Angabe, da man im Quelltext immer gleich sieht, um was für einen Datentyp es sich handelt.

  • ... da würde mich doch glatt interessieren, wie genau die unterschiedlichen BASIC-Dialekte im Vergleich sind. Auf meinem Apple //c sieht das Ergebnis wieder ein bisschen anders aus (siehe Bild).
    MaV: Welches BASIC ist denn vergleichsweise genau? BBC Basic vielleicht?
    Und wie sieht es eigentlich in anderen Programmiersprachen aus. Ich werde das Programm am WE mal in Turbo Pascal und Apple Pascal eingeben und die Ergebnisse vergleichen.

  • ... da würde mich doch glatt interessieren, wie genau die unterschiedlichen BASIC-Dialekte im Vergleich sind. Auf meinem Apple //c sieht das Ergebnis wieder ein bisschen anders aus (siehe Bild).
    MaV Welches BASIC ist denn vergleichsweise genau? BBC Basic vielleicht?
    Und wie sieht es eigentlich in anderen Programmiersprachen aus. Ich werde das Programm am WE mal in Turbo Pascal und Apple Pascal eingeben und die Ergebnisse vergleichen.

    Hm, gute Frage. Ich habe mit anderen BASIC-Dialekten kaum Erfahrung.


    Eine kurze Recherche zu Apple führte mich zu dieser Seite:
    http://www.txbobsc.com/scsc/scdocumentor/


    Dort habe ich mich auf die Suche nach konstanten Fließkommawerten gemacht. Speziell PI ist interessant, weil es ja überall vorhanden sein muss. In S.EFEA kann ich
    CON.PI.HALF .HS 81490FDAA2
    und
    CON.PI.DOUB .HS 83490FDAA2
    finden.


    Demnach würde PI die Bytefolge 82490FDAA2 haben. 82h ist der Exponent, der Rest Mantisse. Das fand ich insofern lustig, weil im CPC die Zahl haargenau so dargestellt wird, nur sind die 5 Bytes umgedreht: A2 DA 0F 49 82.
    Also entspricht die interne Darstellung der Fließkommazahlen im Apple BASIC (von obigem Link) genau der vom CPC.


    Wenn die Ergebnisse sich also unterscheiden, dann weil die Algorithmen dazu anders berechnen. Möglicherweise wird aber nur anders gerundet.


    Von Turbo Pascal habe ich gelesen, dass das REAL-Format mit 6 Bytes rechnet, also wohl etwas genauer also der CPC und der Apple II. Bei anderen BASIC-Dialekten bräuchten wir die genaue interne Repräsentation, um Aussagen treffen zu können.


    @ @Pentagon: Danke! :)

  • Interessant! Das kannte ich bisher nicht. Weiss da jemand mehr :)?


    Witzig ist auch, dass die Ausgabe mit folgender Zeile einwandfrei - also ohne Rundungsfehler - funktioniert:

    Code
    20 PRINT USING "##.###"; i


    Btw, die Variablen kann man schon als "Real" oder "Integer" definieren. So wird bei einigen Programmen aus Geschwindigkeitsgründen ein "DEFINT a-z" vorangestellt, um dem BASIC Interpreter damit zu sagen, dass alle Variablen ganzzahlig sind. Dadurch kann man noch etwas Geschwindigkeit herausholen. Genauso kann man mit "DEFREAL" Fließkommazahlen definieren.


    Kann man, muss man aber nicht - das war ja eines der ursprünglichen Ziele von BASIC, als es in den 60ern gebaut wurde. (Ich schreibe gerade nen Artikel über die Geschichte der Sprache fürs nächste RETURN.)

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung


  • GANZ HERZLICHEN DANK für die Erklärung!!

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

  • Könnt ihr euch daran noch erinnern: http://support.microsoft.com/kb/124345 ( http://en.wikipedia.org/wiki/Pentium_FDIV_bug )?


    Kommt wohl aus derselben Schublade. Was hat es damals Spott und Hohn gegeben ...

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

  • Auch aus der Kuriosiätenecke:
    Das Omikron Basic hat keine echten Zufallszahlen, sondern geht von einer Reihe aus, die jedesmal wieder gleich abläuft, wenn ich die Erklärung eines Users richtig verstanden habe.
    Er hat es festgestellt, weil er mehrere Omikron Programme in VMs hat nebeneinanderlaufen lassen, und bei zwei oder drei VMs kamen identische Ergebnisse nach keine Ahnung wie vielen Durchgängen raus.

  • Auch aus der Kuriosiätenecke:
    Das Omikron Basic hat keine echten Zufallszahlen, sondern geht von einer Reihe aus, die jedesmal wieder gleich abläuft, wenn ich die Erklärung eines Users richtig verstanden habe.
    Er hat es festgestellt, weil er mehrere Omikron Programme in VMs hat nebeneinanderlaufen lassen, und bei zwei oder drei VMs kamen identische Ergebnisse nach keine Ahnung wie vielen Durchgängen raus.


    Echte Zufallszahlen kann es aus einer deterministischen Maschine wie dem Computer sowieso nicht geben. Es wird allerdings unterschieden zwischen Zufallszahlen und Pseudozufallszahlen. Gute Programmiersprachen verwenden erstere, die zumeist aus Zeilenrücklauf-Abfragen des Videochips und anderen Werten im Prozessor gebildet werden; schlechte (wie etwa das Chipmunk-BASIC) nutzen solche Tabellen und man kann damit immer wieder dieselben Reihen von Zufallszahlen produzieren.

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

  • Ich hab mal geguckt, was das Microsoft Basic 4.7 von 1978 (Z80-Version) sagt:


    Dort gibt es nur Probleme bei 7,8 bis 8,1. Der Rest passt.


    In den Unterlagen verschiedener Basic-Dialekte aus den 80ern findet man aber schon Hinweise darauf.
    In einem Artikel wird empfohlen, dass man Eingabewerte mit 10 oder sogar 100 multiplizieren soll und die Ausgabe der Ergebnisse mittels Stringoperationen wieder richtet. Also einfach gesagt, rechnet man mit Ganzzahlen und dann malt man bei der Ausgabe ein Komma da rein.


    Bei der FOR-Schleife reicht bei mir schon folgende Änderung, damit es funktioniert. Klappt das bei euch auch?


    10 FOR 10 TO 100
    20 PRINT I/10,
    30 NEXT I


    Gruss
    Thomas

    -------------------------------------------------------------------------------------------------------------------


    Ich bin immer auf der Suche nach Ersatzteilen und Elekronikrestposten.
    Bitte an mich denken, wenn Ihr über Angebote stolpert!

  • Echte Zufallszahlen kann es aus einer deterministischen Maschine wie dem Computer sowieso nicht geben. Es wird allerdings unterschieden zwischen Zufallszahlen und Pseudozufallszahlen. Gute Programmiersprachen verwenden erstere, die zumeist aus Zeilenrücklauf-Abfragen des Videochips und anderen Werten im Prozessor gebildet werden; schlechte (wie etwa das Chipmunk-BASIC) nutzen solche Tabellen und man kann damit immer wieder dieselben Reihen von Zufallszahlen produzieren.

    Hatte man das beim CPC nicht auch so, und hat dann über einen RANDOMIZE TIME versucht das zu "lösen" :)

  • Ja, das Locomotive-BASIC hat ganz elegante Möglichkeiten, direkt auf Maschinen-Prozeduren zuzugreifen (allein schon die Interrupt-Beeinflussung! Das findet man sonst fast nirgends.)


    Ich habe hier nen Text einer Pädagogik-Kommission von Ende der 1970er-Jahre, die prüfen sollte, welche Sprache für den Einsatz in der Schule geeignet ist. Das halbe Buch handelt von BASIC und wie schlecht es für pädagogische Zwecke ist, weil es "zu problemfern und zu maschinennah" sei. :D


    Man kann BASIC also im Prinzip nur lieben! :D

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

  • Im BASIC vom CPC kann man sich die interne Darstellung recht anschaulich zeigen lassen, weil die Speicheradressen der Variablen mit dem Klammeraffen vor dem Variablennamen ermittelt werden können:



    Zwei Punkte dazu noch:


    1) Das höchstwertige Bit in der Mantisse ist das Vorzeichenbit (0=positiv, 1=negativ). Um davon auf die richtige Darstellung der Mantisse zu kommen, ersetzt man dieses Bit immer mit einer 1. Die wird bei Fließkommazahlen eingespart und setzt dort das Vorzeichenbit, weil die erste Nachkommastelle bei der Mantisse IMMER eine 1 ist. (Manche Fließkommaformate dürften das nicht berücksichtigen, ich bin so einem noch nicht begegnet.)
    Die binäre und hexadezimale Darstellung stellen also ein genaues Abbild der Zahl im Speicher dar, in der Formel für den Taschenrechner ist dieses Bit aber schon berücksichtigt.


    2) Die Größe der Mantisse lässt sich im CPC nicht mehr wirklich korrekt darstellen. Deswegen habe ich mich entschieden in der Taschenrechner-Zeile die Mantisse hexadezimal anzugeben. Ihr braucht also fürs Errechnen des korrekt(er)en Ergebnisses mit dem Taschenrechner einen solchen, der Hexadezimalzahlen darstellen kann. Der Windows-Taschenrechner kann das (XP und 7 getestet).



    Viel Spaß mit dem Testen!


    PS: Probiert mal FOR i!=-10 TO -1 STEP 0.1
    PPS: Es würde mich freuen, wenn jemand für andere BASIC-Dialekte ähnliche Programme schreiben könnte.


    MaV

  • Gerade finde ich eine Interview-Aussage von Thomas E. Kurtz (dem Erfinder von BASIC) hier:


    Zitat

    Alle mathematischen Berechnungen werden mit Gleitkommazahlen durchgeführt. Eines der schwierigsten Konzepte für einen Einsteiger ist die Unterscheidung zwischen Integer- und Gleitkommazahlen. So gut wie alle Programmiersprachen der damaligen Zeit beugten sich der Architektur der Computerhardware bei der es Gleitkommazahlen für mathematische Berechnungen und Integerzahlen für die Effizienz gab. Indem wir alle Berechnungen mit Gleitkommazahlen durchführten, haben wir den Anwender vor den numerischen Typen geschützt. Wir mussten intern ein paar Verrenkungen anstellen, wenn ein Integer-Wert gefordert wurde (wie bei einem Array-Index) und der Anwender eine Kommazahl mitgab (Beispiel 3.1). In solchen Fällen haben wir gerundet. Ähnliche Probleme hatten wir mit dem Unterschied zwischen binären und dezimalen Nachkommastellen. Schauen Sie sich dieses Beispiel an:


    FOR I=1 to 2 STEP 0.1


    Die dezimale Kommazahl 0.1 ist binär eine mit unendlichen vielen Nachkommastellen. Wir mussten einen Korrekturfaktor verwenden, um die Schleife abzuschließen.

    (S. 82f.)


    Ich habe das Interview schon ein paar mal gelesen - seltsam, dass ich mich an diese Stelle erinnert habe. :)

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung


  • Großartig!

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

  • Ist euch eigentlich auch aufgefallen, daß die Schleife nicht mehr mit dem Endwert durchlaufen wird ?
    Der letzte ausgegebene Wert ist 9.90000001. Ein Durchlauf mit 10 findet nicht statt.


    Intern wird die Schleife immer eins weiter gezählt, weil der Interpreter wahrscheinlich nur prüft, ob I schon >10 ist. Wenn du FOR I=1 to 10:NEXT eingibst und danach PRINT I, dann kommt "11" heraus.

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

  • Ist euch eigentlich auch aufgefallen, daß die Schleife nicht mehr mit dem Endwert durchlaufen wird ?
    Der letzte ausgegebene Wert ist 9.90000001. Ein Durchlauf mit 10 findet nicht statt.

    Stimmt. Der letzte Schleifendurchlauf kommt nicht mehr zur Ausführung, weil durch das Aufaddieren von 0,1 noch irgendwo ein paar Bits gesetzt sind. Beim Vergleich von der 10 aus der Schleife mit der 10 als Konstante stellt sich heraus, dass der Schleifenwert schon um einen ganz geringen Betrag größer ist als die Konstante 10.


    Ich habe das mal mit FOR I=1 TO 10.1 STEP 0.1 geprüft:


    Zahl: 10
    Hexadezimal: 20 00 00 02 - Exponent: 84
    Binär: 00100000 00000000 00000000 00000010 - Exponent: 10000100


    Mit dem Taschenrechner ausgerechnet ergibt das den Wert: 10,000000007450580596923828125
    Der Wert ist größer aus eine gerade 10. Die Prüfung, ob "10 = 10" ist schlägt deswegen fehl und der letzte Schritt wird nicht mehr ausgeführt. Deswegen soll man Fließkommawerte immer mit > oder < prüfen.




    Noch zwei Schönheitsfehler sind im Programm:


    Code
    40 PRINT "Zahl: ";i!


    Das Rufzeichen deklariert die Variable als Fließkommazahl im Locomotive BASIC.


    Und in Zeile 130 soll vor 2^32 natürlich ein Divisionszeichen stehen / .

  • Zwei neue Fragen zum Thema:


    Wenn man in BASIC eine Variable als Real-Zahl definiert, etwa


    a=sqr(2)


    dann wird das Ergebins mit 8 Stellen hinter dem Komma angezeigt. So weit nicht ungewöhnlich.


    Wenn ich allerdings einen Sinus-Wert in die Variable schreibe


    a=sin(2)


    dann fasst die Variable auf einmal 9 Stellen hinter dem Komma.


    1. Frage: Wie ist das möglich, dass eine Variable einfacher Genauigkeit mehr als 8 Dezimalstellen hinter dem Komma haben kann?
    2. Frage: Warum ist das bei einigen Funktionen (sin, cos, log) der Fall, bei anderen (tan, sqr) nicht?

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung

  • Hmm, ganz so regelmäßig tauchen die 8-stelligen und 9-stelligen Werte doch nicht auf. lässt man eine schleife von 0 bis 2*PI in 0.1er-Schritten laufen und schaut sich die Sinus-Werte davon an, sind die meisten 9-stellig, aber einige 8-stellig. Dasselbe bei den Quadratwurzeln.


    Vielleicht ist es also bloß eine Rundungsfrage?

    »It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.« (Edsger W. Dijkstra)


    Homespage| Computerarchäologie | Blog | Forschung