6

An algorithm I'm using needs to squeeze as many levels of precision as possible from a float number in Javascript. I don't mind whether the precision comes from a number that is very large or with a lot of numbers after the decimal point, I just literally need as many numerals in it as possible.

(If you care why, it is for a drag n' drop ranking algorithm which has to deal with a lot of halvings before rebalancing itself. I do also know there are better string-based algorithms but the numerical approach suits my purposes)

The MDN Docs say that:

The JavaScript Number type is a double-precision 64-bit binary format IEEE 754 value, like double in Java or C#. This means it can represent fractional values, but there are some limits to what it can store. A Number only keeps about 17 decimal places of precision; arithmetic is subject to rounding.

How should I best use the "17 decimal places of precision"?

Does the 17 decimal places mean "17 numerals in total, inclusive of those before and after the decimal place"

e.g. (adding underscores to represent thousand-separators for readability)

# 17 numerals: safe
111_222_333_444_555_66

# 17 numerals + decimal point: safe
111_222_333_444_555_6.6
1.11_222_333_444_555_66

# 18 numerals: unsafe
111_222_333_444_555_666

# 18 numerals + decimal point: unsafe
1.11_222_333_444_555_666
111_222_333_444_555_66.6

I assume that the precision of the number determines the number of numerals that you can use and that the position of the decimal point in those numerals is effectively academic.

  • Am I thinking about the problem correctly?
  • Does the presence of the decimal point have any bearing on the calculation or is it simply a matter of the number of numerals present
  • Should I assume that 17 numerals is safe / 18 is unsafe?
  • Does this vary by browser (not just today but over say, a 10 year window, should one assume that browser precision may increase)?
phuclv
  • 37,963
  • 15
  • 156
  • 475
Peter Nixey
  • 16,187
  • 14
  • 79
  • 133
  • 4
    `Number.MAX_SAFE_INTEGER` and `Number.MIN_SAFE_INTEGER` tell you how large and small a number can be before it loses precision. If you need numbers larger than that, use [BigInt](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt) – evolutionxbox Sep 09 '21 at 10:50
  • @evolutionxbox that works on a per-browser basis but these numbers will be set and loaded on one browser and then used on another. I need the lowest common denominator. . So I need a universal standard that I can apply regardless of what the particular browser the user is running on will support. Also that only describes integers - it doesn't address the question of the decimal place. – Peter Nixey Sep 09 '21 at 11:58
  • What do you mean? Both are standards used by browsers. Here is the [Number compatibility](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number#browser_compatibility) and [BigInt compatibility](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt#browser_compatibility) – evolutionxbox Sep 09 '21 at 13:49
  • The question relates to the structure of the number WRT the decimal places. How the decimal point affects the precision and whether it makes a difference whether there are more numbers to the right or left of the decimal place or whether it's just about the absoute number of numerals. So `Number.MAX_SAFE_INTEGER` evaluates to 9007199254740991. But is 9007199254740990.1 safe or unsafe. It's less than 9007199254740991 but it carries more numerals. My second point is that what one browser may return from Number.MAX_SAFE_INTEGER and what another may return could be different. I need the LCD – Peter Nixey Sep 09 '21 at 15:57
  • To further clarify - the largest number is not the same as the greatest precision. The browers may accept `9007199254740991` and not `9007199254740992` but my question is whether it accepts `9.0071992547409912` which is a smaller number but greater precision - I would assume not but that's why I'm asking – Peter Nixey Sep 09 '21 at 15:59
  • `9007199254740990.1` is not safe – evolutionxbox Sep 09 '21 at 16:03
  • 1
    _"My second point is that what one browser may return from Number.MAX_SAFE_INTEGER and what another may return could be different"_ - no. This isn't true (well, I'm pretty confident about it anyway). All browsers which use JS use the same number format. --- Also see https://stackoverflow.com/questions/45929493/node-js-maximum-safe-floating-point-number – evolutionxbox Sep 09 '21 at 16:04

2 Answers2

5

Short answer: you can probably squeeze out 15 "safe" digits, and it doesn't matter where you place your decimal point.

It's anyone's guess how the JavaScript standard is going to evolve and use other number representations.

Notice how the MDN doc says "about 17 decimals"? Right, it's because sometimes you can represent that many digits, and sometimes less. It's because the floating point representation doesn't map 1-to-1 to our decimal system.

Even numbers with seemingly less information will give rounding errors.

For example 0.1 + 0.2 => 0.30000000000000004

console.log(0.1 + 0.2);

However, in this case we have a lot of margin in the precision, so you can just ask for the precision you want to get rid of the rounding error

console.log((0.1 + 0.2).toPrecision(1));

For a larger illustration of this, consider the following snippet:

for(let i=0;i<22;i++) { 
  console.log(Number.MAX_SAFE_INTEGER / (10 ** i)); 
}

You will see a lot of rounding errors on digit 16. However, there would be cases where even the 16th decimal shows a rounding error. If you look here

https://en.wikipedia.org/wiki/IEEE_754

it states that binary 64 has 15.95 decimal digits. That's why I'd guess that 15 digits is the max precision you will get out of this.

You'd have to do your operations, and before you save back the number to any representational form, you'd have to do .toPrecision(15).

Finally this has some good explanations. https://floating-point-gui.de/formats/fp/

BTW, I got curious by reading this question so I read up as I wrote this answer. There are many people with better knowledge of this than me.

Chris
  • 486
  • 2
  • 11
3

Does the presence of the decimal point have any bearing on the calculation or is it simply a matter of the number of numerals present

Kinda. To answer that, you'll need to look into how 64bit "double precision" floating point numbers are represented in memory. The "number of numerals" roughly translates into "length of the mantissa", which is indeed fixed and independent from the position of the point. However: it's binary digits and a binary point, not decimal digits and the decimal point. They do not correspond to each other directly. And then there's stuff like subnormal numbers.

Should I assume that 17 numerals is safe / 18 is unsafe?

No. In fact, only 15 decimal numerals would be "safe" if that's the representation you're starting with and want to exactly represent as a double.

Does this vary by browser (not just today but over say, a 10 year window, should one assume that browser precision may increase)?

No, it doesn't vary. The JavaScript number type will always be 64bit doubles.

Am I thinking about the problem correctly?

No.

You say you're considering this in the context of a drag'n'drop ranking algorithm, and you don't want do this string-based. However, thinking about decimal places in numbers is essentially thinking about string representation of numbers. Don't do that - either go all the way to strings, or treat numbers as binary.

Since you also mention "rebalancing", I assume you want to use numbers to encode the position of each item in a binary tree. That's a reasonable approach, but you really need to consider the binary representation of the number for that. And you really should use integers there, not floating-point numbers, as the logic would be much more complex otherwise. Start by deciding how many bits you want to use. There are some limitations for each, so choose wisely:

  • 31/32 bit are what JS bitwise operators for numbers work on. Supported by all browsers easily.
  • 53 bit are the range of integers you can exactly represent with floating-point numbers. Integer arithmetic will work as expected up to that size. Bitwise operations require extra code.
  • Fixed multiples of 8 (say, 64 bit) are what you can represent with typed arrays. Bitwise operations can be done part-wise, arithmetic operations require extra code. Or use a BigUint64Array that gives you 64 bits as a bigint to calculate with/operate on, but is not supported in old browsers.
  • Arbitrary precision can be achieved with bigint numbers, which support both bitwise and arithmetic operations, but again don't work in old browsers. Polyfills and bigint libraries are available though.
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Thanks for your answer @Bergi - I think I may have mid-described the exact use case though, it's best described here: https://softwareengineering.stackexchange.com/questions/195308/storing-a-re-orderable-list-in-a-database. BTW when you said number of numerals is best described as length of the mantissa I was a bit confused. Surely the storage limitations affect the cumulative number of numberals both before and after the decimal place. You couldn't have 100 numerals before and then 15 afterwards no? – Peter Nixey Sep 13 '21 at 08:35
  • 1
    @PeterNixey Yes, all [significant digits](https://en.wikipedia.org/wiki/Significant_figures) count, no matter whether before or after the decimal place. And yes, I saw the database topic you had linked in your question, and I keep my stance on it: whatever you do, using integral numbers will make it easier, do not use floating-point numbers for that. – Bergi Sep 13 '21 at 08:46
  • can you point to any page that would describe in more detail the approach taht you're suggesting - thank you – Peter Nixey Sep 14 '21 at 10:24
  • @PeterNixey Not really. While I had the same problem once and thought about this (something like a binary tree, storing position using the "prefix bits", and essentially inserting stuff by taking the middle between two items - `1011` goes between `101(0)` and `110(0)` - until running out of precision), in the end I went with a simple re-indexing of the few items. But it seemed like you had an idea already - can you describe it (with floating points)? Then I can suggest how to do it better with integers. – Bergi Sep 14 '21 at 11:38
  • I have gone ahead and implemented it using floats. For every item that needs to be inserted I find the middle point between the rank of the item above and below it. I then track the precision required to describe the difference in ranks - I.e. if A is 4.01 and B is 4.03 then the difference is 0.02 and precision of 0.02 is 2. When the precision exceeds 13 (lower than 15for safety) I then rebalance and assign each item an incrementing integer rank based on their position. It all seems to work well and requires rebalancing after about > 40 insertions into the same slot which feels ok – Peter Nixey Sep 14 '21 at 11:44
  • Yes, exactly. Now instead use integers, that should make finding the middle just as easy. And you don't need to care about *decimal* precision (tbh, you shouldn't have had when working with floats either), just notice that you ran out of precision if the "middle" is equal to one of the bounds. Until that point integers and floats work just the same in the algorithm (they just have a different distribution over their domain) and provide ~60 insertions. But the rebalancing will be much easier for integers due to their uniform distribution. – Bergi Sep 14 '21 at 11:52
  • I'm glad it seems sensible :) I don't understand though how you'd have done it with integers - maybe it's because i don't have a good feel for binary but other than choosing very large initial number distribution (1M, 2M, 3M etc), how would you find the middle of two integers while avoiding floats? – Peter Nixey Sep 14 '21 at 11:59
  • @PeterNixey You find the middle between two integers with `(a+b)/2` (or, considering unsigned overflow, `a+(b-a)/2`) :-) And yes, you'd start with the range 0…2^64-1, then place stuff in the middle of that. What values do you use with floats for the edges of your tree? – Bergi Sep 14 '21 at 12:17
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/237094/discussion-between-peter-nixey-and-bergi). – Peter Nixey Sep 14 '21 at 12:19