🧗🏾 🔘 ✊🏿 Müde von albernen JS-Witzen? Schreiben Sie Ihre Bibliothek 🐄 👨🏻‍🎓 🏝️

Es gibt viele Dinge in JavaScript, die die Frage "Was ???" aufwerfen. Trotz der Tatsache, dass die meisten von ihnen eine logische Erklärung haben, können sie dennoch überraschend sein, wenn Sie tief eintauchen. Aber JavaScript verdient definitiv keine empörenden Witze. Zum Beispiel sehen wir manchmal Witze wie diesen:

In diesem Fall ist die Kritik absolut unverdient. Lassen Sie uns herausfinden, warum.

JavaScript repräsentiert wie jede andere gängige Programmiersprache Zahlen mit einem einzigen Standard. Um genau zu sein, ist dies der IEEE 754-Standard für Zahlen im 64-Bit-Binärformat. Versuchen wir denselben Witz in anderen Sprachen:

Wie wäre es mit Ruby? In welcher Sprache ist 0,1 + 0,2 ungleich 0,3?

$ irb
irb(main):001:0> 0.1 + 0.2 == 0.3
=> false
irb(main):002:0> 0.1 + 0.2
=> 0.30000000000000004

Rubin! Was für eine dumme Sprache.

Oder Clojure? In welcher Sprache ist 0,1 + 0,2 ungleich 0,3?

$ clj
Clojure 1.10.1
user=> (== (+ 0.1 0.2) 0.3)
false
user=> (+ 0.1 0.2)
0.30000000000000004

Clojure! Was für eine dumme Sprache.

Oder wie wäre es mit dem mächtigen Haskell? In welcher Sprache ist 0,1 + 0,2 ungleich 0,3?

$ ghci
GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
Prelude> 0.1 + 0.2 == 0.3
False
Prelude> 0.1 + 0.2
0.30000000000000004

Haskell! Hahaha. Was für eine dumme Sprache ...

Sie haben die Idee. Das Problem hier ist nicht JavaScript. Dies ist ein großes Problem bei binären Gleitkommazahlen. Aber ich möchte vorerst nicht auf die Details von IEEE 754 eingehen. Wenn wir willkürlich genaue Zahlen wollen, macht JavaScript sie möglich. Seit Oktober 2019 ist BigInt offiziell Teil des TC39 ECMAScript-Standards .

Warum sich damit beschäftigen?

Wir haben ewig mit IEEE 754 durchgehalten. Dies scheint die meiste Zeit kein Problem zu sein. Wahr. Dies ist fast immer kein Problem. Aber manchmal ist es immer noch ein Problem. Und in Zeiten wie diesen ist es gut, Optionen zu haben.

Zum Beispiel habe ich Anfang dieses Jahres an einer Bibliothek von Diagrammen gearbeitet. Ich wollte Candlestick-Charts in SVG zeichnen. Und SVG hat eine nette Funktion namens Transformation . Sie können es auf eine Gruppe von Elementen anwenden und das Koordinatensystem für diese Elemente wird geändert. Mit ein wenig Sorgfalt können Sie die Generierung des Diagrammbereichs vereinfachen. Anstatt die Koordinaten des Diagramms für jeden Kerzenhalter zu berechnen, geben Sie eine Transformation an. Und dann definieren Sie jede Kerze anhand der Rohdatenwerte. Sehr gepflegt. Zumindest theoretisch.

Aber bei Eigenschaftstests hatte ich Probleme. Wenn das Diagramm klein und die Datenwerte groß wären, würde ich Rundungsfehler erhalten. Und das ist oft normal. In der Grafik müssen jedoch einige Pixel ausgerichtet sein. Ansonsten sieht das Bild falsch aus. Also fing ich an, BigInt zu lernen. Das Ergebnis war eine Bibliothek, die ich Ratio nannte. Und ich zeige dir, wie es geschrieben steht.

Bruchklasse

Das Problem bei Gleitkommazahlen ist ihre binäre Darstellung. Computer führen alle ihre Berechnungen in binärer Form durch. Und für ganze Zahlen ist diese Binärdatei in Ordnung. Das Problem tritt auf, wenn wir Dezimalzahlen darstellen möchten. In englischsprachigen Ländern wie Australien schreiben wir beispielsweise Dezimalstellen wie folgt:

3.1415926

$3.1415926$

Der Teil links von den Punkten (...) ist der gesamte Teil, und rechts vom Punkt ist der Bruchteil. Das Problem ist jedoch, dass einige Zahlen Bruchteile haben, die nicht einfach in zwei Teile geteilt werden können. Es ist also schwierig, sie binär darzustellen. Das gleiche Problem tritt jedoch an der Basis 10 auf. Zum Beispiel der Bruch 10/9. Sie können versuchen, so etwas zu schreiben:

1.111111111111111111111111111111111111.11111111111111111111111111111111111

$1.111111111111111111111111111111111111.11111111111111111111111111111111111$

