In this case, the criticism is absolutely undeserved. Let's figure out why.
JavaScript, like any other popular programming language , represents numbers using a single standard. To be precise, this is the IEEE 754 standard for numbers in 64-bit binary format. Let's try this same joke in other languages:
How about Ruby? In what language is 0.1 + 0.2 not equal to 0.3?
$ irb
irb(main):001:0> 0.1 + 0.2 == 0.3
=> false
irb(main):002:0> 0.1 + 0.2
=> 0.30000000000000004
Ruby! What a stupid language.
Or Clojure? In what language is 0.1 + 0.2 not equal to 0.3?
$ clj Clojure 1.10.1 user=> (== (+ 0.1 0.2) 0.3) false user=> (+ 0.1 0.2) 0.30000000000000004
Clojure! What a stupid language.
Or how about mighty Haskell? In what language is 0.1 + 0.2 not equal to 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. What a stupid language ...
You get the idea. The problem here isn't JavaScript. This is a big problem with binary floating point numbers. But I don't want to go into the details of IEEE 754 for now. Because if we want arbitrary precise numbers, JavaScript makes them possible. Since October 2019, BigInt is officially part of the TC39 ECMAScript standard .
Why bother with this?
We lasted with IEEE 754 for ages. This doesn't seem to be a problem most of the time. True. This is almost always not a problem. But sometimes it's still a problem. And at times like these, it's good to have options.
For example, earlier this year I was working on a library of charts. I wanted to draw candlestick charts in SVG. And SVG has a neat feature called transform . You can apply it to a group of items and it will change the coordinate system for those items. So with a little care you can simplify the generation of the chart area. Instead of calculating the coordinates of the chart for each candlestick, you specify one transformation. And then you define each candle using the raw data values. Very neat. At least in theory.
But in property tests I was having problems. If the graph were small and the data values were large, I would get round-off errors. And this is often normal. But on the graph, some pixels must line up. Otherwise, the drawing looks wrong. So I started to learn BigInt. The result was a library that I named Ratio. And I'll show you how it is written.
Fraction class
The problem with floating point numbers is their binary representation. Computers perform all their calculations in binary form. And for integers this binary is fine. The problem comes when we want to represent decimal numbers. For example, in English speaking countries like Australia, we write decimals like this:
The part to the left of the dots (...) is the whole part, and to the right of the dot is the fractional part. But the problem is that some numbers have fractional parts that cannot be easily divided into two. So it's hard to represent them in binary. But the same problem arises at base 10. For example, the fraction 10/9. You can try writing something like this:
However, this is an approximation. To represent 10/9 accurately, units must be infinite. Therefore, we must use some other notation to represent repetitions. For example this:
This dot above a unit indicates that units are continuing. But most programming languages don't have this point.
Note that 10/9 has perfect accuracy. And all it takes to be accurate is two pieces of information. This is the numerator and denominator . With a single BigInt value, we can represent arbitrarily large integers. But if we create a pair of integers, we can represent arbitrarily large or small numbers.
In JavaScript, it might look like this:
// 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;
}
}
So we did the trickiest part. "Invented" a way to represent numbers with almost infinite precision. (We're still limited by the memory of our devices.) All that remains is to apply the math. So let's add functionality.
Equality
The first thing you want to do is compare the two fractions. What for? Because I like writing tests first . If I can compare two fractions for equality, then writing tests is much easier.
In a simple case, writing an equality method is pretty easy:
// 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
);
}
}
That's good. But it would be nice if our library could tell 1/2 is 2/4. To do this, you need to simplify the fraction. That is, before checking equality, we want to reduce the numerators and denominators of both fractions to as small numbers as possible. So how do we do this?
A naive approach is to run all numbers from 1 to min (n, d) (where nn and dd are the numerator and denominator, respectively). And this is what I tried at the beginning. The code looked something like this:
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);
}
And, as you'd expect, it's incredibly slow. My tests took forever. So we need a more efficient approach. Fortunately, a Greek mathematician found it a couple of millennia ago. The solution is to apply Euclid's algorithm. This is a way to find the greatest common divisor of two integers.
The recursive version of Euclid's algorithm is beautiful and elegant:
function gcd(a, b) {
return (b === 0) ? a : gcd(b, a % b);
}
Memoization is applicable, which makes the algorithm quite attractive. But alas, we don't have tail recursion in V8 or SpiderMonkey yet . (At least not at the time of this writing.) This means that if we run it with large enough integers, we get a stack overflow. Large integers are like a starting point.
So let's use the iterative version instead:
// file: ratio.js
function gcd(a, b) {
let t;
while (b !== 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
Not so elegant, but does the job. And with this code, we can write a function to simplify fractions. While we are doing this, we will make a small change so that the denominators are always positive (i.e., for negative numbers, only the numerator changes the sign).
// 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);
}
And now we can write our equality method:
// 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
);
}
Now you can compare two fractions for equality. It might not sound like a lot, but it does mean we can write unit tests and make sure our library works as expected.
Conversion to other types
I won't bore you by writing out all the unit tests in my library. But it would be nice to convert the fractions to other formats. For example, we might want to represent them as a string in debug messages. Or maybe we want to convert them to numbers. So let's override the .toString () and .toValue () methods for our class.
The .toString () method is the easiest, so let's start with that.
// file: ratio.js -- inside the class declaration
toString() {
return `${this.numerator}/${this.denominator}`;
}
Simple enough. But what about converting back to a number? One way to do this is to simply divide the numerator by the denominator:
// file: ratio.js -- inside the class declaration
toValue() {
return Number(this.numerator) / Number(this.denominator);
}
This often works. But we might want to tweak the code a bit. The whole point of our library is that we use large integers to get the precision we need. And sometimes these integers will be too large to be converted back to Number. But we want to get Number as close to the truth as possible, where possible. So we do some arithmetic while converting BigInt to 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)
);
}
By extracting the integer portion, we reduce the size of the BigInt values before converting them to Number. There are other ways to do this that have less range problems. They are generally harder and slower. If you are interested, I recommend that you look deeper into them. But in this article, a simple approach covers enough cases to be useful.
Multiplication and division
Let's do something with the numbers. How about multiplication and division? It's easy for fractions. Multiply the numerators by the numerators, and the denominators by the denominators.
// file: ratio.js -- inside the class declaration
times(x) {
return simplify(
x.numerator * this.numerator,
x.denominator * this.denominator
);
}
Division is similar to the code above. Flip the second fraction, then multiply.
// file: ratio.js -- inside the class declaration
divideBy(x) {
return simplify(
this.numerator * x.denominator,
this.denominator * x.numerator
);
}
Addition and subtraction
We now have multiplication and division. Logically, the next thing to write is addition and subtraction. It's a little more complicated than multiplication and division. But not too much.
To add two fractions, you first need to bring them to the same denominator, then add the numerators. In code, it might look something like this:
// file: ratio.js -- inside the class declaration
add(x) {
return simplify(
this.numerator * x.denominator + x.numerator * this.denominator,
this.denominator * x.denominator
);
}
Everything is multiplied by the denominators. And we use simplify () to keep the fraction as small as possible in terms of the numerator and denominator numbers.
Subtraction is similar to addition. We are manipulating the two fractions so that the same denominators line up as before. Then we do not add, but subtract.
// file: ratio.js -- inside the class declaration
subtract(x) {
return simplify(
this.numerator * x.denominator - x.numerator * this.denominator,
this.denominator * x.denominator
);
}
So, we have the basic operators. You can add, subtract, multiply, and divide. But we still need a few other methods. In particular, numbers have an important property: we can compare them with each other.
Comparisons
We have already discussed .equals (). But we need more than just equality. We would also like to be able to define the greater-less ratios. Therefore, we will create a .lte () method that will tell us whether one fraction is less than or equal to another fraction. As with .equals (), it is not obvious which of the two is smaller. To compare them, we need to convert both to the same denominator, then compare the numerators. With a little oversimplification, it might look like this:
// 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;
}
Once we get .lte () and .equals (), we can print out the rest of the comparisons. You can choose any comparison operator. But if we have equals () and>, <, ≥ or ≤, then we can infer the rest using boolean logic. In this case, we chose lte () because the FantasyLand standard uses it . Other operators might look like this:
// 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);
}
Rounding
Now we can compare fractions. And we can also multiply and divide, add and subtract. But if we're going to do more fun with our library, we need more tools. The JavaScript Math handy objects contain the .floor () and .ceil () methods.
Let's start with .floor (). Floor takes a value and rounds it down. With positive numbers, this means that we just keep the whole part and discard the rest. But for negative numbers we round up from zero, so negative numbers need to be given a little more 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);
}
You can now use the code above to calculate the rounded up values.
// 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);
}
We now have most of what is needed for many mathematical operations. And with .toValue (), we can easily convert calculations back to decimal numbers. But what if we want to convert a floating point number to a fraction?
Number to fraction
Converting numbers to fractions is more difficult than it might seem at first glance. And there are many different ways to do this transformation. My implementation is not the most accurate, but it's good enough. To make it work, we first convert the number to a string, which, as we know, will take the format of a sequence. To do this, JavaScript provides us with the .toExponential () method. The method returns a number in exponential notation. Here are some examples to help you understand the idea:
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'
The code works by representing a number as a normalized decimal value and a multiplier. The normalized decimal bit is called the mantissa, and the factor is called the exponent. Here "normalized" means that the absolute value of the mantissa is always less than 10. And the exponent is always now 10. We indicate the start of the factor with the letter 'e' (short for 'exponent').
The advantage of this notation is that it is consistent. There is always exactly one digit to the left of the decimal point. And .toExponential () allows us to specify how many significant digits we want. Then comes the 'e' and the exponent is always an integer. Since the value is sequential, we can use a cheeky regex to parse it.
The process goes something like this. As mentioned, .toExponential () takes a parameter to specify the number of significant digits. We need as many numbers as possible. So, we set the precision to 100 (this is what most JavaScript engines will allow). For this example, however, we will stick with a precision of 10. Now imagine we have the number 0.987654321e0. We want to move the decimal point 10 digits to the right. That would give us 9876543210. Then divide by 10 ^ 10 to get 9876543210/100000000. This, in turn, simplifies to 987654321/100000000.
But we must pay attention to this exhibitor. If we have a number like 0.987654321e9, then we will still shift the decimal point 10 digits to the right. But we divide by ten, to the power of 10-9 = 1.
To keep it that way, we have defined a couple of helper functions:
// 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("")}`);
}
With their help, we can piece together the entire fromNumber () function.
// 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));
}
Most of the basic functions are covered. We can go from numbers to fractions and back again. But for my particular application, I needed more. In particular, it was necessary to find exponentiation and logarithms.
Exponentiation
Exponentiation is when a number is multiplied many times by itself. For example, 2 ^ 3 = 2 × 2 × 2 = 8. For simple cases where the degree is an integer, there is a built-in BigInt: ** operator. So if we raise a fraction to the power, that's a good option. This is how a fraction is raised to a power:
Therefore, the first chunk of our exponentiation method might look something like this:
// file: ratio.js -- inside the class declaration
pow(exponent) {
if (exponent.denominator === BigInt(1)) {
return simplify(
this.numerator ** exponent.numerator,
this.denominator ** exponent.numerator
);
}
}
Works great. Well ... mostly good. Now things get more complicated. Outside the constraints of collateral and mathematics, we have to make some trade-offs. We may have to sacrifice accuracy to get a response within a reasonable time frame.
Exponentiation easily generates large numbers. And when the numbers get big, things slow down. While I was writing this article, I also wrote calculations that did not complete over a period of days. So you need to be careful. But that's okay. Everything comes for BigInt.
But there is another problem. What if the denominator of the degree is not one? For example, what if we wanted to calculate 8 ^ (2/3)?
Fortunately, we can split this problem into two smaller problems. We want to reduce one fraction to the power of another. For example, we can attribute x / y to a / b. The laws of exponentiation state that the following is equivalent:
We already know how to convert one BigInt to the power of another BigInt. But what about fractional degrees? Well, there is another equivalent:
That is, reducing xx to the power 1n1n is equivalent to finding the nth root of xx. This means that if we find a way to compute the nth root of BigInt, then we can compute any degree.
With a well-thought-out web search, finding an algorithm for estimating the nth root shouldn't take long. The most common method is Newton's method . It works from the evaluation, rr. Then a calculation is made to get the best estimate:
We keep repeating these calculations until we reach the desired accuracy. Unfortunately, there are some roots that cannot be represented as a finite fraction. In other words, we need infinitely long BigInt values to get perfect precision. In practice, this means that we must choose an arbitrary iteration constraint.
We will come back to this point. For now, let's figure out how to calculate a reasonably accurate nth root. Since the estimate rr will be a fraction, we can write it as:
And this allows us to rewrite the calculations like this:
Now everything is in terms of integer computation, suitable for use with BigInt. Feel free to insert abab into the equation for r′r ′ above and check my findings. In JavaScript, it looks like this:
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);
We simply repeat this calculation until we reach a suitable precision for our nth root estimate. The problem is that we need to come up with suitable values for our constants. That is, NUM_ITERATIONS and INITIAL_ESTIMATE.
Many algorithms start with INITIAL_ESTIMATE one. This is a smart choice. Often we don't have a good way to guess what the nth root might be. But let's write "snag". Let's assume (for now) that our numerator and denominator are in the range Number. We can then use Math.pow () to get the initial score. It might look like this:
// 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))
);
So we have a value for our initial assessment. What about NUM_ITERATION? Well, in practice, what I did was start with an assumption of 10. And then I did property tests. I kept increasing the number until the calculations were within a reasonable time frame. And the figure that finally worked ... 1. One iteration. This saddens me a little, but we are a little more accurate than with floating point calculations. In practice, you can increase this number if you are not calculating many fractional powers.
For simplicity, we will extract the calculation of the nth root into a separate function. Putting it all together, the code might look like this:
// 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);
}
Imperfect and slow. But the task has become largely doable. The question remains how to get the estimate if we have integers greater than Number.MAX_VALUE. However, I will leave this as an exercise for the reader; this article is already too long.
Logarithms
I must admit, the logarithms puzzled me for a few weeks. For my development, I need to calculate the base 10 logarithms. So I went looking for algorithms to calculate the logarithms. And there are many of them. But I couldn't find one that worked well enough to be included in the math library.
Why is it so hard? My goal was to compute logarithms for greater precision than floating point numbers. Otherwise, why all this? Floating-point logarithm function, Math.log10 (), fast and built-in. So, I looked at algorithms that provide ways to iteratively compute logarithms. And they work. But they are slow in getting higher than floating point precision. Not just a little slower. Much slower.
As we go through the iterations, the fraction we build becomes more accurate. But this accuracy comes at a price. The BigInt values in fractions are getting bigger and bigger. And as they get bigger, they start to take a long time to multiply. At some point I left the calculation for three days. But while the calculations were going on, I remembered something.
I remembered that I needed the log10 () method in order to be able to calculate nice scaled values for the graphs. And for these calculations, every time I called .log10 (), I immediately called .floor (). This means that I only need the integer part of the logarithm. Calculating the logarithm to 100 decimal places was just a waste of time and power.
Moreover, there is an easy way to calculate the whole part of the base 10 logarithm. All we need is to count the numbers. A naive attempt might look like this:
// file: ratio.js -- inside the class declaration
floorLog10() {
return simplify(BigInt((this.numerator / this.denominator).toString().length - 1), BigInt(1));
}
Unfortunately, this does not work for values less than 1. But even so, we can use some logarithmic laws to work with such a value.
Therefore:
Putting it all together, we get a more robust floorLog10 () method:
// 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());
}
Again. Why suffer?
At the moment, the library has all the necessary functions for my application to work with graphs. But it may still be interesting, why all this trouble? There are already several arbitrary precision libraries. Why not just use one of them and be done with it?
To be honest, I would use an existing library in most cases. Especially if I'm in a hurry. There is no point in doing all of this if someone has already done superior work.
The key word here is superior. And this is where my motives for wanting to write my own library come into play. The floorLog10 () method above is a perfect example. It provides the exact calculation that I need for what I want to do. It does it efficiently, in about six lines of code.
If I were to use someone else's library, I would run into one of two things:
- The developers did not implement log10 () or any other logarithmic methods.
or
- The developers have implemented the log10 () method (or equivalent).
In the first scenario, I would still have to write floorLog10 (). In the second situation, I would probably use their logarithmic method. And my code would be slower and more complex than it should be.
Writing my own library allows me to adapt it to my application. Of course other people might find the code useful, but I am not responsible for their needs. So that my application doesn't have to carry around complex code that it never uses.
Besides all this, I have learned a lot by creating my own library. I now understand BigInt's limitations much better in practice than I did before. I know I can tune the performance of the nth root method. I can tweak it depending on how much computation I'm doing and how much precision I need.
Sometimes it's worth writing your own general purpose library. Even if you don't plan to open the code. Even if no one else uses it. You can learn a lot and it can also bring joy.
If you would like to know more about floating point issues, refer to 0.30000000000000004.com . And if you want to see the whole library and do some calculations, you can check out this sandbox with the code .
Other professions and courses