Dans ce cas, la critique est absolument imméritée. Voyons pourquoi.
JavaScript, comme tout autre langage de programmation populaire , représente des nombres qui utilisent un seul standard. Pour être précis, il s'agit de la norme IEEE 754 pour les nombres au format binaire 64 bits. Essayons cette même blague dans d'autres langues: qu'en est-
il de Ruby? Dans quelle langue 0,1 + 0,2 n'est-il pas égal à 0,3?
$ irb
irb(main):001:0> 0.1 + 0.2 == 0.3
=> false
irb(main):002:0> 0.1 + 0.2
=> 0.30000000000000004
Rubis! Quelle langue stupide.
Ou Clojure? Dans quelle langue 0,1 + 0,2 n'est-il pas égal à 0,3?
$ clj Clojure 1.10.1 user=> (== (+ 0.1 0.2) 0.3) false user=> (+ 0.1 0.2) 0.30000000000000004
Clojure! Quelle langue stupide.
Ou que diriez-vous du puissant Haskell? Dans quelle langue 0,1 + 0,2 est-il différent de 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. Quelle langue stupide ...
Vous voyez l'idée. Le problème ici n'est pas JavaScript. C'est un gros problème avec les nombres binaires à virgule flottante. Mais je ne veux pas pour l'instant entrer dans les détails de l'IEEE 754. Parce que si nous voulons des nombres précis arbitraires, JavaScript les rend possibles. Depuis octobre 2019, BigInt fait officiellement partie du standard TC39 ECMAScript .
Pourquoi s'embêter avec ça?
Nous avons duré avec IEEE 754 pendant des siècles. Cela ne semble pas être un problème la plupart du temps. Vrai. Ce n'est presque toujours pas un problème. Mais parfois, c'est toujours un problème. Et dans des moments comme ceux-ci, il est bon d'avoir des options.
Par exemple, plus tôt cette année, je travaillais sur une bibliothèque de graphiques. Je voulais dessiner des graphiques en chandeliers en SVG. Et SVG a une fonctionnalité intéressante appelée transformation . Vous pouvez l'appliquer à un groupe d'éléments et cela modifiera le système de coordonnées de ces éléments. Ainsi, avec un peu de soin, vous pouvez simplifier la génération de la zone de graphique. Au lieu de calculer les coordonnées du graphique pour chaque chandelier, vous spécifiez une transformation. Et puis définissez chaque bougie en utilisant les valeurs de données brutes. Très propre. Au moins en théorie.
Mais dans les tests de propriété, j'avais des problèmes. Si le graphique était petit et que les valeurs des données étaient grandes, j'obtiendrais des erreurs d'arrondi. Et c'est souvent normal. Mais sur le graphique, certains pixels doivent s'aligner. Sinon, le dessin ne semble pas correct. J'ai donc commencé à apprendre BigInt. Le résultat a été une bibliothèque que j'ai nommée Ratio. Et je vais vous montrer comment c'est écrit.
Classe de fraction
Le problème avec les nombres à virgule flottante est leur représentation binaire. Les ordinateurs effectuent tous leurs calculs sous forme binaire. Et pour les entiers, ce binaire convient. Le problème survient lorsque nous voulons représenter des nombres décimaux. Par exemple, dans les pays anglophones comme l'Australie, nous écrivons des décimales comme ceci:
La partie à gauche des points (...) est la partie entière, et à droite du point est la partie fractionnaire. Mais le problème est que certains nombres ont des parties fractionnaires qui ne peuvent pas être facilement divisées en deux. Il est donc difficile de les représenter en binaire. Mais le même problème se pose en base 10. Par exemple, la fraction 10/9. Vous pouvez essayer d'écrire quelque chose comme ceci:
Cependant, ceci est une approximation. Pour représenter 10/9 avec précision, les unités doivent être infinies. Par conséquent, nous devons utiliser une autre notation pour représenter les répétitions. Par exemple ceci:
Ce point au-dessus d'une unité indique que les unités continuent. Mais la plupart des langages de programmation n'ont pas ce point.
Notez que 10/9 a une précision parfaite. Et tout ce qu'il faut pour être précis, ce sont deux informations. C'est le numérateur et le dénominateur . Avec une seule valeur BigInt, nous pouvons représenter des entiers arbitrairement grands. Mais si nous créons une paire d'entiers, nous pouvons représenter des nombres arbitrairement grands ou petits.
En JavaScript, cela pourrait ressembler à ceci:
// 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;
}
}
Nous avons donc fait la partie la plus délicate. "Inventé" une façon de représenter les nombres avec une précision presque infinie. (Nous sommes toujours limités par la mémoire de nos appareils.) Il ne reste plus qu'à appliquer les calculs. Alors ajoutons des fonctionnalités.
Égalité
La première chose à faire est de comparer les deux fractions. Pourquoi? Parce que j'aime d'abord écrire des tests . Si je peux comparer deux fractions pour l'égalité, alors écrire des tests est beaucoup plus facile.
Dans un cas simple, écrire une méthode d'égalité est assez simple:
// 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
);
}
}
C'est bon. Mais ce serait bien si notre bibliothèque pouvait dire que 1/2 est 2/4. Pour ce faire, vous devez simplifier la fraction. Autrement dit, avant de vérifier l'égalité, nous voulons réduire les numérateurs et les dénominateurs des deux fractions à des nombres aussi petits que possible. Alors, comment faisons-nous cela?
L'approche naïve consiste à exécuter tous les nombres de 1 à min (n, d) (où nn et dd sont respectivement le numérateur et le dénominateur). Et c'est ce que j'ai essayé au début. Le code ressemblait à ceci:
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);
}
Et, comme vous vous en doutez, c'est incroyablement lent. Mes tests ont pris une éternité. Nous avons donc besoin d'une approche plus efficace. Heureusement, un mathématicien grec l'a découvert il y a quelques millénaires. La solution est d'appliquer l'algorithme d'Euclid. C'est un moyen de trouver le plus grand diviseur commun de deux entiers.
La version récursive de l'algorithme d'Euclid est belle et élégante:
function gcd(a, b) {
return (b === 0) ? a : gcd(b, a % b);
}
La mémorisation est applicable, ce qui rend l'algorithme très attractif. Mais hélas, nous n'avons pas encore de récursivité de queue dans V8 ou SpiderMonkey . (Du moins pas au moment de la rédaction de cet article.) Cela signifie que si nous l'exécutons avec des entiers suffisamment grands, nous obtenons un débordement de pile. Les grands entiers sont comme un point de départ.
Alors utilisons plutôt la version itérative:
// file: ratio.js
function gcd(a, b) {
let t;
while (b !== 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
Pas aussi élégant, mais fait le travail. Et avec ce code, nous pouvons écrire une fonction pour simplifier les fractions. Pendant que nous faisons cela, nous allons faire un petit changement pour que les dénominateurs soient toujours positifs (c'est-à-dire que pour les nombres négatifs, seul le numérateur change le signe).
// 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);
}
Et maintenant, nous pouvons écrire notre méthode d'égalité:
// 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
);
}
Vous pouvez maintenant comparer deux fractions pour l'égalité. Cela peut ne pas sembler beaucoup, mais cela signifie que nous pouvons écrire des tests unitaires et nous assurer que notre bibliothèque fonctionne comme prévu.
Conversion vers d'autres types
Je ne vous ennuierai pas en écrivant tous les tests unitaires de ma bibliothèque. Mais ce serait bien de convertir les fractions dans d'autres formats. Par exemple, nous pourrions vouloir les représenter sous forme de chaîne dans les messages de débogage. Ou peut-être voulons-nous les convertir en nombres. Remplaçons donc les méthodes .toString () et .toValue () pour notre classe.
La méthode .toString () est la plus simple, commençons par là.
// file: ratio.js -- inside the class declaration
toString() {
return `${this.numerator}/${this.denominator}`;
}
Assez simple. Mais qu'en est-il de la reconversion en nombre? Une façon de faire est de simplement diviser le numérateur par le dénominateur:
// file: ratio.js -- inside the class declaration
toValue() {
return Number(this.numerator) / Number(this.denominator);
}
Cela fonctionne souvent. Mais nous pourrions vouloir modifier un peu le code. L'intérêt de notre bibliothèque est que nous utilisons de grands entiers pour obtenir la précision dont nous avons besoin. Et parfois, ces entiers seront trop grands pour être reconvertis en nombre. Mais nous voulons que Number soit aussi proche que possible de la vérité, dans la mesure du possible. Nous faisons donc de l'arithmétique lors de la conversion de BigInt en Number:
// 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)
);
}
En extrayant la partie entière, nous réduisons la taille des valeurs BigInt avant de les convertir en Number. Il existe d'autres moyens de le faire qui posent moins de problèmes de portée. Ils sont généralement plus durs et plus lents. Si vous êtes intéressé, je vous recommande de les approfondir. Mais dans cet article, une approche simple couvre suffisamment de cas pour être utile.
Multiplication et division
Faisons quelque chose avec les chiffres. Et la multiplication et la division? C'est facile pour les fractions. Multipliez les numérateurs par les numérateurs et les dénominateurs par les dénominateurs.
// file: ratio.js -- inside the class declaration
times(x) {
return simplify(
x.numerator * this.numerator,
x.denominator * this.denominator
);
}
La division est similaire au code ci-dessus. Retournez la deuxième fraction, puis multipliez.
// file: ratio.js -- inside the class declaration
divideBy(x) {
return simplify(
this.numerator * x.denominator,
this.denominator * x.numerator
);
}
Addition et soustraction
Nous avons maintenant la multiplication et la division. Logiquement, la prochaine chose à écrire est l'addition et la soustraction. C'est un peu plus compliqué que la multiplication et la division. Mais pas trop.
Pour ajouter deux fractions, vous devez d'abord les amener au même dénominateur, puis ajouter les numérateurs. Dans le code, cela pourrait ressembler à ceci:
// file: ratio.js -- inside the class declaration
add(x) {
return simplify(
this.numerator * x.denominator + x.numerator * this.denominator,
this.denominator * x.denominator
);
}
Tout est multiplié par les dénominateurs. Et nous utilisons simplify () pour garder la fraction aussi petite que possible en termes de numérateur et de dénominateur.
La soustraction est similaire à l'addition. Nous manipulons les deux fractions pour que les mêmes dénominateurs s'alignent comme auparavant. Ensuite, nous n'ajoutons pas, mais soustrayons.
// file: ratio.js -- inside the class declaration
subtract(x) {
return simplify(
this.numerator * x.denominator - x.numerator * this.denominator,
this.denominator * x.denominator
);
}
Donc, nous avons les opérateurs de base. Vous pouvez ajouter, soustraire, multiplier et diviser. Mais nous avons encore besoin de quelques autres méthodes. En particulier, les nombres ont une propriété importante: nous pouvons les comparer les uns aux autres.
Comparaisons
Nous avons déjà discuté de .equals (). Mais nous avons besoin de plus qu'une simple égalité. Nous aimerions également pouvoir définir les ratios plus grand-moins. Par conséquent, nous allons créer une méthode .lte () qui nous dira si une fraction est inférieure ou égale à une autre fraction. Comme avec .equals (), il n'est pas évident de savoir lequel des deux est le plus petit. Pour les comparer, nous devons convertir les deux dans le même dénominateur, puis comparer les numérateurs. Avec un peu de simplification excessive, cela pourrait ressembler à ceci:
// 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;
}
Une fois que nous avons .lte () et .equals (), nous pouvons afficher le reste des comparaisons. Vous pouvez choisir n'importe quel opérateur de comparaison. Mais si nous avons égal () et>, <, ≥ ou ≤, alors nous pouvons déduire le reste en utilisant la logique booléenne. Dans ce cas, nous avons choisi lte () car le standard FantasyLand l'utilise . D'autres opérateurs pourraient ressembler à ceci:
// 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);
}
Arrondi
Maintenant, nous pouvons comparer les fractions. Et nous pouvons aussi multiplier et diviser, additionner et soustraire. Mais si nous voulons nous amuser davantage avec notre bibliothèque, nous avons besoin de plus d'outils. Les objets pratiques JavaScript Math contiennent les méthodes .floor () et .ceil ().
Commençons par .floor (). Le plancher prend une valeur et l'arrondit. Avec des nombres positifs, cela signifie que nous gardons simplement la partie entière et rejetons le reste. Mais pour les nombres négatifs, nous arrondissons à partir de zéro, donc les nombres négatifs doivent recevoir un peu plus d'attention.
// 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);
}
Vous pouvez maintenant utiliser le code ci-dessus pour calculer les valeurs arrondies.
// 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);
}
Nous avons maintenant la plupart de ce qui est nécessaire pour de nombreuses opérations mathématiques. Et avec .toValue (), nous pouvons facilement reconvertir les calculs en nombres décimaux. Mais que faire si nous voulons convertir un nombre à virgule flottante en une fraction?
Nombre à fractionner
La conversion de nombres en fractions est plus difficile qu'il n'y paraît à première vue. Et il existe de nombreuses façons différentes de réaliser cette transformation. Ma mise en œuvre n'est pas la plus précise, mais elle est assez bonne. Pour que cela fonctionne, nous convertissons d'abord le nombre en une chaîne qui, comme nous le savons, prendra un format de séquence. Pour ce faire, JavaScript nous fournit la méthode .toExponential (). La méthode renvoie un nombre en notation exponentielle. Voici quelques exemples pour vous aider à comprendre l'idée:
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'
Le code fonctionne en représentant un nombre sous la forme d'une valeur décimale normalisée et d'un multiplicateur. Le bit décimal normalisé est appelé la mantisse et le facteur est appelé l'exposant. Ici, "normalisé" signifie que la valeur absolue de la mantisse est toujours inférieure à 10. Et l'exposant est toujours maintenant 10. Nous indiquons le début du facteur par la lettre 'e' (abréviation de 'exposant').
L'avantage de cette notation est qu'elle est cohérente. Il y a toujours exactement un chiffre à gauche du point décimal. Et .toExponential () nous permet de spécifier combien de chiffres significatifs nous voulons. Puis vient le «e» et l'exposant est toujours un entier. Puisque la valeur est séquentielle, nous pouvons utiliser une expression régulière effrontée pour l'analyser.
Le processus va quelque chose comme ça. Comme mentionné, .toExponential () prend un paramètre pour spécifier le nombre de chiffres significatifs. Nous avons besoin d'autant de chiffres que possible. Nous définissons donc la précision sur 100 (ce que la plupart des moteurs JavaScript autorisent). Pour cet exemple, cependant, nous allons nous en tenir à une précision de 10. Imaginons maintenant que nous ayons le nombre 0,987654321e0. Nous voulons déplacer la virgule décimale de 10 chiffres vers la droite. Cela nous donnerait 9876543210. Ensuite, divisez par 10 ^ 10 pour obtenir 9876543210/100000000. Ceci, à son tour, simplifie à 987654321/100000000.
Mais il faut faire attention à cet exposant. Si nous avons un nombre tel que 0.987654321e9, nous déplacerons toujours la virgule décimale de 10 chiffres vers la droite. Mais nous divisons par dix, à la puissance 10-9 = 1.
Pour faire de cette façon, nous avons défini quelques fonctions d'assistance:
// 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("")}`);
}
Avec leur aide, nous pouvons reconstituer l'ensemble de la fonction fromNumber ().
// 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));
}
La plupart des fonctions de base sont couvertes. Nous pouvons passer des nombres aux fractions et inversement. Mais pour mon application particulière, j'avais besoin de plus. En particulier, il était nécessaire de trouver l'exponentiation et les logarithmes.
Exponentiation
L'exponentiation est lorsqu'un nombre est multiplié plusieurs fois par lui-même. Par exemple, 2 ^ 3 = 2 × 2 × 2 = 8. Pour les cas simples où le degré est un entier, il existe un opérateur BigInt: ** intégré. Donc, si nous élevons une fraction à la puissance, c'est une bonne option. Voici comment une fraction est élevée à une puissance:
Par conséquent, le premier morceau de notre méthode d'exponentiation pourrait ressembler à ceci:
// file: ratio.js -- inside the class declaration
pow(exponent) {
if (exponent.denominator === BigInt(1)) {
return simplify(
this.numerator ** exponent.numerator,
this.denominator ** exponent.numerator
);
}
}
Fonctionne très bien. Eh bien ... surtout bien. Maintenant, les choses se compliquent. En dehors des contraintes du collatéral et des mathématiques, nous devons faire des compromis. Il se peut que nous devions sacrifier la précision pour obtenir une réponse dans un délai raisonnable.
L'exponentiation génère facilement de grands nombres. Et lorsque les chiffres deviennent importants, les choses ralentissent. Pendant que j'écrivais cet article, j'ai également écrit des calculs qui ne se sont pas terminés sur une période de plusieurs jours. Vous devez donc être prudent. Mais ça va. Tout vient pour BigInt.
Mais il y a un autre problème. Et si le dénominateur du diplôme n'est pas un? Par exemple, que se passerait-il si nous voulions calculer 8 ^ (2/3)?
Heureusement, nous pouvons diviser ce problème en deux problèmes plus petits. Nous voulons réduire une fraction à la puissance d'une autre. Par exemple, nous pouvons attribuer x / y à a / b. Les lois de l'exponentiation indiquent que ce qui suit est équivalent:
Nous savons déjà comment convertir un BigInt en puissance d'un autre BigInt. Mais qu'en est-il des degrés fractionnaires? Eh bien, il existe un autre équivalent:
Autrement dit, réduire xx à la puissance 1n1n équivaut à trouver la nième racine de xx. Cela signifie que si nous trouvons un moyen de calculer la nième racine de BigInt, nous pouvons calculer n'importe quel degré.
Avec une recherche Web bien pensée, trouver un algorithme pour estimer la nième racine ne devrait pas prendre longtemps. La méthode la plus courante est la méthode de Newton . Cela fonctionne à partir de l'évaluation, rr. Ensuite, un calcul est effectué pour obtenir la meilleure estimation:
Nous répétons ces calculs jusqu'à ce que nous atteignions la précision souhaitée. Malheureusement, certaines racines ne peuvent pas être représentées comme une fraction finie. En d'autres termes, nous avons besoin de valeurs BigInt infiniment longues pour obtenir une précision parfaite. En pratique, cela signifie que nous devons choisir une contrainte d'itération arbitraire.
Nous reviendrons sur ce point. Pour l'instant, voyons comment calculer une nième racine raisonnablement précise. Puisque l'estimation rr sera une fraction, nous pouvons l'écrire comme:
Et cela nous permet de réécrire les calculs comme ceci:
Maintenant, tout est en termes de calcul d'entiers, adapté à une utilisation avec BigInt. N'hésitez pas à insérer abab dans l'équation pour r′r ′ ci-dessus et à vérifier mes résultats. En JavaScript, cela ressemble à ceci:
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);
Nous répétons simplement ce calcul jusqu'à ce que nous atteignions une précision appropriée pour notre estimation de la nième racine. Le problème est que nous devons trouver des valeurs adaptées à nos constantes. Autrement dit, NUM_ITERATIONS et INITIAL_ESTIMATE.
De nombreux algorithmes commencent par INITIAL_ESTIMATE. C'est un choix judicieux. Souvent, nous n'avons pas un bon moyen de deviner ce que pourrait être la nième racine. Mais écrivons "accroc". Supposons (pour l'instant) que notre numérateur et notre dénominateur sont dans la plage Number. Nous pouvons ensuite utiliser Math.pow () pour obtenir le score initial. Cela pourrait ressembler à ceci:
// 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))
);
Nous avons donc une valeur pour notre évaluation initiale. Et NUM_ITERATION? Eh bien, en pratique, j'ai commencé par une hypothèse de 10. Et puis j'ai fait des tests de propriété. J'ai continué à augmenter le nombre jusqu'à ce que les calculs soient effectués dans un délai raisonnable. Et le chiffre qui a finalement fonctionné ... 1. Une itération. Cela m'attriste un peu, mais nous sommes un peu plus précis qu'avec les calculs en virgule flottante. En pratique, vous pouvez augmenter ce nombre si vous ne calculez pas de nombreuses puissances fractionnaires.
Pour simplifier, nous allons extraire le calcul de la nième racine dans une fonction distincte. En mettant tout cela ensemble, le code pourrait ressembler à ceci:
// 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);
}
Imparfait et lent. Mais la tâche est devenue largement réalisable. La question reste de savoir comment obtenir l'estimation si nous avons des entiers supérieurs à Number.MAX_VALUE. Cependant, je laisserai cela comme un exercice pour le lecteur; cet article est déjà trop long.
Logarithmes
Je dois admettre que les logarithmes m'ont laissé perplexe pendant quelques semaines. Pour mon développement, j'ai besoin de calculer les logarithmes de base 10. J'ai donc cherché des algorithmes pour calculer les logarithmes. Et il y en a beaucoup. Mais je n'ai pas pu en trouver un qui fonctionnait assez bien pour être inclus dans la bibliothèque de mathématiques.
Pourquoi est-ce si difficile? Mon objectif était de calculer des logarithmes pour une plus grande précision que les nombres à virgule flottante. Sinon, pourquoi tout cela? Fonction logarithme à virgule flottante, Math.log10 (), rapide et intégrée. J'ai donc examiné les algorithmes qui fournissent des moyens de calculer itérativement les logarithmes. Et ils fonctionnent. Mais ils tardent à dépasser la précision en virgule flottante. Pas juste un peu plus lent. Beaucoup plus lent.
Au fur et à mesure que nous parcourons les itérations, la fraction que nous construisons devient plus précise. Mais cette précision a un prix. Les valeurs BigInt en fractions deviennent de plus en plus grandes. Et à mesure qu'ils grossissent, ils mettent beaucoup de temps à se multiplier. À un moment donné, j'ai laissé le calcul pendant trois jours. Mais pendant que les calculs étaient en cours, je me suis souvenu de quelque chose.
Je me suis souvenu que j'avais besoin d'une méthode log10 () pour pouvoir calculer de jolies valeurs mises à l'échelle pour les graphiques. Et pour ces calculs, chaque fois que j'ai appelé .log10 (), j'ai immédiatement appelé .floor (). Cela signifie que je ne veux que la partie entière du logarithme. Calculer le logarithme à 100 décimales n'était qu'une perte de temps et d'énergie.
De plus, il existe un moyen simple de calculer la partie entière du logarithme en base 10. Il suffit de compter les nombres. Une tentative naïve pourrait ressembler à ceci:
// file: ratio.js -- inside the class declaration
floorLog10() {
return simplify(BigInt((this.numerator / this.denominator).toString().length - 1), BigInt(1));
}
Malheureusement, cela ne fonctionne pas pour les valeurs inférieures à 1. Mais même ainsi, nous pouvons utiliser certaines lois logarithmiques pour travailler avec une telle valeur.
Par conséquent:
En mettant tout cela ensemble, nous obtenons une méthode floorLog10 () plus robuste:
// 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());
}
Encore. Pourquoi souffrir?
Pour le moment, la bibliothèque dispose de toutes les fonctions nécessaires pour que mon application fonctionne avec des graphiques. Mais ça peut quand même être intéressant, pourquoi tout ce problème? Il existe déjà plusieurs bibliothèques de précision arbitraire. Pourquoi ne pas en utiliser un et en finir avec lui?
Pour être honnête, j'utiliserais une bibliothèque existante dans la plupart des cas. Surtout si je suis pressé. Il ne sert à rien de faire tout cela si quelqu'un a déjà fait un travail supérieur.
Le mot clé ici est supérieur. Et c'est là que mes motivations pour vouloir écrire ma propre bibliothèque entrent en jeu. La méthode floorLog10 () ci-dessus en est un parfait exemple. Il fournit le calcul exact dont j'ai besoin pour ce que je veux faire. Il le fait efficacement, en environ six lignes de code.
Si je devais utiliser la bibliothèque de quelqu'un d'autre, je rencontrerais l'une des deux choses suivantes:
- Les développeurs n'ont pas implémenté log10 () ni aucune autre méthode logarithmique.
ou
- Les développeurs ont implémenté la méthode log10 () (ou équivalent).
Dans le premier scénario, je devrais encore écrire floorLog10 (). Dans la seconde situation, j'utiliserais probablement leur méthode logarithmique. Et mon code serait plus lent et plus complexe qu'il ne devrait l'être.
Ecrire ma propre bibliothèque me permet de l'adapter à mon application. Bien sûr, d'autres personnes pourraient trouver le code utile, mais je ne suis pas responsable de leurs besoins. Pour que mon application n'ait pas à transporter de code complexe qu'elle n'utilise jamais.
En plus de tout cela, j'ai beaucoup appris en créant ma propre bibliothèque. Je comprends maintenant bien mieux les limites de BigInt dans la pratique qu'auparavant. Je sais que je peux régler les performances de la méthode nième racine. Je peux le modifier en fonction de la quantité de calcul que je fais et de la précision dont j'ai besoin.
Parfois, cela vaut la peine d'écrire votre propre bibliothèque à usage général. Même si vous ne prévoyez pas d'ouvrir le code. Même si personne d'autre ne l'utilise. Vous pouvez apprendre beaucoup et cela peut aussi apporter de la joie.
Si vous souhaitez en savoir plus sur les problèmes de virgule flottante, consultez le site 0.30000000000000004.com . Et si vous voulez voir toute la bibliothèque et faire quelques calculs, vous pouvez consulter ce bac à sable avec le code .
Autres professions et cours