Dies ist jedoch eine Annäherung. Um 10/9 genau darzustellen, müssen die Einheiten unendlich sein. Daher müssen wir eine andere Notation verwenden, um Wiederholungen darzustellen. Zum Beispiel dies:

1. \dot{1}

$1.\dot{1}$

Dieser Punkt über der Einheit zeigt an, dass die Einheiten fortgesetzt werden. Aber die meisten Programmiersprachen haben diesen Punkt nicht.

Beachten Sie, dass 10/9 eine perfekte Genauigkeit aufweist. Und alles, was man braucht, um genau zu sein, sind zwei Informationen. Dies ist der Zähler und Nenner . Mit einem einzelnen BigInt-Wert können wir beliebig große Ganzzahlen darstellen. Wenn wir jedoch ein Paar von ganzen Zahlen erstellen , können wir beliebig große oder kleine Zahlen darstellen.

In JavaScript könnte es so aussehen:

// file: ratio.js
export default class Ratio {
  // We expect n and d to be BigInt values.
  constructor(n, d) {
    this.numerator = n;
    this.denominator = d;
  }
}

Also haben wir den schwierigsten Teil gemacht. "Erfunden" eine Möglichkeit, Zahlen mit nahezu unendlicher Genauigkeit darzustellen. (Wir sind immer noch durch den Speicher unserer Geräte begrenzt.) Alles, was bleibt, ist die Anwendung der Mathematik. Fügen wir also Funktionen hinzu.

Gleichberechtigung

Als erstes möchten Sie die beiden Brüche vergleichen. Wozu? Weil ich zuerst gerne Tests schreibe . Wenn ich zwei Brüche auf Gleichheit vergleichen kann, ist das Schreiben von Tests viel einfacher.

In einem einfachen Fall ist das Schreiben einer Gleichstellungsmethode ziemlich einfach:

// file: ratio.js
export default class Ratio {
  constructor(n, d) {
    this.numerator = n;
    this.denominator = d;
  }

  equals(other) {
    return (
      this.numerator === other.numerator &&
      this.denominator === other.denominator
    );
  }
}

Das ist gut. Aber es wäre schön, wenn unsere Bibliothek sagen könnte, dass 1/2 2/4 ist. Dazu müssen Sie den Bruch vereinfachen. Das heißt, bevor wir die Gleichheit überprüfen, wollen wir die Zähler und Nenner beider Brüche auf so kleine Zahlen wie möglich reduzieren. Wie machen wir das?

Der naive Ansatz besteht darin, alle Zahlen von 1 bis min (n, d) auszuführen (wobei nn und dd der Zähler bzw. der Nenner sind). Und das habe ich am Anfang versucht. Der Code sah ungefähr so aus:

function simplify(numerator, denominator) {
    const maxfac = Math.min(numerator, denominator);
    for (let i=2; i<=maxfac; i++) {
      if ((numerator % i === 0) && (denominator % i === 0)) {
        return simplify(numerator / i, denominator / i);
      }
    }
    return Ratio(numerator, denominator);
}

Und wie zu erwarten ist es unglaublich langsam. Meine Tests haben ewig gedauert. Wir brauchen also einen effizienteren Ansatz. Glücklicherweise hat es ein griechischer Mathematiker vor ein paar Jahrtausenden gefunden. Die Lösung besteht darin, den Euklid-Algorithmus anzuwenden. Dies ist ein Weg, um den größten gemeinsamen Teiler zweier Ganzzahlen zu finden.

Die rekursive Version von Euklids Algorithmus ist wunderschön und elegant:

function gcd(a, b) {
    return (b === 0) ? a : gcd(b, a % b);
}

Das Auswendiglernen ist anwendbar, was den Algorithmus sehr attraktiv macht. Leider haben wir in V8 oder SpiderMonkey noch keine Schwanzrekursion . (Zumindest nicht zum Zeitpunkt dieses Schreibens.) Dies bedeutet, dass wir einen Stapelüberlauf erhalten, wenn wir es mit ausreichend großen Ganzzahlen ausführen. Große ganze Zahlen sind wie ein Ausgangspunkt.

Verwenden wir stattdessen die iterative Version:

