Eine Rechner-App? So etwas kann doch jeder bauen, oder?
(chadnauseam.com)„Eine Rechner-App? So etwas kann doch jeder bauen“ → stimmt in Wirklichkeit nicht
- Ein Rechner muss das Ergebnis mathematischer Ausdrücke exakt anzeigen, und das ist viel schwieriger, als man denkt
- Im iOS-Rechner wird
(10^100) + 1 − (10^100)fälschlicherweise als0berechnet - Android zeigt dagegen korrekt
1an, aber wie das umgesetzt wurde, ist wirklich unglaublich
Google und Hans-J. Boehm
- Google stellte den bekannten Programmierer Hans-J. Boehm ein
- Boehm ist ein Experte, der die Semantik gemeinsamer Variablen in C++ definiert hat
- Doch die Aufgabe, die ihm gegeben wurde, war unerwartet: die Entwicklung einer Rechner-App
Das Problem mit Gleitkommazahlen
- Gleitkommazahlen können Werte wie
0.3oder10^100nicht exakt darstellen - Das heißt, ein auf Gleitkommazahlen basierender Rechner ist nicht vertrauenswürdig
- Für exakte Berechnungen ist daher ein anderer Ansatz nötig
Die Lösung mit Bignum
- Das Problem bei Ganzzahlberechnungen lässt sich mit Bignum (Ganzzahlen beliebiger Größe) lösen
- Bignum ist ein Integer-Typ, der sich je nach verfügbarem Speicher dynamisch erweitert
- Das Problem
(10^100) + 1 - (10^100)lässt sich mit Bignum lösen - Bruchrechnungen bleiben damit jedoch ungelöst
Brüche und algebraische Zahlen
- Brüche (Werte wie
3/4) lassen sich lösen, indem man Zähler und Nenner mit Bignum speichert - Irrationale Zahlen wie π oder √2 lassen sich damit jedoch nicht darstellen
- Boehm versuchte es mit einer auf Polynomen basierenden Darstellung
- Beispiel:
√2kann durch die Gleichungx² - 2 = 0dargestellt werden - Aber π lässt sich auch auf diese Weise nicht darstellen
- Beispiel:
Konstruktive reelle Zahlen (Constructive Real Numbers)
- Boehm untersuchte das Konzept der „rekursiven reellen Arithmetik (RRA)“
- Der Nutzer gibt die gewünschte Genauigkeit an, und der Wert wird innerhalb dieser Genauigkeit berechnet
- Beispiel: Wenn π mit einem Fehler von
0.01dargestellt werden soll, wird3.14zurückgegeben - Dieser Ansatz erschwert jedoch exakte Vergleiche
Das Problem, exakte 0 darzustellen
- Beim RRA-Ansatz kann
1 - 1statt als0auch als0.0000000001dargestellt werden - Das ist aus Sicht der User Experience (UX) problematisch
- Boehm begann zusammen mit anderen Forschern nach einer Lösung zu suchen
Der Richardson-Fitch-Algorithmus
- 1994 lösten Dan Richardson und John Fitch das Problem des Zahlenvergleichs innerhalb bestimmter Operationen
- Doch der Algorithmus ist so langsam, dass er praktisch unbrauchbar ist
- Um zum Beispiel
1 ≠ 1 - e^(-e^1000)zu entscheiden, sind mehr Operationen nötig als es Atome im Universum gibt
Die Kombination aus RRA und rationaler Arithmetik
- Boehm kam auf die Idee, die Vorteile von RRA und rationaler Arithmetik zu kombinieren
- Für einfache Operationen (z. B.
6 × 9oder8 / 3) wird rationale Arithmetik verwendet - RRA wird nur dann verwendet, wenn irrationale Zahlen beteiligt sind
- Dadurch werden Zahlen letztlich in der Form rational × reell dargestellt
Symbolische Darstellung (Symbolic Representation)
- Spezielle Zahlen wie π oder √2 werden nicht per RRA, sondern symbolisch dargestellt
- Beispiel: π wird als Symbol „π“ gespeichert und nur bei Bedarf in einen Zahlenwert umgewandelt
- Nicht nur die vier Grundrechenarten, sondern auch trigonometrische Funktionen (
sin,cos,tan), Logarithmen und Exponentialfunktionen nutzen symbolische Darstellung
Die endgültige Lösung
- Alle Zahlen werden in der Form rational × reell (symbolische Darstellung oder RRA) gespeichert
- Wo immer möglich, wird rationale Arithmetik genutzt, um die Exaktheit zu bewahren
- Symbolische Darstellung wird maximal ausgeschöpft, um RRA-Berechnungen zu minimieren
- Das Ergebnis ist ein perfektes Rechnersystem, das Geschwindigkeit und Genauigkeit in Balance bringt
Fazit
- Der von Boehm und seinem Team entwickelte Android-Rechner ist kein simples Programm
- Er liefert exakte Ergebnisse und verwendet zugleich schnelle und effiziente Algorithmen
- Es ist nicht „einfach nur eine Rechner-App“, sondern ein mathematisch ausgefeiltes System
„Wenn du das nächste Mal den Android-Rechner benutzt, denk an diesen Aufwand!“
12 Kommentare
Nebenbei bemerkt finde ich es interessant, dass die AI neo es mit „geojana“ übersetzt hat. Im Original steht „Anyone could make that“, also ohne diesen verspielten Unterton, haha, aber es passt erstaunlich gut.
Als ich im Grundstudium war, gab es einen Kurs, in dem wir ein 8086-Board von Hand gelötet, einen Ziffernblock und ein Text-LCD angeschlossen und schließlich sogar einen Taschenrechner (nur mit den vier Grundrechenarten) in 8086-Assembly gebaut haben.
Ich habe das Board gebaut, die Tastatur und das LCD angeschlossen und zum Laufen gebracht, aber den Taschenrechner konnte ich nicht fertigstellen.
Damals dachte ich, ich hätte kein Talent für Software, und habe deshalb eine Stelle als Hardware-Ingenieur angenommen, aber irgendwie bin ich dann doch in der Softwareentwicklung gelandet.
Der Taschenrechner war wirklich schwierig.
Das ist ein Tippfehler:
거자나->거잖아. 😃Schon mal versucht, Gleitkommazahlen zu korrigieren? Das wird bestimmt knifflig, hahaha.
Bei Rechner-Apps denke ich sofort an den Standardrechner von Windows. Wenn man
2+2*2berechnet, kommt nicht 6, sondern 8 heraus. Es wirkt, als wäre das absichtlich so gemacht, aber ich kann das überhaupt nicht nachvollziehen. Ich erinnere mich, dass ich früher einmal die Alkoholmenge in einem Cocktail berechnet habe und dabei mehr Alkohol als die Gesamtmenge des Getränks herauskam, was mich ziemlich irritiert hat.Das folgt der üblichen Funktionsweise eines normalen Taschenrechners, bei dem bei jedem Drücken eines Operators der vorherige Ausdruck sofort berechnet wird. Haben Sie vielleicht nur wissenschaftliche Taschenrechner benutzt?
Sehe ich genauso. Ich dachte auch: Ohne Server ist ein Rechner doch super – und dann habe ich mich beim Beheben der ganzen Rechenfehler und Bugs total abgerackert.
Implementierungsübersicht im Quellcode
Erklärung der Logik der Rechneroperationen im Quellcode
Code zur Verarbeitung von Ganzzahlen
Code zur Verarbeitung von Gleitkommazahlen
„Eine Rechner-App? Kann doch jeder machen?“ → stimmt in Wirklichkeit nicht
Dafür scheint es aber unendlich viele Anwendungsmöglichkeiten zu geben, haha
„Python? Ist doch total einfach“ → stimmt in Wirklichkeit nicht
Das habe ich mir beim Anschauen auch gedacht. haha
„JavaScript? Total easy“ → stimmt in Wirklichkeit nicht
"(10^100)+1−(10^100)"Oh, tatsächlich zeigt der iPhone-Rechner 0 an und der Android-Rechner 1.
Aber wenn man es direkt bei Google sucht, wird 0 angezeigt...
Hacker-News-Kommentare