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

Question

I have a feeling that this is a just a harmless bug but I'd still like to understand what's going on.

I was playing with some code to render a Peano curve on a canvas that involves expressing logical coordinates in base 3 when I noticed that a function was returning absurdly long strings in Chrome. Looking more closely, it turns out that the expression

(.1).toString(3)

evaluates in Chrome to

0.0022002200220022002200220022002201000021002100001101010002022011202012121102122020112120001020210222101201120010221010101202020200221020101002002101100100002022210010220022021021221021100020120102202020200110002220220012001021022020001120220101001022112120121220210122121200121200122212100110210102202000012021211200222221101111211122012121111202211210010022212100002210220210122200201120220011210120110011120000011011001010110022012102001102020210211202111001002101200102022221112212012011000022110022020001100112212102102100111000222211012211220200112120002100121210000222002201120220111022021120022101112201220001101012112201211010010110122011201120022210102021100002000121020120001112122222220201200220012211122001022022001222011221100212001100010200001211022021120210222110022221202002120011210220012001022112012202110101212100011220000220200122222102201100202101012110201221202211220201111021112112201120101121122212112220211110002020120201022022121210120002202021212000101222221101122201001100021211101012101011202020110010112202201201001020212002021112020021121202000000222122210022012001201

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

For what I can tell, 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 (!) digits after the dot are produced for different bases and exponents too like (10000000000.1).toString(3) or (.7).toString(7). Other values like (.5).toString(3) also produce strings that long, but the digits all make sense.

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

I have two questions now:

• Why does the representation of decimal numbers in base 3 contain so many insignificant digits in Chrome?
• Where could the random digits possibly come from?

Answer 1

For the particular case you show, it looks as though digits are being generated using the following naive algorithm, starting with x = .1.

1. Multiply x by 3.
2. Extract the integer and fractional parts of the result.
3. Output the integer part as a digit, and replace x with the fractional part.
4. Repeat steps 1 to 3 until bored (or until some preset limit is achieved).

This would work just fine mathematically, but in the world of floating-point this is utter nonsense, of course, since the multiplication by 3 and subsequent round to the nearest floating-point number potentially introduces a small error, and after 30 digits or so the error has completely swamped the original digits, and we're just getting garbage.

Presumably there's also some way of handling the digits before the point for the case where the initial number is larger than 1.0 in absolute value, but without sample output, I'm not going to guess what that algorithm is.

To justify the above, here's some code in Python whose output exactly matches that given in the question. Here, modf is the operation that extracts the fractional and integral parts of a Python float.

>>> 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 output:

0.0022002200220022002200220022002201000021002100001101010002022011202012121102122020112120001020210222101201120010221010101202020200221020101002002101100100002022210010220022021021221021100020120102202020200110002220220012001021022020001120220101001022112120121220210122121200121200122212100110210102202000012021211200222221101111211122012121111202211210010022212100002210220210122200201120220011210120110011120000011011001010110022012102001102020210211202111001002101200102022221112212012011000022110022020001100112212102102100111000222211012211220200112120002100121210000222002201120220111022021120022101112201220001101012112201211010010110122011201120022210102021100002000121020120001112122222220201200220012211122001022022001222011221100212001100010200001211022021120210222110022221202002120011210220012001022112012202110101212100011220000220200122222102201100202101012110201221202211220201111021112112201120101121122212112220211110002020120201022022121210120002202021212000101222221101122201001100021211101012101011202020110010112202201201001020212002021112020021121202000000222122210022012001201

This should answer one of your questions: namely where the random digits come from. I can't answer the question of why Chrome chooses to output so many digits.

Answer 2

First the number .1 has to be converted into floating point, which is represented in binary. In binary, .1 cannot be represented precisely, so where will be some error in the low-order digits. This is analogous to trying to represent 1/7 in decimal: it's the repeating sequence .142857 142857 ...; wherever you end it, you'll have a loss of precision.

When this is then converted into base 3, the error in those digits results in the randomness you're seeing.

Answer 3

Starting off with the ECMAScript 5.1 spec, namely 15.7.4.2 Number.prototype.toString([radix]) and 9.8.1 ToString Applied to the Number Type:

The precise algorithm for converting a number to a string is implementation-dependent if the radix is not 10 (see 15.7.4.2), however, it's expected to be a generalization of the algorithm outlined in 9.8.1.
This means each browser (and every other implementation) is free to choose whether they want to give the standard precision (up to 21 digits) or more.