// file: ratio.js
function gcd(a, b) {
    let t;
    while (b !== 0) {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

Nicht so elegant, macht aber den Job. Und mit diesem Code können wir eine Funktion schreiben, um Brüche zu vereinfachen. Während wir dies tun, werden wir eine kleine Änderung vornehmen, so dass die Nenner immer positiv sind (dh bei negativen Zahlen ändert nur der Zähler das Vorzeichen).

// file: ratio.js

function sign(x) {
  return x === BigInt(0) ? BigInt(0)
       : x > BigInt(0)   ? BigInt(1) 
       /* otherwise */   : BigInt(-1);
}

function abs(x) {
  return x < BigInt(0) ? x * BigInt(-1) : x;
}

function simplify(numerator, denominator) {
  const sgn = sign(numerator) * sign(denominator);
  const n = abs(numerator);
  const d = abs(denominator);
  const f = gcd(n, d);
  return new Ratio((sgn * n) / f, d / f);
}

Und jetzt können wir unsere Gleichstellungsmethode schreiben:

// file: ratio.js -- inside the class declaration
  equals(other) {
    const a = simplify(this);
    const b = simplify(other);
    return (
      a.numerator === b.numerator &&
      a.denominator === b.denominator
    );
  }

Jetzt können Sie zwei Brüche auf Gleichheit vergleichen. Es klingt vielleicht nicht nach viel, aber es bedeutet, dass wir Unit-Tests schreiben und sicherstellen können, dass unsere Bibliothek wie erwartet funktioniert.

Umstellung auf andere Typen

Ich werde Sie nicht langweilen, indem ich alle Unit-Tests in meiner Bibliothek aufschreibe. Aber es wäre schön, die Brüche in andere Formate zu konvertieren. Beispielsweise möchten wir sie möglicherweise als Zeichenfolge in Debug-Nachrichten darstellen. Oder vielleicht wollen wir sie in Zahlen umwandeln. Überschreiben wir also die Methoden .toString () und .toValue () für unsere Klasse.

Die .toString () -Methode ist die einfachste. Beginnen wir also damit.

// file: ratio.js -- inside the class declaration
  toString() {
    return `${this.numerator}/${this.denominator}`;
  }

Einfach genug. Aber was ist mit der Rückkonvertierung in eine Zahl? Eine Möglichkeit, dies zu tun, besteht darin, den Zähler einfach durch den Nenner zu teilen:

// file: ratio.js -- inside the class declaration
  toValue() {
    return  Number(this.numerator) / Number(this.denominator);
  }

Das funktioniert oft. Aber vielleicht möchten wir den Code ein wenig optimieren. Der springende Punkt unserer Bibliothek ist, dass wir große Ganzzahlen verwenden, um die Genauigkeit zu erhalten, die wir benötigen. Und manchmal sind diese Ganzzahlen zu groß, um wieder in Zahl umgewandelt zu werden. Aber wir wollen Number so nah wie möglich an die Wahrheit bringen, wo es möglich ist. Wir rechnen also etwas, während wir BigInt in Number konvertieren:

// file: ratio.js -- inside the class declaration
  toValue() {
    const intPart = this.numerator / this.denominator;
    return (
      Number(this.numerator - intPart * this.denominator) /
        Number(this.denominator) + Number(intPart)
    );
  }

Durch Extrahieren des ganzzahligen Teils reduzieren wir die Größe der BigInt-Werte, bevor wir sie in Number konvertieren. Es gibt andere Möglichkeiten, dies zu tun, die weniger Reichweitenprobleme haben. Sie sind im Allgemeinen härter und langsamer. Wenn Sie interessiert sind, empfehle ich Ihnen, sich diese genauer anzusehen. In diesem Artikel deckt ein einfacher Ansatz jedoch genügend Fälle ab, um nützlich zu sein.

Multiplikation und Division

Lass uns etwas mit den Zahlen machen. Wie wäre es mit Multiplikation und Division? Es ist leicht für Brüche. Multiplizieren Sie die Zähler mit den Zählern und die Nenner mit den Nennern.

// file: ratio.js -- inside the class declaration
  times(x) {
    return simplify(
      x.numerator * this.numerator,
      x.denominator * this.denominator
    );
  }

Die Aufteilung ähnelt dem obigen Code. Drehen Sie den zweiten Bruch um und multiplizieren Sie ihn.

// file: ratio.js -- inside the class declaration
  divideBy(x) {
    return simplify(
      this.numerator * x.denominator,
      this.denominator * x.numerator
    );
  }

Addition und Subtraktion

Wir haben jetzt Multiplikation und Division. Das nächste, was geschrieben werden muss, ist logischerweise Addition und Subtraktion. Dies ist etwas komplizierter als Multiplikation und Division. Aber nicht zu viel.

Um zwei Brüche hinzuzufügen, müssen Sie sie zuerst auf denselben Nenner bringen und dann die Zähler hinzufügen. Im Code könnte es ungefähr so aussehen:

// file: ratio.js -- inside the class declaration
  add(x) {
    return simplify(
      this.numerator * x.denominator + x.numerator * this.denominator,
      this.denominator * x.denominator
    );
  }

Alles wird mit den Nennern multipliziert. Und wir verwenden simplify (), um den Bruch in Bezug auf die Zähler- und Nennerzahlen so klein wie möglich zu halten.

Die Subtraktion ähnelt der Addition. Wir manipulieren die beiden Brüche so, dass die gleichen Nenner wie zuvor ausgerichtet sind. Dann addieren wir nicht, sondern subtrahieren.

// file: ratio.js -- inside the class declaration
  subtract(x) {
    return simplify(
      this.numerator * x.denominator - x.numerator * this.denominator,
      this.denominator * x.denominator
    );
  }

Wir haben also die grundlegenden Operatoren. Sie können addieren, subtrahieren, multiplizieren und dividieren. Aber wir brauchen noch ein paar andere Methoden. Insbesondere Zahlen haben eine wichtige Eigenschaft: Wir können sie miteinander vergleichen.

Vergleiche

Wir haben bereits .equals () besprochen. Wir brauchen aber mehr als nur Gleichheit. Wir möchten auch in der Lage sein, die Verhältnisse zwischen mehr und weniger zu definieren. Daher erstellen wir eine .lte () -Methode, die uns sagt, ob ein Bruch kleiner oder gleich einem anderen Bruch ist. Wie bei .equals () ist es nicht offensichtlich, welcher der beiden kleiner ist. Um sie zu vergleichen, müssen wir beide in denselben Nenner konvertieren und dann die Zähler vergleichen. Mit ein wenig Vereinfachung könnte es so aussehen:

// file: ratio.js -- inside the class declaration
  lte(other) {
    const { numerator: thisN, denominator: thisD } = simplify(
      this.numerator,
      this.denominator
    );
    const { numerator: otherN, denominator: otherD } = simplify(
      other.numerator,
      other.denominator
    );
    return thisN * otherD <= otherN * thisD;
  }

Sobald wir .lte () und .equals () haben, können wir den Rest der Vergleiche ausdrucken. Sie können einen beliebigen Vergleichsoperator auswählen. Wenn wir jedoch gleich () und>, <, ≥ oder ≤ sind, können wir den Rest mithilfe der booleschen Logik ableiten. In diesem Fall haben wir lte () gewählt, weil der FantasyLand-Standard es verwendet . Andere Operatoren könnten folgendermaßen aussehen:

// file: ratio.js -- inside the class declaration
  lt(other) {
    return this.lte(other) && !this.equals(other);
  }

  gt(other) {
    return !this.lte(other);
  }

  gte(other) {
    return this.gt(other) || this.equals(other);
  }

Rundung

Jetzt können wir Brüche vergleichen. Und wir können auch multiplizieren und dividieren, addieren und subtrahieren. Aber wenn wir mehr Spaß mit unserer Bibliothek haben wollen, brauchen wir mehr Werkzeuge. Die JavaScript Math Convenience-Objekte enthalten die Methoden .floor () und .ceil ().

Beginnen wir mit .floor (). Floor nimmt einen Wert und rundet ihn ab. Bei positiven Zahlen bedeutet dies, dass wir nur den gesamten Teil behalten und den Rest verwerfen. Bei negativen Zahlen runden wir jedoch von Null auf, sodass negativen Zahlen etwas mehr Aufmerksamkeit geschenkt werden muss.

// file: ratio.js -- inside the class declaration
  floor() {
    const one = new Ratio(BigInt(1), BigInt(0));
    const trunc = simplify(this.numerator / this.denominator, BigInt(1));
    if (this.gte(one) || trunc.equals(this)) {
      return trunc;
    }
    return trunc.minus(one);
  }

Sie können jetzt den obigen Code verwenden, um die aufgerundeten Werte zu berechnen.

// file: ratio.js -- inside the class declaration
  ceil() {
    const one = new Ratio(BigInt(1), BigInt(0));
    return this.equals(this.floor()) ? this : this.floor().add(one);
  }

Wir haben jetzt das meiste, was für viele mathematische Operationen benötigt wird. Und mit .toValue () können wir Berechnungen einfach wieder in Dezimalzahlen konvertieren. Was aber, wenn wir eine Gleitkommazahl in einen Bruch umwandeln wollen?

Zahl zu Bruch

Das Umrechnen von Zahlen in Brüche ist schwieriger, als es auf den ersten Blick erscheinen mag. Und es gibt viele verschiedene Möglichkeiten, diese Transformation durchzuführen. Meine Implementierung ist nicht die genaueste, aber gut genug. Damit es funktioniert, konvertieren wir zuerst die Zahl in eine Zeichenfolge, die bekanntlich das Format einer Sequenz hat. Zu diesem Zweck stellt uns JavaScript die Methode .toExponential () zur Verfügung. Die Methode gibt eine Zahl in Exponentialschreibweise zurück. Hier sind einige Beispiele, die Ihnen helfen, die Idee zu verstehen:

let x = 12.345;
console.log(x.toExponential(5));
// ⦘ '1.23450e+1''

x = 0.000000000042;
console.log(x.toExponential(3));
// ⦘ '4.200e-11'

x = 123456789;
console.log(x.toExponential(4));
// ⦘ '1.2346e+8'

Der Code repräsentiert eine Zahl als normalisierten Dezimalwert und als Multiplikator. Das normalisierte Dezimalbit wird als Mantisse bezeichnet, und der Faktor wird als Exponent bezeichnet. Hier bedeutet "normalisiert", dass der Absolutwert der Mantisse immer kleiner als 10 ist. Und der Exponent ist immer jetzt 10. Wir geben den Beginn des Faktors mit dem Buchstaben 'e' an (kurz für 'Exponent').

Der Vorteil dieser Notation ist, dass sie konsistent ist. Es gibt immer genau eine Ziffer links vom Dezimalpunkt. Mit .toExponential () können wir angeben, wie viele signifikante Stellen wir möchten. Dann kommt das 'e' und der Exponent ist immer eine ganze Zahl. Da der Wert sequentiell ist, können wir ihn mit einem frechen regulären Ausdruck analysieren.

Der Prozess läuft ungefähr so ab. Wie bereits erwähnt, verwendet .toExponential () einen Parameter, um die Anzahl der signifikanten Stellen anzugeben. Wir brauchen so viele Zahlen wie möglich. Daher setzen wir die Genauigkeit auf 100 (was die meisten JavaScript-Engines zulassen). In diesem Beispiel bleiben wir jedoch bei einer Genauigkeit von 10. Stellen Sie sich nun vor, wir haben die Nummer 0.987654321e0. Wir wollen den Dezimalpunkt um 10 Stellen nach rechts verschieben. Das würde uns 9876543210 geben. Dann dividiere durch 10 ^ 10, um 9876543210/100000000 zu erhalten. Dies vereinfacht sich wiederum zu 987654321/100000000.

Aber wir müssen auf diesen Aussteller achten. Wenn wir eine Zahl wie 0.987654321e9 haben, verschieben wir den Dezimalpunkt immer noch um 10 Stellen nach rechts. Aber wir teilen durch zehn, hoch 10-9 = 1.

0.987654321 \times 10^{9} = 9876543210 / 10^{1} =

$0.987654321×10^9 = 9876543210/ 10^1=$

987654321 / 1

$987654321/1$

Um dies so zu halten, haben wir einige Hilfsfunktionen definiert:

// Transform a ‘+’ or ‘-‘ character to +1 or -1
function pm(c) {
  return parseFloat(c + "1");
}

// Create a new bigint of 10^n. This turns out to be a bit
// faster than multiplying.
function exp10(n) {
  return BigInt(`1${[...new Array(n)].map(() => 0).join("")}`);
}

Mit ihrer Hilfe können wir die gesamte fromNumber () -Funktion zusammensetzen.

// file: ratio.js -- inside the class declaration
  static fromNumber(x) {
    const expParse = /(-?\d)\.(\d+)e([-+])(\d+)/;
    const [, n, decimals, sgn, pow] =
      x.toExponential(PRECISION).match(expParse) || [];
    const exp = PRECISION - pm(sgn) * +pow;
    return exp < 0
      ? simplify(BigInt(`${n}${decimals}`) * exp10(-1 * exp), BigInt(1))
      : simplify(BigInt(`${n}${decimals}`), exp10(exp));
  }

Die meisten Grundfunktionen werden behandelt. Wir können von Zahlen zu Brüchen und wieder zurück gehen. Aber für meine spezielle Anwendung brauchte ich mehr. Insbesondere mussten Exponentiation und Logarithmen gefunden werden.

Potenzierung

Potenzierung ist, wenn eine Zahl mit sich selbst um ein Vielfaches multipliziert wird. Zum Beispiel ist 2 ^ 3 = 2 × 2 × 2 = 8. Für einfache Fälle, in denen der Grad eine Ganzzahl ist, gibt es einen integrierten BigInt: ** -Operator. Wenn wir also einen Bruchteil der Leistung erhöhen, ist dies eine gute Option. So wird ein Bruch zu einer Kraft erhoben:

{(\frac{x}{y})}^{n} = \frac{x^{n}}{y^{n}}

$\left(\frac{x}{y}\right)^{n} = \frac{x^n}{y^n}$

Daher könnte der erste Teil unserer Potenzierungsmethode ungefähr so aussehen:

// file: ratio.js -- inside the class declaration
  pow(exponent) {
    if (exponent.denominator === BigInt(1)) {
        return simplify(
            this.numerator ** exponent.numerator,
            this.denominator ** exponent.numerator
        );
    }
  }

Funktioniert super. Na ja ... meistens gut. Jetzt wird es komplizierter. Außerhalb der Beschränkungen von Sicherheiten und Mathematik müssen wir einige Kompromisse eingehen. Möglicherweise müssen wir die Genauigkeit opfern, um innerhalb eines angemessenen Zeitrahmens eine Antwort zu erhalten.

Exponentiation erzeugt leicht große Zahlen. Und wenn die Zahlen groß werden, verlangsamen sich die Dinge. Während ich diesen Artikel schrieb, schrieb ich auch Berechnungen, die über einen Zeitraum von Tagen nicht abgeschlossen wurden. Sie müssen also vorsichtig sein. Aber das ist OK. Alles kommt für BigInt.

Aber es gibt noch ein anderes Problem. Was ist, wenn der Nenner des Abschlusses nicht einer ist? Was wäre zum Beispiel, wenn wir 8 ^ (2/3) berechnen wollten?

Glücklicherweise können wir dieses Problem in zwei kleinere Probleme aufteilen. Wir wollen einen Bruchteil auf die Kraft eines anderen reduzieren. Zum Beispiel können wir a / b x / y zuordnen. Die Potenzierungsgesetze besagen, dass Folgendes gleichwertig ist:

{(\frac{x}{y})}^{\frac{a}{b}} = {({(\frac{x}{y})}^{\frac{1}{b}})}^{a} = {(\frac{x^{\frac{1}{b}}}{y^{\frac{1}{b}}})}^{a}

$\left(\frac{x}{y}\right)^\frac{a}{b} = \left(\left(\frac{x}{y}\right)^\frac{1}{b}\right)^a = \left(\frac{x^\frac{1}{b}}{y^\frac{1}{b}}\right)^a$

Wir wissen bereits, wie man einen BigInt in die Leistung eines anderen BigInt umwandelt. Aber was ist mit Bruchgraden? Nun, es gibt noch ein anderes Äquivalent:

x^{\frac{1}{n}} = \sqrt[n]{x}

$x^\frac{1}{n} = \sqrt[n]{x}$

Das heißt, xx auf die Potenz 1n1n zu reduzieren, entspricht dem Finden der n-ten Wurzel von xx. Das heißt, wenn wir einen Weg finden, die n-te Wurzel von BigInt zu berechnen, können wir jeden Grad berechnen.

Mit einer gut durchdachten Websuche wird es nicht lange dauern, einen Algorithmus zum Schätzen der n-ten Wurzel zu finden. Die gebräuchlichste Methode ist die Newtonsche Methode . Es funktioniert aus der Auswertung, rr. Dann wird eine Berechnung durchgeführt, um die beste Schätzung zu erhalten:

\begin{aligned} r & \approx x^{\frac{1}{n}} \\ r^{'} & = \frac{1}{n} ((n - 1) r + (\frac{x}{r^{n - 1}})) \end{aligned}

$\begin{align} r &\approx x^{\frac{1}{n}} \\ r^{\prime} &= \frac{1}{n}\left((n-1)r + \left(\frac{x}{r^{n-1}}\right)\right) \end{align}$

Wir wiederholen diese Berechnungen so lange, bis wir die gewünschte Genauigkeit erreicht haben. Leider gibt es einige Wurzeln, die nicht als endlicher Bruch dargestellt werden können. Mit anderen Worten, wir benötigen unendlich lange BigInt-Werte, um eine perfekte Präzision zu erzielen. In der Praxis bedeutet dies, dass wir eine beliebige Iterationsbeschränkung wählen müssen.

Wir werden auf diesen Punkt zurückkommen. Lassen Sie uns zunächst herausfinden, wie eine einigermaßen genaue n-te Wurzel berechnet wird. Da die Schätzung rr ein Bruchteil sein wird, können wir sie schreiben als:

r = \frac{a}{b} .

$r = \frac{a}{b}.$

Und dies ermöglicht es uns, die Berechnungen wie folgt umzuschreiben:

\frac{a^{'}}{b^{'}} = \frac{(n - 1) a^{n} + x b^{n}}{n b a^{n - 1}}

$\frac{a^{\prime}}{b^{\prime}} = \frac{(n - 1)a^{n} + x b^{n}}{n b a^{n - 1}}$

Jetzt ist alles in Form einer Ganzzahlberechnung, die für die Verwendung mit BigInt geeignet ist. Fühlen Sie sich frei, abab in die obige Gleichung für r'r 'einzufügen und meine Ergebnisse zu überprüfen. In JavaScript sieht es so aus:

const estimate = [...new Array(NUM_ITERATIONS)].reduce(r => {
  return simplify(
    (n - BigInt(1)) * r.numerator ** n + x * r.denominator ** n,
    n * r.denominator * r.numerator ** (n - BigInt(1))
  );
}, INITIAL_ESTIMATE);

Wir wiederholen diese Berechnung einfach, bis wir eine geeignete Genauigkeit für unsere n-te Wurzelschätzung erreicht haben. Das Problem ist, dass wir geeignete Werte für unsere Konstanten finden müssen. Das heißt, NUM_ITERATIONS und INITIAL_ESTIMATE.

Viele Algorithmen beginnen mit INITIAL_ESTIMATE one. Dies ist eine kluge Wahl. Oft haben wir keine gute Möglichkeit zu erraten, was die n-te Wurzel sein könnte. Aber schreiben wir "snag". Nehmen wir (vorerst) an, dass unser Zähler und Nenner im Bereich Nummer liegen. Wir können dann Math.pow () verwenden, um die anfängliche Punktzahl zu erhalten. Es könnte so aussehen:

// Get an initial estimate using floating point math
// Recall that x is a bigint value and n is the desired root.
const initialEstimate = Ratio.fromNumber(
    Math.pow(Number(x), 1 / Number(n))
);

Wir haben also einen Wert für unsere erste Einschätzung. Was ist mit NUM_ITERATION? In der Praxis habe ich mit einer Annahme von 10 begonnen. Dann habe ich Eigenschaftstests durchgeführt. Ich habe die Anzahl so lange erhöht, bis die Berechnungen innerhalb eines angemessenen Zeitrahmens lagen. Und die Figur, die endlich funktioniert hat ... 1. Eine Iteration. Das macht mich ein wenig traurig, aber wir sind etwas genauer als bei Gleitkommaberechnungen. In der Praxis können Sie diese Zahl erhöhen, wenn Sie nicht viele Bruchkräfte berechnen.

Der Einfachheit halber werden wir die Berechnung der n-ten Wurzel in eine separate Funktion extrahieren. Alles in allem könnte der Code folgendermaßen aussehen:

// file: ratio.js -- inside the class declaration
  static nthRoot(x, n) {
    // Handle special cases
    if (x === BigInt(1)) return new Ratio(BigInt(1), BigInt(1));
    if (x === BigInt(0)) return new Ratio(BigInt(0), BigInt(1));
    if (x < 0) return new Ratio(BigInt(1), BigInt(0)); // Infinity

    // Get an initial estimate using floating point math
    const initialEstimate = Ratio.fromNumber(
      Math.pow(Number(x), 1 / Number(n))
    );

    const NUM_ITERATIONS = 1;
    return [...new Array(NUM_ITERATIONS)].reduce((r) => {
      return simplify(
        n -
          BigInt(1) * (r.numerator ** n) +
          x * (r.denominator ** n),
        n * r.denominator * r.numerator ** (n - BigInt(1))
      );
    }, initialEstimate);
  }

  pow(n) {
    const { numerator: nNumerator, denominator: nDenominator } = n.simplify();
    const { numerator, denominator } = this.simplify();
    if (nNumerator < 0) return this.invert().pow(n.abs());
    if (nNumerator === BigInt(0)) return Ratio.one;
    if (nDenominator === BigInt(1)) {
      return new Ratio(numerator ** nNumerator, denominator ** nNumerator);
    }
    if (numerator < 0 && nDenominator !== BigInt(1)) {
      return Ratio.infinity;
    }

    const { numerator: newN, denominator: newD } = Ratio.nthRoot(
      numerator,
      nDenominator
    ).divideBy(Ratio.nthRoot(denominator, nDenominator));
    return new Ratio(newN ** nNumerator, newD ** nNumerator);
  }

Unvollkommen und langsam. Aber die Aufgabe ist weitgehend machbar geworden. Die Frage bleibt, wie man die Schätzung erhält, wenn wir ganze Zahlen größer als Number.MAX_VALUE haben. Ich werde dies jedoch als Übung für den Leser belassen; Dieser Artikel ist schon zu lang.

Logarithmen

Ich muss zugeben, die Logarithmen haben mich ein paar Wochen lang verwirrt. Für meine Entwicklung muss ich die Basis-10-Logarithmen berechnen. Deshalb habe ich nach Algorithmen gesucht, um die Logarithmen zu berechnen. Und es gibt viele von ihnen. Aber ich konnte keine finden, die gut genug funktionierte, um in die Mathematikbibliothek aufgenommen zu werden.

Warum ist es so schwer? Mein Ziel war es, Logarithmen für eine höhere Genauigkeit als Gleitkommazahlen zu berechnen. Warum sonst alles? Gleitkomma-Logarithmusfunktion, Math.log10 (), schnell und integriert. Also habe ich mir Algorithmen angesehen, die Möglichkeiten bieten, Logarithmen iterativ zu berechnen. Und sie arbeiten. Sie werden jedoch nur langsam höher als die Gleitkommapräzision. Nicht nur ein bisschen langsamer. Viel langsamer.

Während wir die Iterationen durchlaufen, wird der von uns erstellte Bruch genauer. Diese Genauigkeit hat jedoch ihren Preis. Die BigInt-Werte in Brüchen werden immer größer. Und wenn sie größer werden, dauert es lange, bis sie sich vermehren. Irgendwann habe ich die Berechnung für drei Tage verlassen. Aber während die Berechnungen weitergingen, erinnerte ich mich an etwas.

Ich erinnerte mich, dass ich eine log10 () -Methode brauchte, um schöne skalierte Werte für die Diagramme berechnen zu können. Und für diese Berechnungen habe ich jedes Mal, wenn ich .log10 () aufgerufen habe, sofort .floor () aufgerufen. Dies bedeutet, dass ich nur den ganzzahligen Teil des Logarithmus benötige. Die Berechnung des Logarithmus auf 100 Dezimalstellen war nur eine Verschwendung von Zeit und Leistung.

Darüber hinaus gibt es eine einfache Möglichkeit, den gesamten Teil des Logarithmus zur Basis 10 zu berechnen. Wir müssen lediglich die Zahlen zählen. Ein naiver Versuch könnte so aussehen:

// file: ratio.js -- inside the class declaration
  floorLog10() {
    return simplify(BigInt((this.numerator / this.denominator).toString().length - 1), BigInt(1));
  }

Leider funktioniert dies nicht für Werte unter 1. Aber selbst dann können wir einige logarithmische Gesetze verwenden, um mit einem solchen Wert zu arbeiten.

\begin{aligned} \log_{10} (\frac{a}{b}) & = \log_{10} (a) - \log_{10} (b) \\ \log_{10} (\frac{1}{x}) & = \log_{10} (1) - \log_{10} (x) \\ = - \log_{10} (x) \end{aligned}

$\begin{align} \log_{10}\left(\frac{a}{b}\right) &= \log_{10}(a) - \log_{10}(b) \\ \log_{10}\left(\frac{1}{x}\right) &= \log_{10}(1) - \log_{10}(x) \\ &= -\log_{10}(x) \end{align}$

Deshalb:

\log_{10} (\frac{b}{a}) = - \log_{10} (\frac{a}{b})

$\log_{10}\left(\frac{b}{a}\right) = -\log_{10}\left(\frac{a}{b}\right)$

Wenn wir alles zusammenfügen, erhalten wir eine robustere floorLog10 () -Methode:

// file: ratio.js -- inside the class declaration

  invert() {
    return simplify(this.denominator, this.numerator);
  }

  floorLog10() {
    if (this.equals(simplify(BigInt(0), BigInt(1)))) {
      return new Ratio(BigInt(-1), BigInt(0));
    }
    return this.numerator >= this.denominator
      ? simplify((this.numerator / this.denominator).toString().length - 1, 1)
      : simplify(BigInt(-1), BigInt(1)).subtract(this.invert().floorLog10());
  }

Nochmal. Warum leiden?

Im Moment verfügt die Bibliothek über alle notwendigen Funktionen für meine Anwendung, um mit Grafiken zu arbeiten. Aber es mag trotzdem interessant sein, warum all diese Schwierigkeiten? Es gibt bereits mehrere beliebige Präzisionsbibliotheken. Warum nicht einfach einen von ihnen benutzen und damit fertig sein?

Um ehrlich zu sein, würde ich in den meisten Fällen eine vorhandene Bibliothek verwenden. Besonders wenn ich es eilig habe. Es macht keinen Sinn, all dies zu tun, wenn jemand bereits überlegene Arbeit geleistet hat.

Das Schlüsselwort hier ist überlegen. Und hier kommen meine Motive ins Spiel, meine eigene Bibliothek schreiben zu wollen. Die oben beschriebene Methode floorLog10 () ist ein perfektes Beispiel. Es liefert die genaue Berechnung, die ich für das benötige, was ich tun möchte. Es macht es effizient, in ungefähr sechs Codezeilen.

Wenn ich die Bibliothek eines anderen benutzen würde, würde ich auf eines von zwei Dingen stoßen:

Die Entwickler haben weder log10 () noch andere logarithmische Methoden implementiert.

oder

Die Entwickler haben die log10 () -Methode (oder eine gleichwertige Methode) implementiert .

Im ersten Szenario müsste ich noch floorLog10 () schreiben. In der zweiten Situation würde ich wahrscheinlich ihre logarithmische Methode verwenden. Und mein Code wäre langsamer und komplexer als er sein sollte.

Durch das Schreiben meiner eigenen Bibliothek kann ich sie an meine Anwendung anpassen. Natürlich mögen andere Leute den Code nützlich finden, aber ich bin nicht für ihre Bedürfnisse verantwortlich. Damit meine Anwendung keinen komplexen Code mit sich herumtragen muss, den sie niemals verwendet.

Außerdem habe ich viel gelernt, indem ich meine eigene Bibliothek erstellt habe. Ich verstehe jetzt die Einschränkungen von BigInt in der Praxis viel besser als zuvor. Ich weiß, dass ich die Leistung der n-ten Root-Methode optimieren kann. Ich kann es anpassen, je nachdem, wie viel Berechnung ich mache und wie viel Präzision ich brauche.

Manchmal lohnt es sich, eine eigene Allzweckbibliothek zu schreiben. Auch wenn Sie nicht vorhaben, den Code zu öffnen. Auch wenn es sonst niemand benutzt. Man kann viel lernen und es kann auch Freude bringen.

Wenn Sie mehr über Gleitkommaprobleme erfahren möchten , lesen Sie 0.30000000000000004.com . Wenn Sie die gesamte Bibliothek anzeigen und einige Berechnungen durchführen möchten, können Sie diese Sandbox mit dem Code überprüfen .

Andere Berufe und Kurse

Müde von albernen JS-Witzen? Schreiben Sie Ihre Bibliothek