Why does Chrome produce 1099 digits after the period for (.1) .toString (3)?

Question

I have a feeling that this is just a harmless mistake, but I still want to understand what is happening.

I was playing with some code to render a Peano curve on a canvas that includes expressing logical coordinates in base 3 when I noticed that the function was returning absurdly long lines in Chrome. More carefully, it turns out that the expression

(.1).toString(3) 

evaluated in Chrome on

0, 01100021211101012101011202020110010112202201201001020212002021112020021121202000000222122210022012001201

as shown here: http://jsfiddle.net/zvp8osm8/

For what I can say, only the first 33 digits after the dot make sense in this case, the rest looks like random garbage without a recognizable pattern. Similar results with 1099 (!) Numbers after the point are created for different bases and exhibitors, as well as (10000000000.1).toString(3) or (.7).toString(7) . Other values, such as (.5).toString(3) , also cause long strings, but all values ​​make sense.

Other browsers, with the exception of Opera, only produce a reasonable number of digits in each case, which makes me think that the problem is in the Chrome Javascript engine.

I have two questions:

• Why does decimal representation in base 3 contain so many minor digits in Chrome?
• Where can random numbers be?

Answer 1

In the specific case that you are showing, it looks like the numbers are generated using the following naive algorithm, starting with x = .1 .

• Multiply x by 3.
• Extract the integer and fractional parts of the result.
• Print the integer part as a digit and replace x with the fractional part.
• Repeat steps 1 through 3 until they become boring (or until a specific preset is reached).

This will work fine mathematically, but in a floating-point world, this is certainly completely nonsense, since multiplying by 3 and then rounding to the nearest floating-point number potentially leads to a small error, and after 30 digits, or thus, the error completely fills the original numbers, and we just get the trash.

Presumably there is a way to process the numbers before the point for the case when the initial number is greater than 1.0 in absolute value, but without sample output, I'm not going to guess what kind of algorithm it is.

To justify the above, here is some code in Python whose output exactly matches the one asked in the question. Here modf is an operation that extracts the fractional and integral parts of floating Python.

 >>> from math import modf >>> x = 0.1 >>> digits = [] >>> for _ in xrange(1099): ... x, digit = modf(3.0 * x) ... digits.append(str(int(digit))) ... >>> print('0.' + ''.join(digits)) 

And the conclusion:

0, 01100021211101012101011202020110010112202201201001020212002021112020021121202000000222122210022012001201

This should answer one of your questions: namely, where the random numbers come from. I can't answer the question of why Chrome selects so many numbers.

Answer 2

First, the number .1 must be converted to a floating point, which is presented in binary format. In binary format .1 it is impossible to accurately represent, so where there will be some error in the lower digits. This is similar to trying to represent 1/7 in decimal: this is a repeating sequence .142857 142857 ... ; wherever you finish, you will lose accuracy.

When this is then converted to base 3, an error in these numbers leads to the randomness you see.

Answer 3

Starting with the ECMAScript 5.1 specification, namely 15.7.4.2 Number.prototype.toString([radix]) and 9.8.1 ToString Applies to the type of number :

The exact algorithm for converting a number to a string depends on the implementation, if the radius is not 10 (see 15.7.4.2), but it should be a generalization of the algorithm described in 9.8.1.
This means that every browser (and every other implementation) is free to choose whether they want to give standard accuracy (up to 21 digits) or more.